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

Class DFSPathFinder<V>

java.lang.Object

org.eclipse.incquery.runtime.base.itc.alg.misc.DFSPathFinder<V>

Type Parameters:

V - the node type of the graph

All Implemented Interfaces:

IGraphPathFinder<V>

public class DFSPathFinder<V>
extends java.lang.Object
implements IGraphPathFinder<V>

A depth-first search implementation of the IGraphPathFinder. TODO use ITC to filter nodes that must be traversed, instead of checks

Author:

Abel Hegedus

Constructor Summary

Constructors

Constructor and Description
DFSPathFinder(IGraphDataSource<V> graph, ITcDataSource<V> itc)

Method Summary

Modifier and Type	Method and Description
java.lang.Iterable<java.util.Deque<V>>	getAllPaths(V sourceNode, V targetNode) Returns the collection of paths from the source node to the target node (if such exists).
java.lang.Iterable<java.util.Deque<V>>	getAllPathsToTargets(V sourceNode, java.util.Set<V> targetNodes) Returns the collection of paths from the source node to any of the target nodes (if such exists).
java.util.Deque<V>	getPath(V sourceNode, V targetNode) Returns an arbitrary path from the source node to the target node (if such exists).
java.lang.Iterable<java.util.Deque<V>>	getShortestPaths(V sourceNode, V targetNode) Returns the collection of shortest paths from the source node to the target node (if such exists).
java.lang.String	printPaths(java.util.List<java.util.Deque<V>> paths)

Methods inherited from class java.lang.Object

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

Constructor Detail

DFSPathFinder

public DFSPathFinder(IGraphDataSource<V> graph,
                     ITcDataSource<V> itc)

Method Detail

getAllPaths

public java.lang.Iterable<java.util.Deque<V>> getAllPaths(V sourceNode,
                                                          V targetNode)

Description copied from interface: IGraphPathFinder

Returns the collection of paths from the source node to the target node (if such exists). If there is no path between them, an empty collection is returned.

Specified by:

getAllPaths in interface IGraphPathFinder<V>

Parameters:

sourceNode - the source node of the path

targetNode - the target node of the path

Returns:

the collection of paths from the source to the target, or empty collection if target is not reachable from source.

getAllPathsToTargets

public java.lang.Iterable<java.util.Deque<V>> getAllPathsToTargets(V sourceNode,
                                                                   java.util.Set<V> targetNodes)

Description copied from interface: IGraphPathFinder

Returns the collection of paths from the source node to any of the target nodes (if such exists). If there is no path between them, an empty collection is returned.

Specified by:

getAllPathsToTargets in interface IGraphPathFinder<V>

Parameters:

sourceNode - the source node of the path

targetNodes - the set of target nodes of the paths

Returns:

the collection of paths from the source to any of the targets, or empty collection if neither target is reachable from source.

printPaths

public java.lang.String printPaths(java.util.List<java.util.Deque<V>> paths)

getPath

public java.util.Deque<V> getPath(V sourceNode,
                                  V targetNode)

Description copied from interface: IGraphPathFinder

Returns an arbitrary path from the source node to the target node (if such exists). If there is no path between them, an empty collection is returned.

Specified by:

getPath in interface IGraphPathFinder<V>

Parameters:

sourceNode - the source node of the path

targetNode - the target node of the path

Returns:

the path from the source to the target, or empty collection if target is not reachable from source.

getShortestPaths

public java.lang.Iterable<java.util.Deque<V>> getShortestPaths(V sourceNode,
                                                               V targetNode)

Description copied from interface: IGraphPathFinder

Returns the collection of shortest paths from the source node to the target node (if such exists). If there is no path between them, an empty collection is returned.

Specified by:

getShortestPaths in interface IGraphPathFinder<V>

Parameters:

sourceNode - the source node of the path

targetNode - the target node of the path

Returns:

the collection of shortest paths from the source to the target, or empty collection if target is not reachable from source.