Implementing a directed graph in python

Question

I read Python Patterns - Implementing Graphs. However this implementation is inefficient for getting the edges that point to a node.

In other languages a common solution is using a two-dimensional array, but to do this in Python would require a list of lists. This does not seem pythonic.

What is an implementation of a directed graph in python where finding all the nodes with edges to and from a node (as two separate lists) is fast?

Answer 1

networkx is definitely the most popular Python graph library. It is well documented, has a great API, and is performant. Suppose you have the following graph:

Here's how to create this graph and calculate all the edges that are pointing to node e:

import networkx as nx

graph = nx.DiGraph()
graph.add_edges_from([("root", "a"), ("a", "b"), ("a", "e"), ("b", "c"), ("b", "d"), ("d", "e")])
print(graph.in_edges("e")) # => [('a', 'e'), ('d', 'e')]

Here's how you can calculate all the edges that node b points towards:

print(graph.out_edges("b")) # => [('b', 'c'), ('b', 'd')]

networkx is a fantastic library. See here for more details.

Answer 2

Another library you could use is NetworkX. It provides a implementation of directed graphs that provide functions to get incomming edges DiGraph.in_edges() and outgoing edges DiGraph.out_edges() for arbitrary sets of nodes. Usage samples are provided in the linked documentation, but unfortunately I didn't see any details about efficiency or run time.

Answer 3

Scipy offers efficient Graph routines if computational efficiency or scientific computing is your concern:

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