org.eclipse.viatra.query.runtime.base.itc.alg.incscc

## Class IncSCCAlg<V>

- java.lang.Object
- - org.eclipse.viatra.query.runtime.base.itc.alg.incscc.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.

- - ### Field Summary

    Fields
    Modifier and Type | Field and Description
    --- | ---
    `IBiDirectionalGraphDataSource<V>` | `gds`
    `UnionFind<V>` | `sccs`

  - ### Constructor Summary

    Constructors
    Constructor and Description
    `IncSCCAlg(IGraphDataSource<V> graphDataSource)`

  - ### Method Summary

    All Methods Instance Methods Concrete Methods
    Modifier and Type | Method and Description
    --- | ---
    `void` | `attachObserver(ITcObserver<V> to)` Attach a transitive closure relation observer.
    `boolean` | `checkTcRelation(DRedTcRelation<V> tc)`
    `void` | `detachObserver(ITcObserver<V> to)` Detach a transitive closure relation observer.
    `void` | `dispose()` Call this method to properly dispose the data structures of a transitive closure algorithm.
    `void` | `edgeDeleted(V source, V target)` Used to notify when an edge is deleted from the graph.
    `void` | `edgeInserted(V source, V target)` Used to notify when an edge is inserted into the graph.
    `java.util.Set<V>` | `getAllReachableSources(V target)` Returns all nodes from which the target node is reachable.
    `java.util.Set<V>` | `getAllReachableTargets(V source)` Returns all nodes which are reachable from the source node.
    `IGraphPathFinder<V>` | `getPathFinder()` The returned `IGraphPathFinder` can be used to retrieve paths between nodes using transitive reachability.
    `java.util.List<V>` | `getReachabilityPath(V source, V target)`
    `Graph<V>` | `getReducedGraph()` The graph of SCCs; each SCC is represented by its representative node (see `getRepresentative(Object)`)
    `V` | `getRepresentative(V node)` Returns the node that is selected as the representative of the SCC containing the argument.
    `java.util.Set<Tuple<V>>` | `getTcRelation()`
    `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).
    `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).
    `boolean` | `isIsolated(V node)`
    `boolean` | `isReachable(V source, V target)` Returns true if the target node is reachable from the source node.
    `void` | `nodeDeleted(V n)` Used to notify when a node is deleted from the graph.
    `void` | `nodeInserted(V n)` Used to notify when a node is inserted into the graph.
    `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.

    - ### Methods inherited from class java.lang.Object

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

- - ### Field Detail

    - #### sccs

          public UnionFind<V> sccs

    - #### gds

          public IBiDirectionalGraphDataSource<V> gds

  - ### Constructor Detail

    - #### IncSCCAlg

          public IncSCCAlg(IGraphDataSource<V> graphDataSource)

  - ### 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

    - #### attachObserver

          public void attachObserver(ITcObserver<V> to)

      Description copied from interface: `ITcDataSource`
      Attach a transitive closure relation observer.
      Specified by:
        `attachObserver` in interface `ITcDataSource<V>`
      Parameters:
        `to` - the observer object

    - #### detachObserver

          public void detachObserver(ITcObserver<V> to)

      Description copied from interface: `ITcDataSource`
      Detach a transitive closure relation observer.
      Specified by:
        `detachObserver` in interface `ITcDataSource<V>`
      Parameters:
        `to` - the observer object

    - #### 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)

    - #### getPathFinder

          public IGraphPathFinder<V> getPathFinder()

      Description copied from interface: `ITcDataSource`
      The returned `IGraphPathFinder` can be used to retrieve paths between nodes using transitive reachability.
      Specified by:
        `getPathFinder` in interface `ITcDataSource<V>`
      Returns:
        a path finder for the graph.

    - #### getReducedGraph

          public Graph<V> getReducedGraph()

      The graph of SCCs; each SCC is represented by its representative node (see `getRepresentative(Object)`)
      Since:
        1.6