#include <lemon/bipartite_matching.h>
Public Member Functions | |
MaxBipartiteMatching (const BpUGraph &_graph) | |
Constructor. | |
Execution control | |
The simplest way to execute the algorithm is to use one of the member functions called run() . If you need more control on the execution, first you must call init() or one alternative for it. Finally start() will perform the matching computation or with step-by-step execution you can augment the solution. | |
void | init () |
Initalize the data structures. | |
void | greedyInit () |
Initalize the data structures. | |
template<typename MatchingMap> | |
void | matchingInit (const MatchingMap &matching) |
Initalize the data structures with an initial matching. | |
template<typename MatchingMap> | |
void | checkedMatchingInit (const MatchingMap &matching) |
Initalize the data structures with an initial matching. | |
bool | augment () |
An augmenting phase of the Hopcroft-Karp algorithm. | |
bool | simpleAugment () |
An augmenting phase of the Ford-Fulkerson algorithm. | |
void | start () |
Starts the algorithm. | |
void | run () |
Runs the algorithm. | |
Query Functions | |
The result of the Matching algorithm can be obtained using these functions. Before the use of these functions, either run() or start() must be called. | |
template<typename CoverMap> | |
int | coverSet (CoverMap &covering) const |
Returns an minimum covering of the nodes. | |
template<typename MatchingMap> | |
int | quickMatching (MatchingMap &matching) const |
Set true all matching uedge in the map. | |
template<typename MatchingMap> | |
int | matching (MatchingMap &matching) const |
Set true all matching uedge in the map and the others to false. | |
bool | matchingEdge (const UEdge &edge) const |
Return true if the given uedge is in the matching. | |
UEdge | matchingEdge (const Node &node) const |
Returns the matching edge from the node. | |
int | matchingSize () const |
Gives back the number of the matching edges. |
MaxBipartiteMatching | ( | const BpUGraph & | _graph | ) | [inline] |
Constructor of the algorithm.
void init | ( | ) | [inline] |
It initalizes the data structures and creates an empty matching.
void greedyInit | ( | ) | [inline] |
It initalizes the data structures and creates a greedy matching. From this matching sometimes it is faster to get the matching than from the initial empty matching.
void matchingInit | ( | const MatchingMap & | matching | ) | [inline] |
It initalizes the data structures with an initial matching.
void checkedMatchingInit | ( | const MatchingMap & | matching | ) | [inline] |
It initalizes the data structures with an initial matching.
bool augment | ( | ) | [inline] |
It runs an augmenting phase of the Hopcroft-Karp algorithm. The phase finds maximum count of edge disjoint augmenting paths and augments on these paths. The algorithm consists at most of phase and one phase is
long.
bool simpleAugment | ( | ) | [inline] |
It runs an augmenting phase of the Ford-Fulkerson algorithm. The phase finds only one augmenting path and augments only on this paths. The algorithm consists at most of simple phase and one phase is at most
long.
void start | ( | ) | [inline] |
Starts the algorithm. It runs augmenting phases until the optimal solution reached.
void run | ( | ) | [inline] |
It just initalize the algorithm and then start it.
int coverSet | ( | CoverMap & | covering | ) | const [inline] |
The minimum covering set problem is the dual solution of the maximum bipartite matching. It provides an solution for this problem what is proof of the optimality of the matching.
int quickMatching | ( | MatchingMap & | matching | ) | const [inline] |
Set true all matching uedge in the map. It does not change the value mapped to the other uedges.
int matching | ( | MatchingMap & | matching | ) | const [inline] |
Set true all matching uedge in the map and the others to false.
bool matchingEdge | ( | const UEdge & | edge | ) | const [inline] |
It returns true if the given uedge is in the matching.
UEdge matchingEdge | ( | const Node & | node | ) | const [inline] |
Returns the matching edge from the node. If there is not such edge it gives back INVALID
.
int matchingSize | ( | ) | const [inline] |
Gives back the number of the matching edges.