[Lemon-user] Using NetworkSimplex Algorithm
Kovács Péter
kpeter at inf.elte.hu
Wed Jul 17 15:43:22 CEST 2013
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
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: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]
> Sent: Sunday, June 23, 2013 2:28 PM
> To: T.A. Heba Essam
> Cc: 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
>
> 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]
>> Sent: Wednesday, June 19, 2013 10:08 PM
>> To: T.A. Heba Essam
>> Cc: 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
>>
>> 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
>>
>>> 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#ga6aa57523fe00e2b8fe2f5cd17dd15cea
>> and a class interface:
>> 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] on behalf of Alpar Juttner [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
>>> 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] on behalf of Alpar Juttner [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
>>>> 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 for more details.
>>>>
>>>> Regards,
>>>> Alpar
>>>>
>>>>
>>>>>
>>>>> Regards,
>>>>> Heba Essam
>>>>>
>>>>> ________________________________________
>>>>> From: Kovács Péter [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
>>>>> 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: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] on behalf of Alpar Juttner [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
>>>>>> 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
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>
>>>>
>>>>
>>>>
>>>
>>
>
>
>
More information about the Lemon-user
mailing list