Class StronglyConnectedComponentsGraph<V>

java.lang.Object
org.jgrapht.graph.AbstractGraph<Integer,Integer>
org.jgrapht.graph.AbstractBaseGraph<Integer,Integer>
org.jgrapht.graph.DefaultDirectedGraph<Integer,Integer>
fr.lirmm.graphik.util.graph.scc.StronglyConnectedComponentsGraph<V>
Type Parameters:
V - vertex type of the original graph
All Implemented Interfaces:
Serializable, Cloneable, 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:

  • Field Summary

    Fields inherited from interface org.jgrapht.Graph

    DEFAULT_EDGE_WEIGHT

  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
     
    StronglyConnectedComponentsGraph()
    Creates an empty strongly connected components graph.
     <E> 
    StronglyConnectedComponentsGraph(org.jgrapht.Graph<V,E> graph)
    Construct the StronglyConnectedComponentsGraph of the specified graph

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    addComponent(int vertex, Set<V> vertices)
    Registers one strongly connected component.
    void
    addEdge(int tail, int head)
    Adds an edge between two component vertices.
    int[]
    computeLayers(Iterable<Integer> sources, boolean direction)
    Computes graph layers from the given sources.
    Set<V>
    getComponent(int vertex)
    Returns the original vertices contained in one component.
    int
    getNbrComponents()
    Returns the number of strongly connected components.
    Set<Integer>
    getSinks()
    Returns the sink components of this component graph.
    Set<Integer>
    getSources()
    Returns the source components of this component graph.

    Methods inherited from class org.jgrapht.graph.DefaultDirectedGraph

    createBuilder, createBuilder

    Methods inherited from class org.jgrapht.graph.AbstractBaseGraph

    addEdge, addEdge, addVertex, addVertex, clone, containsEdge, containsVertex, degreeOf, edgeSet, edgesOf, getAllEdges, getEdge, getEdgeSource, getEdgeSupplier, getEdgeTarget, getEdgeWeight, getType, getVertexSupplier, incomingEdgesOf, inDegreeOf, iterables, outDegreeOf, outgoingEdgesOf, removeEdge, removeEdge, removeVertex, setEdgeSupplier, setEdgeWeight, setVertexSupplier, vertexSet

    Methods inherited from class org.jgrapht.graph.AbstractGraph

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

    Methods inherited from class Object

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

    Methods inherited from interface org.jgrapht.Graph

    containsEdge, removeAllEdges, removeAllEdges, removeAllVertices, setEdgeWeight

  • Constructor Details

    • StronglyConnectedComponentsGraph

      public StronglyConnectedComponentsGraph()
      Creates an empty strongly connected components graph.

    • StronglyConnectedComponentsGraph

      public <E> StronglyConnectedComponentsGraph(org.jgrapht.Graph<V,E> graph)
      Construct the StronglyConnectedComponentsGraph of the specified graph
      Type Parameters:
      E - edge type of the original graph
      Parameters:
      graph - the graph to condense into strongly connected components

  • Method Details

    • addEdge

      public void addEdge(int tail, int head)
      Adds an edge between two component vertices.
      Parameters:
      tail - the source component index
      head - the target component index

    • addComponent

      public void addComponent(int vertex, Set<V> vertices)
      Registers one strongly connected component.
      Parameters:
      vertex - the component identifier
      vertices - the vertices belonging to that component

    • getComponent

      public Set<V> getComponent(int vertex)
      Returns the original vertices contained in one component.
      Parameters:
      vertex - the component identifier
      Returns:
      the vertices of the component

    • getSources

      public Set<Integer> getSources()
      Returns the source components of this component graph.
      Returns:
      the component identifiers without incoming edges

    • getSinks

      public Set<Integer> getSinks()
      Returns the sink components of this component graph.
      Returns:
      the component identifiers without outgoing edges

    • getNbrComponents

      public int getNbrComponents()
      Returns the number of strongly connected components.
      Returns:
      the number of components

    • computeLayers

      public int[] computeLayers(Iterable<Integer> sources, boolean direction)
      Computes graph layers from the given sources.
      Parameters:
      sources - the starting components
      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.