-
Notifications
You must be signed in to change notification settings - Fork 0
/
graph.py
141 lines (119 loc) · 4.86 KB
/
graph.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
class Graph:
# ---------------------Nested Vertex class----------------
class Vertex:
__slots__ = 'value'
# Constructor to initialize the value
def __init__(self,value):
self.value = value
# Returning hashed value of the object to be used as key in map
def __hash__(self):
return(hash(id(self)))
# -------------------Nested Edge class--------------------
class Edge:
__slots__ = 'origin','dest','weight'
#Constructor to initialize the edge
def __init__(self,origin,dest,value):
self.origin = origin
self.dest = dest
self.weight = value
#Returns the two endpoints of edge
def endpoints(self):
return(self.origin,self.dest)
#Returns the other end of the edge if one of the vertex is passed
def opposite(self,v):
return self.origin if v is self.dest else self.dest
#Hasing edge to be used as key in map
def __hash__(self):
return(hash(self.origin,self.dest))
#---------------Graph Implementation----------------------------------
# Constructor of Graph class where the outgoing and incoming maps are initialized
def __init__(self,directed=False):
self.directed = directed
self.out = {}
self.inc = {} if self.directed else self.out #inc will be only be used in directed is True
#Returns the count of the vertex
def vertex_count(self):
return(len(self.out))
# Return iteration of all the vertices of graph
def vertices(self):
return self.out.keys()
#Return the total edges
def edge_count(self):
total = sum(len(self.out[v])for v in self.out)
# Return total if its directed else return half
return total if self.directed else total//2
#Returns the set of edges
def edges(self):
#Declaring a set so the same edges are not added in case of undirected graphs
res = set()
for val in self.out.values():
res.update(val.values())
return res
#Return the edge between u and v if it exists
def get_edge(self,u,v):
return(self.out[u].get(v,None))
#Returns number of outgoing edges from v in the graph
def degree(self,v,outgoing = True ):
adjacent = self.out if outgoing else self.inc
return(len(adjacent[v]))
#Returns incident edges going from v
def incident_edges(self,v,outgoing = True):
# If graph is directed the optional parameter should be passed
adjacent = self.out if outgoing else self.inc
for edge in adjacent[v].values():
yield edge #Generator to return edge one by one
#Inserts a new vertex in the graph
def insert_vertex(self,val=None):
vertex = self.Vertex(val) #Creates a vertex object
self.out[vertex] = {} # Declares a map to store adjacent vertices
if self.directed:
self.inc[vertex] = {} #Declare a map for incoming edge for directed graph
return vertex
#Creates a new edge between u and v
def insert_edge(self,u,v,weight=1):
e = self.Edge(u,v,weight)
self.out[u][v] = e
self.inc[v][u] = e
#----------------------End of Graph Implementation---------------------------------
#-----------------Graph Traversal--------------------------------------------
#Depth first search of the graph. Add u to the discovered map before calling the function
def dfs(g,u,discovered):
#g----->Graph object
#u------>Starting vertex
#discovered-------->Map containing discovered vertex along with edge
for e in g.incident_edges(u):
v = e.opposite(u)
if v not in discovered:
discovered[v] = e
dfs(g,u,discovered)
#Once DFS is done we can reconstruct a path from u to v
def construct_path(u,v,discovered):
# discovered ----> the map containing all visited vertex
# along with edge obtained through DFS
path = []
if v in discovered:
path.append(v)
walk = v
while(walk is not u):
e = discovered[v]
parent = e.opposite(v)
path.append(parent)
walk = parent
path.reverse()
return path
# Breadth first traversal of graph using queue
from collections import deque
def bfs(g,s,discovered):
#s----> Starting vertex
queue = deque()
discovered={}
discovered[s]=None
queue.append(s)
while(len(queue)>0):
u = queue[0]
queue.pop()
for e in g.incident_edges(u):
v = e.opposite(u)
if v not in discovered:
discovered[v] = e
queue.append(v)