Classes
struct	DualEdge

Functions
template<typename Node , typename WeightFunc >
auto	build_dual (const std::vector< std::vector< Node > > &faces, WeightFunc weight) -> std::vector< std::vector< DualEdge< Node > > >

template<typename Node >
auto	dijkstra (const std::vector< std::vector< DualEdge< Node > > > &dual, int src) -> std::pair< std::vector< int >, std::vector< int > >

auto	reconstruct_path (const std::vector< int > &prev, int src, int dst) -> std::vector< int >

template<typename Node >
auto	greedy_mwpm (const std::vector< int > &odd_faces, const std::vector< std::vector< int > > &dist) -> std::vector< std::pair< int, int > >

template<typename Node >
auto	exact_mwpm (const std::vector< int > &odd_faces, const std::vector< std::vector< int > > &dist) -> std::vector< std::pair< int, int > >

template<typename Node >
auto	min_weight_perfect_matching (const std::vector< int > &odd_faces, const std::vector< std::vector< int > > &dist) -> std::vector< std::pair< int, int > >

template<typename Graph >
auto	biconnected_components (const Graph &G) -> std::vector< py::set< typename Graph::node_t > >
	Decompose a graph into its biconnected components (blocks).

template<typename Graph , typename WeightFunc >
auto	solve_hadlock_component (const Graph &G, WeightFunc weight, const std::vector< std::vector< typename Graph::node_t > > &faces) -> py::set< std::pair< typename Graph::node_t, typename Graph::node_t > >
	Solve MAX-CUT for a single planar biconnected component.

template<typename Node , typename Validator >
void	reverse_delete_cover (py::set< Node > &soln, const std::vector< Node > &added_order, Validator &&is_valid)
	Reverse-delete post-processing step.

template<typename Node , typename WeightFunc >
auto	prim_mst (size_t n, WeightFunc &&weight) -> std::vector< std::pair< Node, Node > >
	Prim's MST for dense (complete) graphs - O(n^2).

template<typename Node >
auto	find_odd_degree_nodes (const std::vector< std::pair< Node, Node > > &mst_edges, size_t n) -> std::vector< Node >
	Collect vertices with odd degree in the MST.

template<typename Node , typename WeightFunc >
auto	greedy_min_weight_matching (const std::vector< Node > &odd_nodes, WeightFunc &&weight) -> std::vector< std::pair< Node, Node > >
	Greedy minimum-weight perfect matching - O(k^2 log k).

template<typename Node >
auto	build_multigraph (size_t n, const std::vector< std::pair< Node, Node > > &mst_edges, const std::vector< std::pair< Node, Node > > &matching_edges) -> std::vector< std::multiset< Node > >
	Build a multigraph adjacency list (MST + matching).

template<typename Node >
auto	hierholzer (std::vector< std::multiset< Node > > adj, Node start) -> std::vector< std::pair< Node, Node > >
	Hierholzer's algorithm - find an Eulerian circuit.

template<typename Node >
auto	shortcut_eulerian (const std::vector< std::pair< Node, Node > > &eulerian_circuit) -> std::vector< Node >
	Convert an Eulerian circuit to a Hamiltonian cycle by skipping repeated vertices (shortcut).

Variables
constexpr int	INF = std::numeric_limits<int>::max() / 2

Function Documentation

◆ biconnected_components()

template<typename Graph >

auto detail::biconnected_components ( const Graph & G ) -> std::vector< py::set< typename Graph::node_t > >

Decompose a graph into its biconnected components (blocks).

MAX-CUT is additive over biconnected components because edges in different blocks share only articulation points and cannot form cycles together. Processing each block independently reduces the size of the dual-graph shortest-path and MWPM subproblems.

Uses a DFS-based algorithm (Tarjan) tracking discovery time and low-link values, pushing/poping edges onto a stack.

Template Parameters

Graph Graph type (must provide node_t, operator[], begin/end)

Parameters

G	The input graph.

Returns: Vector of node-sets, one per biconnected component. Articulation points may appear in multiple components; each edge belongs to exactly one component.

◆ build_dual()

template<typename Node , typename WeightFunc >

auto detail::build_dual	(	const std::vector< std::vector< Node > > &	faces,
		WeightFunc	weight
	)		-> std::vector<std::vector<DualEdge<Node>>>

◆ build_multigraph()

template<typename Node >

auto detail::build_multigraph	(	size_t	n,
		const std::vector< std::pair< Node, Node > > &	mst_edges,
		const std::vector< std::pair< Node, Node > > &	matching_edges
	)		-> std::vector<std::multiset<Node>>

Build a multigraph adjacency list (MST + matching).

Parallel edges are preserved via std::multiset so that the graph is Eulerian (all vertices have even degree).

◆ dijkstra()

template<typename Node >

auto detail::dijkstra	(	const std::vector< std::vector< DualEdge< Node > > > &	dual,
		int	src
	)		-> std::pair< std::vector< int >, std::vector< int > >

◆ exact_mwpm()

template<typename Node >

auto detail::exact_mwpm	(	const std::vector< int > &	odd_faces,
		const std::vector< std::vector< int > > &	dist
	)		-> std::vector< std::pair< int, int > >

Exact MWPM via DP over subsets (n <= 18, 2^18 = 262k states).

◆ find_odd_degree_nodes()

template<typename Node >

auto detail::find_odd_degree_nodes	(	const std::vector< std::pair< Node, Node > > &	mst_edges,
		size_t	n
	)		-> std::vector<Node>

Collect vertices with odd degree in the MST.

◆ greedy_min_weight_matching()

template<typename Node , typename WeightFunc >

auto detail::greedy_min_weight_matching	(	const std::vector< Node > &	odd_nodes,
		WeightFunc &&	weight
	)		-> std::vector<std::pair<Node, Node>>

Greedy minimum-weight perfect matching - O(k^2 log k).

Builds a sorted list of all candidate edges among odd_nodes and greedily picks the cheapest non-adjacent pair. This is a heuristic; for a provable 3/2 bound a blossom algorithm would be required.

◆ greedy_mwpm()

template<typename Node >

auto detail::greedy_mwpm	(	const std::vector< int > &	odd_faces,
		const std::vector< std::vector< int > > &	dist
	)		-> std::vector< std::pair< int, int > >

Greedy 2-approximation for MWPM on a metric complete graph.

◆ hierholzer()

template<typename Node >

auto detail::hierholzer	(	std::vector< std::multiset< Node > >	adj,
		Node	start
	)		-> std::vector< std::pair< Node, Node > >

Hierholzer's algorithm - find an Eulerian circuit.

Assumes the graph is connected and every vertex has even degree.

Parameters

adj	adjacency (multiset per vertex) - consumed by the algorithm
start	start vertex

Returns: vector of directed edges (u, v) forming the circuit

◆ min_weight_perfect_matching()

template<typename Node >

auto detail::min_weight_perfect_matching	(	const std::vector< int > &	odd_faces,
		const std::vector< std::vector< int > > &	dist
	)		-> std::vector<std::pair<int, int>>

Dispatch MWPM: exact DP for small n, greedy for large n.

◆ prim_mst()

template<typename Node , typename WeightFunc >

auto detail::prim_mst	(	size_t	n,
		WeightFunc &&	weight
	)		-> std::vector<std::pair<Node, Node>>

Prim's MST for dense (complete) graphs - O(n^2).

Template Parameters

Node	integral node type
WeightFunc	callable `double(Node, Node)`

Parameters

n	number of vertices (assumed 0 .. n-1)
weight	edge-weight function

Returns: vector of undirected edges forming the MST

◆ reconstruct_path()

auto detail::reconstruct_path	(	const std::vector< int > &	prev,
		int	src,
		int	dst
	)		-> std::vector<int>

inline

◆ reverse_delete_cover()

template<typename Node , typename Validator >

void detail::reverse_delete_cover	(	py::set< Node > &	soln,
		const std::vector< Node > &	added_order,
		Validator &&	is_valid
	)

Reverse-delete post-processing step.

Iterates through vertices in reverse addition order. For each vertex, temporarily removes it; if the cover remains valid, the removal is kept (vertex was redundant). Otherwise the vertex is restored.

Template Parameters

Node	Vertex type
Validator	Callable that returns true if current cover is valid

Parameters

soln	Mutable cover set (modified in place)
added_order	Vertices in order they were added
is_valid	Validation callable

◆ shortcut_eulerian()

template<typename Node >

auto detail::shortcut_eulerian ( const std::vector< std::pair< Node, Node > > & eulerian_circuit ) -> std::vector<Node>

Convert an Eulerian circuit to a Hamiltonian cycle by skipping repeated vertices (shortcut).

◆ solve_hadlock_component()

template<typename Graph , typename WeightFunc >

auto detail::solve_hadlock_component	(	const Graph &	G,
		WeightFunc	weight,
		const std::vector< std::vector< typename Graph::node_t > > &	faces
	)		-> py::set<std::pair<typename Graph::node_t, typename Graph::node_t>>

Solve MAX-CUT for a single planar biconnected component.

This is the core Hadlock logic factored out so it can be called once per biconnected component. The existing 3-argument overload of solve_hadlock_max_cut delegates here.

Template Parameters

Graph	Graph type
WeightFunc	Callable `(u, v) -> int`

Parameters

G	Planar graph (or subgraph)
weight	Edge weight function
faces	Face boundaries (cyclic node sequences)

Returns: Set of edges in the maximum cut

Variable Documentation

◆ INF

constexpr int detail::INF = std::numeric_limits<int>::max() / 2

constexpr

Classes

Functions

Variables

Function Documentation

◆ biconnected_components()

◆ build_dual()

◆ build_multigraph()

◆ dijkstra()

◆ exact_mwpm()

◆ find_odd_degree_nodes()

◆ greedy_min_weight_matching()

◆ greedy_mwpm()

◆ hierholzer()

◆ min_weight_perfect_matching()

◆ prim_mst()

◆ reconstruct_path()

◆ reverse_delete_cover()

◆ shortcut_eulerian()

◆ solve_hadlock_component()

Variable Documentation

◆ INF