Implementing a directed graph in python

Question

I am reading Python Templates - Implementing graphs . However, this implementation is inefficient for getting edges pointing to node.

In other languages, the general solution uses a two-dimensional array, but for this, Python will require a list of lists. This is not like pythonic.

What is a directed graph implementation in python where to find all nodes with edges in and out of node (like two separate lists) quickly?

Answer 1

Scipy offers efficient graphical procedures if computational efficiency or scientific computing is important to you:

http://docs.scipy.org/doc/scipy/reference/sparse.csgraph.html

Answer 2

Another library you can use is NetworkX . It provides an implementation of oriented graphs that provide functions for obtaining bound boundaries of DiGraph.in_edges() and outgoing edges of DiGraph.out_edges() for arbitrary sets of nodes. Usage examples are provided in the related documentation, but unfortunately I have not seen any details about efficiency or runtime.

Answer 3

This does not answer your question in the graph, but you can certainly implement a 2D list in Python without resorting to list lists in at least two ways:

You can simply use the dictionary:

 import collections t = collections.defaultdict(int) t[0, 5] = 9 print t[0, 5] 

It also has the advantage of being sparse.

For a more convenient approach, but requiring more work, you can use the 1d list and calculate the index using 2D coordinates, as well as the height and width of the table.

 class Table(object): def __init__(self, width, height): self._table = [None,] * (width * height) self._width = width def __getitem__(self, coordinate): if coordinate[0] >= width or coordinate[1] >= height: raise IndexError('Index exceeded table dimensions') if coordinate[0] < 0 or coordinate[1] < 0: raise IndexError('Index must be non-negative') return self._table[coordinate[1] * width + coordinate[0]] def __setitem__(self, coordinate, value): if coordinate[0] >= width or coordinate[1] >= height: raise IndexError('Index exceeded table dimensions') if coordinate[0] < 0 or coordinate[1] < 0: raise IndexError('Index must be non-negative') self._table[coordinate[1] * width + coordinate[0]] = value t = Table(10,10) t[0, 5] = 9 print t[0, 5] 

Answer 4

Take a look at Pygraph . I used it very little for large directed (and non-oriented) graphs without memory or runtime problems, although they are all implemented in Python, so implementing using C ++ can be very fast.