一般グラフのマッチング（C++）

Memo C++

http://www.google.co.jp/url?sa=t&source=web&ct=res&cd=2&url=http%3A%2F%2Fwww.amazon.co.jp%2F%25E7%25B5%2584%25E5%2590%2588%25E3%2581%259B%25E6%259C%2580%25E9%2581%25A9%25E5%258C%2596-%25E7%2590%2586%25E8%25AB%2596%25E3%2581%25A8%25E3%2582%25A2%25E3%2583%25AB%25E3%2582%25B4%25E3%2583%25AA%25E3%2582%25BA%25E3%2583%25A0-B-%25E3%2582%25B3%25E3%2583%25AB%25E3%2583%2586%2Fdp%2F443171183X&ei=hK_ASpKQH5OWkAWT0qQd&usg=AFQjCNHdtcwDlIOoIJdKMLlN2ACyU9eHdg&sig2=ANpOVxP18-oZjU8KB99pKw
にのっているアルゴリズム．
をそのまま実装しただけ．
長くなってしまった．
奇閉路をきりだすのが結構メンドウ．
バグあるかも．

#include <iostream>
#include <vector>

using namespace std;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,c) for (__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define NODE(i,v,path) for (int i = 0, v = path[i]; v >= 0; v = path[++i])

const int N = 100;
int n, mu[N], phi[N], rho[N], pathX[N], pathY[N];
bool scan[N], visitX[N], visitY[N];
vector< vector<int> > neighbor(N, vector<int>());

inline bool even(int x) { return mu[x] == x || phi[mu[x]] != mu[x]; }
inline bool odd(int x) { return mu[x] != x && phi[mu[x]] == mu[x] && phi[x] != x; }
inline bool out(int x) { return mu[x] != x && phi[mu[x]] == mu[x] && phi[x] == x; }

bool scanAllEven(int &x) {
  for (; x < n; ++x) if ( !scan[x] && even(x) ) return false;
  return true;
}

bool adjacent(int x, int &y) {
  FOR(z,neighbor[x]) if (out(*z) || (even(*z) && rho[*z] != rho[x])) { y = *z; return true;}
  return false;
}

bool disjointPath(int x, int y, int &r) {
  REP(v,N) pathX[v] = pathY[v] = -1;
  REP(v,N) visitX[v] = visitY[v] = false;
  for (int i = 0, v = x; !visitX[v]; ++i) pathX[i] = v, visitX[v] = true, v = i%2 ? phi[v]: mu[v];
  for (int i = 0, v = y; !visitY[v]; ++i) pathY[i] = v, visitY[v] = true, v = i%2 ? phi[v]: mu[v];
  for (int i = 0; pathX[i] >= 0; ++i) {
    if (!visitY[pathX[i]]) continue;
    r = pathX[i];
    for (++i; pathX[i] >= 0; ++i) visitX[pathX[i]] = false, pathX[i] = -1;
    for (i=0; pathY[i] != r; ++i);
    for (++i; pathY[i] >= 0; ++i) visitY[pathY[i]] = false, pathY[i] = -1;
    return false;
  }
  return true;
}

void augment(int &x, int y) {
  NODE(i,v,pathX) if (i%2) mu[phi[v]] = v, mu[v] = phi[v];
  NODE(i,v,pathY) if (i%2) mu[phi[v]] = v, mu[v] = phi[v];
  mu[x] = y, mu[y] = x;
  REP(v,n) phi[v] = rho[v] = v, scan[v] = false;
}

void shrink(int x, int y, int r) {
  NODE(i,v,pathX) if (i%2 && rho[phi[v]] != r) phi[phi[v]] = v;
  NODE(i,v,pathY) if (i%2 && rho[phi[v]] != r) phi[phi[v]] = v;
  if (rho[x] != r) phi[x] = y;
  if (rho[y] != r) phi[y] = x;
  REP(v,n) if(visitX[rho[v]] || visitY[rho[v]]) rho[v] = r;
}

void matching() {
  REP(v,N)
    mu[v] = phi[v] = rho[v] = v, scan[v] = false;
  int x = 0, y ,r;
  while (!scanAllEven(x)) {
    if (!adjacent(x,y)) scan[x] = true, x = 0;
    else if (out(y)) phi[y] = x; // grow
    else if (disjointPath(x,y,r)) augment(x, y), x = 0;
    else shrink(x,y,r);
  }
}

こんなふうに使う．

int main() {
  n = 15;
  addEdge(1,2);
  addEdge(2,3);
  addEdge(2,13);
  addEdge(2,14);
  addEdge(3,4);
  addEdge(3,6);
  addEdge(4,5);
  addEdge(4,10);
  addEdge(5,8);
  addEdge(5,7);
  addEdge(6,7);
  addEdge(6,10);
  addEdge(8,9);
  addEdge(8,13);
  addEdge(8,14);
  addEdge(10,12);
  addEdge(11,12);
  cout << "#Graph#" << endl;
  REP(i,n) {
    cout << i << " -> " ;
    FOR(j,neighbor[i]) cout << *j << " ";
    cout << endl;
  }
  matching();
  cout << "#Matching#" << endl;
  REP(i,n) if (i < mu[i]) cout << i << " -- " << mu[i] << endl;
}

出力．

#Graph#
0 -> 
1 -> 2 
2 -> 1 3 13 14 
3 -> 2 4 6 
4 -> 3 5 10 
5 -> 4 8 7 
6 -> 3 7 10 
7 -> 5 6 
8 -> 5 9 13 14 
9 -> 8 
10 -> 4 6 12 
11 -> 12 
12 -> 10 11 
13 -> 2 8 
14 -> 2 8 
#Matching#
1 -- 2
3 -- 6
4 -- 10
5 -- 7
8 -- 9
11 -- 12