JGraphT: Replacing subtree in a directed acyclic graph by another subtree

Question

Let's assume I have the following two tree graphs:

     a                               i
   /    \                          /    \
  b      c                        j      k
 / \    / \                      / \    / \
d   e  f   g                    l   m  n   o

And I need to extract the subgraph b from the first graph and replace it in the second graph like this:

     i
   /    \
  j      b
 / \    / \
l   m  d   e

Is there any existing API in JGraphT to allow this?

Answer 1

The following answer is based on the following assumptions:

• both input graphs, g1 and g2 are acyclic directed graphs (trees)
• you want to replace a subtree in g2 by a subtree in g1
• both g1 and g2 are vertex and edge disjoint, that is a vertex (edge) in g1 does not appear in g2 and vice versa.

JGraphT does not have a built-in method for subtree replacements, but it would be fairly simple to implement such method:

/**
* Replaces the subtree rooted in root2 in graph g2 with the subtree rooted in root1 in graph g1. Graph g1 is left
* unchanged.
* @param g1 first graph
* @param g2 second graph
* @param root1 root of subtree in first graph
* @param root2 root of subtree in second graph
* @param <V> vertex type
* @param <E> edge type
*/
public static <V,E> void replaceSubtree(Graph<V, E> g1, Graph<V, E> g2, V root1, V root2){
    //1. Add subtree under root1 to graph g2 as a disconnected component
    BreadthFirstIterator<V, E> bfs = new BreadthFirstIterator<>(g1,root1);
    g2.addVertex(bfs.next());
    while (bfs.hasNext()){
        V vertex=bfs.next();
        V parent=bfs.getParent(vertex);
        g2.addVertex(vertex);
        g2.addEdge(parent,vertex,bfs.getSpanningTreeEdge(vertex));
    }

    //2. Get the edge (object) between root2 and its parent. A special case occurs if root2 is also the root of g2
    // in which case it does not have a parent.
    E treeEdge = (g2.incomingEdgesOf(root2).isEmpty() ? null : g2.incomingEdgesOf(root2).iterator().next());
    V parent= (treeEdge == null ? null : Graphs.getOppositeVertex(g2, treeEdge, root2));

    //3. Remove subtree rooted in vertex k
    bfs = new BreadthFirstIterator<>(g2,root2);
    while(bfs.hasNext())
        g2.removeVertex(bfs.next());

    //4. Reconnect the two components
    if(parent != null)
        g2.addEdge(parent, root1, treeEdge);
}

Here's some test code:

public static void main(String[] args){
    Graph<String, DefaultEdge> g1 = new SimpleDirectedGraph<>(DefaultEdge.class);
    Graphs.addAllVertices(g1, Arrays.asList("a", "b", "c", "d", "e", "f", "g"));
    g1.addEdge("a", "b");
    g1.addEdge("a", "c");
    g1.addEdge("b", "d");
    g1.addEdge("b", "e");
    g1.addEdge("c", "f");
    g1.addEdge("c", "g");

    Graph<String, DefaultEdge> g2 = new SimpleDirectedGraph<>(DefaultEdge.class);
    Graphs.addAllVertices(g2, Arrays.asList("i", "j", "k", "l", "m", "n", "o"));
    g2.addEdge("i", "j");
    g2.addEdge("i", "k");
    g2.addEdge("j", "l");
    g2.addEdge("j", "m");
    g2.addEdge("k", "n");
    g2.addEdge("k", "o");

    replaceSubtree(g1, g2, "b", "k");

    System.out.println(g2);
}

• replaceSubtree(g1, g2, "b", "k"); gives: ([i, j, l, m, b, d, e], [(i,j), (j,l), (j,m), (b,d), (b,e), (i,b)])
• replaceSubtree(g1, g2, "b", "i"); gives: ([b, d, e], [(b,d), (b,e)])