jGraphT

Question

我是图表的新手，目前正在摆弄 JGraphT。我有一个简单的图形，我想在其中删除某个顶点。删除完全没有问题，但我需要重新连接与删除的顶点相连的所有顶点。请参阅此示例图：

    SimpleDirectedGraph<String, DefaultEdge> g = new SimpleDirectedGraph<>(DefaultEdge.class);
    g.addVertex("Level 1");
    g.addVertex("Level 2.1");
    g.addVertex("Level 2.2");
    g.addVertex("Level 3.1");
    g.addVertex("Level 3.2");
    g.addVertex("Level 3.3");
    g.addVertex("Level 3.4");

    g.addEdge("Level 1", "Level 2.1");
    g.addEdge("Level 1", "Level 2.2");

    g.addEdge("Level 2.1", "Level 3.1");
    g.addEdge("Level 2.1", "Level 3.2");
    g.addEdge("Level 2.1", "Level 3.3");

    g.addEdge("Level 2.2", "Level 3.4");

如何删除顶点“2.1 级”并将级别 3 的顶点与级别 1 的顶点重新连接。我当然可以自己实现一些东西。但我认为 JGraphT 将提供一种更方便的方式来做到这一点。最后，我想以一种简单的方式将提到的图形转换为这个图形。（我的实际用例要复杂得多）

        SimpleDirectedGraph<String, DefaultEdge> g = new SimpleDirectedGraph<>(DefaultEdge.class);
        g.addVertex("Level 1");
        g.addVertex("Level 2.2");
        g.addVertex("Level 3.1");
        g.addVertex("Level 3.2");
        g.addVertex("Level 3.3");
        g.addVertex("Level 3.4");

        g.addEdge("Level 1", "Level 2.2");
        g.addEdge("Level 1", "Level 3.1");
        g.addEdge("Level 1", "Level 3.2");
        g.addEdge("Level 1", "Level 3.3");

        g.addEdge("Level 2.2", "Level 3.4");

我希望有人能给我正确的提示。提前致谢。

Answer 1

您作为输入提供的图形是树形图。一般程序是：

存储要删除的顶点的前驱顶点
存储要删除的顶点的后继顶点
删除顶点，并重新连接所有前驱到所有后继。实现这个的代码：

//Create the graph
Graph<String, DefaultEdge> g = new SimpleDirectedGraph<>(DefaultEdge.class);
g.addVertex("Level 1");
g.addVertex("Level 2.1");
g.addVertex("Level 2.2");
g.addVertex("Level 3.1");
g.addVertex("Level 3.2");
g.addVertex("Level 3.3");
g.addVertex("Level 3.4");

g.addEdge("Level 1", "Level 2.1");
g.addEdge("Level 1", "Level 2.2");

g.addEdge("Level 2.1", "Level 3.1");
g.addEdge("Level 2.1", "Level 3.2");
g.addEdge("Level 2.1", "Level 3.3");

g.addEdge("Level 2.2", "Level 3.4");

String vertex="Level 2.1"; //Vertex to be removed
//Get predecessors of the vertex that you want to delete:
List<String> pre = Graphs.predecessorListOf(g, vertex);
//Get successors of vertex that you want to delete:
List<String> suc = Graphs.successorListOf(g, vertex);
//Remove the vertex
g.removeVertex(vertex);
//Reconnect all vertices in the pre list to all vertices in the suc list.
for(String v1 : pre)
    for(String v2 : suc)
        g.addEdge(v1,v2);

System.out.println(g);

输出：

([Level 1, Level 2.2, Level 3.1, Level 3.2, Level 3.3, Level 3.4], [(Level 1,Level 2.2), (Level 2.2,Level 3.4), (Level 1,Level 3.1), (Level 1,Level 3.2), (Level 1,Level 3.3)])

请注意，上述过程不会保留边缘对象。它只是 re-connects 通过创建新边来绘制图形。如果要保留边对象，还必须在删除顶点之前存储这些对象。可以通过g.outgoingEdgesOf(vertex).

查询边

jGraphT - 删除一个顶点并重新连接所有连接到删除的顶点的顶点

jGraphT - Remove a vertex and reconnect all vertices which were connected to the removed one