Blossom.H File Reference

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

#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<class GT , class 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<class GT , class 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 maximum cardinality matching in undirected graphs.

Problem solved

Given an undirected graph \(G=(V,E)\), find a matching of maximum cardinality, where a matching is a set of arcs with no shared endpoint.

Highlights

• Works on general (non-bipartite) graphs
• Handles odd cycles through blossom contraction
• Supports all Aleph graph backends through the generic graph interface (List_Graph, List_SGraph, Array_Graph)
• Can be filtered with Aleph arc filters

Complexity

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

See also

tpl_bipartite.H For bipartite matching algorithms

Hungarian.H For assignment problem matching

Author

Leandro Rabindranath León

Definition in file Blossom.H.