[Lemon-user] Using NetworkSimplex Algorithm

[T.A. Heba Essam]

Thanks tons. Never encountered as active and helpful community as yours before!

Thanks Peter & Alpar :)

________________________________________
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
>>>>
>>>>
>>>>
>>>>
>>>
>>>
>>>
>>>
>>
>>
>>
>>
>