Files @ r807:83ce7ce39f21

Location: LEMON/LEMON-official/test/gomory_hu_test.cc

Load file history 
r807:83ce7ce39f21
2.7 KiB
text/x-c++src
Show annotation Show as raw Download as raw
gravatar
kpeter (Peter Kovacs)
Rework and fix the implementation of MinMeanCycle (#179) - Fix the handling of the cycle means. - Many implementation improvements: - More efficient data storage for the strongly connected components. - Better handling of BFS queues. - Merge consecutive BFS searches (perform two BFS searches instead of three). This version is about two times faster on average and an order of magnitude faster if there are a lot of strongly connected components.
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <iostream>



#include "test_tools.h"

#include <lemon/smart_graph.h>

#include <lemon/concepts/graph.h>

#include <lemon/concepts/maps.h>

#include <lemon/lgf_reader.h>

#include <lemon/gomory_hu.h>

#include <cstdlib>



using namespace std;

using namespace lemon;



typedef SmartGraph Graph;



char test_lgf[] =

  "@nodes\n"

  "label\n"

  "0\n"

  "1\n"

  "2\n"

  "3\n"

  "4\n"

  "@arcs\n"

  "     label capacity\n"

  "0 1  0     1\n"

  "1 2  1     1\n"

  "2 3  2     1\n"

  "0 3  4     5\n"

  "0 3  5     10\n"

  "0 3  6     7\n"

  "4 2  7     1\n"

  "@attributes\n"

  "source 0\n"

  "target 3\n";

  

void checkGomoryHuCompile()

{

  typedef int Value;

  typedef concepts::Graph Graph;



  typedef Graph::Node Node;

  typedef Graph::Edge Edge;

  typedef concepts::ReadMap<Edge, Value> CapMap;

  typedef concepts::ReadWriteMap<Node, bool> CutMap;



  Graph g;

  Node n;

  CapMap cap;

  CutMap cut;

  Value v;

  int d;



  GomoryHu<Graph, CapMap> gh_test(g, cap);

  const GomoryHu<Graph, CapMap>&

    const_gh_test = gh_test;



  gh_test.run();



  n = const_gh_test.predNode(n);

  v = const_gh_test.predValue(n);

  d = const_gh_test.rootDist(n);

  v = const_gh_test.minCutValue(n, n);

  v = const_gh_test.minCutMap(n, n, cut);

}



GRAPH_TYPEDEFS(Graph);

typedef Graph::EdgeMap<int> IntEdgeMap;

typedef Graph::NodeMap<bool> BoolNodeMap;



int cutValue(const Graph& graph, const BoolNodeMap& cut,

	     const IntEdgeMap& capacity) {



  int sum = 0;

  for (EdgeIt e(graph); e != INVALID; ++e) {

    Node s = graph.u(e);

    Node t = graph.v(e);



    if (cut[s] != cut[t]) {

      sum += capacity[e];

    }

  }

  return sum;

}





int main() {

  Graph graph;

  IntEdgeMap capacity(graph);



  std::istringstream input(test_lgf);

  GraphReader<Graph>(graph, input).

    edgeMap("capacity", capacity).run();



  GomoryHu<Graph> ght(graph, capacity);

  ght.run();



  for (NodeIt u(graph); u != INVALID; ++u) {

    for (NodeIt v(graph); v != u; ++v) {

      Preflow<Graph, IntEdgeMap> pf(graph, capacity, u, v);

      pf.runMinCut();

      BoolNodeMap cm(graph);

      ght.minCutMap(u, v, cm);

      check(pf.flowValue() == ght.minCutValue(u, v), "Wrong cut 1");

      check(cm[u] != cm[v], "Wrong cut 2");

      check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 3");



      int sum=0;

      for(GomoryHu<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a)

        sum+=capacity[a]; 

      check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt");



      sum=0;

      for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n)

        sum++;

      for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n)

        sum++;

      check(sum == countNodes(graph), "Problem with MinCutNodeIt");

    }

  }

  

  return 0;

}