Any implementations of graph st-ordering or ear-decomposition?
- by chang
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.