Mailing List Archive

Directed Acyclic Graph Representation
Is anybody aware of a reasonable package for representing a directed
acyclic graph in Python, and for rendering that graph in some meaningful
way? I need to build a dependency tree analyzer for, for example,
determining the necessary link order for a set of object libraries.
--
- Tim Roberts, timr@probo.com
Providenza & Boekelheide, Inc.
Directed Acyclic Graph Representation [ In reply to ]
Boa Constructor has one for Python classes (but is GPL). It uses a
(generation-producing) topological sort to create the logical dependency
tree, then draw it using wxPython calls.

I'd suggest just using the topological sort and doing your own drawing
(draw each generation, draw links between each dependent object and its
dependency).

Topological sort module available at:
http://members.rogers.com/mcfletch/programming

HTH,
Mike


Tim Roberts wrote:
> Is anybody aware of a reasonable package for representing a directed
> acyclic graph in Python, and for rendering that graph in some meaningful
> way? I need to build a dependency tree analyzer for, for example,
> determining the necessary link order for a set of object libraries.
> --
> - Tim Roberts, timr@probo.com
> Providenza & Boekelheide, Inc.
>


--
_______________________________________
Mike C. Fletcher
http://members.rogers.com/mcfletch/
Directed Acyclic Graph Representation [ In reply to ]
In article <j9du6uckr4g1am3780qtig50jdhcaf6fcr@4ax.com>, Tim Roberts
<timr@probo.com> writes
>Is anybody aware of a reasonable package for representing a directed
>acyclic graph in Python, and for rendering that graph in some meaningful
>way? I need to build a dependency tree analyzer for, for example,
>determining the necessary link order for a set of object libraries.
>--
>- Tim Roberts, timr@probo.com
> Providenza & Boekelheide, Inc.
GvR did an essay called "Python Patterns - Implementing Graphs". It
should be somewhere at www.python.org. As I recall he did stuff using
edgelists implemented using dictionaries.
--
Robin Becker
Directed Acyclic Graph Representation [ In reply to ]
In article <j9du6uckr4g1am3780qtig50jdhcaf6fcr@4ax.com>, Tim Roberts wrote:
>Is anybody aware of a reasonable package for representing a directed
>acyclic graph in Python, and for rendering that graph in some meaningful
>way? I need to build a dependency tree analyzer for, for example,
>determining the necessary link order for a set of object libraries.

At least efficient representation is available through kjbuckets:
http://www.chordate.com/kjbuckets/

If you'd like to store large graphs efficiently, e4graph might be
interesting:
http://e4graph.sourceforge.net/

Not sure how easy it is to use from Python, but it is based on
MetaKit, which has very nice Python mappings:
http://www.equi4.com/metakit/python.html

--
Magnus Lie Hetland The Anygui Project
http://hetland.org http://anygui.org