PKG-INFO

   1 Metadata-Version: 1.0
   2 Name: digraphtools
   3 Version: 0.2.1
   4 Summary: Some tools for working with digraphs, partial orders and topological sorting with Python
   5 Home-page: https://github.com/dbasden/python-digraphtools
   6 Author: David Basden
   7 Author-email: davidb-python@rcpt.to
   8 License: UNKNOWN
   9 Description:
  10         ============
  11         digraphtools
  12         ============
  13
  14         Some tools for working with directed acyclic graphs, partial orders and
  15         topological sorting with Python
  16
  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
  19         way.
  20
  21         The code is hosted on github at https://github.com/dbasden/python-digraphtools
  22
  23         Graph Representation
  24         ====================
  25
  26         Graphs
  27         ------
  28
  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.
  31
  32         e.g.
  33
  34                 graph = { 1: [2,3],
  35                           2: [3],
  36                           3: [] }
  37
  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)
  40
  41         There are helper methods in deptools to generate graphs from a
  42         list of edges, and vice versa
  43
  44         Binary relations
  45         ----------------
  46
  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
  50
  51
  52         Topological Sorting
  53         ===================
  54
  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
  57         requirements):
  58
  59         deptools.dfs_topsort_traversal
  60         ------------------------------
  61
  62         deptools.dfs_topsort_traversal will take a graph and iterate over a
  63         single valid topologicaly sorted order
  64
  65         deptools.topsort.vr_topsort
  66         ---------------------------
  67
  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).
  71
  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
  75         deptools).
  76
  77         See the examples in topsort.py and test/test_topsort.py for how to do this.
  78
  79
  80         Authors
  81         =======
  82
  83         digraphtools was initially written by David Basden
  84
  85
  86         Thanks
  87         ======
  88
  89         Thanks to Yaakov L. Varol and Doron Rotem for the design of the algorithm
  90         in topsort.py
  91
  92 Platform: any
  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