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

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

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

# 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

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