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 and Description
static class	DirectedGraph.SCC<N> Strongly connected component (SCC) of a graph.

Constructor Summary

Constructors

Constructor and Description
DirectedGraph()

Method Summary

Modifier and Type	Method and 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 Detail

DirectedGraph

public DirectedGraph()

Method Detail

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 https://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm