Buscando algoritmo para invertir (?? Revertir espejo de vuelta de dentro a fuera) un DAG

Question

Busco un algoritmo para "invertir" (?? Revertir vuelta de dentro a fuera) un DAG:

 A*  # I can't ascii-art the arrows, so just 
    /\  # pretend the slashes are all pointing 
    B C  # "down" (south-east or south-west) 
    //\ # e.g. 
    G E D # A -> (B -> G, C -> (E -> F, D -> F)) 
     \/
     F 

La representación que estoy usando es inmutable verdaderamente un DAG (no hay punteros "parentales"). Me gustaría recorrer el gráfico de alguna manera mientras construyo un gráfico de "imagen espejo" con nodos equivalentes, pero con la dirección de las relaciones entre los nodos invertidos.

  F* 
     /\ 
    G* E D # F -> (E -> C -> A, D -> C -> A), G -> B -> A 
    \ \/ # 
    B C  # Again, arrows point "down" 
     \/ # 
     A  # 

Entonces la entrada es un conjunto de "raíces" (aquí, {A}). La salida debe ser un conjunto de "raíces" en el gráfico de resultados: {G, F}. (Por raíz me refiero a un nodo sin referencias entrantes. Una hoja es un nodo sin referencias salientes.)

Las raíces de la entrada se convierten en las hojas de la salida y la visa versa. La transformación debería ser un inverso de sí mismo.

(Para los curiosos, me gustaría añadir una característica a una biblioteca que estoy usando para represento XML para la consulta estructural por el cual puedo mapear cada nodo en el primer árbol su "imagen en espejo" en el el segundo árbol (y de vuelta otra vez) para proporcionar más flexibilidad de navegación para mis reglas de consulta.)

Answer 1

Recorre el gráfico construyendo un conjunto de bordes invertidos y una lista de nodos hoja.

Realice una clasificación topológica de los bordes invertidos utilizando los nodos de hoja (que ahora son raíz) para comenzar.

Construya el gráfico invertido basándose en los bordes invertidos empezando por el final de la lista ordenada. Como los nodos se construyen en orden topológico inverso, se garantiza que se han construido los elementos secundarios de un nodo determinado antes de construir el nodo, por lo que es posible crear una representación inmutable.

Esto es O (N) si usa estructuras para su representación intermedia que rastrean todos los enlaces en ambas direcciones asociadas con un nodo, o O (NlnN) si usa clasificación para encontrar todos los enlaces de un nodo. Para gráficos pequeños, o idiomas que no sufren desbordamientos de pila, puede simplemente construir el gráfico perezosamente en lugar de realizar explícitamente el tipo topológico. Entonces, depende un poco de lo que está implementando todo en lo diferente que esto sería.

A -> (B -> G, C -> (E -> F, D -> F)) 

original roots: [ A ] 
original links: [ AB, BG, AC, CE, EF, CD, DF ] 
reversed links: [ BA, GB, CA, EC, FE, DC, FD ] 
reversed roots: [ G, F ] 
reversed links: [ BA, CA, DC, EC, FE, FD, GB ] (in order of source) 
topologically sorted: [ G, B, F, E, D, C, A ] 
construction order : A, C->A, D->C, E->C, F->(D,E), B->A, G->B 

Answer 2

Depth-first search podría generar lo que está buscando: Observe su ruta a través del árbol y cada vez que atraviese agregue el reverso al DAG resultante (las hojas son raíces).

Answer 3

Simplemente haga una búsqueda de profundidad marcando donde ya ha estado, y cada vez que atraviesa una flecha agrega el reverso a su resultado DAG. Agrega las hojas como raíces.

Answer 4

Mi sugerencia intuitiva sería realizar un cruce de profundidad primero de su gráfico, y construir su gráfico duplicado simultáneamente.

Al atravesar cada nodo, cree un nuevo nodo en el gráfico reflejado y cree un borde entre él y su predecesor en el nuevo gráfico.

Si en algún momento llega a un nodo que no tiene hijos, márquelo como raíz.

Answer 5

Resolví esto con un simple recorrido de gráfico. Tenga en cuenta que la clasificación topológica solo será útil para gráficos acíclicos dirigidos.

Utilicé una lista de adyacencia, pero puede hacer algo similar con una matriz de adyacencia.

En Python que se parece a esto:

# Basic Graph Structure 
g = {} 
g[vertex] = [v1, v2, v3] # Each vertex contains a lists of its edges 

permite encontrar todos los bordes de v, a continuación, recorrer la lista g [v] y que le dará todas (v, u) bordes.

para construir el gráfico invertido crea un nuevo diccionario y construir algo como esto:

reversed = {} 
    for v in g: 
     for e in g[v]: 
      if e not in reversed: 
       reversed[e] = [] 
      reversed[e].append(v) 

Esto es muy intensivo de memoria para grandes gráficos (duplicando el uso de memoria), pero es una manera muy fácil trabaja con ellos y bastante rápido. Puede haber soluciones más inteligentes que involucren la construcción de un generador y el uso de un algoritmo dfs de algún tipo, pero no he pensado mucho en ello.