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 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 returnedIGraphPathFinder
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 (seegetRepresentative(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.
-
-
-
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:IGraphObserver
Used to notify when an edge is inserted into the graph.- Specified by:
edgeInserted
in 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:IGraphObserver
Used to notify when an edge is deleted from the graph.- Specified by:
edgeDeleted
in interfaceIGraphObserver<V>
- Parameters:
source
- the source of the edgetarget
- 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 interfaceIGraphObserver<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 interfaceIGraphObserver<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 interfaceITcDataSource<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 interfaceITcDataSource<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 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:ITcDataSource
Returns all nodes from which the target node is reachable.- Specified by:
getAllReachableSources
in 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:ITcDataSource
Returns true if the target node is reachable from the source node.- Specified by:
isReachable
in 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:ITcDataSource
Call this method to properly dispose the data structures of a transitive closure algorithm.- Specified by:
dispose
in 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:ITcDataSource
The returnedIGraphPathFinder
can be used to retrieve paths between nodes using transitive reachability.- Specified by:
getPathFinder
in 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
-
-