minicp.util

Class GraphUtil

java.lang.Object

minicp.util.GraphUtil

public class GraphUtil
extends Object

Algorithms and Graph interface

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static interface	GraphUtil.Graph Directed graph API

Constructor Summary

Constructors

Constructor and Description
GraphUtil()

Method Summary

Modifier and Type	Method and Description
static int[]	stronglyConnectedComponents(GraphUtil.Graph graph) Computes the strongly connected components of the graph
static GraphUtil.Graph	transpose(GraphUtil.Graph graph) Transpose the graph i.e. every edge is reversed.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

GraphUtil

public GraphUtil()

Method Detail

transpose

public static GraphUtil.Graph transpose(GraphUtil.Graph graph)

Transpose the graph i.e. every edge is reversed.

Parameters:

graph - a Graph

Returns:

a new graph such that every edge is reversed

stronglyConnectedComponents

public static int[] stronglyConnectedComponents(GraphUtil.Graph graph)

Computes the strongly connected components of the graph

Parameters:

graph - the input graph on which to compute the strongly connected components

Returns:

for each node id, an id of the strongly connected components it belongs to