Package jenkins.util

Class DirectedGraph<N>

java.lang.Object

jenkins.util.DirectedGraph<N>

public abstract class DirectedGraph<N>
extends Object

A possible cyclic directed graph. This class defines various algorithms on a directed graph that's not necessarily acyclic.

Author:

Kohsuke Kawaguchi

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	DirectedGraph.SCC<N>	Strongly connected component (SCC) of a graph.

Constructor Summary

Constructors

Constructor	Description
DirectedGraph()

Method Summary

Modifier and Type	Method	Description
protected abstract Collection<N>	forward(N node)	Forward traversal of the edges.
List<DirectedGraph.SCC<N>>	getStronglyConnectedComponents()	Performs the Tarjan's algorithm and computes strongly-connected components from the sink to source order.
protected abstract Collection<N>	nodes()	All the vertices of the nodes.

Methods inherited from class java.lang.Object

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

Constructor Details

DirectedGraph

public DirectedGraph()

Method Details

nodes

protected abstract Collection<N> nodes()

All the vertices of the nodes.

forward

protected abstract Collection<N> forward(N node)

Forward traversal of the edges.

getStronglyConnectedComponents

public List<DirectedGraph.SCC<N>> getStronglyConnectedComponents()

Performs the Tarjan's algorithm and computes strongly-connected components from the sink to source order. See the Wikipedia page.