2 ============
3 digraphtools
4 ============
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
11 way.
13 The code is hosted on github at https://github.com/dbasden/python-digraphtools
15 Graph Representation
16 ====================
18 Graphs
19 ------
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.
24 e.g.
26         graph = { 1: [2,3],
27                   2: ,
28                   3: [] }
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
36 Binary relations
37 ----------------
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
44 Topological Sorting
45 ===================
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
49 requirements):
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
67 deptools).
69 See the examples in topsort.py and test/test_topsort.py for how to do this.
72 Authors
73 =======
75 digraphtools was initially written by David Basden
78 Thanks
79 ======
81 Thanks to Yaakov L. Varol and Doron Rotem for the design of the algorithm
82 in topsort.py