Welcome, guest | Sign In | My Account | Store | Cart
```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

self[v] = set()

@abstractmethod
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 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)

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)

return False

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):

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):

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'
```