# digraphtools Release 0.1.0

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

License
Other
Install
``` pip install digraphtools==0.1.0 ```

### Documentation

```============
digraphtools
============

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.

Authors
=======

digraphtools was initially written by David Basden

Thanks
======

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