test/gomory_hu_test.cc
changeset 974 b1744d7bdb47
parent 596 293551ad254f
child 1008 d216e1c8b3fa
equal deleted inserted replaced
4:536890415a48 5:84e3f8a84c6c
       
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
       
     2  *
       
     3  * This file is a part of LEMON, a generic C++ optimization library.
       
     4  *
       
     5  * Copyright (C) 2003-2010
       
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
       
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
       
     8  *
       
     9  * Permission to use, modify and distribute this software is granted
       
    10  * provided that this copyright notice appears in all copies. For
       
    11  * precise terms see the accompanying LICENSE file.
       
    12  *
       
    13  * This software is provided "AS IS" with no warranty of any kind,
       
    14  * express or implied, and with no claim as to its suitability for any
       
    15  * purpose.
       
    16  *
       
    17  */
       
    18 
     1 #include <iostream>
    19 #include <iostream>
     2 
    20 
     3 #include "test_tools.h"
    21 #include "test_tools.h"
     4 #include <lemon/smart_graph.h>
    22 #include <lemon/smart_graph.h>
     5 #include <lemon/concepts/graph.h>
    23 #include <lemon/concepts/graph.h>
    31   "0 3  6     7\n"
    49   "0 3  6     7\n"
    32   "4 2  7     1\n"
    50   "4 2  7     1\n"
    33   "@attributes\n"
    51   "@attributes\n"
    34   "source 0\n"
    52   "source 0\n"
    35   "target 3\n";
    53   "target 3\n";
    36   
    54 
    37 void checkGomoryHuCompile()
    55 void checkGomoryHuCompile()
    38 {
    56 {
    39   typedef int Value;
    57   typedef int Value;
    40   typedef concepts::Graph Graph;
    58   typedef concepts::Graph Graph;
    41 
    59 
    67 GRAPH_TYPEDEFS(Graph);
    85 GRAPH_TYPEDEFS(Graph);
    68 typedef Graph::EdgeMap<int> IntEdgeMap;
    86 typedef Graph::EdgeMap<int> IntEdgeMap;
    69 typedef Graph::NodeMap<bool> BoolNodeMap;
    87 typedef Graph::NodeMap<bool> BoolNodeMap;
    70 
    88 
    71 int cutValue(const Graph& graph, const BoolNodeMap& cut,
    89 int cutValue(const Graph& graph, const BoolNodeMap& cut,
    72 	     const IntEdgeMap& capacity) {
    90              const IntEdgeMap& capacity) {
    73 
    91 
    74   int sum = 0;
    92   int sum = 0;
    75   for (EdgeIt e(graph); e != INVALID; ++e) {
    93   for (EdgeIt e(graph); e != INVALID; ++e) {
    76     Node s = graph.u(e);
    94     Node s = graph.u(e);
    77     Node t = graph.v(e);
    95     Node t = graph.v(e);
   105       check(cm[u] != cm[v], "Wrong cut 2");
   123       check(cm[u] != cm[v], "Wrong cut 2");
   106       check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 3");
   124       check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 3");
   107 
   125 
   108       int sum=0;
   126       int sum=0;
   109       for(GomoryHu<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a)
   127       for(GomoryHu<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a)
   110         sum+=capacity[a]; 
   128         sum+=capacity[a];
   111       check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt");
   129       check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt");
   112 
   130 
   113       sum=0;
   131       sum=0;
   114       for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n)
   132       for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n)
   115         sum++;
   133         sum++;
   116       for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n)
   134       for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n)
   117         sum++;
   135         sum++;
   118       check(sum == countNodes(graph), "Problem with MinCutNodeIt");
   136       check(sum == countNodes(graph), "Problem with MinCutNodeIt");
   119     }
   137     }
   120   }
   138   }
   121   
   139 
   122   return 0;
   140   return 0;
   123 }
   141 }