Welcome, guest | Sign In | My Account | Store | Cart

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

Python, 140 lines
  1
  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'
Created by jimmy2times on Wed, 20 Apr 2011 (MIT)
Python recipes (4591)
jimmy2times's recipes (4)

Required Modules

  • (none specified)

Other Information and Tasks