时间戳

首页 > 解决方案 > jGraphT - 删除一个顶点并重新连接所有连接到已删除顶点的顶点

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

问题描述

我是图表新手，目前正在摆弄 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");

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

标签： jgrapht

解决方案

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

  1. 存储要删除的顶点的前驱顶点
  2. 存储要删除的顶点的后继顶点
  3. 删除顶点，并将所有前任重新连接到所有后继。完成此操作的代码：
//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)])

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

推荐阅读