COIN-OR::LEMON - Graph Library

Changeset 2137:54043fa66bce in lemon-0.x


Ignore:
Timestamp:
07/14/06 12:25:26 (18 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2851
Message:

Using fixed bipartite graph

File:
1 edited

Legend:

Unmodified
Added
Removed
  • test/bipartite_matching_test.cc

    r2116 r2137  
    33#include <sstream>
    44
    5 #include <lemon/list_graph.h>
     5#include <lemon/smart_graph.h>
    66
    77#include <lemon/bpugraph_adaptor.h>
     
    1717using namespace lemon;
    1818
    19 typedef ListBpUGraph Graph;
     19typedef SmartBpUGraph Graph;
    2020BPUGRAPH_TYPEDEFS(Graph);
    2121
    22 int main(int argc, const char *argv[]) {
     22const int n = 10;
     23const int m = 10;
     24const int e = 52;
     25const int c = 100;
     26
     27const int sa[e] = { 6, 5, 6, 4, 1, 0, 9, 5, 2, 4, 4, 3, 5,
     28                    2, 3, 8, 3, 4, 9, 6, 9, 4, 3, 1, 5, 8,
     29                    4, 8, 9, 2, 2, 3, 0, 5, 2, 3, 6, 3, 8,
     30                    8, 4, 0, 9, 9, 6, 2, 1, 2, 7, 1, 9, 4};
     31
     32const int ta[e] = { 2, 7, 4, 8, 6, 3, 4, 1, 7, 7, 0, 1, 6,
     33                    3, 2, 6, 8, 3, 5, 6, 3, 1, 8, 7, 2, 0,
     34                    6, 9, 6, 7, 8, 3, 3, 4, 5, 8, 6, 4, 1,
     35                    4, 3, 3, 8, 7, 7, 3, 7, 7, 3, 5, 1, 6};
     36
     37const int wa[e] = { 3, 99, 85, 16, 79, 52, 83, 99, 62, 6, 42, 6, 95,
     38                    13, 34, 9, 5, 38, 39, 75, 99, 12, 73, 35, 93, 43,
     39                    54, 91, 45, 26, 77, 47, 11, 22, 50, 74, 37, 64, 91,
     40                    60, 6, 92, 29, 46, 34, 84, 67, 34, 45, 0, 39, 47};
     41
     42
     43int main() {
    2344  Graph graph;
    2445  vector<Node> aNodes;
    2546  vector<Node> bNodes;
    26   int n = argc > 1 ? atoi(argv[1]) : 10;
    27   int m = argc > 2 ? atoi(argv[2]) : 10;
    28   int e = argc > 3 ? atoi(argv[3]) : (int)((n+m) * log(n+m));
    29   int c = argc > 4 ? atoi(argv[4]) : 100;
    3047
    3148  Graph::UEdgeMap<int> weight(graph);
     
    4562  }
    4663  for (int i = 0; i < e; ++i) {
    47     Node aNode = aNodes[urandom(n)];
    48     Node bNode = bNodes[urandom(m)];
     64    Node aNode = aNodes[sa[i]];
     65    Node bNode = bNodes[ta[i]];
    4966    UEdge uedge = graph.addEdge(aNode, bNode);
    50     weight[uedge] = urandom(c);
    51   }
     67    weight[uedge] = wa[i];
     68  }
     69
    5270
    5371  {
     
    272290  Graph::UEdgeMap<int> cost(graph);
    273291  cost = subMap(constMap<UEdge>(c), weight);
    274 
    275292  {
    276293
     
    285302    bpmatch.potential(pm);
    286303   
    287     for (UEdgeIt it(graph); it != INVALID; ++it) {
    288       if (mm[it]) {
    289         check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] == 0,
    290               "INVALID DUAL");
    291       } else {
    292         check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] >= 0,
    293               "INVALID DUAL");
    294       }
    295     }
    296 
    297     for (ANodeIt it(graph); it != INVALID; ++it) {
    298       int num = 0;
    299       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
    300         if (mm[jt]) ++num;
    301     }
    302       check(num <= 1, "INVALID PRIMAL");
    303     }
    304 
    305304    min_cost_matching = bpmatch.matchingCost();
    306305    check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
     
    308307          == bpmatch.matchingCost(), "WRONG SIZE");
    309308
     309    for (UEdgeIt it(graph); it != INVALID; ++it) {
     310      if (mm[it]) {
     311        check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] == 0,
     312              "INVALID DUAL");
     313      } else {
     314        check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] >= 0,
     315              "INVALID DUAL");
     316      }
     317    }
     318
     319    for (ANodeIt it(graph); it != INVALID; ++it) {
     320      int num = 0;
     321      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
     322        if (mm[jt]) ++num;
     323    }
     324      check(num <= 1, "INVALID PRIMAL");
     325    }
     326
     327    min_cost_matching = bpmatch.matchingCost();
     328    check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
     329    check(max_cardinality * c - max_cardinality_max_weight
     330          == bpmatch.matchingCost(), "WRONG SIZE");
     331
    310332  }
    311333
Note: See TracChangeset for help on using the changeset viewer.