Package tools.refinery.interpreter.rete.itc.alg.incscc

Class IncSCCAlg<V>

java.lang.Object
tools.refinery.interpreter.rete.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 Object implements IGraphObserver<V>, ITcDataSource<V>
Incremental SCC maintenance + counting algorithm.

  • Field Details

  • Constructor Details

  • Method Details

    • 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 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 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 List<V> getReachabilityPath(V source, V target)

    • 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(Set<V> sources, 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 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