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'
Diff to Previous Revision
--- revision 6 2011-04-21 13:39:53
+++ revision 7 2011-04-21 13:40:32
@@ -137,4 +137,4 @@
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'
+ print 'OK'
