[Lemon-user] Preflow help

[Balázs Dezső]

Hi,

For floating point numbers the next statement is not hold:
a + (b - a) == b
Therefore the computations cannot be completely exact.

Here is a link about floating point computations and comparison:
http://www.cygnus-software.com/papers/comparingfloats/comparingfloats.htm

In the preflow algorithm, the comparing with epsilon method is used,
and it is implemented in  the Tolerance<double> class.

You can use the following code to compare your values:
if (!preflow_test1.tolerance().different(maxflow, demand)) {
  ...
}

Otherwise, if your task make it possible, you can use rather fixed
point numbers (which is more safe solution).

Best regards, Balazs


On Mon, Nov 1, 2010 at 7:32 AM, Arun Reddy Kandoor
<karunreddy30 at gmail.com> 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
>
> _______________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
>
>