Blossom_Weighted.H File Reference

Maximum-weight matching in general undirected graphs. More...

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <limits>
#include <type_traits>
#include <utility>
#include <ah-errors.H>
#include <ahSort.H>
#include <cookie_guard.H>
#include <tpl_array.H>
#include <tpl_dynDlist.H>
#include <tpl_graph.H>
#include <tpl_graph_utils.H>
#include <blossom_weighted_mwmatching.H>

Include dependency graph for Blossom_Weighted.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	Aleph::Blossom_Weighted_Result< Weight_Type >
	Result of weighted matching. More...
class	Aleph::Compute_Maximum_Weight_General_Matching< GT, Weight, SA >
	Functor wrapper for weighted blossom matching. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.
namespace	Aleph::blossom_weighted_detail

Functions
template<typename T >
long long	Aleph::blossom_weighted_detail::to_ll_checked (T value)
template<class GT , class Weight = Dft_Dist<GT>, class SA = Dft_Show_Arc<GT>>
Blossom_Weighted_Result< long long >	Aleph::compute_maximum_weight_general_matching (const GT &g, DynDlist< typename GT::Arc * > &matching, Weight weight=Weight(), SA sa=SA(), const bool max_cardinality=false)
	Compute maximum-weight matching in a general undirected graph.
template<class GT , class Weight = Dft_Dist<GT>, class SA = Dft_Show_Arc<GT>>
Blossom_Weighted_Result< long long >	Aleph::blossom_maximum_weight_matching (const GT &g, DynDlist< typename GT::Arc * > &matching, Weight weight=Weight(), SA sa=SA(), const bool max_cardinality=false)
	Alias for compute_maximum_weight_general_matching().

Detailed Description

Maximum-weight matching in general undirected graphs.

This header provides an Edmonds-blossom based solver for maximum-weight matching in non-bipartite graphs.

Problem solved

Given an undirected graph \(G=(V,E)\) where each edge \(e \in E\) has a weight \(w(e)\), find a matching \(M\) such that \(\sum_{e \in M} w(e)\) is maximized.

Highlights

• Works on all Aleph graph backends (List_Graph, List_SGraph, Array_Graph)
• Supports arc filters
• Optional maximum-cardinality mode (maximize cardinality first, then weight)
• Validated with exhaustive oracle-backed tests across all three Aleph graph backends (Tests/weighted_blossom_test.cc)

Complexity

• Time: \(O(V^3)\)
• Space: \(O(V + E)\)

Weight model

• The default weight accessor is Dft_Dist<GT>.
• Current Aleph wrapper uses integral weights (long long).

Example

using G = List_Graph<Graph_Node<int>, Graph_Arc<int>>;
G g;
// ... build a weighted graph ...
DynDlist<G::Arc*> matching;
auto res = blossom_maximum_weight_matching(g, matching);
 
std::cout << "Matching weight: " << res.total_weight << "\n";
std::cout << "Matching size: " << res.cardinality << "\n";

See also

Blossom.H For maximum-cardinality (unweighted) matching

Definition in file Blossom_Weighted.H.