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.
-
-
Constructor Summary
Constructors Constructor Description IncSCCAlg(IGraphDataSource<V> graphDataSource)
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description voidattachObserver(ITcObserver<V> to)Attach a transitive closure relation observer.booleancheckTcRelation(DRedTcRelation<V> tc)voiddetachObserver(ITcObserver<V> to)Detach a transitive closure relation observer.voiddispose()Call this method to properly dispose the data structures of a transitive closure algorithm.voidedgeDeleted(V source, V target)Used to notify when an edge is deleted from the graph.voidedgeInserted(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 returnedIGraphPathFindercan 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 (seegetRepresentative(Object))VgetRepresentative(V node)Returns the node that is selected as the representative of the SCC containing the argument.java.util.Set<Tuple<V>>getTcRelation()booleanhasIncomingEdges(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).booleanhasOutgoingEdges(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).booleanisIsolated(V node)booleanisReachable(V source, V target)Returns true if the target node is reachable from the source node.voidnodeDeleted(V n)Used to notify when a node is deleted from the graph.voidnodeInserted(V n)Used to notify when a node is inserted into the graph.protected voidnotifyTcObservers(java.util.Set<V> sources, java.util.Set<V> targets, Direction direction)Call this method to notify the observers of the transitive closure relation.
-
-
-
Field Detail
-
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:IGraphObserverUsed to notify when an edge is inserted into the graph.- Specified by:
edgeInsertedin interfaceIGraphObserver<V>- Parameters:
source- the source of the edgetarget- the target of the edge
-
edgeDeleted
public void edgeDeleted(V source, V target)
Description copied from interface:IGraphObserverUsed to notify when an edge is deleted from the graph.- Specified by:
edgeDeletedin interfaceIGraphObserver<V>- Parameters:
source- the source of the edgetarget- the target of the edge
-
nodeInserted
public void nodeInserted(V n)
Description copied from interface:IGraphObserverUsed to notify when a node is inserted into the graph.- Specified by:
nodeInsertedin interfaceIGraphObserver<V>- Parameters:
n- the node
-
nodeDeleted
public void nodeDeleted(V n)
Description copied from interface:IGraphObserverUsed to notify when a node is deleted from the graph.- Specified by:
nodeDeletedin interfaceIGraphObserver<V>- Parameters:
n- the node
-
attachObserver
public void attachObserver(ITcObserver<V> to)
Description copied from interface:ITcDataSourceAttach a transitive closure relation observer.- Specified by:
attachObserverin interfaceITcDataSource<V>- Parameters:
to- the observer object
-
detachObserver
public void detachObserver(ITcObserver<V> to)
Description copied from interface:ITcDataSourceDetach a transitive closure relation observer.- Specified by:
detachObserverin interfaceITcDataSource<V>- Parameters:
to- the observer object
-
getAllReachableTargets
public java.util.Set<V> getAllReachableTargets(V source)
Description copied from interface:ITcDataSourceReturns all nodes which are reachable from the source node.- Specified by:
getAllReachableTargetsin interfaceITcDataSource<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:ITcDataSourceReturns all nodes from which the target node is reachable.- Specified by:
getAllReachableSourcesin interfaceITcDataSource<V>- Parameters:
target- the target node- Returns:
- the set of source nodes
-
isReachable
public boolean isReachable(V source, V target)
Description copied from interface:ITcDataSourceReturns true if the target node is reachable from the source node.- Specified by:
isReachablein interfaceITcDataSource<V>- Parameters:
source- the source nodetarget- the target node- Returns:
- true if target is reachable from source, false otherwise
-
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:ITcDataSourceCall this method to properly dispose the data structures of a transitive closure algorithm.- Specified by:
disposein interfaceITcDataSource<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 nodestargets- the target nodesdirection-
-
getRepresentative
public V getRepresentative(V node)
Returns the node that is selected as the representative of the SCC containing the argument.- Since:
- 1.6
-
isIsolated
public boolean isIsolated(V node)
-
getPathFinder
public IGraphPathFinder<V> getPathFinder()
Description copied from interface:ITcDataSourceThe returnedIGraphPathFindercan be used to retrieve paths between nodes using transitive reachability.- Specified by:
getPathFinderin interfaceITcDataSource<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 (seegetRepresentative(Object))- Since:
- 1.6
-
-