Package org.graph4j.route

Class PathFinder

java.lang.Object

org.graph4j.GraphAlgorithm

org.graph4j.route.PathFinder

public class PathFinder
extends GraphAlgorithm

Algorithms for finding paths in unweighted directed or undirected graph.

Author:

Cristian Frăsinaru

Field Summary

Fields inherited from class org.graph4j.GraphAlgorithm

directed, graph

Constructor Summary

Constructors

Constructor	Description
PathFinder(Graph graph)

Method Summary

Modifier and Type	Method	Description
Path	findShortestPath(Graph graph, int v, int u, int[] forbiddenVertices)	Finds the path with the fewest edges connecting two vertices.
boolean	hasPath(int v, int u)	Determines if there is a path connecting two vertices.

Methods inherited from class org.graph4j.GraphAlgorithm

getGraph

Methods inherited from class java.lang.Object

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

Constructor Details

PathFinder

public PathFinder(Graph graph)

Method Details

findShortestPath

public Path findShortestPath(Graph graph,
 int v,
 int u,
 int[] forbiddenVertices)

Finds the path with the fewest edges connecting two vertices. If the input graph is directed, the path takes into account the edge orientations. The path is found using a BFS iterator, therefore it is an induced path. The weights of the edges (if the graph is edge-weighted) are not taken in consideration. For determining a shortest path in an edge-weighted graph (see org.graph4j.shortestpath package).

Parameters:

graph - the input graph.

v - a vertex number.

u - a vertex number.

forbiddenVertices - vertices that are not allowed in the path; can be null if there are no forbidden vertices.

Returns:

a path connecting v and u or null if no such path exists.

Throws:

InvalidVertexException - if any of the specified vertices is not in the graph.

See Also:

• BFSSinglePairShortestPath

hasPath

public boolean hasPath(int v,
 int u)

Determines if there is a path connecting two vertices. If the input graph is directed, the path takes into account the edge orientations.

Parameters:

v - a vertex number.

u - a vertex number.

Returns:

true if there is a path connecting v and u, false otherwise.