com.graphhopper.routing.subnetwork

Class TarjanSCC

java.lang.Object

com.graphhopper.routing.subnetwork.TarjanSCC

public class TarjanSCC
extends Object

Tarjan's algorithm to find strongly connected components of a directed graph. Two nodes belong to the same connected component iff they are reachable from each other. Reachability from A to B is not necessarily equal to reachability from B to A because the graph is directed.

This class offers two ways to run the algorithm: Either using (function call) recursion findComponentsRecursive() or recursion using an explicit stack findComponents(). The first one is easier to implement and understand and the second one allows running the algorithm also on large graphs without having to deal with JVM stack size limits.

Tarjan's algorithm is explained for example here: - http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm - http://www.timl.id.au/?p=327 - http://homepages.ecs.vuw.ac.nz/~djp/files/P05.pdf

Author:

easbar

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	TarjanSCC.ConnectedComponents

Method Summary

Modifier and Type	Method and Description
static TarjanSCC.ConnectedComponents	findComponents(Graph graph, EdgeFilter edgeFilter, boolean excludeSingleNodeComponents) Runs Tarjan's algorithm using an explicit stack.
static TarjanSCC.ConnectedComponents	findComponentsRecursive(Graph graph, EdgeFilter edgeFilter, boolean excludeSingleNodeComponents) Runs Tarjan's algorithm in a recursive way.

Methods inherited from class java.lang.Object

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

Method Detail

findComponents

public static TarjanSCC.ConnectedComponents findComponents(Graph graph,
                                                           EdgeFilter edgeFilter,
                                                           boolean excludeSingleNodeComponents)

Runs Tarjan's algorithm using an explicit stack.

Parameters:

excludeSingleNodeComponents - if set to true components that only contain a single node will not be returned when calling findComponents(com.graphhopper.storage.Graph, com.graphhopper.routing.util.EdgeFilter, boolean) or findComponentsRecursive(), which can be useful to save some memory.

findComponentsRecursive

public static TarjanSCC.ConnectedComponents findComponentsRecursive(Graph graph,
                                                                    EdgeFilter edgeFilter,
                                                                    boolean excludeSingleNodeComponents)

Runs Tarjan's algorithm in a recursive way. Doing it like this requires a large stack size for large graphs, which can be set like `-Xss1024M`. Usually the version using an explicit stack (findComponents()) should be preferred. However, this recursive implementation is easier to understand.

See Also:

findComponents(Graph, EdgeFilter, boolean)