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

Class DRedAlg<V>

java.lang.Object

org.eclipse.incquery.runtime.base.itc.alg.dred.DRedAlg<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 DRedAlg<V>
extends java.lang.Object
implements IGraphObserver<V>, ITcDataSource<V>

This class is the optimized implementation of the DRED algorithm.

Author:

Tamas Szabo

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
DRedAlg(IGraphDataSource<V> gds) Constructs a new DRED algorithm and initializes the transitive closure relation with the given graph data source.
DRedAlg(IGraphDataSource<V> gds, DRedTcRelation<V> tc) Constructs a new DRED algorithm and initializes the transitive closure relation with the given relation.

Method Summary

Modifier and Type	Method and Description
void	attachObserver(ITcObserver<V> to) Attach a transitive closure relation observer.
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.
DRedTcRelation<V>	getTcRelation()
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.
void	setTcRelation(DRedTcRelation<V> tc)

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

DRedAlg

public DRedAlg(IGraphDataSource<V> gds)

Constructs a new DRED algorithm and initializes the transitive closure relation with the given graph data source. Attach itself on the graph data source as an observer.

Parameters:

gds - the graph data source instance

DRedAlg

public DRedAlg(IGraphDataSource<V> gds,
               DRedTcRelation<V> tc)

Constructs a new DRED algorithm and initializes the transitive closure relation with the given relation. Attach itself on the graph data source as an observer.

Parameters:

gds - the graph data source instance

tc - the transitive closure instance

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

getTcRelation

public DRedTcRelation<V> getTcRelation()

setTcRelation

public void setTcRelation(DRedTcRelation<V> tc)

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

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

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

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>

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.