source: lemon-0.x/test/bipartite_matching_test.cc @ 2078:123f08422c14

#include <cstdlib>
#include <iostream>
#include <sstream>

#include <lemon/list_graph.h>

#include <lemon/bpugraph_adaptor.h>
#include <lemon/bipartite_matching.h>

#include <lemon/graph_utils.h>

#include <lemon/maps.h>

#include "test_tools.h"

using namespace std;
using namespace lemon;

typedef ListBpUGraph Graph;
BPUGRAPH_TYPEDEFS(Graph);

int main(int argc, const char *argv[]) {
  Graph graph;
  vector<Node> aNodes;
  vector<Node> bNodes;
  int n = argc > 1 ? atoi(argv[1]) : 10;
  int m = argc > 2 ? atoi(argv[2]) : 10;
  int e = argc > 3 ? atoi(argv[3]) : (int)((n+m) * log(n+m));
  int c = argc > 4 ? atoi(argv[4]) : 100;

  Graph::UEdgeMap<int> weight(graph);

  int max_cardinality;
  int max_weight;
  int max_cardinality_max_weight;
  int min_cost_matching;

  for (int i = 0; i < n; ++i) {
    Node node = graph.addANode();
    aNodes.push_back(node);
  }
  for (int i = 0; i < m; ++i) {
    Node node = graph.addBNode();
    bNodes.push_back(node);
  }
  for (int i = 0; i < e; ++i) {
    Node aNode = aNodes[urandom(n)];
    Node bNode = bNodes[urandom(m)];
    UEdge uedge = graph.addEdge(aNode, bNode);
    weight[uedge] = urandom(c);
  }

  {
    MaxBipartiteMatching<Graph> bpmatch(graph);

    bpmatch.run();

    Graph::UEdgeMap<bool> mm(graph);
    Graph::NodeMap<bool> cs(graph);
    
    check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
    
    for (UEdgeIt it(graph); it != INVALID; ++it) {
      check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
    }
    
    for (ANodeIt it(graph); it != INVALID; ++it) {
      int num = 0;
      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
        if (mm[jt]) ++num;
      }
      check(num <= 1, "INVALID PRIMAL");
    }
    max_cardinality = bpmatch.matchingSize();
  }

  {
    Graph::UEdgeMap<bool> mm(graph);

    check(max_cardinality == maxBipartiteMatching(graph, mm),
          "WRONG MATCHING");
    
    for (ANodeIt it(graph); it != INVALID; ++it) {
      int num = 0;
      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
        if (mm[jt]) ++num;
      }
      check(num <= 1, "INVALID PRIMAL");
    }
  }

  {
    MaxBipartiteMatching<Graph> bpmatch(graph);

    bpmatch.greedyInit();
    bpmatch.start();

    Graph::UEdgeMap<bool> mm(graph);
    Graph::NodeMap<bool> cs(graph);

    check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
    
    for (UEdgeIt it(graph); it != INVALID; ++it) {
      check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
    }
    
    for (ANodeIt it(graph); it != INVALID; ++it) {
      int num = 0;
      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
        if (mm[jt]) ++num;
    }
      check(num <= 1, "INVALID PRIMAL");
    }
  }

  {
    MaxBipartiteMatching<Graph> bpmatch(graph);

    bpmatch.greedyInit();
    while (bpmatch.simpleAugment());
    
    Graph::UEdgeMap<bool> mm(graph);
    Graph::NodeMap<bool> cs(graph);
    
    check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
    
    for (UEdgeIt it(graph); it != INVALID; ++it) {
      check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
    }
    
    for (ANodeIt it(graph); it != INVALID; ++it) {
      int num = 0;
      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
        if (mm[jt]) ++num;
    }
      check(num <= 1, "INVALID PRIMAL");
    }
  }

  {
    MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);

    bpmatch.init();

    max_weight = 0;
    while (bpmatch.augment(true)) {
    
      Graph::UEdgeMap<bool> mm(graph);
      Graph::NodeMap<int> pm(graph);
      
      bpmatch.matching(mm);
      bpmatch.potential(pm);
      
      for (UEdgeIt it(graph); it != INVALID; ++it) {
        if (mm[it]) {
          check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
                "INVALID DUAL");
        } else {
          check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
                "INVALID DUAL");
        }
      }

      for (ANodeIt it(graph); it != INVALID; ++it) {
        int num = 0;
        for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
          if (mm[jt]) ++num;
        }
        check(num <= 1, "INVALID PRIMAL");
      }
      if (bpmatch.matchingValue() > max_weight) {
        max_weight = bpmatch.matchingValue();
      }
    }
  }

  {
    Graph::UEdgeMap<bool> mm(graph);

    check(max_weight == maxWeightedBipartiteMatching(graph, weight, mm),
          "WRONG MATCHING");
    
    for (ANodeIt it(graph); it != INVALID; ++it) {
      int num = 0;
      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
        if (mm[jt]) ++num;
      }
      check(num <= 1, "INVALID PRIMAL");
    }
  }

  {
    MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);

    bpmatch.run();
    
    Graph::UEdgeMap<bool> mm(graph);
    Graph::NodeMap<int> pm(graph);

    bpmatch.matching(mm);
    bpmatch.potential(pm);
    
    for (UEdgeIt it(graph); it != INVALID; ++it) {
      if (mm[it]) {
        check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
              "INVALID DUAL");
      } else {
        check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
              "INVALID DUAL");
      }
    }

    for (ANodeIt it(graph); it != INVALID; ++it) {
      int num = 0;
      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
        if (mm[jt]) ++num;
    }
      check(num <= 1, "INVALID PRIMAL");
    }
    check(max_weight == bpmatch.matchingValue(), "WRONG WEIGHT");
  }

  {
    MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);

    bpmatch.run(true);
    
    Graph::UEdgeMap<bool> mm(graph);
    Graph::NodeMap<int> pm(graph);

    bpmatch.matching(mm);
    bpmatch.potential(pm);
    
    for (UEdgeIt it(graph); it != INVALID; ++it) {
      if (mm[it]) {
        check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
              "INVALID DUAL");
      } else {
        check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
              "INVALID DUAL");
      }
    }

    for (ANodeIt it(graph); it != INVALID; ++it) {
      int num = 0;
      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
        if (mm[jt]) ++num;
    }
      check(num <= 1, "INVALID PRIMAL");
    }
    check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
    max_cardinality_max_weight = bpmatch.matchingValue();

  }

  {
    Graph::UEdgeMap<bool> mm(graph);

    check(max_cardinality_max_weight == 
          maxWeightedMaxBipartiteMatching(graph, weight, mm),
          "WRONG MATCHING");
    
    for (ANodeIt it(graph); it != INVALID; ++it) {
      int num = 0;
      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
        if (mm[jt]) ++num;
      }
      check(num <= 1, "INVALID PRIMAL");
    }
  }

  Graph::UEdgeMap<int> cost(graph);
  cost = subMap(constMap<UEdge>(c), weight);

  {

    MinCostMaxBipartiteMatching<Graph> bpmatch(graph, cost);

    bpmatch.run();
    
    Graph::UEdgeMap<bool> mm(graph);
    Graph::NodeMap<int> pm(graph);

    bpmatch.matching(mm);
    bpmatch.potential(pm);
    
    for (UEdgeIt it(graph); it != INVALID; ++it) {
      if (mm[it]) {
        check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] == 0,
              "INVALID DUAL");
      } else {
        check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] >= 0,
              "INVALID DUAL");
      }
    }

    for (ANodeIt it(graph); it != INVALID; ++it) {
      int num = 0;
      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
        if (mm[jt]) ++num;
    }
      check(num <= 1, "INVALID PRIMAL");
    }

    min_cost_matching = bpmatch.matchingCost();
    check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
    check(max_cardinality * c - max_cardinality_max_weight 
          == bpmatch.matchingCost(), "WRONG SIZE");

  }

  {
    Graph::UEdgeMap<bool> mm(graph);

    check(min_cost_matching == 
          minCostMaxBipartiteMatching(graph, cost, mm),
          "WRONG MATCHING");
    
    for (ANodeIt it(graph); it != INVALID; ++it) {
      int num = 0;
      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
        if (mm[jt]) ++num;
      }
      check(num <= 1, "INVALID PRIMAL");
    }
  }

  return 0;
}