Partial order with equalities

edit

This seems to work only if I do the merge after adding all the edges:

 D = DiGraph({'a':[], 'd':[], 'e':[]})
 D.add_edge('a', 'd')
 D.add_edge('e', 'a')
 print len(D.all_simple_cycles())  #0

  D.merge_vertices(['d', 'e'])
  print len(D.all_simple_cycles()) #1

But, if the merge is done in the middle, it doesn't work:

D = DiGraph({'a':[], 'd':[], 'e':[]})
D.add_edge('a', 'd')
print len(D.all_simple_cycles())   # 0

D.merge_vertices(['d', 'e'])
print len(D.all_simple_cycles()) # 0

D.add_edge('e', 'a')
print len(D.all_simple_cycles())   # 0

The digraph does not "remember" that the vertices are merged... Is there a way to tell the digraph that two vertices are equivalent, so that it will remember it later?

I think that bookkeeping should be done by hand. Here you are merging vertices d and e and (as specified in the manual) the vertex resulting from merging will be called d. Thus you should be adding edge ('d','a') instead of ('e','a').

Perhaps you can keep a dictionary which tells you which letter actually represents each vertex in the resulting graphs.

Alternatively, you can do the merge just before testing...

def has_cycle_with_merged_vertices(G, merged_groups):
    H = G.copy()
    for m in merged_groups:
        H.merge_vertices(m)
    return bool(H.all_simple_cycles())