cunningham.hpp File Reference

Exact spanning tree modulus via Cunningham's algorithm. More...

#include <algorithm>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <utility>
#include <vector>
#include <boost/graph/push_relabel_max_flow.hpp>
#include <boost/rational.hpp>
#include "graphs.hpp"
#include "solver_trace.hpp"

Include dependency graph for cunningham.hpp:

Go to the source code of this file.

Classes
struct	discrete_modulus::FlowContext
	The reusable max-flow network for cunningham_min / graph_vulnerability / spanning_tree_modulus, built once per graph by create_flow_graph. More...

Namespaces
namespace	discrete_modulus
namespace	discrete_modulus::detail

Functions
FlowEdge	discrete_modulus::detail::add_capacity_edge (FlowGraph &fg, FlowVertex u, FlowVertex v, long capacity)
	Adds a directed capacity edge u -> v to fg, along with its required zero-capacity reverse-residual companion v -> u.
std::pair< long, std::set< Edge > >	discrete_modulus::detail::solve_subproblem (Graph &g, FlowContext &ctx, const Edge &e, long q)
	One max-flow step of Cunningham's algorithm: how far can x be increased on edge e without leaving the polymatroid P(qf)?
FlowContext	discrete_modulus::create_flow_graph (Graph &g)
	Builds the reusable max-flow network for g.
std::pair< long, std::set< Edge > >	discrete_modulus::cunningham_min (Graph &g, FlowContext &ctx, long p, long q)
	Finds a P(qf)-basis for the constant function p, along with a tight set, using Cunningham's greedy algorithm.
std::pair< rational< long >, std::set< Edge > >	discrete_modulus::graph_vulnerability (Graph &g, FlowContext &ctx, rational< long > ubound=rational< long >(1, 1))
	Finds the vulnerability theta(G) of a graph by binary search, along with an optimal tight set.
std::map< Edge, rational< long > >	discrete_modulus::spanning_tree_modulus (Graph &g, bool verbose=false, SolverTrace *trace=nullptr)
	Computes the exact spanning tree modulus of g using Cunningham's algorithm.

Detailed Description

Exact spanning tree modulus via Cunningham's algorithm.

Implements the algorithm of Albin, Kottegoda, and Poggi-Corradini, "An Exact-Arithmetic Algorithm for Spanning Tree Modulus," Networks 85(4), 412-424, which builds on Cunningham's matroid-greedy algorithm for polymatroid bases. See the Python package's discrete_modulus.spanning_tree_modulus module and the companion book's "Exact Spanning Tree Modulus" chapter for the underlying theory (rank, polymatroids, polymatroid bases, the max-flow subproblem, the integer-arithmetic reformulation, graph vulnerability, and computing modulus by repeatedly extracting tight sets).

This is an independent C++ implementation, not a port bound to the Python package's exact internal structure – but it deliberately mirrors its public shape (create_flow_graph, cunningham_min, graph_vulnerability, spanning_tree_modulus) and drops the performance-variant flags of the original research code in favor of a single algorithm path, for clarity and cross-language verifiability.

One optimization from the original is kept: since a component produced by splitting on a tight set can never have a larger vulnerability than the component it was split from, spanning_tree_modulus passes each child component's parent's theta down as an upper bound to graph_vulnerability, restricting its binary search range. Dropping this (as an earlier version of this file did) measurably matters: on examples/random.edges, which decomposes into many components, the unrestricted search never finished in a reasonable time.