mixle.enumeration.spanning module

k-best spanning tree enumeration (Gabow’s partition algorithm).

Enumerate the spanning trees of an undirected weighted graph in increasing total edge cost – the minimum spanning tree first, then the next-cheapest, and so on – without materializing the (often exponential) set of trees. This is the spanning-tree analogue of Murty’s k-best assignment: pop the best tree from a priority queue, then partition the remaining trees into subproblems (each forcing some tree edges in and one tree edge out) and solve each with one constrained-MST call.

The MST oracle is a small Kruskal with union-find, so forcing edges in (add them first, fail on a cycle) and out (skip them) is direct, and infeasibility (a forced-out edge disconnecting the graph) is detected by the tree having fewer than n-1 edges. Edges with non-finite cost are absent. SpanningTreeDistribution consumes this to enumerate trees in decreasing probability via cost = -log(weights).

k_best_spanning_trees(cost, k=None)

Yield spanning trees of a symmetric cost matrix in increasing total cost (Gabow’s algorithm).

Each item is (total_cost, edges) with edges a list of (i, j) pairs (i < j). Non-finite cost entries are treated as absent edges. Enumeration is lazy; k=None runs until the trees are exhausted.

Parameters:

• cost (ndarray) – symmetric n-by-n edge-cost matrix (diagonal ignored).

• k (int | None) – maximum number of trees to yield; None for all.

Yields:

(total_cost, edges) in nondecreasing total cost.

Return type:

Iterator[tuple[float, list[tuple[int, int]]]]