Partición de un grafo dirigido

Question

Estoy tratando de dividir una red en una o más partes en función de un conjunto de vértices críticos. Tengo un código que creo que resuelve mi problema (al menos, para los casos que me interesan), pero para garantizar la corrección en general, estoy buscando el nombre de lo que estoy haciendo desde la teoría de grafos, o incluso una referencia en un algoritmo o proceso equivalente.

La red de entrada es un gráfico dirigido con un único vértice fuente y sumidero. Las particiones resultantes deben tener la misma propiedad que el original (gráficos dirigidos, vértice de origen único, vértice de un único receptor), con el requisito adicional de que cada partición solo debe tener dos vértices que están en el conjunto crítico, y deben ser la inicial y vértices terminales

Editar

Si la fuente y el sumidero son el mismo vértice, la resultante sub-gráfico contendría una ciclo. El código existente está disponible para detectar y eliminar dichos ciclos. .

Fin Editar

En este caso, un diagrama vale 1000 palabras, he elaborado un gráfico sencillo, los vértices de colores representan los vértices críticos, y las líneas de puntos son las particiones de la gráfica.

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

En este caso, la intención es encontrar las particiones posibles entre 1-1, 1-3, 1-7, 3-1, 3-3, 3-7, 7-1, 7-3 o 7-7. Solo existen las particiones 1-3, 3-3 y 3-7 (ver imagen a continuación). Además, como la partición 3-3 no es válida, el gráfico se ha vuelto a etiquetar para eliminar la inconsistencia.

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

Si ayuda, mis obras psuedocode pitón-eque mediante la realización de una serie de recorridos gráfico de avance y retroceso para identificar todas las posibles particiones.

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

Creo que estás tratando de encontrar cuts between connected components.