[SOLVED] Graph Transpose using Google Guava Graph API

Graph Transpose using Google Guava Graph API

I am implementing Kosaraju's algorithm using Google Guava Graph API but currently stuck to obtain a transpose of a MutableValueGraph using standard guava APIs.

Below is my code:

MutableValueGraph<GraphNode,Integer> graph = ValueGraphBuilder.directed()
    .allowsSelfLoops(true)
    .build();

Can someone suggest a good way to convert the graph to its transpose keeping the underlying interface same (MutableValueGraph)? Is there any way to do that? If not, I am happy to change the underlying interface.

Solution

You should look at Graphs helper class, which contains set of transpose methods, specifically Graphs#transpose(ValueGraph), which

Returns a view of graph with the direction (if any) of every edge reversed. All other properties remain intact, and further updates to graph will be reflected in the view.

Note that returned view is not mutable itself (it's ValueGraph), so if you want mutate transposed graph you have to copy its values yourself:

// to obtain a transposed view:
final ValueGraph<String, Integer> transposed = Graphs.transpose(graph); 
// to make a mutable copy of transposed graph:
final MutableValueGraph<String, Integer> transposedMutable = Graphs.copyOf(transposed);