Partycjonowanie skierowanego wykresu

Question

Próbuję podzielić sieć na jedną lub więcej części na podstawie zestawu krytycznych wierzchołków. Mam kod, który według mnie rozwiązuje mój problem (przynajmniej dotyczy to przypadków, które mnie interesują), ale w trosce o ogólną poprawność szukam nazwy tego, co robię z teorii grafów, a nawet odniesienie do równoważnego algorytmu lub procesu.

Sieć wejściowa jest skierowanym wykresem z pojedynczym źródłem i wierzchołkiem pochodni. Wynikowe partycje muszą mieć tę samą właściwość co oryginał (skierowane wykresy, pojedynczy wierzchołek wierzchołka, pojedynczy wierzchołek zagłębienia), z dodatkowym wymogiem, aby każda partycja miała tylko dwa wierzchołki znajdujące się w zestawie krytycznym i muszą one być początkowe i wierzchołki końcowe.

Edycja

Jeśli źródłem i zlewozmywak są takie same wierzchołki, powstałą pod-wykres zawierałby cyklu. Istniejący kod jest dostępny do wykrywania i usuwania takich cykli. .

End Edit

W tym przypadku schemat jest wart 1000 słów, mam sporządzić prosty wykres, kolorowe wierzchołki stanowią krytyczne wierzchołki, a linie przerywane są partycje wykresie.

alt text http://i50.tinypic.com/1254bkg.jpg

W tym przypadku celem jest znalezienie ewentualnych przegrody pomiędzy 1-1, 1-3, 1-7, 3-1, 3-3, 3-7, 7-1, 7-3 lub 7-7. W rzeczywistości istnieją tylko partycje 1-3, 3-3 i 3-7 (patrz zdjęcie poniżej). Ponadto, ponieważ partycja 3-3 jest nieprawidłowa, wykres został ponownie oznaczony w celu usunięcia niespójności.

alt text http://i49.tinypic.com/2qdsf42.png

Jeśli to pomoże, moje python-eque prace psuedocode wykonując serię przodu i do tyłu wykresu przechodzenia przez zidentyfikowanie wszystkich możliwych partycji.

def graphTraversal(graph,srcid,endids): 
    ''' 
    Given a graph, start a traversal from srcid, stopping search 
    along a branch any time a vertex is in endids. 

    Return the visited subgraph 
    ''' 
    closed = set() 
    open = set([srcid]) 
    while len(open) != 0: 
     i = open.pop() 
     for j in graph.succ(i): 
      if (i,j) not in closed: 
       if j not in endids: 
        open.add(j) 
       closed.add((i,j)) 
    return = graphFromList(closed) 

def findAllValidPartitions(graph,srcids): 
    res = [] 
    for n in srcids: 
     g2 = graphTraversal(graph,n,t) 
     g2rev = reverseEdgesInGraph(g2) 
     for s in srcids: 
      g3 = graphTraversal(g2rev ,s,t) 
      g3rev = reverseEdgesInGraph(g3) 
      g3rev = removeCycles(g3rev,s) 
      if len(g3rev .E) > 0: 
       res.append(g3rev) 
    return res 

Answer 1

Myślę, że próbujesz znaleźć cuts between connected components.