algorithm - que - ordenamientos recursivos

Algoritmo eficiente para fusionar dos DAG

Question

Tengo dos DAG ponderados (gráficos acíclicos dirigidos) y necesito fusionarlos en uno, para poder obtener un orden topológico (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 alguna forma inteligente de fusionar los gráficos? Igualmente bueno sería un algoritmo para recorrer todos los gráficos "a la vez".

Editar:

Con "fusionar" me refiero a combinar todos los bordes y vértices de ambos gráficos (preservando los pesos, por supuesto), si 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 tus sugerencias.

Answer 1

Suponiendo que los vértices son los mismos para ambos gráficos, de lo contrario, solo considere

V = V1 U V1

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

Después de esto, puede iterar para todos los vértices v en V1 y V2, y hacer un tipo de combinación de las listas de adyacencia de v en V1 y V2. Esto es similar a encontrar la unión de 2 matrices ordenadas mediante el tipo de combinación, solo que cuando encuentre un elemento en ambos, puede elegir el borde más grande.

Answer 2

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

Considere, por ejemplo, los DAG {(a, b), (a, c)} y {(b, a), (b, c)}. Puedes "fusionar" estos de dos maneras diferentes:

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

El número de soluciones crece combinatoriamente con el número de ciclos en la unión de los dos gráficos, por lo que para sus gráficos grandes hay probablemente una gran cantidad de maneras de "fusionarlos".

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

Answer 3

Tuve un problema similar que resolví así:

Transformé mi DAG en un mapa con un mapa de nodos (codificado por ID de nodo, valor una colección de nodos, probablemente uno para comenzar) y un 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 era una colección de "raíces", cada nodo tenía una colección de niños

Podría fusionar dos de estos juntos fusionando nodos por clave y bordes por clave. 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 {}))})