java - JGraphT:用另一个子树替换有向无环图中的子树

Question

假设我有以下两个树形图:

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

我需要从第一个图中提取子图 b 并将其替换到第二个图中，如下所示:

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

JGraphT 中是否有任何现有的 API 允许这样做？

Answer 1

以下答案基于以下假设:

• 两个输入图，g1 和 g2 都是非循环有向图(树)
• 您想要用 g1 中的子树替换 g2 中的子树
• g1 和 g2 都是顶点和边不相交的，即 g1 中的顶点(边)不会出现在 中g2，反之亦然。

JGraphT 没有用于子树替换的内置方法，但实现这种方法相当简单:

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

这是一些测试代码:

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"); 给出: ([i, j, l, m, b, d, e], [(i ,j), (j,l), (j,m), (b,d), (b,e), (i,b)])
• replaceSubtree(g1, g2, "b", "i"); 给出: ([b, d, e], [(b,d), (b,e )])