6 Some tools for working with directed acyclic graphs, partial orders and
7 topological sorting with Python
9 digraphtools was written as a lightweight way of using DAGs and partial
10 ordering to represent, sort and traverse dependency trees in a lightweight
13 The code is hosted on github at https://github.com/dbasden/python-digraphtools
21 A graph is represented as a dict which maps a node to a list
22 nodes connected via the outgoing edges of that node.
30 is a DAG represented by the edges (1,2) (1,3) (2,3)
31 where the edge 2tuple is in the form of (from,to)
33 There are helper methods in deptools to generate graphs from a
34 list of edges, and vice versa
39 If a DAG represents dependencies, e.g. the edge (1,2) is taken
40 to mean "1 depends on 2", this is backwards from a binary relation.
41 (1,2) would be the relation 2P1
47 There are two ways of generating linear extensions / topological sorts of
48 dependencies (i.e. orders items must be processed in to satisfy dependency
51 deptools.dfs_topsort_traversal
52 ------------------------------
54 deptools.dfs_topsort_traversal will take a graph and iterate over a
55 single valid topologicaly sorted order
57 deptools.topsort.vr_topsort
58 ---------------------------
60 deptools.topsort.vr_topsort will generate all valid linear extensions /
61 topological orderings given an initial 'seed' linear extension (such as
62 the one generated by deptools.dfs_topsort_traversal).
64 The method does not take the graph format as used by deptools as input,
65 but it does have a helper method to generate it's input matrix from a
66 partial order set (which can be generated from a graph using helpers in
69 See the examples in topsort.py and test/test_topsort.py for how to do this.
75 digraphtools was initially written by David Basden
81 Thanks to Yaakov L. Varol and Doron Rotem for the design of the algorithm