test/gomory_hu_test.cc
changeset 750 b7e3662faf02
parent 546 d6b40ebb2617
child 877 141f9c0db4a3
child 1007 7e368d9b67f7
equal deleted inserted replaced
3:79a89ff956a2 4:536890415a48
     1 #include <iostream>
     1 #include <iostream>
     2 
     2 
     3 #include "test_tools.h"
     3 #include "test_tools.h"
     4 #include <lemon/smart_graph.h>
     4 #include <lemon/smart_graph.h>
       
     5 #include <lemon/concepts/graph.h>
       
     6 #include <lemon/concepts/maps.h>
     5 #include <lemon/lgf_reader.h>
     7 #include <lemon/lgf_reader.h>
     6 #include <lemon/gomory_hu.h>
     8 #include <lemon/gomory_hu.h>
     7 #include <cstdlib>
     9 #include <cstdlib>
     8 
    10 
     9 using namespace std;
    11 using namespace std;
    30   "4 2  7     1\n"
    32   "4 2  7     1\n"
    31   "@attributes\n"
    33   "@attributes\n"
    32   "source 0\n"
    34   "source 0\n"
    33   "target 3\n";
    35   "target 3\n";
    34   
    36   
       
    37 void checkGomoryHuCompile()
       
    38 {
       
    39   typedef int Value;
       
    40   typedef concepts::Graph Graph;
       
    41 
       
    42   typedef Graph::Node Node;
       
    43   typedef Graph::Edge Edge;
       
    44   typedef concepts::ReadMap<Edge, Value> CapMap;
       
    45   typedef concepts::ReadWriteMap<Node, bool> CutMap;
       
    46 
       
    47   Graph g;
       
    48   Node n;
       
    49   CapMap cap;
       
    50   CutMap cut;
       
    51   Value v;
       
    52   int d;
       
    53 
       
    54   GomoryHu<Graph, CapMap> gh_test(g, cap);
       
    55   const GomoryHu<Graph, CapMap>&
       
    56     const_gh_test = gh_test;
       
    57 
       
    58   gh_test.run();
       
    59 
       
    60   n = const_gh_test.predNode(n);
       
    61   v = const_gh_test.predValue(n);
       
    62   d = const_gh_test.rootDist(n);
       
    63   v = const_gh_test.minCutValue(n, n);
       
    64   v = const_gh_test.minCutMap(n, n, cut);
       
    65 }
       
    66 
    35 GRAPH_TYPEDEFS(Graph);
    67 GRAPH_TYPEDEFS(Graph);
    36 typedef Graph::EdgeMap<int> IntEdgeMap;
    68 typedef Graph::EdgeMap<int> IntEdgeMap;
    37 typedef Graph::NodeMap<bool> BoolNodeMap;
    69 typedef Graph::NodeMap<bool> BoolNodeMap;
    38 
    70 
    39 int cutValue(const Graph& graph, const BoolNodeMap& cut,
    71 int cutValue(const Graph& graph, const BoolNodeMap& cut,
    68       Preflow<Graph, IntEdgeMap> pf(graph, capacity, u, v);
   100       Preflow<Graph, IntEdgeMap> pf(graph, capacity, u, v);
    69       pf.runMinCut();
   101       pf.runMinCut();
    70       BoolNodeMap cm(graph);
   102       BoolNodeMap cm(graph);
    71       ght.minCutMap(u, v, cm);
   103       ght.minCutMap(u, v, cm);
    72       check(pf.flowValue() == ght.minCutValue(u, v), "Wrong cut 1");
   104       check(pf.flowValue() == ght.minCutValue(u, v), "Wrong cut 1");
    73       check(cm[u] != cm[v], "Wrong cut 3");
   105       check(cm[u] != cm[v], "Wrong cut 2");
    74       check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 2");
   106       check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 3");
    75 
   107 
    76       int sum=0;
   108       int sum=0;
    77       for(GomoryHu<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a)
   109       for(GomoryHu<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a)
    78         sum+=capacity[a]; 
   110         sum+=capacity[a]; 
    79       check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt");
   111       check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt");
    82       for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n)
   114       for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n)
    83         sum++;
   115         sum++;
    84       for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n)
   116       for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n)
    85         sum++;
   117         sum++;
    86       check(sum == countNodes(graph), "Problem with MinCutNodeIt");
   118       check(sum == countNodes(graph), "Problem with MinCutNodeIt");
    87       
       
    88     }
   119     }
    89   }
   120   }
    90   
   121   
    91   return 0;
   122   return 0;
    92 }
   123 }