[Lemon-user] Using NetworkSimplex Algorithm
T.A. Heba Essam
Heba.Essam at cis.asu.edu.eg
Tue Aug 20 12:02:55 CEST 2013
Dear Peter,
Hope you enjoyed your holiday. You are right about starting a new thread instead. To be considered.
Thanks a lot,
Heba
________________________________________
From: Kovács Péter [kpeter at inf.elte.hu]
Sent: Monday, August 19, 2013 8:17 PM
To: T.A. Heba Essam
Cc: lemon-user at lemon.cs.elte.hu
Subject: Re: [Lemon-user] Using NetworkSimplex Algorithm
Hi Heba,
I'm sorry for not answering for a week, but I was on holiday. (Anyway,
your question is really unrelated to NetworkSimplex. I would suggest to
start a new email thread with a better subject in such cases.)
About the compilation problem: use initializer list.
In the header file, simply write this:
ListDigraph::NodeMap<int> dijNodeID;
and in the .cpp file, instead of these lines:
CDijkstras::CDijkstras(...)
: size(_size), sourceNode(sourceNode), targetNode(targetNode)
write this:
CDijkstras::CDijkstras(...)
: dijNodeID(dijGraph), size(_size), sourceNode(sourceNode),
targetNode(targetNode)
Regards,
Peter
On 2013.08.12. 22:40, T.A. Heba Essam wrote:
> Here you are the error picture
>
> Regards,
> Heba
> ________________________________________
> From: Kovács Péter [kpeter at inf.elte.hu]
> Sent: Thursday, July 18, 2013 1:39 PM
> To: Matthew Galati
> Cc: T.A. Heba Essam; lemon-user at lemon.cs.elte.hu
> Subject: Re: [Lemon-user] Using NetworkSimplex Algorithm
>
> Hi All,
>
> Theoretically, NetworkSimplex could support non-integer input data, but
> it would require careful modifications to avoid potential issues related
> to inexact computations. We did not implement this feature yet, but only
> for technical reasons and lack of time.
>
> On the other hand, CapacityScaling algorithm already supports
> non-integer arc costs (although it is usually slower than
> NetworkSimplex), but other data (supply, capacity, flow) should be
> integer-valued.
>
> Here is an issue about this topic:
> http://lemon.cs.elte.hu/trac/lemon/ticket/261
>
> Regards,
> Peter
>
>
> On 2013.07.18. 14:44, Matthew Galati wrote:
>> 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?
>>
>> 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.
>>
>>
>> On Wed, Jul 17, 2013 at 9:43 AM, Kovács Péter <kpeter at inf.elte.hu
>> <mailto:kpeter at inf.elte.hu>> wrote:
>>
>> Hi Heba,
>>
>> 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:
>> lemon.cs.elte.hu/pub/doc/1.2.__3/a00231.html
>> <http://lemon.cs.elte.hu/pub/doc/1.2.3/a00231.html>
>>
>> Have you tried your example scaling up all supply values by a factor
>> of 2? It should provide correct results.
>>
>> 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.
>>
>> Best regards,
>> Peter
>>
>>
>>
>> On 2013.07.17. 14 <tel:2013.07.17.%2014>:03, T.A. Heba Essam wrote:
>>
>> Dears,
>>
>> 1- For the supply map in network simplex algorithm, can it
>> accept fractional numbers?
>>
>> 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.
>>
>> Best regards,
>> Heba
>> __________________________________________
>> From: Kovács Péter [kpeter at inf.elte.hu <mailto:kpeter at inf.elte.hu>]
>> Sent: Sunday, June 23, 2013 2:28 PM
>> To: T.A. Heba Essam
>> Cc: lemon-user at lemon.cs.elte.hu <mailto:lemon-user at lemon.cs.elte.hu>
>> Subject: Re: [Lemon-user] Using NetworkSimplex Algorithm
>>
>> Hi Heba,
>>
>> Dear all,
>>
>> The first question is more of a theoritical one,
>>
>> 1- Is there a way to avoid that a supply value of a node
>> doesn't get splitted into two arcs?
>> I mean, any settings for capacity values or graph
>> formation to achieve that?
>>
>>
>> In general, this requirement leads to a "unsplittable flow" problem,
>> which cannot be transformed to the standard min cost flow
>> problem. It is
>> actually a much harder, NP-complete problem. See e.g.:
>> http://www.redaktion.tu-__berlin.de/fileadmin/i26/__download/AG_DiskAlg/FG___KombOptGraphAlg/preprints/__2000/Report-685-2000.pdf
>> <http://www.redaktion.tu-berlin.de/fileadmin/i26/download/AG_DiskAlg/FG_KombOptGraphAlg/preprints/2000/Report-685-2000.pdf>
>>
>> In a special case, when all supply values are the same, there is a
>> trivial transformation: scaling down all capacity and supply/demand
>> values by this value so as to have 1 as supply value at each supply
>> node. However, the general case cannot be handled this way.
>>
>> 2- Can't I get an arc length in Lemon? unless I'm previously
>> defining a length map for it?
>>
>>
>> No, you can't. In LEMON, graph nodes and arcs cannot store any
>> attached
>> value (length, label, color etc.), maps should be used for all such
>> purposes.
>>
>> Regards,
>> Peter
>>
>>
>> __________________________________________
>> From: Kovács Péter [kpeter at inf.elte.hu
>> <mailto:kpeter at inf.elte.hu>]
>> Sent: Wednesday, June 19, 2013 10:08 PM
>> To: T.A. Heba Essam
>> Cc: lemon-user at lemon.cs.elte.hu
>> <mailto:lemon-user at lemon.cs.elte.hu>
>> Subject: Re: [Lemon-user] Using NetworkSimplex Algorithm
>>
>> Hi Heba,
>>
>> Dears,
>>
>> 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?
>>
>> - Is it the flowmap or potentialmap data member? and,
>>
>> - How it can be interpreted/accessed, please?
>>
>>
>> The flow map provides the information you are looking for.
>> Although it
>> is a bit more complex stuff than paths. You could check the
>> documentation here:
>> http://lemon.cs.elte.hu/pub/__doc/1.2.3/a00005.html
>> <http://lemon.cs.elte.hu/pub/doc/1.2.3/a00005.html>
>>
>> The (primal) solution of the problem is the flow function
>> (map) that
>> associates a flow value with each arc of the graph (which is
>> between the
>> lower and upper bounds given for that arc). This function is
>> denoted as
>> f in the above doc and can be accessed using either the
>> flow() or the
>> flowMap() function of NetworkSimplex (after running the
>> algorithm):
>> http://lemon.cs.elte.hu/pub/__doc/1.2.3/a00231.html
>> <http://lemon.cs.elte.hu/pub/doc/1.2.3/a00231.html>
>>
>> For Dijkstra's algorithm, I used "dijkstra(dijGraph,
>> length).run(source, target);"
>>
>> - Does "path" gives me the shortest path between source
>> & target? and,
>> - "dist" gives me the shortst path distance between them?
>>
>>
>> Yes.
>>
>> 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?
>>
>>
>> In the following example:
>> bool reached = dijkstra(g, length).path(p).dist(d).run(s, t);
>>
>> The results are obtained as follows: the return value
>> indicates if a
>> directed path can be found from s to t; p is a Path
>> structure in which a
>> shortest s->t path will be copied; d is a number type
>> variable (e.g. int
>> or double), which will be set to the shortest path distance
>> of s and t.
>>
>> Note that there are two interfaces for using Dijsktra: a
>> simpler,
>> function-type interface:
>> http://lemon.cs.elte.hu/pub/__doc/1.2.3/a00531.html#__ga6aa57523fe00e2b8fe2f5cd17dd1__5cea
>> <http://lemon.cs.elte.hu/pub/doc/1.2.3/a00531.html#ga6aa57523fe00e2b8fe2f5cd17dd15cea>
>> and a class interface:
>> http://lemon.cs.elte.hu/pub/__doc/1.2.3/a00110.html
>> <http://lemon.cs.elte.hu/pub/doc/1.2.3/a00110.html>
>>
>> It seems that you used the former one, so I wrote about this
>> solution,
>> but the path(Node), dist(Node) functions are for the
>> class-type interface.
>>
>> Regards,
>> Peter
>>
>>
>> Thanks a lot,
>> Heba
>>
>>
>>
>> __________________________________________
>> From: Alpár Jüttner [alpar.juttner at gmail.com
>> <mailto:alpar.juttner at gmail.com>] on behalf of Alpar
>> Juttner [alpar at cs.elte.hu <mailto:alpar at cs.elte.hu>]
>> Sent: Friday, June 14, 2013 3:03 PM
>> To: T.A. Heba Essam
>> Cc: Kovács Péter; lemon-user at lemon.cs.elte.hu
>> <mailto:lemon-user at lemon.cs.elte.hu>
>> Subject: Re: [Lemon-user] Using NetworkSimplex Algorithm
>>
>> On Thu, 2013-06-13 at 11:46 +0000, T.A. Heba Essam wrote:
>>
>> Dear Alpar,
>>
>> I tried so many alternatives, the only thing that
>> compiles for me is
>> your piece of advice of including header files of
>> lemon before VS ones.
>>
>>
>> That's great. I still highly recommend isolating (direct
>> or indirect)
>> any use of windows.h (or any other nasty headers) in
>> dedicated object
>> files.
>>
>> Regards,
>> Alpar
>>
>>
>>
>> Thanks,
>> Heba
>> __________________________________________
>> From: Alpár Jüttner [alpar.juttner at gmail.com
>> <mailto:alpar.juttner at gmail.com>] on behalf of Alpar
>> Juttner [alpar at cs.elte.hu <mailto:alpar at cs.elte.hu>]
>> Sent: Wednesday, June 12, 2013 4:01 PM
>> To: T.A. Heba Essam
>> Cc: Kovács Péter; lemon-user at lemon.cs.elte.hu
>> <mailto:lemon-user at lemon.cs.elte.hu>
>> Subject: Re: [Lemon-user] Using NetworkSimplex Algorithm
>>
>> Hi,
>>
>> Well, I actually found out that many other
>> "#include" cause the
>> problem, not only stdafx.h :(
>>
>> Seems like it doesn't accept including files
>> rather than lemon ones or
>> else it gives compilation errors!! which I can't
>> do as I'm using LEMON
>> as a part of my project. Sounds weird, having no
>> clue how this can be
>> handled.
>>
>>
>> LEMON should work seamlessly with _any_ correctly
>> written header files,
>> we put high emphasis on compatibility, and are very
>> conservative to put
>> nothing into the global namespace in order to avoid
>> conflicts with other
>> packages.
>>
>> Note that, however, the Visual Studio header files
>> are _not_ written
>> correctly. They are ridiculously badly designed and
>> fails to follow even
>> the most basic coding principles. For example
>> windows.h has #define
>> declarations (yes, #define not const values or
>> enums) for random keyword
>> such as "Arc", "IN" or "OUT". This means that you
>> shoot yourself in the
>> foot e.g. if the try to name class as "Arc" even if
>> it is in your own
>> namespace.
>>
>> It may help if you include the window header _after_
>> the LEMON ones.
>> Then it cannot overwrite LEMON's code with its
>> stupid #define
>> declarations. But it will still spoil your codes.
>>
>> The only safe solution is to completely avoid
>> including windows.h (or
>> using in separated .cc files only, see below),
>> whether or not you use
>> LEMON.
>>
>> mmmmm I may separate the Lemon usage parts in
>> different simple files
>> (where I won't need to include any external
>> headers) and call them far
>> from any other place within my project. Will try
>> it and keep you
>> updated.
>>
>>
>> Why not do it the other way around? Put the guilty
>> one in the prison,
>> not every one else!
>> Write wrapper functions for your windows.h calls and
>> place them into a
>> separate .cc.
>>
>> In fact, LEMON does the same internally, and does it
>> for the very same
>> reason. All Windows system call are placed in
>> lemon/bits/windows.cc, and
>> nowhere else do we use #include<windows.h>.
>>
>> See http://lemon.cs.elte.hu/trac/__lemon/ticket/215
>> <http://lemon.cs.elte.hu/trac/lemon/ticket/215> for
>> more details.
>>
>> Regards,
>> Alpar
>>
>>
>>
>> Regards,
>> Heba Essam
>>
>> __________________________________________
>> From: Kovács Péter [kpeter at inf.elte.hu
>> <mailto:kpeter at inf.elte.hu>]
>> Sent: Wednesday, June 12, 2013 10:52 AM
>> To: T.A. Heba Essam
>> Cc: Alpar Juttner; lemon-user at lemon.cs.elte.hu
>> <mailto:lemon-user at lemon.cs.elte.hu>
>> Subject: Re: [Lemon-user] Using NetworkSimplex
>> Algorithm
>>
>> Hi Heba,
>>
>> I checked your code example. Without #include
>> "stdafx.h", it compiles
>> and runs correctly for me using GCC compiler
>> (well, INFINITE must be
>> defined then, e.g. #define INFINITE 1000000).
>>
>> Therefore, the problem may be related to your
>> stdafx.h or the compiler.
>> Could you try compiling the code without
>> including stdafx.h?
>>
>> Regards,
>> Peter
>>
>>
>> On 2013.06.12. 12 <tel:2013.06.12.%2012>:24,
>> T.A. Heba Essam wrote:
>>
>> Thanks Alpar :)
>>
>> Then, I still hope if we can figure out the
>> cause of these errors.
>>
>> Regards,
>> Heba
>> __________________________________________
>> From: Alpár Jüttner [alpar.juttner at gmail.com
>> <mailto:alpar.juttner at gmail.com>] on behalf
>> of Alpar Juttner [alpar at cs.elte.hu
>> <mailto:alpar at cs.elte.hu>]
>> Sent: Wednesday, June 12, 2013 10:14 AM
>> To: T.A. Heba Essam
>> Cc: Kovács Péter;
>> lemon-user at lemon.cs.elte.hu
>> <mailto:lemon-user at lemon.cs.elte.hu>
>> Subject: Re: [Lemon-user] Using
>> NetworkSimplex Algorithm
>>
>> Hi,
>>
>> Note: as VS 2010 is 32-bit while LEMON
>> is 64,
>>
>>
>> There is nothing 64-bit specific in LEMON.
>>
>> can this cause the problem by any
>> means?
>>
>>
>> No, it cannot.
>>
>> Regards,
>> Alpar
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>> _________________________________________________
>> Lemon-user mailing list
>> Lemon-user at lemon.cs.elte.hu <mailto:Lemon-user at lemon.cs.elte.hu>
>> http://lemon.cs.elte.hu/__mailman/listinfo/lemon-user
>> <http://lemon.cs.elte.hu/mailman/listinfo/lemon-user>
>>
>>
>
>
>
More information about the Lemon-user
mailing list