fr.lirmm.graphik.util.graph.scc

Class StronglyConnectedComponentsGraph<V>

java.lang.Object

org.jgrapht.graph.AbstractGraph<V,E>

org.jgrapht.graph.AbstractBaseGraph<V,E>

org.jgrapht.graph.DefaultDirectedGraph<Integer,Integer>

fr.lirmm.graphik.util.graph.scc.StronglyConnectedComponentsGraph<V>

All Implemented Interfaces:

Serializable, Cloneable, org.jgrapht.DirectedGraph<Integer,Integer>, org.jgrapht.Graph<Integer,Integer>

public class StronglyConnectedComponentsGraph<V>
extends org.jgrapht.graph.DefaultDirectedGraph<Integer,Integer>

The StronglyConnectedComponentsGraph represents a graph of strongly connected components of an other graph.

Author:

Clément Sipieter (INRIA) <clement@6pi.fr>

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
StronglyConnectedComponentsGraph()
StronglyConnectedComponentsGraph(org.jgrapht.DirectedGraph<V,E> graph) Construct the StronglyConnectedComponentsGraph of the specified graph

Method Summary

Modifier and Type	Method and Description
void	addComponent(int vertex, Set<V> vertices)
void	addEdge(int tail, int head)
int[]	computeLayers(Iterable<Integer> sources, boolean direction)
Set<V>	getComponent(int vertex)
int	getNbrComponents()
Set<Integer>	getSinks()
Set<Integer>	getSources()

Methods inherited from class org.jgrapht.graph.AbstractBaseGraph

addEdge, addEdge, addVertex, clone, containsEdge, containsVertex, degreeOf, edgeSet, edgesOf, getAllEdges, getEdge, getEdgeFactory, getEdgeSource, getEdgeTarget, getEdgeWeight, incomingEdgesOf, inDegreeOf, isAllowingLoops, isAllowingMultipleEdges, outDegreeOf, outgoingEdgesOf, removeEdge, removeEdge, removeVertex, setEdgeSetFactory, setEdgeWeight, vertexSet

Methods inherited from class org.jgrapht.graph.AbstractGraph

assertVertexExist, containsEdge, equals, hashCode, removeAllEdges, removeAllEdges, removeAllEdges, removeAllVertices, toString, toStringFromSets

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface org.jgrapht.DirectedGraph

incomingEdgesOf, inDegreeOf, outDegreeOf, outgoingEdgesOf

Methods inherited from interface org.jgrapht.Graph

addEdge, addEdge, addVertex, containsEdge, containsEdge, containsVertex, edgeSet, edgesOf, getAllEdges, getEdge, getEdgeFactory, getEdgeSource, getEdgeTarget, getEdgeWeight, removeAllEdges, removeAllEdges, removeAllVertices, removeEdge, removeEdge, removeVertex, vertexSet

Constructor Detail

StronglyConnectedComponentsGraph

public StronglyConnectedComponentsGraph()

StronglyConnectedComponentsGraph

public StronglyConnectedComponentsGraph(org.jgrapht.DirectedGraph<V,E> graph)

Construct the StronglyConnectedComponentsGraph of the specified graph

Parameters:

graph -

Method Detail

addEdge

public void addEdge(int tail,
                    int head)

addComponent

public void addComponent(int vertex,
                         Set<V> vertices)

getComponent

public Set<V> getComponent(int vertex)

getSources

public Set<Integer> getSources()

getSinks

public Set<Integer> getSinks()

getNbrComponents

public int getNbrComponents()

computeLayers

public int[] computeLayers(Iterable<Integer> sources,
                           boolean direction)

Parameters:

sources -

direction - if true, following the direction of the edges, otherwise follows the reverse direction.

Returns:

an array of int containing the layer number of each components of this graph.