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

Question

I`m new to graphs and fiddling around with JGraphT at the moment. I have a simple graph where I want to remove a certain vertex. Removing is no problem at all but I need to reconnect all the vertices which were connected with the removed one. See this example graph:

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

How do I remove the vertex "Level 2.1" and reconnect the vertices of level 3 with the one of level 1. I could surely implement something on my own. But I think JGraphT will offer a more convienent way to do this. In the end I want to transform the mentioned graph into this one in an easy manner. (My real use cases are much more complex)

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

I hope someone has the right hint for me. Thanks in advance.

Answer 1

The graph you provided as input is a tree graph. The general procedure would be to:

1. Store the predecessor vertices of the vertex you want to remove
2. Store the successor vertices of the vertex you want to remove
3. Remove the vertex, and reconnect all predecessors to all successors. The code to accomplish this:

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

The output:

([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)])

Note that the above procedure does not preserve the edge objects. It simply re-connects the graph by creating new edges. If you want to preserve the edge objects, you must also store these prior to removal of the vertex. You can query the edges through g.outgoingEdgesOf(vertex).