Skip to content

num::structures::sample_biclique_tree

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

template <typename Weight, typename Rng, typename Emit>
void sample_biclique_tree(const array<Weight> &x, const array<Weight> &y, Weight pivot,
                          Rng &rng, std::size_t trees, Emit emit);

Sample a spanning tree of the directed product biclique left by an LU pivot.

Eliminating pivot v leaves the rank-one Schur update \(xy^{T}/a\), with \(x_i = -A_{iv}\), \(y_j = -A_{vj}\) and \(a = A_{vv}\). Each in-neighbour becomes \(i_L\) and each out-neighbour \(j_R\) of a bipartite graph with conductances \(x_iy_j/a\). Edge \(i_L j_R\) enters the tree with probability \(p_{ij} = 1 - (1-\alpha_i)(1-\beta_j)\), where \(\alpha_i = x_i/X\) and \(\beta_j = y_j/Y\), and reweighting by \(w_{ij}/p_{ij}\) gives \(\mathbb{E}[\widetilde S_v] = xy^{T}/a\). It requires \(x_i, y_j, a > 0\), as in a nonsymmetric M-matrix; otherwise nothing is emitted.

Parameters

  • x: Incoming conductances, all strictly positive.
  • y: Outgoing conductances, all strictly positive.
  • pivot: \(a = A_{vv}\), strictly positive.
  • rng: Random source.
  • trees: Independent trees to average; each sampled weight is divided by this.
  • emit: Callable void(std::size_t i, std::size_t j, Weight w) receiving directed fill.