|
discrete-modulus (C++)
Reference implementations of discrete modulus algorithms (C++)
|
Namespaces | |
| namespace | detail |
Classes | |
| struct | FlowContext |
| The reusable max-flow network for cunningham_min / graph_vulnerability / spanning_tree_modulus, built once per graph by create_flow_graph. More... | |
| struct | NonCriticalEdge |
| Edge filter selecting edges not in a given critical/tight set. More... | |
| struct | SolverTrace |
| The full recorded trace of a spanning_tree_modulus run. More... | |
| struct | TraceRound |
| One round of spanning_tree_modulus's main loop: the component it was carved from, the edge set dispatched at eta* = theta, and theta itself. More... | |
Typedefs | |
| using | Traits = adjacency_list_traits< vecS, vecS, undirectedS > |
| Traits for Graph. | |
| using | Graph = adjacency_list< vecS, vecS, undirectedS, property< vertex_name_t, Traits::vertex_descriptor >, property< edge_index_t, int, property< edge_weight_t, long > > > |
| The undirected graph type used throughout this library. | |
| using | Vertex = graph_traits< Graph >::vertex_descriptor |
| using | Edge = graph_traits< Graph >::edge_descriptor |
| using | VertexIterator = graph_traits< Graph >::vertex_iterator |
| using | EdgeIterator = graph_traits< Graph >::edge_iterator |
| using | FlowTraits = adjacency_list_traits< vecS, vecS, directedS > |
| Traits for FlowGraph. | |
| using | FlowVertex = FlowTraits::vertex_descriptor |
| using | FlowEdge = FlowTraits::edge_descriptor |
| using | FlowGraph = adjacency_list< vecS, vecS, directedS, no_property, property< edge_capacity_t, long, property< edge_residual_capacity_t, long, property< edge_reverse_t, FlowTraits::edge_descriptor > > > > |
The directed, capacitated graph type used for the max-flow subproblem in Cunningham's algorithm (see create_flow_graph in cunningham.hpp). edge_reverse records, for every directed edge, its paired reverse-residual edge, as required by boost::push_relabel_max_flow. | |
Functions | |
| FlowContext | create_flow_graph (Graph &g) |
Builds the reusable max-flow network for g. | |
| std::pair< long, std::set< Edge > > | 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 > > | 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 > > | spanning_tree_modulus (Graph &g, bool verbose=false, SolverTrace *trace=nullptr) |
Computes the exact spanning tree modulus of g using Cunningham's algorithm. | |
| template<typename G > | |
| Graph | subgraph (const G &g, std::vector< Vertex > v) |
Builds the subgraph of g induced by the given vertices. | |
| template<typename G > | |
| std::vector< Graph > | connected_component_graphs (const G &g) |
Splits g into one Graph per connected component. | |
| std::vector< Graph > | induced_components (Graph &g, const std::set< Edge > &A) |
Splits g into connected components after removing the critical edge set A. | |
| template<typename G > | |
| bool | is_simple_graph (const G &g) |
Checks whether g is a simple graph: no self-loops, no parallel edges between the same pair of vertices. | |
| Graph | cycle_plus_triangle (int n) |
A cycle on n vertices plus one extra chord (between vertices 1 and n-1). | |
| Graph | complete_graph (int n) |
The complete graph on n vertices. | |
| Graph | wheel_graph (int n) |
| The wheel graph: a cycle on n-1 vertices plus one hub vertex n-1. | |
| Graph | growing_multipartite (int n_layers) |
| A multipartite graph with growing layer sizes (1, 2, ..., n_layers) and complete bipartite connections between consecutive layers. | |
| Graph | complete_plus_triangle (int n) |
| The complete graph on n-1 vertices, plus one extra vertex attached to two of them. | |
| Graph | permuted_graph (const Graph &g, const std::vector< int > &perm) |
g with vertices relabeled according to perm. | |
| Graph | disconnected_graph () |
| Two disjoint triangles: a minimal example of a disconnected graph. | |
| Graph | random_gnp_graph (int n, double p, int seed) |
| An Erdos-Renyi G(n,p) random graph. | |
| Graph | random_geometric_graph (int n, double r, int seed=381928) |
| A random geometric graph: n uniform points in the unit square, connected within radius r. | |
| void | write_trace_json (std::ostream &os, const SolverTrace &trace) |
Writes trace to os as versioned JSON ("version": 1). | |
| using discrete_modulus::Edge = typedef graph_traits<Graph>::edge_descriptor |
| using discrete_modulus::EdgeIterator = typedef graph_traits<Graph>::edge_iterator |
| using discrete_modulus::FlowEdge = typedef FlowTraits::edge_descriptor |
| using discrete_modulus::FlowGraph = typedef adjacency_list< vecS, vecS, directedS, no_property, property<edge_capacity_t, long, property<edge_residual_capacity_t, long, property<edge_reverse_t, FlowTraits::edge_descriptor> >> > |
The directed, capacitated graph type used for the max-flow subproblem in Cunningham's algorithm (see create_flow_graph in cunningham.hpp). edge_reverse records, for every directed edge, its paired reverse-residual edge, as required by boost::push_relabel_max_flow.
| using discrete_modulus::FlowTraits = typedef adjacency_list_traits<vecS, vecS, directedS> |
Traits for FlowGraph.
| using discrete_modulus::FlowVertex = typedef FlowTraits::vertex_descriptor |
| using discrete_modulus::Graph = typedef adjacency_list< vecS, vecS, undirectedS, property<vertex_name_t, Traits::vertex_descriptor>, property<edge_index_t, int, property<edge_weight_t, long> >> |
The undirected graph type used throughout this library.
Vertices carry a vertex_name property (used to map a component's local vertex descriptors back to the original graph's vertex descriptors after splitting into connected components; see subgraph). Edges carry an edge_index (a stable 0..m-1 numbering) and an edge_weight (used as the current point x in Cunningham's algorithm; see cunningham.hpp).
| using discrete_modulus::Traits = typedef adjacency_list_traits<vecS, vecS, undirectedS> |
Traits for Graph.
| using discrete_modulus::Vertex = typedef graph_traits<Graph>::vertex_descriptor |
| using discrete_modulus::VertexIterator = typedef graph_traits<Graph>::vertex_iterator |
|
inline |
The complete graph on n vertices.
|
inline |
The complete graph on n-1 vertices, plus one extra vertex attached to two of them.
| std::vector< Graph > discrete_modulus::connected_component_graphs | ( | const G & | g | ) |
Splits g into one Graph per connected component.
|
inline |
Builds the reusable max-flow network for g.
g outlives, and is not modified (beyond its edge_weight property, which cunningham_min manages) for the lifetime of, the returned FlowContext – it assigns and relies on a stable edge_index numbering of g's edges.
|
inline |
Finds a P(qf)-basis for the constant function p, along with a tight set, using Cunningham's greedy algorithm.
| g | Graph to compute on; its edge_weight property map is used to store the current point x and is reset to zero at the start of this call. |
| ctx | Reusable flow network for g, from create_flow_graph. |
| p,q | Together, p/q is the rational constant whose P(f)-basis is being sought. |
{x(E), A}: the total weight of the P(qf)-basis found (x itself is left in g's edge_weight property map), and a tight set A for it (i.e. x(A) == q * f(A)).
|
inline |
A cycle on n vertices plus one extra chord (between vertices 1 and n-1).
|
inline |
Two disjoint triangles: a minimal example of a disconnected graph.
|
inline |
Finds the vulnerability theta(G) of a graph by binary search, along with an optimal tight set.
| g | Graph to compute on. |
| ctx | Reusable flow network for g, from create_flow_graph. |
| ubound | An upper bound on theta(G), when known (e.g. the parent component's own theta, during spanning_tree_modulus's recursive decomposition) – restricts the binary search range. Defaults to 1, theta's global maximum possible value. |
{theta, J}: the vulnerability of g, and a tight edge set achieving it.
|
inline |
A multipartite graph with growing layer sizes (1, 2, ..., n_layers) and complete bipartite connections between consecutive layers.
|
inline |
Splits g into connected components after removing the critical edge set A.
| bool discrete_modulus::is_simple_graph | ( | const G & | g | ) |
Checks whether g is a simple graph: no self-loops, no parallel edges between the same pair of vertices.
spanning_tree_modulus assumes this. It's not just a matter of degree: eta_star's own construction looks up edge(u, v, g), which identifies an edge by its endpoint pair alone – unambiguous only when g is simple. Fed a multigraph, that lookup would silently return an arbitrary one of several parallel edges and mis-assign its eta*, not fail loudly. (The spanning-tree-modulus solver was never designed to handle multigraph inputs – the shrunk multigraphs that show up in deflation/certification, e.g. Multigraph in the Lean verifier or the networkx multigraphs pmf_construction.py builds, are a separate, purely conceptual construction the certificate builder reasons about after the fact; the solver itself only ever recurses on vertex-induced subgraphs of the original input, so it never needs to represent one internally.)
g with vertices relabeled according to perm.
|
inline |
A random geometric graph: n uniform points in the unit square, connected within radius r.
|
inline |
An Erdos-Renyi G(n,p) random graph.
|
inline |
Computes the exact spanning tree modulus of g using Cunningham's algorithm.
| g | Graph to compute on. |
| verbose | If true, prints a progress table to stdout as edges are assigned their eta* value. |
| trace | If non-null, appends one TraceRound per round of the main loop below (opt-in; leaving this null, the default, reproduces the exact behavior of every existing caller). |
Builds the subgraph of g induced by the given vertices.
The returned graph's vertex_name property maps each of its (local) vertices back to the corresponding vertex descriptor in g, so that results computed on the subgraph can be mapped back to g.
|
inline |
The wheel graph: a cycle on n-1 vertices plus one hub vertex n-1.
|
inline |
Writes trace to os as versioned JSON ("version": 1).
Every value is either an integer or an array of them, so this is a plain hand-written emitter – no JSON library dependency, no escaping concerns (there are no free-form strings in the schema).
1.9.8