Some tools for working with digraphs, partial orders and topological sorting with Python

## Project Description

Some tools for working with directed acyclic graphs, partial orders and topological sorting with Python

digraphtools was written as a lightweight way of using DAGs and partial ordering to represent, sort and traverse dependency trees in a lightweight way.

The code is hosted on github at https://github.com/dbasden/python-digraphtools

## Graph Representation

### Graphs

A graph is represented as a dict which maps a node to a list nodes connected via the outgoing edges of that node.

e.g.

- graph = { 1: [2,3],
- 2: [3], 3: [] }

is a DAG represented by the edges (1,2) (1,3) (2,3) where the edge 2tuple is in the form of (from,to)

There are helper methods in deptools to generate graphs from a list of edges, and vice versa

### Binary relations

If a DAG represents dependencies, e.g. the edge (1,2) is taken to mean “1 depends on 2”, this is backwards from a binary relation. (1,2) would be the relation 2P1

## Topological Sorting

There are two ways of generating linear extensions / topological sorts of dependencies (i.e. orders items must be processed in to satisfy dependency requirements):

### deptools.dfs_topsort_traversal

deptools.dfs_topsort_traversal will take a graph and iterate over a single valid topologicaly sorted order

### deptools.topsort.vr_topsort

deptools.topsort.vr_topsort will generate all valid linear extensions / topological orderings given an initial ‘seed’ linear extension (such as the one generated by deptools.dfs_topsort_traversal).

The method does not take the graph format as used by deptools as input, but it does have a helper method to generate it’s input matrix from a partial order set (which can be generated from a graph using helpers in deptools).

See the examples in topsort.py and test/test_topsort.py for how to do this.

## Thanks

Thanks to Yaakov L. Varol and Doron Rotem for the design of the algorithm in topsort.py

## Release history Release notifications

## Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Filename, size & hash SHA256 hash help | File type | Python version | Upload date |
---|---|---|---|

digraphtools-0.2.1.tar.gz (8.2 kB) Copy SHA256 hash SHA256 | Source | None | Sep 7, 2011 |