Implementing a directed graph in python

user_750024 0
Viewed 35598

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?

python
5 Answers

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:

enter image description here

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.

user_11251590
Related