Level Queue

The levelqueue module provides level-based node managers. Nodes are grouped by search depth (level) and each level maintains its own PriorityManagerInterface queue.

LevelManagerInterface is the abstract base class. Two concrete strategies are provided:

CyclicBestSearch — cyclic best-first search, cycling through levels before falling back to the global best.
DfsPriority — depth-first with priority ordering within each level.

For simpler priority-queue managers without level cycling see Node Priority Queue.

LevelQueue

class bnbpy.cython.levelqueue.LevelQueue

Bases: object

A single level in a level-based node manager.

Internally holds a wrapper of a raw C++ NodePriQueueWrapper (min-heap) and maintains doubly-linked pointers to neighbouring levels.

The ordering key for each node is produced by make_priority(); subclasses override this to customise the intra-level priority.

filter(max_lb)

level

make_priority(node)

Return the ordering key for node (smaller → dequeued first).

Default is best-first: (lb, -level, -index). Override in subclasses to change intra-level ordering.

Parameters:: node (Node) – The node being enqueued.
Returns:: Priority vector; smaller values are dequeued first.
Return type:: list[float]

next

pop()

pq

prev

push(node)

size()

LevelManagerInterface

class bnbpy.cython.levelqueue.LevelManagerInterface

Bases: BaseNodeManager

Abstract base for level-based node managers.

Nodes are bucketed by tree level into doubly-linked LevelQueue objects. Concrete subclasses must override new_level() to control which LevelQueue subclass (and thus which priority) is used at each level.

clear(): Makes the manager empty.

dequeue()

Removes and returns the next node, updating bound_memory.

Returns:: The next node, or None if empty.
Return type:: Node

enqueue(node)

Adds a node to the manager and records it in bound_memory.

Parameters:: node (Node) – The node to add.

enqueue_all(nodes)

Adds a list of nodes to the manager.

Parameters:: nodes (list[Node]) – The list of nodes to add.

filter_by_lb(max_lb)

Remove nodes with lb >= max_lb and update bound_memory.

Parameters:: max_lb (float) – The maximum lower bound value (exclusive upper bound).

get_lower_bound()

Gets a node with the global minimum lower bound without removing it.

Returns:: A node with the lowest lower bound, or None if empty.
Return type:: Node

new_level(level)

not_empty()

Checks if the manager is not empty.

Returns:: True if the manager is not empty, False otherwise.
Return type:: bool

size()

Returns the number of nodes in the manager.

Returns:: The number of nodes in the manager.
Return type:: int

CyclicBestSearch

class bnbpy.cython.levelqueue.CyclicBestSearch

Bases: LevelManagerInterface

Cyclic best-first search.

Cycles through tree levels in round-robin order, always dequeuing the lowest-lb node within the current level. Switches to a DFS-like deepest-first strategy when the total node count exceeds max_size, and returns to cycling once the count falls to half of max_size (unless permanent_fallback is set).

DfsPriority

class bnbpy.cython.levelqueue.DfsPriority

Bases: LevelManagerInterface

Depth-first priority manager.

Always dequeues the best node (lowest lb) from the deepest non-empty level, giving DFS order with best-first tie-breaking within a level. The fallback mode is engaged permanently from initialisation.