hadlock.hpp File Reference

#include <algorithm>
#include <cassert>
#include <functional>
#include <limits>
#include <map>
#include <py2cpp/dict.hpp>
#include <py2cpp/set.hpp>
#include <queue>
#include <set>
#include <utility>
#include <vector>
#include <xnetwork/thread_pool.hpp>

Include dependency graph for hadlock.hpp:

Go to the source code of this file.

Classes
struct	std::hash< pair< T1, T2 > >
struct	detail::DualEdge< Node >

Namespaces
namespace	std
namespace	detail

Functions
template<typename Node , typename WeightFunc >
auto	detail::build_dual (const std::vector< std::vector< Node > > &faces, WeightFunc weight) -> std::vector< std::vector< DualEdge< Node > > >
template<typename Node >
auto	detail::dijkstra (const std::vector< std::vector< DualEdge< Node > > > &dual, int src) -> std::pair< std::vector< int >, std::vector< int > >
auto	detail::reconstruct_path (const std::vector< int > &prev, int src, int dst) -> std::vector< int >
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 > >
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 > >
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 > >
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).
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.
template<typename Graph , typename WeightFunc >
auto	solve_hadlock_max_cut (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 planar graph using Hadlock's algorithm.
template<typename Graph , typename WeightFunc >
auto	solve_hadlock_max_cut (const Graph &G, WeightFunc weight, const std::vector< std::vector< std::vector< typename Graph::node_t > > > &component_faces) -> py::set< std::pair< typename Graph::node_t, typename Graph::node_t > >
	Solve MAX-CUT using biconnected component decomposition for speed.
template<typename Graph , typename WeightFunc >
auto	validate_max_cut (const Graph &G, const py::set< std::pair< typename Graph::node_t, typename Graph::node_t > > &cut_edges, WeightFunc weight) -> std::pair< bool, int >
template<typename Graph >
auto	validate_max_cut (const Graph &G, const py::set< std::pair< typename Graph::node_t, typename Graph::node_t > > &cut_edges) -> std::pair< bool, int >

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

Detailed Description

Hadlock's algorithm: planar MAX-CUT -> minimum weight perfect matching on dual.

The algorithm is accelerated by biconnected component decomposition: 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 dramatically reduces the size of the dual-graph shortest-path and MWPM subproblems.

Reference: Hadlock, F. O. (1975). "Finding a Maximum Cut of a Planar Graph in Polynomial Time." SIAM Journal on Computing, 4(3), 221-225.

Function Documentation

solve_hadlock_max_cut() [1/2]

template<typename Graph , typename WeightFunc >

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

Solve MAX-CUT using biconnected component decomposition for speed.

The graph is first decomposed into biconnected components (blocks). MAX-CUT is solved independently per block (each with its own faces), and the results are unioned. This is significantly faster because all-pairs shortest paths and MWPM are computed on smaller dual graphs.

Parameters

G	planar graph
weight	callable weight(u, v) -> int
component_faces	vector of face-lists, one per biconnected component. component_faces[i] is the list of face-boundary node sequences for the i-th biconnected component.

Returns

set of edges belonging to the maximum cut

solve_hadlock_max_cut() [2/2]

template<typename Graph , typename WeightFunc >

auto solve_hadlock_max_cut	(	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 planar graph using Hadlock's algorithm.

This overload processes the graph as-is (no decomposition).

Parameters

G	planar graph (must provide edges(), node type node_t)
weight	callable weight(u, v) -> int
faces	list of faces, each a cyclic node sequence

Returns

set of edges belonging to the maximum cut

validate_max_cut() [1/2]

template<typename Graph >

auto validate_max_cut	(	const Graph &	G,
		const py::set< std::pair< typename Graph::node_t, typename Graph::node_t > > &	cut_edges
	)		-> std::pair<bool, int>

validate_max_cut() [2/2]

template<typename Graph , typename WeightFunc >

auto validate_max_cut	(	const Graph &	G,
		const py::set< std::pair< typename Graph::node_t, typename Graph::node_t > > &	cut_edges,
		WeightFunc	weight
	)		-> std::pair<bool, int>