-
Notifications
You must be signed in to change notification settings - Fork 0
/
graph_search.py
177 lines (145 loc) · 4.52 KB
/
graph_search.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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
from collections import deque
from collections import defaultdict
class Graph:
def __init__(self, directed=True):
self.graph = defaultdict(set)
self.directed = directed
def add_edge(self, a, b):
"""
Add an edge
Add an edge between vertex a and b.
If undirected, add an edge between b and a too.
Parameters
----------
a : int or str
Vertex id.
b : int or str
Vertex id.
"""
self.graph[a].add(b)
if not self.directed:
self.graph[b].add(a)
def bfs(self, start):
"""
Breadth First Search that uses queues
Parameters
----------
graph: dict
A dictionary representing adjacency lists
start: str
A starting vertex
Returns
-------
list
Order of traversal in BFS
dict
Parent nodes of every vertex
"""
visited = defaultdict(lambda: False)
parents = defaultdict(lambda: None)
queue = [start]
order = []
while queue:
next_ = queue.pop(0)
if not visited[next_]:
order.append(next_)
visited[next_] = True
unexplored = [
neigh for neigh in self.graph[next_] if not visited[neigh]]
queue.extend(unexplored)
for v in unexplored:
if not parents[v]:
parents[v] = next_
return order, parents
def find_path(self, start, end, parents=None, path=[]):
"""
Find the shortest path.
Parameters
----------
start : int or str
Starting vertex
end : int or str
Ending vertex
Returns
-------
list
A list of vertices that takes us from start to finish.
"""
if parents is None:
_, parents = self.bfs(start)
if start == end or end is None:
path.insert(0, start)
else:
path.insert(0, end)
self.find_path(start, parents[end], parents, path)
return path
@staticmethod
def _complement(colour):
if colour == 'red':
return 'black'
else:
return 'red'
def is_bipartite(self):
"""
Determine if the graph is bipartite
Returns
-------
bool
True if bipartite. False otherwise.
Notes
-----
1. We start with a regular BFS
a. Initialize queue with a start node
b. Color it 'red'
c. Repeat until empty queue
i. Popleft the next node
ii. Mark it as visited
iii. Gather all it's neighbors
iv. If a neighbor is not colored, paint it the complementary
color
v. If a neighbor is colored, and it's the same as it's
predecessor, then the graph is not bipartite, return False.
vi. Otherwise, carry on.
d. Return True in the end, if we could successfully color all
vertices the correct color.
"""
start = list(self.graph)[0]
color = defaultdict(lambda: None)
visited = defaultdict(lambda: False)
queue = deque()
queue.append(start)
color[start] = 'red'
while queue:
next_ = queue.popleft()
visited[next_] = True
neigh = self.graph[next_]
for v in neigh:
if color[v] is None:
color[v] = self._complement(color[next_])
if color[v] == color[next_]:
return False
if not visited[v]:
queue.append(v)
return True
def dfs(self, start):
"""
Depth First Search
Parameters
----------
start : int or str
Starting node
Returns
-------
list
Traversal order
"""
order = []
stack = [start]
visited = defaultdict(lambda: False)
while stack:
next_ = stack.pop()
if not visited[next_]:
order.append(next_)
visited[next_] = True
stack.extend(list(self.graph[next_]))
return order