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_visit(G, s, q, pre=None, post=None):
visited = set()
q.put(s)
while not q.empty():
u = q.get()
if u not in visited:
if pre:
pre(u)
for v in G.neighbours(u):
q.put(v)
if post:
post(u)
visited.add(u)
def generic_search(G, s, t, visit):
generic_search.found = False
def search_pre(v):
if v == t:
generic_search.found = True
visit(G, s, pre=search_pre)
return generic_search.found
def breadth_first_visit(G, s, pre=None, post=None):
generic_visit(G, s, Queue(), pre, post)
def depth_first_visit(G, s, pre=None, post=None):
generic_visit(G, s, LifoQueue(), pre, post)
def breadth_first_search(G, s, t):
return generic_search(G, s, t, breadth_first_visit)
def depth_first_search(G, s, t):
return generic_search(G, s, t, depth_first_visit)
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))
Diff to Previous Revision
--- revision 1 2011-04-20 01:11:45
+++ revision 2 2011-04-21 02:43:09
@@ -1,5 +1,6 @@
from abc import ABCMeta, abstractmethod
-import collections
+from collections import Counter
+from Queue import Queue, LifoQueue
class AbstractGraph(dict):
@@ -54,7 +55,7 @@
def __init__(self):
AbstractGraph.__init__(self)
- self.indegree = collections.Counter()
+ self.indegree = Counter()
def in_degree(self, v):
return self.indegree[v]
@@ -76,17 +77,17 @@
self.indegree[v] -= 1
-def generic_visit(G, s, expand, pre=None, post=None):
+def generic_visit(G, s, q, pre=None, post=None):
visited = set()
- q = collections.deque()
- q.append(s)
+ q.put(s)
- while len(q) > 0:
- u = q.popleft()
+ while not q.empty():
+ u = q.get()
if u not in visited:
if pre:
pre(u)
- expand(q, u)
+ for v in G.neighbours(u):
+ q.put(v)
if post:
post(u)
visited.add(u)
@@ -105,21 +106,11 @@
def breadth_first_visit(G, s, pre=None, post=None):
-
- def bfs_expand(q, u):
- for v in G.neighbours(u):
- q.append(v)
-
- generic_visit(G, s, bfs_expand, pre, post)
+ generic_visit(G, s, Queue(), pre, post)
def depth_first_visit(G, s, pre=None, post=None):
-
- def dfs_expand(q, u):
- for v in G.neighbours(u):
- q.appendleft(v)
-
- generic_visit(G, s, dfs_expand, pre, post)
+ generic_visit(G, s, LifoQueue(), pre, post)
def breadth_first_search(G, s, t):
