Package org.graph4j.hamiltonian

Class BacktrackLongestPathAlgoritm

java.lang.Object

org.graph4j.GraphAlgorithm

org.graph4j.hamiltonian.BacktrackLongestPathAlgoritm

public class BacktrackLongestPathAlgoritm
extends GraphAlgorithm

Backtracking algorithm for determining the longest path in a graph (directed or not).

Author:

Cristian Frăsinaru

See Also:

• Path

Field Summary

Fields inherited from class org.graph4j.GraphAlgorithm

directed, graph

Constructor Summary

Constructors

Constructor	Description
BacktrackLongestPathAlgoritm(Graph graph)

Method Summary

Modifier and Type	Method	Description
Path	getLongestPath()	Returns the longest path in the graph.
Path	getLongestPath(int source)	Returns the longest path in the graph, starting in the source vertex.
Path	getLongestPath(int source, int target)	Returns the longest path in the graph, starting in the source vertex and ending in the target vertex.

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

BacktrackLongestPathAlgoritm

public BacktrackLongestPathAlgoritm(Graph graph)

Method Details

getLongestPath

public Path getLongestPath()

Returns the longest path in the graph. If the graph contians more paths of maximum length, it returns the first one found.

Returns:

the longest path in the graph.

getLongestPath

public Path getLongestPath(int source)

Returns the longest path in the graph, starting in the source vertex.

Parameters:

source - the source vertex number.

Returns:

the longest path in the graph, starting in the source vertex.

getLongestPath

public Path getLongestPath(int source,
 int target)

Returns the longest path in the graph, starting in the source vertex and ending in the target vertex.

Parameters:

source - the source vertex number.

target - the target vertex number.

Returns:

the longest path in the graph, starting in the source vertex and ending in the target vertex.