algoritmo eficiente para la fusión de dos DAG

Question

tengo dos DAG ponderados (dirigidos acíclicos gráficos) y la necesidad de fusionar en uno, por lo que puedo conseguir un ordenamiento topológico (que podría ser más de dos en algunos casos). El problema es que los gráficos son acíclicos cada uno, pero pueden formar un ciclo juntos. Además, los gráficos son grandes (100k + nodos, 500k + bordes). ¿Hay una forma inteligente de combinar los gráficos? Igualmente bueno sería un algoritmo para recorrer todos los gráficos "a la vez".

Editar:

Por "combinación" me refiero a la combinación de todos los bordes y vértices de ambos gráficos juntos (preservación de pesos de curso), si es que no crean ciclos. Si un borde ya existe, quiero usar el mayor peso para él.

La idea es que comenzar con dos gráficos acíclicos debería dar una ventaja sobre simplemente "arreglar" el resultado después (esto implicaría encontrar el conjunto de arco de retroalimentación que es NP difícil así que quería evitar eso).

Gracias por sus sugerencias.

Answer 1

Suponiendo que los vértices son los mismos tanto para los gráficos si no, simplemente consideran

V = V1 U V1 

supongamos que usted tiene una lista de adyacencia. Ahora, para cada vértice v en V1 y V2, puede ordenar la lista de adyacencia por el vértice del borde conduce a (si es (vértice, peso) par, ordenar por vértice). Esto no debería ser tan caro ya que la gráfica es pequeña, y sería summation degree(v)*log(degree(v)) que no debe ser tan malo.

Después de esto se puede repetir para todos los vértices v en V1 y V2, y hacer una especie de combinación de las listas de adyacencia de v en V1 y V2. Esto es similar a la búsqueda de la unión de 2 arrays ordenados usando ordenamiento por mezcla, solo que donde encontrará un elemento que ocurre en ambos se puede elegir el borde más grande.

Answer 2

Un problema es que no puede haber más de una solución.

Considérese por ejemplo el DAG {(a, b), (a, c)} y {(b, a), (b, c)}. Puede "fusionar" éstos de dos maneras diferentes:

1. {(a, b), (a, c), (b, c)}
2. {(a, c), (b, a), (b, c)}

el número de soluciones crece de forma combinatoria con el número de ciclos en la unión de los dos gráficos, por lo que para sus grandes gráficos es probable que haya un gran número de maneras en que puede "fusionar " ellos.

¿Tiene un criterio que podría ayudar a decidir qué DAG es "mejor" que otro?

Answer 3

que tenía un problema similar que he resuelto de este modo:

transformé mi DAG en un mapa con un mapa de nodos (introducido por el ID de nodo, el valor de una colección de nodos, probablemente, uno para empezar) y una mapa de bordes (codificado por fuente, par de destino, valor es una colección de bordes, probablemente uno para comenzar). Llamé a esto normalizar. El gráfico original de una colección de "raíces" cada nodo tenía una colección de los niños

Entonces podría fusionar dos de ellos juntos mediante la fusión de los nodos y los bordes de la tecla por tecla. es decir: si un nodo existía, entonces contra el nuevo nodo para el valor del nodo existente, si un nodo no existe, entonces agréguelo. lo mismo con los bordes.

Esto funcionó bastante limpio, pero no evitó los ciclos.

Aquí hay un código (clojure) que utilicé:

(def empty-graph 
    {:nodes {} 
    :edges {}}) 

(defn merge-graphs 
    [a b] 
    {:nodes (merge-with concat (get a :nodes) (get b :nodes)) 
    :edges (merge-with concat (get a :edges) (get b :edges))}) 

(defn normalize-graph 
    [graph] 
    {:nodes (->> 
      graph 
      (mapcat 
       (fn [root] 
       (->> 
        root 
        (tree-seq (fn [_] true) (fn [node] (get node :children))) 
        (mapcat 
        (fn [edge] 
         (concat 
         (if-let [source (get edge "source")] 
          [[source [source]]] 
          []) 
         (if-let [target (get edge "target")] 
          [[target [target]]] 
          []))))))) 
      (into {})) 
    :edges (->> 
      graph 
      (mapcat 
       (fn [root] 
       (->> 
        root 
        (tree-seq (fn [_] true) (fn [node] (get node :children))) 
        (filter (fn [edge] (and (not (nil? (get edge "source"))) (not (nil? (get edge "target")))))) ;this sucks but is necessary 
        (map 
        (fn [edge] 
         (let [compact (dissoc edge :children)] 
         [[(get edge "source") (get edge "target")] [compact]])))))) 
      (into {}))})