У меня есть две взвешенные DAG (направленные ациклические графы) и нужно объединить их в одну, поэтому я могу получить топологическое упорядочение (в некоторых случаях это может быть больше двух). Проблема состоит в том, что графики являются ациклическими, но могут образовывать цикл вместе. Кроме того, графики большие (100k + узлы, 500 k + ребра). Есть ли разумный способ слияния графиков? Столь же хорошим был бы алгоритм, который бы проходил все графики "сразу".
Edit:
Под "merge" я подразумеваю объединение всех ребер и вершин обоих графиков вместе (с сохранением веса, конечно), если они не создают циклы. Если край уже существует, я хочу использовать для него больший вес.
Идея состоит в том, что начало с двух ациклических графов должно дать преимущество перед просто "фиксацией" результата после этого (это означало бы найти набор дуги обратной связи, который является NP жестким, поэтому я хотел этого избежать).
Спасибо за ваши предложения.
Одна проблема заключается в том, что может быть несколько решений.
Рассмотрим, например, DAGs {(a, b), (a, c)} и {(b, a), (b, c)}. Вы можете "объединить" их двумя способами:
Число решений растет комбинаторно с числом циклов в объединении двух графиков, поэтому для ваших больших графиков существует, вероятно, огромное количество способов их "слить".
Есть ли у вас критерий, который может помочь вам решить, какая DAG "лучше", чем другая?
Предполагая, что вершины одинаковы для обоих графиков, если нет, просто рассмотрите
V = V1 U V1
Предположим, у вас есть список смежности. Теперь для каждой вершины v в V1 и V2 вы можете отсортировать список смежности по вершине, к которой ведет край (если она (вершина, вес), сортировать по вершине). Это не должно быть так дорого, так как график мал, и это будет summation degree(v)*log(degree(v)), что не должно быть так плохо.
После этого вы можете выполнять итерацию для всех вершин v в V1 и V2, а также сортировать список смежности v в V1 и V2. Это похоже на поиск объединения двух отсортированных массивов с использованием сортировки слияния, только там, где вы найдете элемент, встречающийся в обоих случаях, вы можете выбрать более крупный ребро.
У меня была аналогичная проблема, которую я решил так:
Я преобразовал свою DAG в карту с картой узлов (с ключом node id, значение коллекции узлов, возможно, один для запуска), а карта ребер (с ключом по источнику, целевая пара, значение - это сбор ребер, возможно, один для начала). Я назвал это нормализацией. Исходным графом была коллекция "корней", каждая из которых node имела набор детей
Затем я мог бы объединить два из них, объединив узлы по ключам и кромкам по клавишам. т.е.: если существовал node, то новый node соответствует существующему значению node, если node не существует, а затем добавьте его. то же самое с краями.
Это работало довольно чисто, но не избегало циклов.
Вот какой код (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 {}))})