CODEWITHSUNDEEP
algorithmgraphdirected-acyclic-graphsjgraphtspanning-tree
Liang Lu
Liang Lu

Reputation: 3

Jgrapht: how to convert a directed cyclic graph into a DAG?

One thought is run a spanning tree algorithm (e.g., Kruskal) to get the spanning tree, and then construct a new graph from the spanning tree, which is quite messy in terms of code. Looks like there is no available implementation to obtain a DAG subgraph of a directed graph. Please instruct if there are better ways of doing this with jgrapht. Thanks!

As described in the previous section.

Upvotes: 0

Views: 1063

Answers (2)

ravenspoint
ravenspoint

Reputation: 20596

It rather depends on why you want to do this and what changes to your graph you will accept.

The straightforward way would be to find the cycles in the graph and select one of the edges in each cycle to be removed. However, deciding which edge to remove to remove from each cycle is a problem. You do not provide enough information in your question to make any suggestions about this.

To find the cycles in a graph only requires a modification to a simple depth first search that checks for a 'back edge' whenever a previously visited vertex is reached again. Here is some C++ code to do this:

https://github.com/JamesBremner/PathFinder/blob/d557d433e6676a1c066bc9ff5f5fdd8c8e3d9c61/src/GraphTheory.cpp#L247-L297

Here is a screenshot of a test run

enter image description here

Here are the results of a timing test on a significantly sized graph:

4,720 vertices 27,444 edges 13,722 cycles => 700 seconds

Of course, removing edges to break all these cycles will leave the graph in a horrible mess. Which is why I wonder why you want to do this. I asked you why, but you still haven't answered!

Upvotes: 0

Joris Kinable
Joris Kinable

Reputation: 2411

Your suggestion is not necessary bad. Not sure why this would be messy in code:

Graph<Integer,DefaultEdge> graphWithCycles = ...; //Your graph with cycles

//Compute spanning tree
SpanningTreeAlgorithm<DefaultEdge> sa = new KruskalMinimumSpanningTree<>(graphWithCycles);
SpanningTreeAlgorithm.SpanningTree<DefaultEdge> tree = sa.getSpanningTree();

//Create new graph without cycles induced by the spanning tree
Graph<Integer,DefaultEdge> graphWithoutCycles = ...; //Your graph without cycles, definition depends on graphWithCycles
for(DefaultEdge edge: tree.getEdges())
    Graphs.addEdgeWithVertices​(graphWithoutCycles, graphWithCycles, edge);

There's various other approaches, e.g. you could also simply run a BreadthFirstSearch on your graph with cycles and create a new graph induced by the BFS tree as you go:

Graph<Integer,DefaultEdge> graphWithCycles = ...; //Your graph with cycles
Graph<Integer,DefaultEdge> graphWithoutCycles = ...; //Your graph without cycles
BreadthFirstIterator​ bfs = new BreadthFirstIterator​(graphWithCycles);
while(bfs.hasNext()){
    Integer vertex = bfs.next(); 
    graphWithoutCycles.addVertex(vertex);
    DefaultEdge edge = bfs.getSpanningTreeEdge(vertex);
    if(edge != null) //Edge is null if the vertex is the root of the BFS tree
        graphWithoutCycles.addEdge(bfs.getParent(vertex),vertex,edge);
}

Upvotes: 0

Related Questions