CoCalc -- Coen Function File.sage

Views: ⁸²
1
def 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
14
    adjMat = GG.adjacency_matrix();    # adjMat = adjacency matrix of input graph H
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
28
            #end if adjacent
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

43
def Random_Digraph(n,p):
44
    GG = digraphs.RandomDirectedGNP(n,p,loops=False)
45
    return GG
46

47
def Reverse_Digraph(G):
48
    G_Reverse = G.reverse()
49
    return G_Reverse
50

51
def 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

60
def 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
66