typescript - 将两个有向(可能是循环)图合并为一个

Question

在我的项目中，我将给定的移动应用程序表示为有向图。移动应用程序的每个屏幕都充当图形节点和从一个屏幕到下一个屏幕的边链接。边缘存储在每个父屏幕内。还使用深度优先搜索将每条边分类为 TREE、FORWARD、CROSS 或 BACK 边。现在一切正常。

我的问题是我需要将两个图合并为一个图。这两个图可能代表移动应用程序的不同构建。一个版本可能有以下链:

Screen#1 -> Screen#2 -> Screen#3

下一个版本可能有如下链:

Screen#1 -> Screen#X -> Screen#2 -> Screen#3

我需要能够合并这两个图以得到下图:

Screen#1 -> Screen#X -+
         |            |
         +------------> Screen#2 -> Screen#3

我可以测试每个节点与其他每个节点是否相等。但我似乎无法设计出一种算法来将这两个图合并为一个。

我在 Internet 上浏览了很多次，但一直找不到关于如何合并图形的站点、讲座或研究论文。我当前的实现(非常有问题)是这样的:

1. Identify all nodes in graph A that also exist in graph B (S#1, S#2, S#3)
2. Copy all of these nodes in the final tree..
3. For each of these common nodes, recursively explore their children..
4. If the child exists in the resultant tree, add an edge between the parent and the child. Otherwise, add the child and an edge between the parent and child and repeat the algorithm on the child itself.
5. Do this till there are no unvisited nodes left.

有人可以指出我在合并这些图表时应该采用什么方法的正确方向吗？请注意，这两个图可能是循环的。

谢谢，阿西姆

Answer 1

因为您还没有发布 Minimal, Complete, and Verifiable example ，这里的答案可能不完全适合您的用例。希望您无论如何都能利用它:

---

我建议您将图形表示为一组节点数据，其节点由字符串标签标识，同时还有一组节点标签对来表示边。像这样:

// T represents the data type, K represents the union of node labels
class Graph<K extends string, T> {
  nodes: Record<K, T>; 
  edges: Array<{ start: K, end: K }>;

  constructor(nodes: Record<K, T>, edges: Array<{ start: K, end: K }>) {
    this.nodes = Object.assign({}, nodes);
    this.edges = edges.slice();
  }
}

// graphOne is a Graph<"a"|"b"|"c", string>
const graphOne = new Graph(
  {
    a: "NodeA", b: "NodeB", c: "NodeC"
  }, [
    { start: "a", end: "b" },
    { start: "b", end: "c" }
  ]
);

在上面，graphOne 是一个简单的图，具有三个标记为 "a"、"b" 和 "的节点c"，从 "a" 到 "b" 以及从 "b" 到 “c”。在这种情况下，存储在每个节点中的数据只是一个字符串。在这里，让我们为 Graph 类创建一个简单的控制台日志记录方法:

  print() {
    console.log(this.nodes)
    console.log(this.edges.map(e => e.start + "➡" + e.end));
  }

并使用它:

graphOne.print();
// Object { a: "NodeA", b: "NodeB", c: "NodeC" }
// Array [ "a➡b", "b➡c" ]

---

在这一点上，您可能会反对这种表示并不能自然地表达您如何使用图形，其中每个节点都有数据和一些子节点，并且您可以通过递归遍历子节点来遍历图形(并且可能陷入循环)等。也就是说，您可能会想到这样的事情:

interface TraversableGraph<T> {
  nodes: Array<TraversableNode<T>>;
}
interface TraversableNode<T> {
  data: T,
  children: Array<TraversableNode<T>>;
}

幸运的是，您可以相当轻松地将 Graph 转换为 TraversableGraph。这是一种方法。让我们向 Graph 添加一个 asTraversableGraph() 方法:

  asTraversableGraph(): TraversableGraph<T> {
    return {
      nodes: (Object.keys(this.nodes) as K[]).map(
        k => this.asTraverableNode(k))
    };
  }

  private asTraverableNode(k: K): TraversableNode<T> {
    const graph = this;
    return {
      get data() {
        return graph.nodes[k];
      },
      get children() {
        return graph.edges.filter(e => e.start === k).map(
          e => graph.asTraverableNode(e.end));
      }
    }
  }

我选择使用 getters这样可遍历图将(可能，也许)反射(reflect)图的变化(例如，您向 Graph 添加一条新边，并且 TraversableGraph 也将具有该新边如果你穿过它，就进入它的边缘)。但您不必那样做。

让我们确保它的行为合理:

graphOne.asTraversableGraph().nodes[0].data; // "NodeA"
graphOne.asTraversableGraph().nodes[0].children[0].data; // "NodeB"

---

现在我们终于可以合并了。使用 Graph 表示，这不再是一些奇怪的毛茸茸的/循环的/递归的东西。您只需合并节点并合并边缘，然后回家。这是一种可能的方法，通过向 Graph 添加 merge() 方法:

  merge<L extends string, U, V>(
    otherGraph: Graph<L, U>, 
    dataMerge: (x: T | undefined, y: U | undefined) => V
  ): Graph<K | L, V> {
    const thisGraph = this as Graph<K | L, T | undefined>;
    const thatGraph = otherGraph as Graph<K | L, U | undefined>;

    // merge nodes
    const nodes = {} as Record<K | L, V>;
    (Object.keys(thisGraph.nodes) as (K | L)[]).forEach(
      k => nodes[k] = dataMerge(thisGraph.nodes[k], thatGraph.nodes[k]));
    (Object.keys(thatGraph.nodes) as (K | L)[]).filter(k => !(k in nodes)).forEach(
      k => nodes[k] = dataMerge(thisGraph.nodes[k], thatGraph.nodes[k]));

    // merge edges
    const edges: Record<string, { start: K | L, end: K | L }> = {};
    thisGraph.edges.forEach(e => edges[JSON.stringify(e)] = e);
    thatGraph.edges.forEach(e => edges[JSON.stringify(e)] = e);

    return new Graph(nodes, Object.keys(edges).map(k => edges[k]));
  }

请注意，merge() 需要两个参数:另一个图和一个 dataMerge() 回调，其工作是合并来自第一个图上的节点的数据(如果它存在)与来自第二个图上相同标记节点的数据(如果它存在)并产生你想在合并图中看到的数据。

通过遍历每个图的节点列表并在每个图的相同标记节点上运行 dataMerge() 来合并节点。通过合并两个边列表并确保没有重复项来合并边(我通过在边上使用 JSON.stringify() 作为唯一键来实现)。

让我们通过引入另一个图看看它是否有效:

// graphTwo is a Graph<"b" | "c" | "d", string>
const graphTwo = new Graph(
  {
    b: "NodeB", c: "Node C", d: "NodeD"
  }, [
    { start: "b", end: "d" },
    { start: "b", end: "c" },
    { start: "d", end: "c" }
  ]
);

graphTwo.print();
// Object { b: "NodeB", c: "Node C", d: "NodeD" }
// Array(3) [ "b➡d", "b➡c", "d➡c" ]

并合并它，注意 dataMerge() 有点复杂，要处理 graphOne 中存储的字符串数据与 中存储的字符串数据之间可能发生的冲突图二:

// graphMerged is a Graph<"a" | "b" | "c" | "d", string>
const graphMerged = graphOne.merge(graphTwo,
  (x, y) => typeof x === 'undefined' ?
    (typeof y === 'undefined' ? "??" : y) :
    ((x === y || typeof y === 'undefined') ? x : x + "/" + y)
);

graphMerged.print();
// Object { a: "NodeA", b: "NodeB", c: "NodeC/Node C", d: "NodeD" }
// Array(4) [ "a➡b", "b➡c", "b➡d", "d➡c" ]

而且有效!尽管 graphOne 和 graphTwo 具有相同的边，但合并后的图只有一条 b➡c 边。标记为 c 的节点名称在 graphOne ("NodeC") 和 graphTwo ( "Node C")，所以 dataMerge() 加入了它们 ("NodeC/Node C")。

这是一个 Playground link以上所有代码。

---

希望对您有所帮助。祝你好运!