Blossom.H File Reference

Edmonds' Blossom algorithm for maximum matching in general graphs. More...

#include <ah-graph-concepts.H>
#include <cstdint>
#include <cstddef>
#include <cassert>
#include <functional>
#include <utility>
#include <cookie_guard.H>
#include <tpl_array.H>
#include <tpl_dynListQueue.H>
#include <tpl_dynMapTree.H>
#include <tpl_dynDlist.H>
#include <tpl_graph.H>
#include <ah-errors.H>

Include dependency graph for Blossom.H:

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

Go to the source code of this file.

Classes
class	Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >
class	Aleph::Compute_Maximum_Cardinality_General_Matching< GT, SA >
	Functor wrapper for maximum cardinality general matching. More...

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

Functions
template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>
size_t	Aleph::compute_maximum_cardinality_general_matching (const GT &g, DynDlist< typename GT::Arc * > &matching, SA sa=SA())
	Computes a maximum cardinality matching in a general graph.
template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>
size_t	Aleph::blossom_maximum_cardinality_matching (const GT &g, DynDlist< typename GT::Arc * > &matching, SA sa=SA())
	Alias of compute_maximum_cardinality_general_matching().

Detailed Description

Edmonds' Blossom algorithm for maximum matching in general graphs.

This file implements the classic Edmonds-Blossom algorithm for finding a maximum cardinality matching in an undirected graph.

Unlike bipartite matching, general graph matching must account for odd cycles. The algorithm identifies such cycles (called "blossoms") and contracts them into single super-nodes to find augmenting paths that would otherwise be hidden.

Complexity

Algorithm	Time	Space
Edmonds-Blossom	O(V^2 * E)	O(V + E)

Example

List_Graph<Node, Arc> g;
// ... add nodes and arcs ...
 
DynDlist<List_Graph<Node, Arc>::Arc*> matching;
size_t size = compute_maximum_cardinality_general_matching(g, matching);
// matching now contains the arcs of an optimal matching

Definition in file Blossom.H.