12

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

编辑：

“合并”是指将两个图的所有边和顶点组合在一起（当然保留权重），如果它们不创建循环的话。如果边缘已经存在，我想为它使用更大的权重。

这个想法是，从两个无环图开始应该比之后简单地“修复”结果更有优势（这意味着要找到 NP 困难的反馈弧集，所以我想避免这种情况）。

谢谢你的建议。

4

3 回答 3

2

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

例如考虑 DAG {(a,b),(a,c)} 和 {(b,a),(b,c)}。您可以通过两种不同的方式“合并”它们：

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

解决方案的数量与两个图联合中的循环数组合增长，因此对于您的大图，您可能有很多方法可以“合并”它们。

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

于 2011-04-28T15:20:35.753 回答
0

假设两个图的顶点相同，如果不是，只需考虑

V = V1 U V1

让我们假设你有一个邻接列表。现在，对于 V1 和 V2 中的每个顶点 v，您可以按边缘通向的顶点对邻接列表进行排序（如果是 (vertex, weight) 对，则按顶点排序）。这不应该那么昂贵，因为图表很小，而且summation degree(v)*log(degree(v))不应该那么糟糕。

在此之后，您可以迭代 V1 和 V2 中的所有顶点 v，并对 V1 和 V2 中的 v 的邻接列表进行合并排序。这类似于使用归并排序查找 2 个已排序数组的并集，只是在两个都出现的元素中，您可以选择较大的边。

于 2010-12-31T20:05:48.313 回答
0

我有一个类似的问题，我像这样解决了：

我将我的 DAG 转换为带有节点图（以节点 ID 为键，值是节点集合，可能是一个开始）和边图（以源、目标对为键，值是边的集合，可能一个开始）。我称之为规范化。原始图是“根”的集合，每个节点都有一个子节点的集合

然后我可以通过按键合并节点和按键合并其中的两个。即：如果节点确实存在，则将新节点转换为现有节点值，如果节点不存在，则添加它。与边缘相同。

这工作得非常干净，但它并没有避免循环。

这是我使用的一些代码（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 {}))})
于 2017-04-04T20:30:50.433 回答