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:

java.io.Serializable, IGraphObserver<V>, ITcDataSource<V>

public class IncSCCAlg<V>
extends java.lang.Object
implements IGraphObserver<V>, ITcDataSource<V>

Incremental SCC maintenance + counting algorithm.

See Also:

Serialized Form

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

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