-
Notifications
You must be signed in to change notification settings - Fork 0
/
Matching.hpp
50 lines (43 loc) · 1.34 KB
/
Matching.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/*!
* \file Matching.h
* Matching algorithms
*/
#ifndef MATCHING_H
#define MATCHING_H
#include <list>
#include "Structures.h"
#include "Flow.h"
namespace sgl
{
/*! Computes the maximum matching cardinal using Fulkerson algorithm
\remarks The maximum matching cardinal is equal to the minimum vertex cover cardinal
\todo Output the edges of a maximum matching and the vertices of the minimum vertex cover */
template<typename type_flow = int, class Edge = Edge_Flow<type_flow>, class Bipartite = Bipartite_list<Edge> > class MaxMatching_Graph
{
public:
int s, t;
Bipartite &G;
/*! Construct the associated std::max flow problem
\param G: Bipartite graph, all edges must have capacity equals to one */
MaxMatching_Graph(Bipartite &G) : G(G)
{
s = G.V();
t = G.V() + 1;
G.resize(G.V() + 2); // on rajoute s et t
for(std::list<int>::iterator it = G.X.begin(); it != G.X.end(); ++it)
G.insert(new Edge(s, *it, 1));
for(std::list<int>::iterator it = G.Y.begin(); it != G.Y.end(); ++it)
G.insert(new Edge(*it, t, 1));
};
/*! \returns Maximum matching cardinal */
int operator()()
{
NoNullCap<Edge> proc(G.V(), t);
DFS<NoNullCap<Edge>, Edge, Bipartite> dfs(G, proc);
Fulkerson<type_flow, Edge, NoNullCap<Edge>, Bipartite, DFS<NoNullCap<Edge>, Edge, Bipartite> > ful(G, proc);
ful(s, t);
return ful.get_outflow(s);
}
};
}
#endif