CoCalc Shared FilesCoen Function File.sageOpen in CoCalc with one click!
Author: Patrick Coen
Views : 11
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