CoCalc Public FilesCoen Function File.sage
Author: Patrick Coen
Views : 47
Compute Environment: Ubuntu 18.04 (Deprecated)
1def Depth_First_Search(GG):
2# Name: Patrick Coen
3#Description: Incomplete Code for SA403 Final. Examines whether or not a graph is connected, and returns a list of function times.
4#Input:         GG = Digraph
5#Output:        Graph_Connected: Integer value (1 = Connected, 2 = Not Connected)
6#               finish_time: vector of finish times for the SCC algorithm
7
8# NOTES
9# This code is modified from my submission for the Depth_First_Search algorithm. To note, my submission for the Depth_First_Search HW dependend on help I received from 2/C Shires. As a result, this submission has been assisted (indirecrtly) by 2/C Shires.
10# "colors:"   0 = unvisited, 1 = currently visiting, 2 = have been visited
11# "Graph_Connected:"  0 = initial value, 1 = connected, 2 = not connected
12
13    vertNum = GG.order();              # vertNum is an integer = number of vertices in graph
15    color = matrix(1,vertNum);          # color is the vector holding assigned color values for vertices. To start, it is all zeroes.
16    startVert = 0;                    # chosen arbitrarily
17    run_steps = 0;                    # run_steps will be the value we add to finish_time; for now, it is 0.
18    Graph_Connected = 0;
19    finish_time = matrix(1,vertNum);  # finish_time is the vector holding all of the assigned finish times - its size is number of vertices, initially all 0
20
21    def Depth_First_Search_Visit(v0):
22        color[0,v0] = 1;             # We examine the start_vertex, and declared it "currently visiting", or 1
23        for counter in xrange(0,vertNum):  # Runs loop for every vertex in the graph
24            if(adjMat[v0,counter] == 1):   # If counter_vertex (one we are examining) is adjacent to the initial vertex...
25                if(color[0,counter] == 0): # ...and has "color" 0,
26                    Depth_FirstSearch_Visit(counter);     # Loops back through
27                #end if unvisited
29        #end for all vertices
30        color[0,v0] = 2;              #If there are no remaining vertices adjacent to c with "color" 0, give vertex c "color" 2.
31
32
33    Depth_First_Search_Visit(startVert);
34    for c in xrange(0,vertNum):
35        if(color[0,c] != 2):
36            Graph_Connected = 2;
37            return (Graph_Connected, finish_times)          # If not all of the vertices have been visited (i.e., color=2), then the graph returns "false"
38    Graph_Connected = 1;
39    return (Graph_Connected, finish_times)                   #Otherwise, function returns true
40
41
42
43def Random_Digraph(n,p):
44    GG = digraphs.RandomDirectedGNP(n,p,loops=False)
45    return GG
46
47def Reverse_Digraph(G):
48    G_Reverse = G.reverse()
49    return G_Reverse
50
51def Order_List(list):
52    length = len(list);
53    ordered_list = [0]*length;
54    L = [i[0] for i in sorted(enumerate(list), key=lambda x:x[1])]
55    for i in range(0,length):
56        j = L[i]
57        ordered_list[i] = list[j]
58    return ordered_list
59
60def Reverse_list(list):
61    length = len(list);
62    for i in range(0,length)
63        j = length - i
64        reverse_list[j] = list[i]
65    return reverse_list