CODEWITHSUNDEEP
python
jan
jan

Reputation: 2423

Implementing a directed graph in python

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?

Upvotes: 13

Views: 51036

Answers (5)

Michael Mauderer
Michael Mauderer

Reputation: 3872

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.

Upvotes: 7

Powers
Powers

Reputation: 19308

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.

Upvotes: 7

Nathan
Nathan

Reputation: 4937

This doesn't answer your graph question, but you can certainly implement a 2D list in Python without resorting to lists of lists in at least two ways:

You can simply use a dictionary:

import collections
t = collections.defaultdict(int)

t[0, 5] = 9
print t[0, 5]

This also has the advantage that it is sparse.

For a fancier approach, but one requiring more work, you can use a 1d list and compute the index using the 2D coordinates along with the table's height and width.

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]

Upvotes: 4

Pyrce
Pyrce

Reputation: 8596

Take a look at the Pygraph. I've used it quite a bit for large directed (and undirected) graphs without memory or run-time issues, though it is all implemented in Python so a C++ wrapped implementation could be much fast.

Upvotes: 1

Edmon
Edmon

Reputation: 4872

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

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

Upvotes: 5

Related Questions