合并两个有向无环图的高效算法

Question

我有两个加权DAG（有向无环图），需要将它们合并为一个，以便获得一个拓扑排序（在某些情况下可能会超过两个）。问题在于，这些图各自都是无环的，但一起可能形成循环。此外，这些图很大（100k+节点，500k+边）。 有没有聪明的方法来合并这些图？同样好的方案是编写一种算法以“同时”遍历所有图。

编辑： 通过“合并”，我意味着将两个图的所有边和顶点组合在一起（当然要保留权重），如果它们不会创建循环。如果边已经存在，则要使用更大的权重。 这个想法是从两个无环图开始应该比之后简单地“修复”结果更有优势（这将意味着找到NP难的反馈弧集，因此我想避免那个）。 感谢您的建议。

- Thomas

---

"merge"在数学中指合并或融合。请更加数学化地解释这个概念。 - Armen Tsirunyan

感谢您的回答。我修改了问题以澄清。 - Thomas

当创建一个循环时，仍然不清楚该怎么做。 - wnoise

Answer 1

一个问题是可能存在不止一种解决方案。

例如考虑{(a,b),(a,c)}和{(b,a),(b,c)}这两个DAG，你可以用两种不同的方式进行“合并”:

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

随着这两个图中环的数量组合数增长，解决方案的数量呈指数级增长，因此在您的大型图中，您可能有很多“合并”它们的方法。

您是否有一个标准，可以帮助您决定哪个DAG比另一个更好？

- mitchus

Answer 2

假设两个图形的顶点相同，如果不同，请考虑。

V = V1 U V1

假设您有一个邻接表。现在对于V1和V2中的每个顶点v，您可以按照边所指向的顶点（如果是(vertex, weight)对，则按顶点排序）对邻接表进行排序。由于图很小，这不应该太昂贵，并且它将是summation degree(v)*log(degree(v))，这应该不会太糟糕。

之后，您可以迭代所有V1和V2中的顶点v，并对V1和V2中v的邻接列表执行归并排序。这类似于使用归并排序找到2个排序数组的并集，只是当您发现两个元素都存在时，可以选择更大的边缘。

- user513590

Answer 3

我曾经遇到过类似的问题，我是这样解决的：

我将我的DAG转换成了一个地图，其中包含节点地图（由节点ID键入，值为节点集合，可能是一个开始节点），以及边缘地图（由源、目标对键入，值为边缘集合，可能是一个开始边缘）。我称之为normalize。原始图形是一组“根”，每个节点都有一个子节点集合。

然后，我可以通过按键合并两个节点地图和边缘地图。即：如果节点存在，则将新节点连接到现有节点值中，如果节点不存在，则添加它。边缘也是如此。

这种方法非常简洁，但无法避免循环。

以下是我使用的一些代码（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 {}))})

- Brad