Эффективный алгоритм объединения двух DAG

Question

У меня есть два взвешенных DAG (направленных ациклических графа), и мне нужно объединить их в один, чтобы я мог получить топологический порядок (в некоторых случаях он может быть больше двух).Проблема в том, что каждый график ацикличен, но может образовывать цикл вместе.Кроме того, графики большие (100 тыс. + Узлов, 500 тыс. + Ребер).Есть ли умный способ объединить графики?Не менее хорошим будет алгоритм для обхода всех графов «сразу».

Редактировать:

Под «объединением» я подразумеваю объединение всех ребер и вершин обоих графов вместе (конечно, сохраняя веса), если они не создают циклы.Если ребро уже существует, я хочу использовать для него больший вес.

Идея состоит в том, что начинание с двух ациклических графов должно дать преимущество по сравнению с простым «исправлением» результата впоследствии (это подразумевает поиск обратной связи).набор дуг, который NP труден, поэтому я хотел избежать этого).

Спасибо за ваши предложения.

Answer 1

Одна проблема заключается в том, что может быть более одного решения.

Рассмотрим, например, группы обеспечения доступности баз данных {(a, b), (a, c)} и {(b, a), (b, в)}.Вы можете «объединить» их двумя различными способами:

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

Количество решений растет комбинаторно с числом циклов в объединении двух графов, поэтому для ваших больших графов, вероятно, существуетогромное количество способов их объединения.

Есть ли у вас критерий, который поможет вам решить, какой DAG "лучше", чем другой?

Answer 2

У меня была похожая проблема, которую я решил следующим образом:

Я преобразовал свою группу обеспечения доступности баз данных в карту с картой узлов (с ключом по идентификатору узла, значением набора узлов, вероятно, одного из них для запуска)карта ребер (с указанием источника, целевой пары, значение - это набор ребер, вероятно, один из них для начала).Я назвал это нормализацией.Исходный граф представлял собой коллекцию «корней», каждый узел имел коллекцию дочерних элементов

. Затем я мог объединить два из них, объединяя узлы по ключу и ребра по ключу.То есть: если узел существовал, то объединяет новый узел со значением существующего узла, если узел не существует, то добавьте его.то же самое с краями.

Это сработало довольно чисто, но не избежало циклов.

Вот код (clojure), который я использовал:

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

Answer 3

Предполагая, что вершины одинаковы для обоих графиков, если нет, просто подумай

V = V1 U V1

Предположим, у вас есть список смежности. Теперь для каждой вершины v в V1 и V2 вы можете отсортировать список смежности по вершине, к которой ведет ребро (если это пара (вершина, вес), сортировка по вершине). Это не должно быть так дорого, так как график маленький, и это будет summation degree(v)*log(degree(v)), что не должно быть так плохо.

После этого вы можете выполнить итерацию для всех вершин v в V1 и V2 и выполнить сортировку списков смежности для v в V1 и V2. Это похоже на поиск объединения 2-х отсортированных массивов с использованием сортировки слиянием, только в том случае, когда вы найдете элемент, встречающийся в обоих, вы можете выбрать большее ребро.