Yönlendirilmiş bir grafiğin bölümlendirilmesi

Question

Bir ağı kritik bir dizi kümesine göre bir veya daha fazla parçaya bölmeye çalışıyorum. Sorunumu çözdüğüme inandığım bir kod var (en azından ilgilendiğim vakalar için), ama genel olarak doğruluk sağlamak adına, yaptığım şeyin adını arıyorum. grafik teorisinden veya hatta eşdeğer bir algoritma veya süreç üzerindeki bir referanstan.

Giriş ağı, tek bir kaynağa ve sink vertex'e sahip yönlendirilmiş bir grafiktir. Ortaya çıkan bölümler, orijinalin (yönlendirilmiş grafikler, tek kaynak köşe, tek havuzlu köşe) aynı özelliğe sahip olması gerekir. Ayrıca, her bölümün yalnızca kritik kümedeki iki köşeye sahip olması gerekir ve bunlar başlangıç ​​ve terminal noktaları. Kaynak ve lavabo aynı tepe ise

düzenleme

, elde edilen alt-grafik bir çevrimi ihtiva edecektir. Bu kodları tespit etmek ve kaldırmak için mevcut kod mevcuttur. .

bir diyagram 1000 kelimeye bedeldir Bu durumda

sonu Düzenleme, basit bir grafik hazırlanan ettik renkli köşe kritik köşeleri temsil eder ve noktalı çizgiler grafiğin bölümlerdir. Bu durumda

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

, niyet arasındaki olası bölümleri bulmaktır 1-1, 1-3, 1-7, 3-1, 3-3, 3-7, 7-1, 7-3 veya 7-7. Sadece bölüm 1-3, 3-3 ve 3-7 aslında var (aşağıdaki resme bakınız). Ayrıca, 3-3 bölümü geçersiz olduğundan, grafik inconsistancy'yi kaldırmak için yeniden etiketlendi.

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

Eğer yardımı olacaksa, ileri ve geri grafik geçişleri bir dizi gerçekleştirerek benim python-eque psuedocode çalışmaları mümkün, tüm bölümleri tanımlamak için.

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

cuts between connected components'u bulmaya çalışıyorsunuz.