Class DFSPathFinder<V>
- java.lang.Object
-
- org.eclipse.viatra.query.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 theIGraphPathFinder. 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
All Methods Instance Methods Concrete Methods Modifier and Type Method 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).protected java.lang.Iterable<java.util.Deque<V>>getPaths(java.util.List<java.util.Deque<V>> paths, java.util.Deque<V> visited, java.util.Set<V> targetNodes)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.StringprintPaths(java.util.List<java.util.Deque<V>> paths)
-
-
-
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:IGraphPathFinderReturns 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:
getAllPathsin interfaceIGraphPathFinder<V>- Parameters:
sourceNode- the source node of the pathtargetNode- 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:IGraphPathFinderReturns 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:
getAllPathsToTargetsin interfaceIGraphPathFinder<V>- Parameters:
sourceNode- the source node of the pathtargetNodes- 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 java.lang.Iterable<java.util.Deque<V>> getPaths(java.util.List<java.util.Deque<V>> paths, java.util.Deque<V> visited, java.util.Set<V> targetNodes)
-
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:IGraphPathFinderReturns 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:
getPathin interfaceIGraphPathFinder<V>- Parameters:
sourceNode- the source node of the pathtargetNode- 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:IGraphPathFinderReturns 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:
getShortestPathsin interfaceIGraphPathFinder<V>- Parameters:
sourceNode- the source node of the pathtargetNode- 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.
-
-