minicp.util

Class GraphUtil

java.lang.Object

minicp.util.GraphUtil

public class GraphUtil
extends java.lang.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 boolean	pathExists(GraphUtil.Graph graph, int start, int end) Checks if a path exists between start and end
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.

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

pathExists

public static boolean pathExists(GraphUtil.Graph graph,
                                 int start,
                                 int end)

Checks if a path exists between start and end

Parameters:

graph -

start - a node id from the graph

end - a node id from the graph

Returns:

true if a directed path from start to end exists, false otherwise