Merging two directed (possibly cyclic) graphs into one

Question

In my project, I am representing a given mobile application as a directed graph. Each screen of the mobile application serves as a graph node and an edge links from one screen to the next. The edges are stored inside each parent screen. Each edge is also classified as either a TREE, FORWARD, CROSS or BACK edge using Depth First Search. All this is working fine right now.

My problem is that I need to merge two graphs into a single graph. The two graphs might represent a different build of the mobile application. One version may have the following chain:

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

The next version may have the following chain:

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

I need to be able to merge these two graphs to end up with the following graph:

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

I can test for equality of each node with every other node. But I can't seem to be able to devise an algorithm that would allow me to merge these two graphs into one.

I have looked around the internet quite a lot but have been unable to find a single site or lecture or research paper on how to merge graphs. My current implementation (very buggy) goes like so:

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.

Can someone point me in the right direction as to what should be my approach in merging these graphs? Please note that the two graphs might be cyclic.

Thanks, Asim

Answer 1

Since you haven't posted a Minimal, Complete, and Verifiable example, the answer here might not fit your use case exactly. Hopefully you can make use of it anyway:

---

I would suggest that you represent your graph as a set of node data whose nodes are identified by string labels, alongside an array of pairs of node labels to represent the edges. Something like this:

// 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" }
  ]
);

In the above, graphOne is a simple graph with three nodes labeled "a", "b", and "c", with a single path going through them from "a" to "b" and from "b" to "c". The data stored in each node in this case is just a string. Here, let's create a simple console logging method to the Graph class:

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

and use it:

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

---

At this point you might object that this representation doesn't naturally express how you use a graph, where each node has data and some children, and you can traverse the graph by recursively iterating through children (and maybe get caught in a loop), etc. That is, you might be thinking of something like this instead:

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

Luckily you can fairly easily convert a Graph to a TraversableGraph. Here's one way to do it. Let's add a asTraversableGraph() method to Graph:

  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));
      }
    }
  }

I opted to use getters so that the traversable graph would (possibly, maybe) reflect mutations of the graph (e.g., you add a new edge to the Graph, and the TraversableGraph would also have that new edge in it if you walk through it). But you don't have to do that.

Let's make sure it behaves reasonably:

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

---

Finally now we get to the merging. With the Graph representation, this is no longer some weird hairy/loopy/recursive thing. You just merge the nodes and merge the edges and then go home. Here's one possible way to do it, by adding a merge() method to Graph:

  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]));
  }

Note that merge() needs two parameters: the other graph, and a dataMerge() callback whose job is to merge the data from a node on the first graph (if it exists) with the data from the same-labeled node on the second graph (if it exists) and produce the data you want to see in the merged graph.

Nodes are merged by walking though the node list of each graph and running dataMerge() on the same-labeled node from each. Edges are merged by just merging the two edge lists and making sure there are no duplicates (I do it by using JSON.stringify() on the edge as a unique key).

Let's see if it works by introducing another graph:

// 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" ]

And merge it, noting that the dataMerge() is a bit complicated to deal with possible conflicts between the string data stored in graphOne and that stored in graphTwo:

// 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" ]

And it works! The merged graph has a single b➡c edge even though both graphOne and graphTwo have the same edge. And the name of the node labeled c was not the same in graphOne ("NodeC") and graphTwo ("Node C"), so dataMerge() joined them ("NodeC/Node C").

Here's a Playground link to all the code above.

---

Hope that helps. Good luck!