org.eclipse.incquery.runtime.base.itc.alg.incscc

Class IncSCCAlg<V>

java.lang.Object

org.eclipse.incquery.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.

Author:

Tamas Szabo

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) Returns a reachability path between the given source and target elements, or null if no such transitive reachability is present in the graph.
java.util.Set<Tuple<V>>	getTcRelation()
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.

Methods inherited from class java.lang.Object

equals, 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)

Description copied from interface: ITcDataSource

Returns a reachability path between the given source and target elements, or null if no such transitive reachability is present in the graph. The returned List contains the nodes along the path (this means that there is an edge in the graph between two consecutive nodes), including the source and target nodes. A self loop (one edge) is indicated with the source node being present two times in the returned List.

Note that the paths are not maintained incrementally and in worst case the complexity of the path construction is O(|V|+|E|) (one depth-first graph traversal). There is no guarantee that the given path is the shortest one between the given two nodes.

Specified by:

getReachabilityPath in interface ITcDataSource<V>

Parameters:

source - the source node

target - the target node

Returns:

a path between the nodes, or null if target is not reachable from source

checkTcRelation

public boolean checkTcRelation(DRedTcRelation<V> tc)

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>

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.