Class IncSCCAlg<V>

  • Type Parameters:
    V - the type parameter of the nodes in the graph data source
    All Implemented Interfaces:
    IGraphObserver<V>, ITcDataSource<V>

    public class IncSCCAlg<V>
    extends java.lang.Object
    implements IGraphObserver<V>, ITcDataSource<V>
    Incremental SCC maintenance + counting algorithm.
    • Method Detail

      • edgeInserted

        public void edgeInserted​(V source,
                                 V target)
        Description copied from interface: IGraphObserver
        Used to notify when an edge is inserted into the graph.
        Specified by:
        edgeInserted in interface IGraphObserver<V>
        Parameters:
        source - the source of the edge
        target - the target of the edge
      • edgeDeleted

        public void edgeDeleted​(V source,
                                V target)
        Description copied from interface: IGraphObserver
        Used to notify when an edge is deleted from the graph.
        Specified by:
        edgeDeleted in interface IGraphObserver<V>
        Parameters:
        source - the source of the edge
        target - the target of the edge
      • nodeInserted

        public void nodeInserted​(V n)
        Description copied from interface: IGraphObserver
        Used to notify when a node is inserted into the graph.
        Specified by:
        nodeInserted in interface IGraphObserver<V>
        Parameters:
        n - the node
      • nodeDeleted

        public void nodeDeleted​(V n)
        Description copied from interface: IGraphObserver
        Used to notify when a node is deleted from the graph.
        Specified by:
        nodeDeleted in interface IGraphObserver<V>
        Parameters:
        n - the node
      • getAllReachableTargets

        public java.util.Set<V> getAllReachableTargets​(V source)
        Description copied from interface: ITcDataSource
        Returns all nodes which are reachable from the source node.
        Specified by:
        getAllReachableTargets in interface ITcDataSource<V>
        Parameters:
        source - the source node
        Returns:
        the set of target nodes
      • getAllReachableSources

        public java.util.Set<V> getAllReachableSources​(V target)
        Description copied from interface: ITcDataSource
        Returns all nodes from which the target node is reachable.
        Specified by:
        getAllReachableSources in interface ITcDataSource<V>
        Parameters:
        target - the target node
        Returns:
        the set of source nodes
      • isReachable

        public boolean isReachable​(V source,
                                   V target)
        Description copied from interface: ITcDataSource
        Returns true if the target node is reachable from the source node.
        Specified by:
        isReachable in interface ITcDataSource<V>
        Parameters:
        source - the source node
        target - the target node
        Returns:
        true if target is reachable from source, false otherwise
      • getReachabilityPath

        public java.util.List<V> getReachabilityPath​(V source,
                                                     V target)
      • checkTcRelation

        public boolean checkTcRelation​(DRedTcRelation<V> tc)
      • hasIncomingEdges

        public boolean hasIncomingEdges​(V root)
        Returns true if the SCC represented by the given root node has incoming edges in the reduced graph, false otherwise (if this SCC is a source in the reduced graph).
        Parameters:
        root - the root node of an SCC
        Returns:
        true if it has incoming edges, false otherwise
        Since:
        1.6
      • hasOutgoingEdges

        public boolean hasOutgoingEdges​(V root)
        Returns true if the SCC represented by the given root node has outgoing edges in the reduced graph, false otherwise (if this SCC is a sink in the reduced graph).
        Parameters:
        root - the root node of an SCC
        Returns:
        true if it has outgoing edges, false otherwise
        Since:
        1.6
      • dispose

        public void dispose()
        Description copied from interface: ITcDataSource
        Call this method to properly dispose the data structures of a transitive closure algorithm.
        Specified by:
        dispose in interface ITcDataSource<V>
      • notifyTcObservers

        protected void notifyTcObservers​(java.util.Set<V> sources,
                                         java.util.Set<V> targets,
                                         Direction direction)
        Call this method to notify the observers of the transitive closure relation. The tuples used in the notification will be the Descartes product of the two sets given.
        Parameters:
        sources - the source nodes
        targets - the target nodes
        direction -
      • getRepresentative

        public V getRepresentative​(V node)
        Returns the node that is selected as the representative of the SCC containing the argument.
        Since:
        1.6
      • getTcRelation

        public java.util.Set<Tuple<V>> getTcRelation()
      • isIsolated

        public boolean isIsolated​(V node)
      • getReducedGraph

        public Graph<V> getReducedGraph()
        The graph of SCCs; each SCC is represented by its representative node (see getRepresentative(Object))
        Since:
        1.6