[Lemon-user] Using NetworkSimplex Algorithm

Wed Jul 17 14:03:50 CEST 2013

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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: Zero flow Problem.docx
Type: application/vnd.openxmlformats-officedocument.wordprocessingml.document
Size: 30989 bytes
Desc: Zero flow Problem.docx
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20130717/651cfffb/attachment-0001.docx>