Class Node

java.lang.Object
topics.branchandbound.utils.Node
All Implemented Interfaces:
Comparable<Node>
Direct Known Subclasses:
AssignmentState, BoardState, Game, InterleavingNode, PuzzleState
public abstract class Node extends Object implements Comparable<Node>

State Space Tree Node

An abstract representation of a distinct mathematical state within the execution tree of a Branch and Bound algorithmic process.

This class establishes the fundamental topological contract for any state node, providing built-in mechanisms for unique identification, lineage tracking (parenting), depth monitoring, and heuristic cost evaluation. It implements the Comparable interface to allow automatic prioritization within the execution engine's exploration queue.

Author:
vicegd

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected int
    depth
    The topological depth of this state within the execution tree.
    protected int
    heuristicValue
    The calculated lower-bound metric evaluating the optimistic cost of this state.
    protected final UUID
    id
    The immutable unique identifier for this specific state configuration.
    protected UUID
    parentId
    The unique identifier of the preceding node from which this state was derived, allowing the extraction of the final path lineage.

  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    protected
    Node()
    Initializes the foundational properties of a new state node, generating its unique identity and establishing it as an unlinked topological root by default.

  • Method Summary

    Modifier and Type
    Method
    Description
    abstract void
    calculateHeuristicValue()
    Executes the mathematical formulation to compute the specific lower-bound heuristic estimate for this state configuration.
    int
    compareTo(Node other)
    Defines the prioritization logic for the execution engine's priority queue.
    boolean
    equals(Object obj)
    Evaluates topological equivalence between this state and another object.
    abstract List<Node>
    expand()
    Generates all mathematically valid state configurations extending from this specific topological juncture.
    int
    getDepth()
    Retrieves the execution depth of this state.
    int
    getHeuristicValue()
    Retrieves the optimistic heuristic evaluation cost of this state.
    UUID
    getId()
    Retrieves the unique identifier of this node.
    UUID
    getParentId()
    Retrieves the unique identifier of the parent node.
    int
    hashCode()
     
    int
    initialValuePruneLimit()
    Establishes the preliminary upper-bound limit to trigger the initial pruning phase.
    abstract boolean
    isSolution()
    Determines whether the current node represents a fully resolved configuration satisfying all problem constraints.

    Methods inherited from class Object

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

  • Field Details

    • id

      protected final UUID id
      The immutable unique identifier for this specific state configuration.

    • parentId

      protected UUID parentId
      The unique identifier of the preceding node from which this state was derived, allowing the extraction of the final path lineage.

    • depth

      protected int depth
      The topological depth of this state within the execution tree. Represents the number of discrete moves or transitions applied since the root node.

    • heuristicValue

      protected int heuristicValue
      The calculated lower-bound metric evaluating the optimistic cost of this state.

  • Constructor Details

    • Node

      protected Node()
      Initializes the foundational properties of a new state node, generating its unique identity and establishing it as an unlinked topological root by default.

  • Method Details

    • getId

      public UUID getId()
      Retrieves the unique identifier of this node.
      Returns:
      The UUID assigned to this state.

    • getParentId

      public UUID getParentId()
      Retrieves the unique identifier of the parent node.
      Returns:
      The UUID of the parent state, or null if this is the root.

    • getDepth

      public int getDepth()
      Retrieves the execution depth of this state.
      Returns:
      The integer depth level within the execution tree.

    • getHeuristicValue

      public int getHeuristicValue()
      Retrieves the optimistic heuristic evaluation cost of this state.
      Returns:
      The calculated integer bounding value.

    • equals

      public boolean equals(Object obj)
      Evaluates topological equivalence between this state and another object.

      By default, it determines equivalence by comparing the serialized string representation of the states. Subclasses may override this behavior if a more highly optimized mathematical comparison (e.g., matrix hashing) is required.

      Overrides:
      equals in class Object
      Parameters:
      obj - The target object to compare against.
      Returns:
      true if the states are structurally equivalent; false otherwise.

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object

    • initialValuePruneLimit

      public int initialValuePruneLimit()
      Establishes the preliminary upper-bound limit to trigger the initial pruning phase.

      By default, this assumes no prior domain knowledge, returning the maximum theoretical integer value. Subclasses should override this method to provide a tighter mathematical baseline (e.g., a greedy heuristic estimate) if available.

      Returns:
      The initial upper bound estimate.

    • compareTo

      public int compareTo(Node other)
      Defines the prioritization logic for the execution engine's priority queue. States with a lower heuristic value are granted higher priority, enforcing the Best-First Search exploration pattern.
      Specified by:
      compareTo in interface Comparable<Node>
      Parameters:
      other - The competing state node to compare against.
      Returns:
      A negative integer, zero, or a positive integer as this node is prioritized higher, equal to, or lower than the specified node.

    • calculateHeuristicValue

      public abstract void calculateHeuristicValue()
      Executes the mathematical formulation to compute the specific lower-bound heuristic estimate for this state configuration.

    • expand

      public abstract List<Node> expand()
      Generates all mathematically valid state configurations extending from this specific topological juncture.
      Returns:
      A list containing the resulting child nodes.

    • isSolution

      public abstract boolean isSolution()
      Determines whether the current node represents a fully resolved configuration satisfying all problem constraints.
      Returns:
      true if the state is a complete mathematical solution; false otherwise.