[Lemon-user] Preflow help

[Alpár Jüttner]

Hi,

You can never assume exact result from a floating point calculation.
Therefore you should never check the result of a complex calculation
using operator =. Check the difference between the obtained and the
expected results instead.

As a general advice, use integer flow and capacity values whenever you
need fully precise result (scale up all the values appropriately if you
need non-integer capacities).

Regards,
Alpar


 On Mon, 2010-11-01 at 03:32 -0400, Arun Reddy Kandoor wrote:
> 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 
>