from abc import ABCMeta, abstractmethod
import collections
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 = collections.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, expand, pre=None, post=None):
visited = set()
q = collections.deque()
q.append(s)
while len(q) > 0:
u = q.popleft()
if u not in visited:
if pre:
pre(u)
expand(q, u)
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):
def bfs_expand(q, u):
for v in G.neighbours(u):
q.append(v)
generic_visit(G, s, bfs_expand, 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)
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))
