<div dir="ltr">What part of the network simplex implementation fails if you use double data type instead of integer? Theoretically, you lose the guarantee that the output (flows) are integer. But, do you lose correctness?<div>
<br></div><div>Scaling can be difficult to maintain accuracy as you must keep all your input below INT_MAX to use integer types. You also then have to worry about overflow issues.</div></div><div class="gmail_extra"><br><br>
<div class="gmail_quote">On Wed, Jul 17, 2013 at 9:43 AM, Kovács Péter <span dir="ltr"><<a href="mailto:kpeter@inf.elte.hu" target="_blank">kpeter@inf.elte.hu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Hi Heba,<br>
<br>
The min cost flow algorithms currently do not support fractional input data. There is a warning about that on the doc page of NetworkSimplex as well:<br>
<a href="http://lemon.cs.elte.hu/pub/doc/1.2.3/a00231.html" target="_blank">lemon.cs.elte.hu/pub/doc/1.2.<u></u>3/a00231.html</a><br>
<br>
Have you tried your example scaling up all supply values by a factor of 2? It should provide correct results.<br>
<br>
In general, you can always find a suitable scaling factor to convert the supply values to integers. And this factor can also be used to convert the flow values back in order to obtain a fractional solution for the original problem.<br>
<br>
Best regards,<br>
Peter<div class="HOEnZb"><div class="h5"><br>
<br>
<br>
On <a href="tel:2013.07.17.%2014" value="+12013071714" target="_blank">2013.07.17. 14</a>:03, T.A. Heba Essam wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Dears,<br>
<br>
1- For the supply map in network simplex algorithm, can it accept fractional numbers?<br>
<br>
I'm having the attached problem and my first guess is (maybe fractions are rounded up leading to unbalanced supply and demand values). Kindly have a look.<br>
<br>
Best regards,<br>
Heba<br>
______________________________<u></u>__________<br>
From: Kovács Péter [<a href="mailto:kpeter@inf.elte.hu" target="_blank">kpeter@inf.elte.hu</a>]<br>
Sent: Sunday, June 23, 2013 2:28 PM<br>
To: T.A. Heba Essam<br>
Cc: <a href="mailto:lemon-user@lemon.cs.elte.hu" target="_blank">lemon-user@lemon.cs.elte.hu</a><br>
Subject: Re: [Lemon-user] Using NetworkSimplex Algorithm<br>
<br>
Hi Heba,<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Dear all,<br>
<br>
The first question is more of a theoritical one,<br>
<br>
1- Is there a way to avoid that a supply value of a node doesn't get splitted into two arcs?<br>
I mean, any settings for capacity values or graph formation to achieve that?<br>
</blockquote>
<br>
In general, this requirement leads to a "unsplittable flow" problem,<br>
which cannot be transformed to the standard min cost flow problem. It is<br>
actually a much harder, NP-complete problem. See e.g.:<br>
<a href="http://www.redaktion.tu-berlin.de/fileadmin/i26/download/AG_DiskAlg/FG_KombOptGraphAlg/preprints/2000/Report-685-2000.pdf" target="_blank">http://www.redaktion.tu-<u></u>berlin.de/fileadmin/i26/<u></u>download/AG_DiskAlg/FG_<u></u>KombOptGraphAlg/preprints/<u></u>2000/Report-685-2000.pdf</a><br>
<br>
In a special case, when all supply values are the same, there is a<br>
trivial transformation: scaling down all capacity and supply/demand<br>
values by this value so as to have 1 as supply value at each supply<br>
node. However, the general case cannot be handled this way.<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
2- Can't I get an arc length in Lemon? unless I'm previously defining a length map for it?<br>
</blockquote>
<br>
No, you can't. In LEMON, graph nodes and arcs cannot store any attached<br>
value (length, label, color etc.), maps should be used for all such<br>
purposes.<br>
<br>
Regards,<br>
Peter<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
______________________________<u></u>__________<br>
From: Kovács Péter [<a href="mailto:kpeter@inf.elte.hu" target="_blank">kpeter@inf.elte.hu</a>]<br>
Sent: Wednesday, June 19, 2013 10:08 PM<br>
To: T.A. Heba Essam<br>
Cc: <a href="mailto:lemon-user@lemon.cs.elte.hu" target="_blank">lemon-user@lemon.cs.elte.hu</a><br>
Subject: Re: [Lemon-user] Using NetworkSimplex Algorithm<br>
<br>
Hi Heba,<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Dears,<br>
<br>
For a minimum cost flow problem, can the network simplex algorithm gives information about nodes movement. I.e. n1 goes to n2 goes to n3 & n5 -> n6 -> n7...etc?<br>
<br>
- Is it the flowmap or potentialmap data member? and,<br>
<br>
- How it can be interpreted/accessed, please?<br>
</blockquote>
<br>
The flow map provides the information you are looking for. Although it<br>
is a bit more complex stuff than paths. You could check the<br>
documentation here:<br>
<a href="http://lemon.cs.elte.hu/pub/doc/1.2.3/a00005.html" target="_blank">http://lemon.cs.elte.hu/pub/<u></u>doc/1.2.3/a00005.html</a><br>
<br>
The (primal) solution of the problem is the flow function (map) that<br>
associates a flow value with each arc of the graph (which is between the<br>
lower and upper bounds given for that arc). This function is denoted as<br>
f in the above doc and can be accessed using either the flow() or the<br>
flowMap() function of NetworkSimplex (after running the algorithm):<br>
<a href="http://lemon.cs.elte.hu/pub/doc/1.2.3/a00231.html" target="_blank">http://lemon.cs.elte.hu/pub/<u></u>doc/1.2.3/a00231.html</a><br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
For Dijkstra's algorithm, I used "dijkstra(dijGraph, length).run(source, target);"<br>
<br>
- Does "path" gives me the shortest path between source & target? and,<br>
- "dist" gives me the shortst path distance between them?<br>
</blockquote>
<br>
Yes.<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
as I see in the documenation that "path" and "dist" takes a variable "node" and calculate it to the root. What about having a specific source and target nodes?<br>
</blockquote>
<br>
In the following example:<br>
bool reached = dijkstra(g, length).path(p).dist(d).run(s, t);<br>
<br>
The results are obtained as follows: the return value indicates if a<br>
directed path can be found from s to t; p is a Path structure in which a<br>
shortest s->t path will be copied; d is a number type variable (e.g. int<br>
or double), which will be set to the shortest path distance of s and t.<br>
<br>
Note that there are two interfaces for using Dijsktra: a simpler,<br>
function-type interface:<br>
<a href="http://lemon.cs.elte.hu/pub/doc/1.2.3/a00531.html#ga6aa57523fe00e2b8fe2f5cd17dd15cea" target="_blank">http://lemon.cs.elte.hu/pub/<u></u>doc/1.2.3/a00531.html#<u></u>ga6aa57523fe00e2b8fe2f5cd17dd1<u></u>5cea</a><br>
and a class interface:<br>
<a href="http://lemon.cs.elte.hu/pub/doc/1.2.3/a00110.html" target="_blank">http://lemon.cs.elte.hu/pub/<u></u>doc/1.2.3/a00110.html</a><br>
<br>
It seems that you used the former one, so I wrote about this solution,<br>
but the path(Node), dist(Node) functions are for the class-type interface.<br>
<br>
Regards,<br>
Peter<br>
<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Thanks a lot,<br>
Heba<br>
<br>
<br>
<br>
______________________________<u></u>__________<br>
From: Alpár Jüttner [<a href="mailto:alpar.juttner@gmail.com" target="_blank">alpar.juttner@gmail.com</a>] on behalf of Alpar Juttner [<a href="mailto:alpar@cs.elte.hu" target="_blank">alpar@cs.elte.hu</a>]<br>
Sent: Friday, June 14, 2013 3:03 PM<br>
To: T.A. Heba Essam<br>
Cc: Kovács Péter; <a href="mailto:lemon-user@lemon.cs.elte.hu" target="_blank">lemon-user@lemon.cs.elte.hu</a><br>
Subject: Re: [Lemon-user] Using NetworkSimplex Algorithm<br>
<br>
On Thu, 2013-06-13 at 11:46 +0000, T.A. Heba Essam wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Dear Alpar,<br>
<br>
I tried so many alternatives, the only thing that compiles for me is<br>
your piece of advice of including header files of lemon before VS ones.<br>
</blockquote>
<br>
That's great. I still highly recommend isolating (direct or indirect)<br>
any use of windows.h (or any other nasty headers) in dedicated object<br>
files.<br>
<br>
Regards,<br>
Alpar<br>
<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
Thanks,<br>
Heba<br>
______________________________<u></u>__________<br>
From: Alpár Jüttner [<a href="mailto:alpar.juttner@gmail.com" target="_blank">alpar.juttner@gmail.com</a>] on behalf of Alpar Juttner [<a href="mailto:alpar@cs.elte.hu" target="_blank">alpar@cs.elte.hu</a>]<br>
Sent: Wednesday, June 12, 2013 4:01 PM<br>
To: T.A. Heba Essam<br>
Cc: Kovács Péter; <a href="mailto:lemon-user@lemon.cs.elte.hu" target="_blank">lemon-user@lemon.cs.elte.hu</a><br>
Subject: Re: [Lemon-user] Using NetworkSimplex Algorithm<br>
<br>
Hi,<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Well, I actually found out that many other "#include" cause the<br>
problem, not only stdafx.h :(<br>
<br>
Seems like it doesn't accept including files rather than lemon ones or<br>
else it gives compilation errors!! which I can't do as I'm using LEMON<br>
as a part of my project. Sounds weird, having no clue how this can be<br>
handled.<br>
</blockquote>
<br>
LEMON should work seamlessly with _any_ correctly written header files,<br>
we put high emphasis on compatibility, and are very conservative to put<br>
nothing into the global namespace in order to avoid conflicts with other<br>
packages.<br>
<br>
Note that, however, the Visual Studio header files are _not_ written<br>
correctly. They are ridiculously badly designed and fails to follow even<br>
the most basic coding principles. For example windows.h has #define<br>
declarations (yes, #define not const values or enums) for random keyword<br>
such as "Arc", "IN" or "OUT". This means that you shoot yourself in the<br>
foot e.g. if the try to name class as "Arc" even if it is in your own<br>
namespace.<br>
<br>
It may help if you include the window header _after_ the LEMON ones.<br>
Then it cannot overwrite LEMON's code with its stupid #define<br>
declarations. But it will still spoil your codes.<br>
<br>
The only safe solution is to completely avoid including windows.h (or<br>
using in separated .cc files only, see below), whether or not you use<br>
LEMON.<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
mmmmm I may separate the Lemon usage parts in different simple files<br>
(where I won't need to include any external headers) and call them far<br>
from any other place within my project. Will try it and keep you<br>
updated.<br>
</blockquote>
<br>
Why not do it the other way around? Put the guilty one in the prison,<br>
not every one else!<br>
Write wrapper functions for your windows.h calls and place them into a<br>
separate .cc.<br>
<br>
In fact, LEMON does the same internally, and does it for the very same<br>
reason. All Windows system call are placed in lemon/bits/windows.cc, and<br>
nowhere else do we use #include<windows.h>.<br>
<br>
See <a href="http://lemon.cs.elte.hu/trac/lemon/ticket/215" target="_blank">http://lemon.cs.elte.hu/trac/<u></u>lemon/ticket/215</a> for more details.<br>
<br>
Regards,<br>
Alpar<br>
<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
Regards,<br>
Heba Essam<br>
<br>
______________________________<u></u>__________<br>
From: Kovács Péter [<a href="mailto:kpeter@inf.elte.hu" target="_blank">kpeter@inf.elte.hu</a>]<br>
Sent: Wednesday, June 12, 2013 10:52 AM<br>
To: T.A. Heba Essam<br>
Cc: Alpar Juttner; <a href="mailto:lemon-user@lemon.cs.elte.hu" target="_blank">lemon-user@lemon.cs.elte.hu</a><br>
Subject: Re: [Lemon-user] Using NetworkSimplex Algorithm<br>
<br>
Hi Heba,<br>
<br>
I checked your code example. Without #include "stdafx.h", it compiles<br>
and runs correctly for me using GCC compiler (well, INFINITE must be<br>
defined then, e.g. #define INFINITE 1000000).<br>
<br>
Therefore, the problem may be related to your stdafx.h or the compiler.<br>
Could you try compiling the code without including stdafx.h?<br>
<br>
Regards,<br>
Peter<br>
<br>
<br>
On <a href="tel:2013.06.12.%2012" value="+12013061212" target="_blank">2013.06.12. 12</a>:24, T.A. Heba Essam wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Thanks Alpar :)<br>
<br>
Then, I still hope if we can figure out the cause of these errors.<br>
<br>
Regards,<br>
Heba<br>
______________________________<u></u>__________<br>
From: Alpár Jüttner [<a href="mailto:alpar.juttner@gmail.com" target="_blank">alpar.juttner@gmail.com</a>] on behalf of Alpar Juttner [<a href="mailto:alpar@cs.elte.hu" target="_blank">alpar@cs.elte.hu</a>]<br>
Sent: Wednesday, June 12, 2013 10:14 AM<br>
To: T.A. Heba Essam<br>
Cc: Kovács Péter; <a href="mailto:lemon-user@lemon.cs.elte.hu" target="_blank">lemon-user@lemon.cs.elte.hu</a><br>
Subject: Re: [Lemon-user] Using NetworkSimplex Algorithm<br>
<br>
Hi,<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Note: as VS 2010 is 32-bit while LEMON is 64,<br>
</blockquote>
<br>
There is nothing 64-bit specific in LEMON.<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
can this cause the problem by any means?<br>
</blockquote>
<br>
No, it cannot.<br>
<br>
Regards,<br>
Alpar<br>
<br>
<br>
<br>
<br>
</blockquote>
<br>
<br>
<br>
<br>
</blockquote>
<br>
<br>
<br>
<br>
</blockquote>
<br>
</blockquote>
<br>
</blockquote>
<br>
<br>
<br>
</blockquote>
<br>
<br></div></div><div class="HOEnZb"><div class="h5">
______________________________<u></u>_________________<br>
Lemon-user mailing list<br>
<a href="mailto:Lemon-user@lemon.cs.elte.hu" target="_blank">Lemon-user@lemon.cs.elte.hu</a><br>
<a href="http://lemon.cs.elte.hu/mailman/listinfo/lemon-user" target="_blank">http://lemon.cs.elte.hu/<u></u>mailman/listinfo/lemon-user</a><br>
</div></div></blockquote></div><br></div>