Class HeapThreads

java.lang.Object
topics.branchandbound.utils.threads.HeapThreads
public class HeapThreads extends Object

Concurrent State Space Queue (Heap)

Manages the frontier of unexplored nodes during a multithreaded Branch and Bound execution. This data structure ensures thread-safe prioritization, extraction, and duplicate-state detection across parallel workers.

*

Architecture invalid input: '&' Complexity

  • Priority Queue: Utilizes a PriorityBlockingQueue to maintain the Best-First Search ordering concurrently. Extraction is O(log N).
  • Lineage Tracking: Employs a ConcurrentMap to link extracted states back to their parents for final path reconstruction. Lookup is O(1).
  • Duplicate Pruning: Integrates a concurrent Set to track topologically equivalent states, preventing redundant exploration loops in O(1) time.
Author:
vicegd

  • Constructor Summary

    Constructors
    Constructor
    Description
    HeapThreads()
    Initializes the concurrent collections required to manage the state space.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    clear()
    Flushes all active nodes from the priority queue.
    int
    estimateBest()
    Peeks at the most promising active node to estimate the current best theoretical outcome without removing it from the queue.
    Node
    extractBestNode()
    Thread-safe retrieval and removal of the highest-priority node from the frontier.
    List<Node>
    extractUsedNodesFrom(Node targetNode)
    Traces the ancestral lineage of a specific node back to the root of the execution tree.
    void
    insert(Node node)
    Safely inserts a new node into the priority queue if it has not been explored previously.
    boolean
    isEmpty()
    Evaluates whether the active frontier contains any pending nodes.

    Methods inherited from class Object

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

  • Constructor Details

    • HeapThreads

      public HeapThreads()
      Initializes the concurrent collections required to manage the state space.

  • Method Details

    • clear

      public void clear()
      Flushes all active nodes from the priority queue.

      Note: This does not clear the lineage or explored states registries, preserving the historical context of the execution.

    • insert

      public void insert(Node node)
      Safely inserts a new node into the priority queue if it has not been explored previously.
      Parameters:
      node - The mathematical state node to be evaluated for insertion.

    • isEmpty

      public boolean isEmpty()
      Evaluates whether the active frontier contains any pending nodes.
      Returns:
      true if the priority queue is empty; false otherwise.

    • estimateBest

      public int estimateBest()
      Peeks at the most promising active node to estimate the current best theoretical outcome without removing it from the queue.
      Returns:
      The heuristic value of the highest-priority node, or Integer.MAX_VALUE if the queue is temporarily empty.

    • extractBestNode

      public Node extractBestNode()
      Thread-safe retrieval and removal of the highest-priority node from the frontier. Registers the extracted node in the lineage and explored-state trackers.
      Returns:
      The optimal pending node, or null if the queue is empty.

    • extractUsedNodesFrom

      public List<Node> extractUsedNodesFrom(Node targetNode)
      Traces the ancestral lineage of a specific node back to the root of the execution tree.
      Parameters:
      targetNode - The terminal node (typically the optimal solution leaf).
      Returns:
      A chronologically ordered list representing the path from the target node up to the root node.