Any implementations of graph st-ordering or ear-decomposition?

Posted by chang on Stack Overflow See other posts from Stack Overflow or by chang
Published on 2010-04-26T21:10:03Z Indexed on 2010/04/26 21:23 UTC
Read the original article Hit count: 321

Filed under:
|
|
|
|

I'm in the search for an implementation of an ear-decomposition algorithm (http://www.ics.uci.edu/~eppstein/junkyard/euler/ear.html). I examined networkx and didn't find one. Although the algorithm layout is vaguely in my mind, I'd like to see some reference implementation, too.

I'm aware of Ulrik Brandes publication on a linear time Eager st-ordering algorithm, which results in an ear decomposition as a side product, if I understand correctly (it even includes pseudocode, which I'm trying to base my implementation on).

Side problem: First step could be an st-ordering of a graph. Are there any implementations for st-ordering algorithms you know?

Thanks for your input. I'd really like to contribute e.g. to networkx by implementing the ear-decomposition algorithm in python.

© Stack Overflow or respective owner

Related posts about graph

Related posts about decomposition