Package tools.refinery.interpreter.rete.itc.alg.misc

Class DFSPathFinder<V>

java.lang.Object

tools.refinery.interpreter.rete.itc.alg.misc.DFSPathFinder<V>

Type Parameters:

V - the node type of the graph

All Implemented Interfaces:

IGraphPathFinder<V>

public class DFSPathFinder<V>
extends 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

Constructor Summary

Constructors

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

Method Summary

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

Methods inherited from class java.lang.Object

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

Constructor Details

DFSPathFinder

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

Method Details

getAllPaths

public Iterable<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 Iterable<Deque<V>> getAllPathsToTargets(V sourceNode,
 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.

getPaths

protected Iterable<Deque<V>> getPaths(List<Deque<V>> paths,
 Deque<V> visited,
 Set<V> targetNodes)

printPaths

public String printPaths(List<Deque<V>> paths)

getPath

public 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 Iterable<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.