num::structures::sample_clique_tree

Defined in header <structures/graph/clique.hpp>

template <typename Weight, std::integral Index, typename Queue, typename Rng>
void sample_clique_tree(array<array<multi_edge<Weight, Index>>> &G, Queue &q,
                        const array<multi_edge<Weight, Index>> &nbr,
                        Weight total_weight, Rng &rng, std::size_t trees = 1);

Replace the star-mesh clique by a random spanning tree of it, reweighted so the elimination stays unbiased in expectation.

Eliminating v adds a clique on its neighbours with weights \(w_{ij} = c_i c_j / C\), where \(c_i\) is the conductance from v to i and \(C = \sum_i c_i\). Edge \(ij\) enters the tree with probability \(p_{ij} = (c_i + c_j)/C\) and is reweighted to the harmonic mean \(c_i c_j / (c_i + c_j)\), so \(\mathbb{E}[\widetilde L^{(v)}] = \mathrm{Sc}(L)\). The walk is capped: past the cap the remaining vertices attach to the heaviest neighbour, which keeps a spanning tree but loses exactness for that elimination.

Parameters

• G: Adjacency being eliminated; sampled edges are appended.
• q: Degree queue, rekeyed for each endpoint touched.
• nbr: Neighbours of the eliminated vertex, with their conductances.
• total_weight: \(C\), the sum of those conductances.
• rng: Random source.