Des implémentations de st-ordre de graphe ou de décomposition de l'oreille?

Question

Je suis à la recherche d'une implémentation d'un algorithme de décomposition de l'oreille (http://www.ics.uci.edu/~eppstein/junkyard/euler/ear.html). J'ai examiné networkx et n'en ai pas trouvé. Bien que la mise en page de l'algorithme soit vaguement dans mon esprit, j'aimerais aussi voir une implémentation de référence. Je suis au courant de Ulrik Brandes publication sur un algorithme de st-ordre Eager temps linéaire, qui se traduit par une décomposition de l'oreille en tant que produit secondaire, si je comprends bien (il comprend même pseudocode, que je suis en train de baser ma mise en œuvre sur).

Problème secondaire: La première étape pourrait être un st-ordre d'un graphe. Existe-t-il des implémentations pour les algorithmes de classement?

Merci de votre participation. J'aimerais vraiment contribuer, par exemple. à networkx en implémentant l'algorithme de décomposition de l'oreille en python.

Answer 1

Je creusèrent ce, mais le crédit va à son auteur Minjae Parc

# 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()