Module org.jgrapht.core
Package org.jgrapht.alg.tour

Class HamiltonianPathAlgorithmBase<V,E>

java.lang.Object
org.jgrapht.alg.tour.HamiltonianPathAlgorithmBase<V,E>
Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
HamiltonianPathAlgorithm<V,E>
Direct Known Subclasses:
BacktrackingHamiltonianPath, DagHamiltonianPath, HeldKarpHamiltonianPath
public abstract class HamiltonianPathAlgorithmBase<V,E> extends Object implements HamiltonianPathAlgorithm<V,E>
Base class for HamiltonianPathAlgorithm implementations.

Shares the small amount of plumbing common to the Hamiltonian path solvers in this package: input validation, the singleton-vertex special case, an open-vertex-list to GraphPath converter, and an adjacency-list builder that collapses parallel edges and skips self-loops.

This class is structurally similar to HamiltonianCycleAlgorithmBase but adapted to the open-path semantics (start and end vertex may differ; no closing edge is appended).

Author:
seilat

  • Constructor Details

    • HamiltonianPathAlgorithmBase

      protected HamiltonianPathAlgorithmBase()
      Constructs a new instance.

  • Method Details

    • requireNotEmpty

      protected void requireNotEmpty(Graph<V,E> graph)
      Throws IllegalArgumentException if graph has no vertices.
      Parameters:
      graph - the input graph
      Throws:
      IllegalArgumentException - if graph has no vertices

    • singletonPath

      protected GraphPath<V,E> singletonPath(Graph<V,E> graph)
      Returns the trivial Hamiltonian path of a graph with exactly one vertex: a GraphWalk whose vertex list contains only that vertex, no edges, and weight 0.
      Parameters:
      graph - the input graph, which must contain exactly one vertex
      Returns:
      the single-vertex path

    • vertexListToPath

      protected GraphPath<V,E> vertexListToPath(List<V> vertices, Graph<V,E> graph)
      Converts a complete vertex sequence into a GraphPath. For every consecutive vertex pair (u, v) the edge returned by graph.getEdge(u, v) is appended; the path weight is the sum of the chosen edges' graph.getEdgeWeight values. In multigraphs the chosen edge is an arbitrary representative; this method does not attempt to minimise weight across parallel edges.
      Parameters:
      vertices - the vertex sequence (must contain at least one vertex)
      graph - the input graph
      Returns:
      a GraphPath corresponding to vertices

    • buildAdjacency

      protected int[][] buildAdjacency(Graph<V,E> graph, List<V> indexToVertex, Map<V,Integer> vertexToIndex, boolean directed)
      Builds an integer-indexed adjacency list over the supplied vertex ordering. Self-loops are skipped because they cannot participate in a simple path; parallel edges between the same vertex pair collapse to a single neighbour entry, which is sufficient for the existence-only search performed by the Hamiltonian path solvers.

      For directed graphs only outgoing edges are recorded. For undirected graphs every incident edge contributes a neighbour entry.

      Parameters:
      graph - the input graph
      indexToVertex - vertex ordering used as the row index of the returned adjacency
      vertexToIndex - inverse of indexToVertex for fast neighbour lookup
      directed - true if graph is directed
      Returns:
      adjacency list as a jagged int[][]; row i lists the neighbours of indexToVertex.get(i) as indices into indexToVertex