Basic graph traversals

Question

Below is an implementation of two graph traversals. Graph constructor creates a random graph with a fixed number of edges (fixed as a proportion of the maximum number of vertices, number_nodes-1).

Any comments welcome, but especially data structure and algorithm comments. Tests are not implemented properly, but it is ok in this case.

import random
class Graph:
    def __init__(self, number_nodes, max_number_edges = 0.5): 
        if (max_number_edges > 1) or (max_number_edges < 0):
            raise ValueError("max_number_edges is out of range")
        self.nodes_connections = {node_nb : range(node_nb+1, number_nodes) for node_nb in xrange(number_nodes)}
        for key, value in self.nodes_connections.iteritems():
            while len(value) > (max_number_edges * (number_nodes - key - 1)):
                index_to_remove = random.randint(0, len(value)-1)
                del value[index_to_remove]

    def Print(self): 
        for key, value in self.nodes_connections.iteritems():
            print key, value 

    def IterateInBreadth(self, start_node_id):
        visited_nodes_ids = []
        scheduled_nodes_ids = [start_node_id] 
        while scheduled_nodes_ids:
            node_id = scheduled_nodes_ids[0]
            new_scheduled_nodes_ids = [node for node in self.nodes_connections[node_id] 
                                        if not (node in visited_nodes_ids or node in scheduled_nodes_ids)] 
            new_scheduled_nodes_ids += [key for key, value in self.nodes_connections.iteritems() 
                                            if (node_id in value) and not (key in visited_nodes_ids or key in scheduled_nodes_ids)] 
            scheduled_nodes_ids += new_scheduled_nodes_ids 
            visited_nodes_ids.append(node_id)
            del scheduled_nodes_ids[0]
        return visited_nodes_ids

    def __IterateInDepth(self, start_node_id, visited_nodes):
        visited_nodes.append(start_node_id)
        for key, value in self.nodes_connections.iteritems():
            if start_node_id in value:
                if key not in visited_nodes:
                    self.__IterateInDepth(start_node_id = key, visited_nodes = visited_nodes)
        for value in self.nodes_connections[start_node_id]:
            if value not in visited_nodes:
                self.__IterateInDepth(start_node_id = value, visited_nodes = visited_nodes)            

    def IterateInDepth(self, start_node_id):
        visited_nodes = []
        self.__IterateInDepth(start_node_id, visited_nodes = visited_nodes)
        return visited_nodes

if __name__ == '__main__':
    #random.seed(1000)

    g = Graph(number_nodes = 11, max_number_edges = 0.33)
    g.Print()
    print g.IterateInBreadth(8)
    print g.IterateInBreadth(0)
    print g.IterateInDepth(8)
    print g.IterateInDepth(0)

Answer 1

1. It's not very relevant for traversal, but a dict-of-sets may be a better overall structure than a dict-of-lists, as it would let you check for edge existence between two random nodes in amortized constant time, as opposed to worst case linear on the number of edges.
2. Using sets instead of lists for things like visited_nodes is bound to have a significant impact on performance for larger graphs though.
3. Another point to consider, since you are building an iterator, is to make your function return, well, an iterator of course! You can always materialize them calling list on the return, but for traversals of huge graphs it may spare you a generous amount of memory.

I'm going to skip the making it a class part, but with graph being a dict-of-iterables, and the above points in mind, you could implement depth-first iteration as:

def _dfs_iter(graph, node, visited_nodes):
    if node in visited_nodes:
        raise StopIteration

    visited_nodes.add(node)
    yield node

    for next_node in graph[node]:
        for n in _dfs_iter(graph, next_node, visited_nodes):
            yield n

def dfs_iter(graph, node):
    assert node in graph
    visited_nodes = set()
    return _dfs_iter(graph, node, visited_nodes)

4. There is no native Python data structure really well suited to create a FIFO queue. There is deque in collections, but it is a little obscure language feature, and also not ideally suited, so I'm going to pass on using it. Your implementation using a list and removing items from the front will lead to a terrible worse case performance, probably quadratic in the number of nodes. At the cost of not releasing the memory early, I think it is better to never remove items from the queue, and use an indexing pointer.

With the same caveats as before, you could do breadth-first iteration as:

def bfs_iter(graph, node):
    assert node in graph

    fifo_index = 0
    fifo_queue = [node]
    scheduled_nodes = set(fifo_queue)

    while fifo_index < len(fifo_queue):
        node = fifo_queue[fifo_index]
        fifo_index += 1
        fifo_queue.extend([n for n in graph[node] if n not in scheduled_nodes])
        scheduled_nodes.update(graph[node])
        yield node

5. Note that I'm keeping duplicate accounting on scheduled_nodes, both in fifo_queue and scheduled_nodes. This is to have the ordering of the FIFO queue and the fast membership check of a hash table. You could get rid of scheduled_nodes by checking against membership in fifo_queue, but you will again get quadratic performance, not a good thing.

A simple test on this graph:

6 - 0 - 1
| / | \ |
5   4 - 3 - 2 - 7

seems to yield correct results:

if __name__ == '__main__':

    graph = {0: set([1, 4, 5, 6,]),
             1: set([0, 3,]),
             2: set([3, 7]),
             3: set([0, 1, 2, 3, 4,]),
             4: set([0, 3,]),
             5: set([0, 6,]),
             6: set([0, 5,]),
             7: set([2,]),
             }
    assert list(dfs_iter(graph, 0)) == [0, 1, 3, 2, 7, 4, 5, 6]
    assert list(bfs_iter(graph, 0)) == [0, 1, 4, 5, 6, 3, 2, 7]

Note that, since we are using sets, the exact order of iteration over the connected nodes is implementation dependent, so a failure form the above tests doesn't necessarily mean that something is broken in the algorithm.

Answer 2

If I understand correctly, your graph is represented as a dictionary of connections, where the dictionary keys are node indices and the values are lists of node indices to which the keyed node is connected.

One point of confusion: when I used random.seed(1000) and ran your code, I got this graph:

0 [2, 3, 9]
1 [7, 10]
2 [4, 8]
3 [5, 8]
4 [6]
5 [10]
6 [9]
7 []
8 []
9 []
10 []

If I am understanding correctly, I see that node 0 is connected to nodes 2, 3, and 9. Is that right? My confusion is that node 9 is not connected to node 0. Is this to avoid double-counting edges? Or is this meant to represent a directed graph? The output of your traversal routines makes me think that you want undirected graphs.

Some suggestions:

1. Two other useful ways to represent graphs is via edge lists or via adjacency matrices. Your representation is sort of like a sparse adjacency matrix, but not quite. For your application, I'd suggest edge lists unless you really need the format you have for some other reason.

Here's a quick implementation of breadth-first traversal using an edge_list.

from random import sample, seed

num_nodes = 11
density = 0.33

node_indices = range(num_nodes)

num_edges = int(density * num_nodes * (num_nodes-1) / 2)

# generate a random graph in edge list format:
seed(0)
edge_list = []
while len(edge_list) < num_edges:
    edge = tuple(sample(node_indices, 2))
    if edge not in edge_list:
        edge_list.append(edge)

visited = []
def breadth_first_traversal(visited, edge_list, start_node_list):
    """
    Function to vist nodes in a graph represented by an edge list in breadth-first order.
        :param:     visited,  a global list of node indices
        :param:     edge_list, list of (int, int) tuples representing graph to be traversed.
        :param:     start_node_list, a list of ints: nodes at which to start traversal
    """
    visited.extend(start_node_list)

    # find nodes connected to start_nodes
    connections = []
    for node in start_node_list:
        connections.extend([x for (x, y) in edge_list if y==node] +
                           [y for (x, y) in edge_list if x==node])

    # remove any already-vistied nodes from the connections list and remove duplicates
    connections = list(set(connections) - set(visited))

    # continue traversal at each newly visited node
    if connections:
        breadth_first_traversal(visited, edge_list, connections)
    else:
        return

print 'Edge list for random graph:'
for edge in sorted(edge_list):
    print sorted(edge)

breadth_first_traversal(visited, edge_list, [0])

print 'Breadth-first traversal of graph: %s' % visited

Edge list for random graph:
[0, 4]
[2, 8]
[3, 7]
[2, 4]
[4, 6]
[1, 5]
[4, 5]
[5, 8]
[5, 10]
[0, 6]
[2, 6]
[3, 7]
[3, 8]
[8, 9]
[5, 9]
[6, 9]
[7, 9]
[9, 10]
Breadth-first traversal of graph: [0, 4, 6, 9, 2, 5, 8, 1, 10, 7, 3]

Opinions will vary on whether my use of a global visited list is good, but it is faster than writing methods that return visited lists since only one list is modified in place and copies are not created. It can make the code a bit trickier to digest, though.

2. For code this complex, comments and docstrings are good!

3. Why is there are "internal" __ method required for IterateInDepth, but not for IterateInBreadth? I'd expect more symmetry between the two implementations.

4. Your definition of max_num_edges is confusing because it is somehow normalized to the number of nodes in the graph. Is your definition equivalent to the density of a graph? If so, I'd rename your variable to density or something similar.

5. As I mentioned in the comments, check out networkx. The source for their implementation of breadth first search is available in Github.

6. I'm still learning OOP myself, but your class structure seems solid to me.