Collaboration diagram for Graph Algorithms:
![]() |
Files | |
file | max_matching.h |
Maximum matching algorithm. | |
Modules | |
General Graph Utilities | |
This group describes some simple general graph utilities. | |
Path and Flow Algorithms | |
This group describes the algorithms for finding paths and flows in graphs. | |
Minimum Cost Spanning Tree Algorithms | |
This group containes the algorithms for finding a minimum cost spanning tree in a graph. | |
Classes | |
class | MaxMatching |
Edmonds' alternating forest maximum matching algorithm. More... | |
Functions | |
void | lemon::MaxMatching::run () |
Runs Edmonds' algorithm. | |
void | lemon::MaxMatching::runEdmonds (int heur) |
Runs Edmonds' algorithm. | |
void | lemon::MaxMatching::greedyMatching () |
Finds a greedy matching starting from the actual matching. | |
int | lemon::MaxMatching::size () const |
Returns the size of the actual matching stored. | |
void | lemon::MaxMatching::resetMatching () |
Resets the actual matching to the empty matching. |
|
Runs Edmonds' algorithm for sparse graphs (number of edges < 2*number of nodes), and a heuristical Edmonds' algorithm with a heuristic of postponing shrinks for dense graphs. Definition at line 279 of file max_matching.h. |
Here is the call graph for this function:
|
If heur=0 it runs Edmonds' algorithm. If heur=1 it runs Edmonds' algorithm with a heuristic of postponing shrinks, giving a faster algorithm for dense graphs. Definition at line 288 of file max_matching.h. |
Here is the call graph for this function:
|
Starting form the actual matching stored, it finds a maximal greedy matching. Definition at line 452 of file max_matching.h. |
|
Returns the size of the actual matching stored. After run() it returns the size of a maximum matching in the graph. Definition at line 467 of file max_matching.h. |
|
Resets the actual matching to the empty matching. Definition at line 478 of file max_matching.h. |