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.String
printPaths(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: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 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: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 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: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 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: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 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.
-
-