The purpose of this recipe is to look at algorithmic graph theory from an object-oriented perspective.
A graph is built on top of a dictionary indexed by its vertices, each item being the set of neighbours of the key vertex. This ensures that iterating through the neighbours of a vertex is still efficient in sparse graphs (as with adjacency lists) while at the same time checking for adjacency is expected constant-time (as with the adjacency matrix).
Any valid class of graph must implement the interface defined by AbstractGraph.
A generic search algorithm takes as input a graph, source and target vertices and a queue. A queue must implement the methods Q.get(), Q.put() and Q.empty() in such a way to get the desired order in visiting the vertices.
Given this pattern, breadth-first and depth-first search are essentially defined by the corresponding expansion policies: the first one uses an actual FIFO queue, the second one a LIFO queue (or stack).
Download
Copy to clipboard1 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 | from abc import ABCMeta, abstractmethod
from collections import Counter
from Queue import Queue, LifoQueue
class AbstractGraph(dict):
__metaclass__ = ABCMeta
def __init__(self):
dict.__init__(self)
self._size = 0
def order(self):
return len(self)
def size(self):
return self._size
def neighbours(self, v):
return self[v]
@abstractmethod
def degree(self, v):
pass
def add_vertex(self, v):
self[v] = set()
@abstractmethod
def add_edge(self, u, v):
self._size += 1
@abstractmethod
def remove_edge(self, u, v):
self._size -= 1
class UndirectedGraph(AbstractGraph):
def degree(self, v):
return len(self.neighbours(v))
def add_edge(self, u, v):
AbstractGraph.add_edge(self, u, v)
self.neighbours(u).add(v)
self.neighbours(v).add(u)
def remove_edge(self, u, v):
AbstractGraph.remove_edge(self, u, v)
self.neighbours(u).remove(v)
self.neighbours(v).remove(u)
class DirectedGraph(AbstractGraph):
def __init__(self):
AbstractGraph.__init__(self)
self._indegree = Counter()
def in_degree(self, v):
return self._indegree[v]
def out_degree(self, v):
return len(self.neighbours(v))
def degree(self, v):
return self.in_degree(v) + self.out_degree(v)
def add_edge(self, u, v):
AbstractGraph.add_edge(self, u, v)
self.neighbours(u).add(v)
self._indegree[v] += 1
def remove_edge(self, u, v):
AbstractGraph.remove_edge(self, u, v)
self.neighbours(u).remove(v)
self._indegree[v] -= 1
def generic_search(G, s, t, Q):
visited = set()
Q.put(s)
while not Q.empty():
u = Q.get()
if u not in visited:
if u == t:
return True
for v in G.neighbours(u):
Q.put(v)
visited.add(u)
return False
def breadth_first_search(G, s, t):
return generic_search(G, s, t, Queue())
def depth_first_search(G, s, t):
return generic_search(G, s, t, LifoQueue())
if __name__ == '__main__':
G = UndirectedGraph()
for i in range(1, 5):
G.add_vertex(i)
G.add_edge(1, 2)
G.add_edge(2, 3)
assert G.order() == 4
assert G.size() == 2
assert 2 in G.neighbours(1) and 1 in G.neighbours(2)
assert G.degree(1) == 1 and G.degree(2) == 2
assert breadth_first_search(G, 1, 3) and depth_first_search(G, 1, 3)
assert breadth_first_search(G, 3, 1) and depth_first_search(G, 3, 1)
assert not (breadth_first_search(G, 4, 2) or depth_first_search(G, 4, 2))
G = DirectedGraph()
for i in range(1, 4):
G.add_vertex(i)
G.add_edge(1, 2)
G.add_edge(2, 3)
assert G.order() == 3
assert G.size() == 2
assert 2 in G.neighbours(1) and 1 not in G.neighbours(2)
assert G.degree(1) == 1 and G.degree(2) == 2
assert G.in_degree(2) == G.out_degree(2) == 1
assert breadth_first_search(G, 1, 3) and depth_first_search(G, 1, 3)
assert not (breadth_first_search(G, 3, 1) or depth_first_search(G, 3, 1))
print 'OK'
|
