Coding Project

Author: Matt Kenney

To find the longest path in a directed, cyclic graph, $G = (V, E)$ (as asked in Coding Assignment 4 part e), I implemented an algorithm which generates a number of permutations of DAG reductions, $G{\pi}$, of the graph $G$, and finds the longest path in each of these DAGs. As described in these MIT lecture notes on using Random DAGs to compute the NP-hard longest path problem we've been assigned, there is a $\frac{1}{k!}$ chance that a path of length $k$ in $G$ is also present in a given random topological reduction of $G$, $G{\pi}$. If we convert $G$ to a DAG using $k!$ different permutations of the topological ordering $\pi$, then we have a strong chance that we will identify whether or not a k-length path exists in $G$. Therefore, below, we attempt up to $n!$ ($n = |V|$) DAG reductions of G and find the longest path in each of these reductions, $G{\pi}$. We stop when we reach the time limit (10 mins), since, in reality, computing the longest path in $n!$ DAG reductions of $G$ is not feasible in the case of the FaceBook graph, which has $n > 4000$. To compute random DAG reductions, we simply call $\textbf{DFS}$ with different random orderings, $\sigma$, of the vertices $v \in V$, to obtain different topological orderings, $\pi$, in this way. To obtain topological reductions, as described in the lecture notes linked above, we convert $G$ into a DAG, $G{\pi}$, by running $\textbf{DFS}(G, \sigma)$, where $\sigma$ is a random ordering of the vertices in $G$. to optain a topological ordering, $\pi$. We then remove all edges from $G$ which do not satisfy the topological order. Lets denote the index of vertex $i$ in the ordering of $\pi$ as $\pi(i)$ (so if $\sigma = a, b, c$, then $\pi(a) = 1$, $\pi(b) = 2$, and $\pi(c) = 3$). Specically, then, to create the random DAG reduction $G_{\pi}$, we retain only the edges $(i, j) \in G$ such that $\pi(i) < \pi(j)$.

To compute the longest path in each our our random DAG permutations, I used the lowest cost path in a DAG algorithm, but interpreted edge weights as $c(e) = -1 ~~ \forall e \in E$ so that in fact the longest path in the DAG is returned. Since we have obtained the topological ordering $\pi$ already for each of these DAGs, we simply search for the longest path starting at $\pi0$, or the first known source of the DAG. In order to implement this algorithm, I used a GPU accelerated approach using the cuGraph library, which implements the longest path in a DAG problem in a time complexity that is a function of $\log n$ by leveraging parallelism. This is in contrast to the $O(|V| + |E|)$ time complexity of the standard serial algorithm. See more information on the time complexity of Parallel Single-Source Shortest Path here. This parallelism adaptation makes finding the longest path in the Facebook graph much more feasible. See the implementation below.

Despite the speedup obtained in the parallel shortest path algorithm, I do recognize that this algorithm remains bounded by DFS speed. If I get the time, I'd like to either 1) Implement the algorithm for Monte-Carlo type randomized graph "coloring", as described Here, which runs in around $4^n$ time, or 2) work on implementing a parallel approach to finding a topological ordering, so that I can remove the bottleneck posed by that step. In any case, though, getting to use GPU libraries (and install them, which is much trickier than expected) and working to implement this algorithm were both valuable learning experiences.

from graph_class import graph from collections import deque, Counter, defaultdict import matplotlib.pyplot as plt import networkx as nx import pandas as pd import random import math import time import cugraph

DFS

Below is the DFS iterative implementation I wrote for my coding group. It is just a 'helper' function in this larger project

class DFS_Vars: """ A class to keep track of variables we use during DFS. Depending on the application of DFS, not all vars are neccessarily use """ def __init__(self, sigma): self.first = defaultdict(int) self.last = defaultdict(int) self.visited = set() self.exploring = set() self.root = {} self.Fcomp = {} self.parent = {} self.fcomp = 0 self.time = 0 self.traversal_order = [] self.cycles = [] self.cyclic = False self.F = graph()

def DFS_iter(G, sigma): # sigma is an ordering of the vertices ''' Iterative DFS on entire graph ''' dfs_vars = DFS_Vars(sigma) for v in sigma: if v not in dfs_vars.visited: # print("Running DFS on", v) dfs_vars.fcomp += 1 dfs_vars.root[dfs_vars.fcomp] = v dfs_iter(G, v, dfs_vars) return dfs_vars def dfs_iter(G, v, dfs_vars): ''' Iterative DFS from a vertex. - Note that time here isn't calculated exactly as we did in class, but the order of last[v] is still preserved - Note that this method only returns the pieces neccessary for the SCC algorithm ''' node_stack = deque([v]) # start with the passed vertex v while node_stack: v = node_stack.pop() # The trick to keeping track of time during iterative DFS is that, the first time we pop v off the stack # We push it back onto the stack and we know that we've finished exploring once we reach # v a second time. Credit: https://stackoverflow.com/questions/24051386/kosaraju-finding-finishing-time-using-iterative-dfs if v not in dfs_vars.visited: # Add v to the stack a second time node_stack.append(v) # Mark v visited dfs_vars.visited.add(v) dfs_vars.Fcomp[v] = dfs_vars.fcomp # Set v's tree in the forest for u in G.adj_list[v]: # sorted by reverse alphabetical order # If not visited if u not in dfs_vars.visited: dfs_vars.F.Add_Edge(v,u) node_stack.append(u) else: # If we have yet to set the finish time for v if dfs_vars.last[v] == 0: dfs_vars.last[v] = dfs_vars.time dfs_vars.time += 1

Get Random DAG algorithm

As described in the introduction, this algorithm computes random DAG reductions of the passed graph, G

def get_random_dag(G): # Convert G into a DAG, Gπ, by removing all nodes that do not satisfy the topological order # That is, all edges (j, i) such that π(i) < π(j), will be removed. verts = list(G.vertices) random.shuffle(verts) dfs_results = DFS_iter(G, verts) pi = sorted(dfs_results.last.keys(), key=lambda v: dfs_results.last[v], reverse=True) # topological ordering pi_order = {k: v for v, k in enumerate(pi)} # Remove bad edges to form the DAG reduction: G_pi = graph() for i, neighbors in G.adj_list.items(): for j in neighbors: if pi_order[i] < pi_order[j]: G_pi.Add_Edge(i, j) return G_pi, pi

def get_networkx(G, edge_weight=1): ''' cuGraph takes networkx graphs as output, so this function converts our in-class graph class to a networkx graph. ''' networkx_graph = nx.DiGraph() for v in G.vertices: for u in G.adj_list[v]: networkx_graph.add_edge(v, u, weight=edge_weight) return networkx_graph

# Read in Graph fb_graph = graph() fb_graph.Read_Edges(fname='facebooksample.txt', sep=' ', flag='d')

## Show that shortest path fails when we attempt to operate on a non-DAG fb_graph_nx = get_networkx(fb_graph, edge_weight=-1) source = list(fb_graph.vertices)[0] # cugraph.shortest_path_length(fb_graph_nx, source=source) # Running this cell throws Error

Longest Path algorithm from `cuGraph`

Here, we use the algorithm implemented in cuGraph to find the shortest path in a DAG. More precisely, though, this algorithm finds the lowest cost path in a DAG, where the cost of a path is the sum of the cost of the edges in the path i.e. $c(p) = \sum{e \in p} c(e)$. If we set all edges in some DAG, $G{\pi}=(V, E)$, such that $c(e) = -1 ~~ \forall e \in E $, then the lowest cost path becomes the longest path, and the cost of this path is exactly the length of the longest path in $G_{\pi}$.

random_fb_dag, pi = get_random_dag(fb_graph) # pi is the randomly discovered topological ordering used to make the DAG random_fb_dag = get_networkx(random_fb_dag, edge_weight=-1) # set all edge weights to -1 print('Source Vertex is', pi[0])

# Show the algorithm in action source = pi[0] sssp_result = cugraph.sssp(random_fb_dag, source=source) # GPU implementation of Single Source Shortest Path (SSSP) sssp_result # note that e+38 distances indicate positive infinity

# This is the longest path in the random DAG we have created -sssp_result['distance'].min()

# Get the vertex v which has the longest path in the DAG from source -> v sssp_result[sssp_result['distance'] == sssp_result['distance'].min()]

# Show the distance to the source, and show that source has no parent sssp_result[sssp_result['vertex'] == source]

target_vertex = sssp_result[sssp_result['distance'] == sssp_result['distance'].min()] target_vertex

sssp_result[sssp_result['vertex'] == target_vertex['predecessor'].iloc[0]]

# Recover the longest path in the DAG curr_vertex = target_vertex longest_path = deque([]) while int(curr_vertex['predecessor'].iloc[0]) >= 0: longest_path.appendleft(curr_vertex['vertex'].iloc[0]) curr_vertex = sssp_result[sssp_result['vertex'] == curr_vertex['predecessor'].iloc[0]] print(longest_path)

# Demonstrate how different random DAGs produce different longest path results # Note that shortest_path_length is an analagous parallel shorest path algorithm, which returns less data for _ in range(5): random_fb_dag, pi = get_random_dag(fb_graph) # pi is the randomly discovered topological ordering used to make the DAG random_fb_dag = get_networkx(random_fb_dag, edge_weight=-1) print('Source Vertex is', pi[0]) result = cugraph.shortest_path_length(random_fb_dag, source=pi[0]) # GPU implementation of shortest path print('Longest path found in this DAG is:', -result['distance'].min() )

Run the Longest Path NP Hard Algorithm

# 1e def check_path(G: graph, p: list): ''' Take a graph, G, and a list of vertices, p. Returns True if p is a simple path, False otherwise. Meant as a validation that my longest path algorithm works ''' # If there are any repeats, then p is not a path: if len(set(p)) != len(p): return False # If the path is not feasible (i.e. we cannot traverse the graph to get the path) then return False for u, v in zip(p[:-1], p[1:]): # if path p = 1, 2, 3, 4, p[:-1] = 1, 2, 3 and p[1:] = 2, 3, 4 if not G.isEdge(u, v): return False return True

# Recover the longest path in the DAG def get_longest_path(sssp_result): ''' Recovers the longest path from the result of the longest path algorithm run by cuGraph ''' target_vertex = sssp_result[sssp_result['distance'] == sssp_result['distance'].min()] curr_vertex = target_vertex longest_path = deque([]) while int(curr_vertex['predecessor'].iloc[0]) >= 0: longest_path.appendleft(curr_vertex['vertex'].iloc[0]) curr_vertex = sssp_result[sssp_result['vertex'] == curr_vertex['predecessor'].iloc[0]] return list(longest_path)

def random_dags_longest_path(G, time_limit): ''' Computes longest paths in G by generating random DAG reductions of G and finding the longest path in them Stops either when we reach n! tries, or when the time limit is up. Clearly, we will not reach n!, but we'll see how far we can go. ''' n = len(list(G.vertices)) start_time = time.time() longest_path = None longest_path_len = 0 num_permutations_tried = 0 same_ordering = 0 # if we attempt the same ordering 100 times in a row, we'll give up for i in range(math.factorial(n)): # Get random DAG G_pi, pi = get_random_dag(G) G_pi = get_networkx(G_pi, edge_weight=-1) # negative weights # Compute the shortest paths source = pi[0] path_len = -cugraph.shortest_path_length(G_pi, source)['distance'].min() if path_len > longest_path_len: # Recover the path itself longest_path_len = path_len sssp_result = cugraph.sssp(G_pi, source=source) # get longest path (this method returns predecessors as well) longest_path = get_longest_path(sssp_result) print('New longest path:', path_len) if time.time() - start_time > time_limit: num_permutations_tried = i print('Tried', num_permutations_tried, 'random DAG permutations before the time limit was reached.') break return longest_path_len, longest_path, num_permutations_tried

longest_path_len, longest_path, num_permutations_tried = random_dags_longest_path(fb_graph, 600) # 600 seconds

print('Longest path found was', int(longest_path_len), 'vertices long and the number of DAGs tried in 10 minutes was', num_permutations_tried)

# Show that the path is valid valid = check_path(fb_graph, longest_path) print("The returned path is valid:", valid)

# Confirm the length of the path len(longest_path)

# Show the path itself print('The path itself was:\n' + str(longest_path))

# Try the same with epinions epinions = graph() epinions.Read_Edges(fname="epinions.txt")

longest_path_len, longest_path, num_permutations_tried = random_dags_longest_path(epinions, 600) # 600 seconds

print('Longest path found was', int(longest_path_len), 'vertices long and the number of DAGs tried in 10 minutes was', num_permutations_tried)

Coding Project

Author: Matt Kenney

DFS

Get Random DAG algorithm

Longest Path algorithm from `cuGraph`

Run the Longest Path NP Hard Algorithm

Recommended on Deepnote

Stock Market Analysis

The 10 Best Ways to Create NumPy Arrays

Wide Residual Networks

Coding Project

Author: Matt Kenney

DFS

Get Random DAG algorithm

Longest Path algorithm from cuGraph

Run the Longest Path NP Hard Algorithm

Recommended on Deepnote

Stock Market Analysis

The 10 Best Ways to Create NumPy Arrays

Wide Residual Networks

Longest Path algorithm from `cuGraph`