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

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-decomposi开发者_如何学Pythontion algorithm in python.

---

I dug this up, but the credit goes to it's author Minjae Park

# 20106911 Minjae Park
# Finding an Ear decomposition of 2(-edge)-connected graph

import networkx as nx
import matplotlib.pyplot as plt

colorList = ["orange", "blue", "red", "green", "magenta", "purple", "yellow", "black"]
global count
count=0

'''
Input Graph
'''
# Complete Graph
#G=nx.complete_graph(6)

'''
# Non 2-connected (but 2-edge-connected) Graph
G=nx.Graph()
G.add_edge(0,1)
G.add_edge(1,2)
G.add_edge(2,0)
G.add_edge(2,3)
G.add_edge(3,4)
G.add_edge(4,5)
G.add_edge(5,3)
G.add_edge(4,2)
'''

# Petersen Graph
G=nx.petersen_graph()

'''
Testing 2-edge-connectivity
'''
for e in G.edges():
    H=nx.Graph(G)
    G.remove_edge(*e)
    if not nx.is_connected(G):
        raise SystemExit("G is not 2-edge-connected. This algorithm is not valid.")
    G=H

'''
Testing 2-connectivity
'''
for v in G.nodes():
    H=nx.Graph(G)
    G.remove_node(v)
    if not nx.is_connected(G):
        print "G is not 2-connected. The result is not an open ear decomposition."
    G=H

'''
Algorithm for Finding an Ear Decomposition
'''
def makeSpanningTree(G,root):
    T=nx.Graph()
    T.add_node(root)
    T.node[root]['dfsnum']=len(T.nodes())
    makeSpanningTreeDFS(G,T,root)
    return T

def makeSpanningTreeDFS(G,T,current):
    if not 'child' in T.node[current]:
        T.node[current]['child']=[]
    for neighbor in G.neighbors(current):
        if not neighbor in T.nodes():
            T.add_node(neighbor)
            T.add_edge(current,neighbor)
            T.node[neighbor]['dfsnum']=len(T.nodes())
            T.node[neighbor]['parent']=current
            T.node[current]['child'].append(neighbor)
            makeSpanningTreeDFS(G,T,neighbor)

def assignNonTreeEdgeLabel(G,T,current):
    global count
    subrootdfsnum=T.nodes(data=True)[current][1]['dfsnum']
    for node,nodeattr in T.nodes(data=True):
        if nodeattr['dfsnum']>subrootdfsnum:
            if ((current,node) in G.edges() or (node,current) in G.edges()) and not ((current,node) in T.edges() or (node,current) in T.edges()):
                G[current][node]['label']=count
                count+=1
    for neighbor in T.nodes(data=True)[current][1]['child']:
        assignNonTreeEdgeLabel(G,T,neighbor)

def assignTreeEdgeLabel(G,T,current):
    if not T.nodes(data=True)[current][1]['child']:
        label=[]
        for neighbor in G.neighbors(current):
            if 'label' in G[current][neighbor]:
                label.append(G[current][neighbor]['label'])
        if 'parent' in T.node[current]:
            parent=T.node[current]['parent']
            G[current][parent]['label']=min(label)
    else:
        for neighbor in T.nodes(data=True)[current][1]['child']:
            if not 'label' in T.node[neighbor]:
                assignTreeEdgeLabel(G,T,neighbor)
        if 'parent' in T.node[current]:
            parent=T.node[current]['parent']
            label=[]
            for neighbor in G.neighbors(current):
                if 'label' in G[current][neighbor]:
                    label.append(G[current][neighbor]['label'])
            G[current][parent]['label']=min(label)


T=makeSpanningTree(G,0)
assignNonTreeEdgeLabel(G,T,0)
assignTreeEdgeLabel(G,T,0)

'''
Output
'''
pos=nx.circular_layout(G)
ear_list=[[] for i in range(count+1)]
for (x,y) in G.edges():
    ear=G[x][y]['label']
    ear_list[ear].append((x,y))
nx.draw_networkx_nodes(G,pos)
nx.draw_networkx_labels(G,pos)
for i in range(len(ear_list)):
    nx.draw_networkx_edges(G,pos,edgelist=ear_list[i],edge_color=colorList[i%len(colorList)],alpha=0.5,width=3)
nx.draw_networkx_edge_labels(G,pos,alpha=0.5)

plt.show()