4 Summary: Some tools for working with digraphs, partial orders and topological sorting with Python
5 Home-page: https://github.com/dbasden/python-digraphtools
7 Author-email: davidb-python@rcpt.to
14 Some tools for working with directed acyclic graphs, partial orders and
15 topological sorting with Python
17 digraphtools was written as a lightweight way of using DAGs and partial
18 ordering to represent, sort and traverse dependency trees in a lightweight
21 The code is hosted on github at https://github.com/dbasden/python-digraphtools
29 A graph is represented as a dict which maps a node to a list
30 nodes connected via the outgoing edges of that node.
38 is a DAG represented by the edges (1,2) (1,3) (2,3)
39 where the edge 2tuple is in the form of (from,to)
41 There are helper methods in deptools to generate graphs from a
42 list of edges, and vice versa
47 If a DAG represents dependencies, e.g. the edge (1,2) is taken
48 to mean "1 depends on 2", this is backwards from a binary relation.
49 (1,2) would be the relation 2P1
55 There are two ways of generating linear extensions / topological sorts of
56 dependencies (i.e. orders items must be processed in to satisfy dependency
59 deptools.dfs_topsort_traversal
60 ------------------------------
62 deptools.dfs_topsort_traversal will take a graph and iterate over a
63 single valid topologicaly sorted order
65 deptools.topsort.vr_topsort
66 ---------------------------
68 deptools.topsort.vr_topsort will generate all valid linear extensions /
69 topological orderings given an initial 'seed' linear extension (such as
70 the one generated by deptools.dfs_topsort_traversal).
72 The method does not take the graph format as used by deptools as input,
73 but it does have a helper method to generate it's input matrix from a
74 partial order set (which can be generated from a graph using helpers in
77 See the examples in topsort.py and test/test_topsort.py for how to do this.
83 digraphtools was initially written by David Basden
89 Thanks to Yaakov L. Varol and Doron Rotem for the design of the algorithm
93 Classifier: Intended Audience :: Developers
94 Classifier: Development Status :: 3 - Alpha
95 Classifier: License :: OSI Approved :: BSD License
96 Classifier: Operating System :: OS Independent
97 Classifier: Programming Language :: Python