Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
Public Types | Public Member Functions | Private Types | Private Member Functions | Static Private Member Functions | Private Attributes | Static Private Attributes | List of all members
Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA > Class Template Reference

#include <Blossom.H>

Collaboration diagram for Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >:
[legend]

Public Types

using Node = typename GT::Node
 
using Arc = typename GT::Arc
 

Public Member Functions

 Edmonds_Blossom_Matcher (const GT &graph, SA __sa=SA())
 Initialize the matcher with a graph and an optional filter.
 
size_t solve ()
 Execute the matching algorithm.
 
const Array< long > & get_match_vector () const noexcept
 Returns the match vector (mate of each node index).
 
Arc * get_pair_arc (size_t u, size_t v) const noexcept
 Returns the arc connecting node indices u and v.
 

Private Types

using Pair_Key = std::pair< size_t, size_t >
 

Private Member Functions

void build_node_index ()
 Index nodes from 0 to n-1 and set up the cookie-based mapping.
 
void build_adjacency ()
 Build a simplified adjacency list for faster traversal.
 
size_t lca (size_t a, size_t b) const
 Find the lowest common ancestor of two nodes in the alternating tree.
 
void mark_path (size_t v, const size_t blossom_base, size_t child)
 Mark the path from v to the blossom base and set up parents.
 
void clear_queue ()
 
long find_augmenting_path (const size_t root)
 Search for an augmenting path starting from root.
 
void augment_matching (const long endpoint)
 Augment the matching along the path ending at endpoint.
 

Static Private Member Functions

static Pair_Key normalized_pair (size_t u, size_t v) noexcept
 

Private Attributes

const GT & g
 
SA sa
 
Cookie_Saver< GT > cookie_saver
 
Array< Node * > nodes
 
Array< Array< size_t > > adjacency
 
DynMapTree< Pair_Key, Arc * > pair_to_arc
 
Array< long > match
 
Array< long > parent
 
Array< long > base
 
Array< char > in_queue
 
Array< char > in_blossom
 
DynListQueue< size_t > bfs_queue
 

Static Private Attributes

static constexpr long No_Vertex = -1
 

Detailed Description

template<class GT, class SA>
class Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >

Definition at line 99 of file Blossom.H.

Member Typedef Documentation

◆ Arc

template<class GT , class SA >
using Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::Arc = typename GT::Arc

Definition at line 103 of file Blossom.H.

◆ Node

template<class GT , class SA >
using Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::Node = typename GT::Node

Definition at line 102 of file Blossom.H.

◆ Pair_Key

template<class GT , class SA >
using Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::Pair_Key = std::pair<size_t, size_t>
private

Definition at line 106 of file Blossom.H.

Constructor & Destructor Documentation

◆ Edmonds_Blossom_Matcher()

template<class GT , class SA >
Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::Edmonds_Blossom_Matcher ( const GT &  graph,
SA  __sa = SA() 
)
inlineexplicit

Initialize the matcher with a graph and an optional filter.

Definition at line 334 of file Blossom.H.

References Aleph::Array< T >::append(), Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::base, Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::build_adjacency(), Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::build_node_index(), Aleph::Array< T >::empty(), Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::in_blossom, Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::in_queue, Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::match, Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::No_Vertex, Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::nodes, Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::parent, Aleph::Array< T >::reserve(), and Aleph::Array< T >::size().

Member Function Documentation

◆ augment_matching()

template<class GT , class SA >
void Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::augment_matching ( const long  endpoint)
inlineprivate

Augment the matching along the path ending at endpoint.

Definition at line 316 of file Blossom.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::match, Aleph::next(), Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::No_Vertex, and Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::parent.

Referenced by Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::solve().

◆ build_adjacency()

template<class GT , class SA >
void Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::build_adjacency ( )
inlineprivate

Build a simplified adjacency list for faster traversal.

Definition at line 149 of file Blossom.H.

References Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::adjacency, Aleph::divide_and_conquer_partition_dp(), Aleph::DynSetTree< Key, Tree, Compare >::empty(), Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::g, GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::DynMapTree< Key, Data, Tree, Compare >::insert(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), NODE_COOKIE, Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::nodes, Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::normalized_pair(), Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::pair_to_arc, Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::sa, Aleph::DynMapTree< Key, Data, Tree, Compare >::search(), and Aleph::Array< T >::size().

Referenced by Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::Edmonds_Blossom_Matcher().

◆ build_node_index()

template<class GT , class SA >
void Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::build_node_index ( )
inlineprivate

Index nodes from 0 to n-1 and set up the cookie-based mapping.

Definition at line 133 of file Blossom.H.

References Aleph::Array< T >::append(), Aleph::Array< T >::empty(), Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::g, GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), NODE_COOKIE, Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::nodes, and Aleph::Array< T >::reserve().

Referenced by Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::Edmonds_Blossom_Matcher().

◆ clear_queue()

template<class GT , class SA >
void Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::clear_queue ( )
inlineprivate

Definition at line 239 of file Blossom.H.

References Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::bfs_queue, and Aleph::DynListQueue< T >::clear().

Referenced by Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::find_augmenting_path().

◆ find_augmenting_path()

template<class GT , class SA >
long Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::find_augmenting_path ( const size_t  root)
inlineprivate

Search for an augmenting path starting from root.

If a blossom is encountered, it is contracted.

Returns
The endpoint node ID of the augmenting path, or No_Vertex.

Definition at line 250 of file Blossom.H.

References Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::adjacency, Aleph::and, Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::base, Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::bfs_queue, Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::clear_queue(), Aleph::divide_and_conquer_partition_dp(), Aleph::DynListQueue< T >::get(), Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::in_blossom, Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::in_queue, Aleph::DynListQueue< T >::is_empty(), Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::lca(), m, Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::mark_path(), Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::match, Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::No_Vertex, Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::nodes, Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::parent, Aleph::DynListQueue< T >::put(), root(), and Aleph::Array< T >::size().

Referenced by Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::solve().

◆ get_match_vector()

template<class GT , class SA >
const Array< long > & Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::get_match_vector ( ) const
inlinenoexcept

Returns the match vector (mate of each node index).

Definition at line 390 of file Blossom.H.

References Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::match.

◆ get_pair_arc()

template<class GT , class SA >
Arc * Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::get_pair_arc ( size_t  u,
size_t  v 
) const
inlinenoexcept

Returns the arc connecting node indices u and v.

Definition at line 396 of file Blossom.H.

References Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::normalized_pair(), Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::pair_to_arc, and Aleph::DynMapTree< Key, Data, Tree, Compare >::search().

◆ lca()

template<class GT , class SA >
size_t Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::lca ( size_t  a,
size_t  b 
) const
inlineprivate

Find the lowest common ancestor of two nodes in the alternating tree.

Used to find the base of a new blossom.

Definition at line 195 of file Blossom.H.

References Aleph::and, Aleph::Array< T >::append(), Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::base, Aleph::divide_and_conquer_partition_dp(), Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::match, Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::No_Vertex, Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::nodes, Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::parent, Aleph::Array< T >::reserve(), and Aleph::Array< T >::size().

Referenced by Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::find_augmenting_path().

◆ mark_path()

template<class GT , class SA >
void Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::mark_path ( size_t  v,
const size_t  blossom_base,
size_t  child 
)
inlineprivate

Mark the path from v to the blossom base and set up parents.

Definition at line 226 of file Blossom.H.

References Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::base, Aleph::divide_and_conquer_partition_dp(), Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::in_blossom, Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::match, and Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::parent.

Referenced by Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::find_augmenting_path().

◆ normalized_pair()

template<class GT , class SA >
static Pair_Key Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::normalized_pair ( size_t  u,
size_t  v 
)
inlinestaticprivatenoexcept

Definition at line 125 of file Blossom.H.

Referenced by Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::build_adjacency(), and Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::get_pair_arc().

◆ solve()

template<class GT , class SA >
size_t Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::solve ( )
inline

Execute the matching algorithm.

Iteratively finds augmenting paths until no more can be found.

Returns
Total cardinality of the matching.

Definition at line 367 of file Blossom.H.

References Aleph::and, Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::augment_matching(), Aleph::divide_and_conquer_partition_dp(), Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::find_augmenting_path(), Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::match, Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::No_Vertex, Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::nodes, and Aleph::Array< T >::size().

Member Data Documentation

◆ adjacency

template<class GT , class SA >
Array<Array<size_t> > Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::adjacency
private

Definition at line 115 of file Blossom.H.

Referenced by Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::build_adjacency(), and Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::find_augmenting_path().

◆ base

template<class GT , class SA >
Array<long> Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::base
private

Definition at line 120 of file Blossom.H.

Referenced by Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::Edmonds_Blossom_Matcher(), Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::find_augmenting_path(), Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::lca(), and Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::mark_path().

◆ bfs_queue

template<class GT , class SA >
DynListQueue<size_t> Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::bfs_queue
private

Definition at line 123 of file Blossom.H.

Referenced by Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::clear_queue(), and Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::find_augmenting_path().

◆ cookie_saver

template<class GT , class SA >
Cookie_Saver<GT> Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::cookie_saver
private

Definition at line 112 of file Blossom.H.

◆ g

template<class GT , class SA >
const GT& Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::g
private

Definition at line 110 of file Blossom.H.

Referenced by Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::build_adjacency(), and Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::build_node_index().

◆ in_blossom

template<class GT , class SA >
Array<char> Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::in_blossom
private

Definition at line 122 of file Blossom.H.

Referenced by Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::Edmonds_Blossom_Matcher(), Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::find_augmenting_path(), and Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::mark_path().

◆ in_queue

template<class GT , class SA >
Array<char> Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::in_queue
private

Definition at line 121 of file Blossom.H.

Referenced by Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::Edmonds_Blossom_Matcher(), and Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::find_augmenting_path().

◆ match

template<class GT , class SA >
Array<long> Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::match
private

Definition at line 118 of file Blossom.H.

Referenced by Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::Edmonds_Blossom_Matcher(), Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::augment_matching(), Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::find_augmenting_path(), Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::get_match_vector(), Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::lca(), Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::mark_path(), and Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::solve().

◆ No_Vertex

template<class GT , class SA >
constexpr long Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::No_Vertex = -1
staticconstexprprivate

Definition at line 108 of file Blossom.H.

Referenced by Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::Edmonds_Blossom_Matcher(), Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::augment_matching(), Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::find_augmenting_path(), Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::lca(), and Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::solve().

◆ nodes

template<class GT , class SA >
Array<Node *> Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::nodes
private

Definition at line 114 of file Blossom.H.

Referenced by Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::Edmonds_Blossom_Matcher(), Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::build_adjacency(), Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::build_node_index(), Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::find_augmenting_path(), Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::lca(), and Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::solve().

◆ pair_to_arc

template<class GT , class SA >
DynMapTree<Pair_Key, Arc *> Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::pair_to_arc
private

Definition at line 116 of file Blossom.H.

Referenced by Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::build_adjacency(), and Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::get_pair_arc().

◆ parent

template<class GT , class SA >
Array<long> Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::parent
private

Definition at line 119 of file Blossom.H.

Referenced by Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::Edmonds_Blossom_Matcher(), Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::augment_matching(), Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::find_augmenting_path(), Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::lca(), and Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::mark_path().

◆ sa

template<class GT , class SA >
SA Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::sa
private

Definition at line 111 of file Blossom.H.

Referenced by Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::build_adjacency().

The documentation for this class was generated from the following file: