[Lemon-user] Preflow help

[Arun Reddy Kandoor]

Hello all,

I am facing a strange problem when I try to use preflow class. I thought it
has some inherent problem with the preflow class output which is showing
this strange result. I have used a small example in the attached file to
explain my problem. The program adds 5 edge nodes and 4 internal nodes along
with arcs and bandwidth attributes to each of them. The bandwidth attribute
is set so that the effective flows from first edge node to every other edge
node are as follows:
a0-a1: 4.67
a0-a2: 3.32
a0-a3: 4.99
a0-a4: 0.15

The output for the attached code is:
*0.15 Not equal to 0.15*
*0.15 Not equal to 0.15*
*0.15 Not equal to 0.15*

which is obtained from the fourth Preflow run in the attached example. I am
unable to figure out why a simple equality check is failing when the values
are same in the fourth run. Would anyone please take a look at the attached
"very simple" example and point out my mistake? I am trying since past one
week trying to figure out the problem. It would be a GREAT HELP to me.

I am also pasting the example here for your convenience:

#include <iostream>
#include <lemon/list_graph.h>
#include<lemon/math.h>
#include <lemon/maps.h>
#include <lemon/preflow.h>

using namespace lemon;
using namespace std;

int main()
{
  ListDigraph g;
  ListDigraph::ArcMap<double> map_bw(g);
  IdMap<ListDigraph,ListDigraph::Arc> arc_id(g);

  ListDigraph::Node a0 = g.addNode();
  ListDigraph::Node a1 = g.addNode();
  ListDigraph::Node a2 = g.addNode();
  ListDigraph::Node a3 = g.addNode();
  ListDigraph::Node a4 = g.addNode();
  ListDigraph::Node i1 = g.addNode();
  ListDigraph::Node i2 = g.addNode();
  ListDigraph::Node i3 = g.addNode();
  ListDigraph::Node i4 = g.addNode();

  ListDigraph::Arc  e0 = g.addArc(a0, i1);
  map_bw[e0]=13.13;
  ListDigraph::Arc  e1 = g.addArc(i1, i2);
  map_bw[e1]=4.67;
  ListDigraph::Arc  e2 = g.addArc(i2, a1);
  map_bw[e2]=4.67;
  ListDigraph::Arc  e3 = g.addArc(i1, a2);
  map_bw[e3]=3.32;
  ListDigraph::Arc  e4 = g.addArc(i1, i3);
  map_bw[e4]=5.14;
  ListDigraph::Arc  e5 = g.addArc(i3, i4);
  map_bw[e5]=4.99;
  ListDigraph::Arc  e6 = g.addArc(i4, a3);
  map_bw[e6]=4.99;
  ListDigraph::Arc  e7 = g.addArc(i3, a4);
  map_bw[e7]=0.15;

  double demand,maxflow;
  // a0-a1: demand=4.67
  Preflow<ListDigraph, ListDigraph::ArcMap< double > >  preflow_test1
(g,map_bw,a0,a1);
  preflow_test1.run();
  demand=4.67;
  maxflow=preflow_test1.flowValue();

  for (ListDigraph::ArcIt a(g); a != INVALID; ++a){
    if(preflow_test1.flow(a)>0){
      if(maxflow==demand){
map_bw[a] -= preflow_test1.flow(a);
      }
      else
cout<<maxflow<<" Not equal to "<< demand<<endl;
    }
  }
  // a0-a2: demand=3.32
  Preflow<ListDigraph, ListDigraph::ArcMap< double > >  preflow_test2
(g,map_bw,a0,a2);
  preflow_test2.run();
  demand=3.32;
  maxflow=preflow_test2.flowValue();

  for (ListDigraph::ArcIt a(g); a != INVALID; ++a){
    if(preflow_test2.flow(a)>0){
      if(maxflow==demand){
map_bw[a] -= preflow_test2.flow(a);
      }
      else
cout<<maxflow<<" Not equal to "<< demand<<endl;
    }
  }
  // a0-a3: demand=4.99
  Preflow<ListDigraph, ListDigraph::ArcMap< double > >  preflow_test3
(g,map_bw,a0,a3);
  preflow_test3.run();
  demand=4.99;
  maxflow=preflow_test3.flowValue();

  for (ListDigraph::ArcIt a(g); a != INVALID; ++a){
    if(preflow_test3.flow(a)>0){
      if(maxflow==demand){
map_bw[a] -= preflow_test3.flow(a);
      }
      else
cout<<maxflow<<" Not equal to "<< demand<<endl;
    }
  }

  // a0-a4: demand=0.15
  Preflow<ListDigraph, ListDigraph::ArcMap< double > >  preflow_test4
(g,map_bw,a0,a4);
  preflow_test4.run();
  demand=0.15;
  maxflow=preflow_test4.flowValue();

  for (ListDigraph::ArcIt a(g); a != INVALID; ++a){
    if(preflow_test4.flow(a)>0){
      if(maxflow==demand){
map_bw[a] -= preflow_test4.flow(a);
      }
      else
cout<<maxflow<<" Not equal to "<< demand<<endl;
    }
  }

  return 0;
}


Thanks,
-- 
Arun
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20101101/40047690/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: preflow.cc
Type: application/octet-stream
Size: 2872 bytes
Desc: not available
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20101101/40047690/attachment.obj>