Efektywny algorytm łączenia dwóch DAGów

Question

Mam dwa ważone DAG (skierowane acykliczne wykresy) i muszę je połączyć w jeden, więc mogę uzyskać zamówienie topologiczne (w niektórych przypadkach może to być więcej niż dwa). Problem polega na tym, że wykresy są acykliczne, ale mogą tworzyć razem cykl. Ponadto wykresy są duże (100k + węzły, 500k + krawędzie). Czy istnieje sprytny sposób na scalenie wykresów? Równie dobry byłby algorytm przechodzenia przez wszystkie wykresy "naraz".

Edycja:

Przez „scalania” to znaczy, łącząc wszystkie krawędzie i wierzchołki obydwu wykresów sobą (zachowaniu grubości oczywiście), o ile nie tworzą one cykli. Jeśli krawędź już istnieje, chcę użyć większej wagi.

Pomysł polega na tym, że rozpoczynanie od dwóch acyklicznych wykresów powinno dawać przewagę nad po prostu "naprawianiem" wyniku później (wymagałoby to znalezienia zestawu łuków zwrotnych, który jest NP trudny, więc chciałem tego uniknąć).

Dziękujemy za sugestie.

Answer 1

Zakładając wierzchołki są takie same dla obu wykresach jeśli nie, prostu uważają

V = V1 U V1 

Załóżmy, że masz listę sąsiedztwa. Teraz dla każdego wierzchołka v w V1 i V2 możesz sortować listę przyległości według wierzchołka, do którego prowadzi krawędź (jeśli jest to para (wierzchołek, waga), sortuj według wierzchołka). To nie powinno być tak drogie, ponieważ wykres jest mały i będzie to summation degree(v)*log(degree(v)), które nie powinno być takie złe.

Po tym można wykonać iterację dla wszystkich wierzchołków v w V1 i V2, a także scalić sortowane listy v w V1 i V2. Jest to podobne do znalezienia unii dwóch uporządkowanych tablic za pomocą sortowania scalonego, tyle że tam, gdzie znajdziesz element występujący w obu, możesz wybrać większy brzeg.

Answer 2

Jednym z problemów jest to, że może istnieć więcej niż jedno rozwiązanie.

Rozważmy na przykład DAGy {(a, b), (a, c)} i {(b, a), (b, c)}. Można "łączą się" są dwoma różnymi sposobami:

1. {(a, b), (A, C), (B, C)}
2. {(a, c), (B, A), (b, c)}

Liczba rozwiązań rośnie kombinacyjnie z liczbą cykli w połączeniu dwóch wykresów, więc dla dużych wykresów prawdopodobnie istnieje ogromna liczba sposobów, w jakie można "scalić" " im.

Czy masz jakieś kryterium, które może pomóc ci zdecydować, który DAG jest "lepszy" od drugiego?

Answer 3

Miałem podobny problem rozwiązałem tak:

przerabiałem mój DAG na mapie z mapą węzłów (zamocowanej przez węzeł id, wartość zbiór węzłów, prawdopodobnie jeden na start) oraz mapa krawędzi (kluczowana według źródła, pary docelowej, wartość to zbiór krawędzi, prawdopodobnie początek). Nazwałam to normalizacją. Pierwotny wykres był zbiorem "korzeni" każdego węzła miał kolekcję dzieci

Mogłem następnie połączyć dwa z nich razem, łącząc węzły kluczem i krawędziami za pomocą klucza. to znaczy: jeśli węzeł istniał, to przekaż nowy węzeł do istniejącej wartości węzła, jeśli węzeł nie istnieje, dodaj go. to samo z krawędziami.

To działało całkiem czysto, ale nie uniknęło cykli.

Oto kod (clojure), które użyłem:

(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 {}))})