[Lemon-user] Executing one aglortihm multiple times

[Alpár Jüttner]

Hi,

I think both Version 1 and 2 should be correct, while Version 3 is not.
Version 2 shouldn't crash, it is a probably a bug (could you submit a
bug report at http://lemon.cs.elte.hu/trac/lemon/wiki/IssueTracker ?).

The general concept is that run() runs everything from scratch, and it
is basically equivalent with init()+start(). Also, the input is
generally not allowed to change between init() and start().

There might be more permissive algorithm implementations but the keeping
above rules should always work.

The init()/start() separation is basically there in order to allow more
sophisticated control on the execution(). See e.g. Dijkstra,
( http://lemon.cs.elte.hu/pub/doc/1.1.2/a00087.html ). There you can add
additional sources between init() and start() or you can do step-by-step
execution by using processNextNode() instead of start().

Besides, I don't think Version 1. is so much suboptimal. Yes, you could
save freeing and reallocating a couple of memory blocks, but this time
is probably negligible compared to the time needed for reinitializing
then + executing the algorithm.

Regards,
Alpar


. On Sat, 2010-03-13 at 14:12 +0100, Ben Strasser wrote:
> Hello,
> 
> I'm having problems understanding how the init/start/run functions of 
> the algorithm classes such as MaxWeightedPerfectMatching are supposed to 
> be used. At which points am I allowed to change which parameters of the 
> algorithm? How do I rerun the algorithm after changing a few paramters?
> 
> Unfortunately the documenation of this subject is pretty sparse. :(
> 
> I have a graph and several weights and I want to calculate a matching 
> for each. What usage pattern am I supposed to employ?
> 
> === Version 1 ===
> 
> Graph g;
> Graph::EdgeMap<int>w(g);
> // fill g and w
> {
>  MaxWeightedPerfectMatching mm(g, w);
>  mm.run();
>  // extract matching
> }
> // modify w
> {
>  MaxWeightedPerfectMatching mm(g, w);
>  mm.run();
>  // extract matching
> }
> 
> (Works be seems suboptimal)
> 
> === Version 2 ===
> 
> Graph g;
> Graph::EdgeMap<int>w(g);
> // fill g and w
> MaxWeightedPerfectMatching mm(g, w);
> mm.run();
> // extract matching
> // modify w
> mm.run();
> // extract matching
> 
> (Crashs in 1.1.2)
> 
> === Version 3 ===
> 
> Graph g;
> Graph::EdgeMap<int>w(g);
> // fill g and w
> MaxWeightedPerfectMatching mm(g, w);
> mm.init();
> mm.start();
> // extract matching
> // modify w
> mm.start();
> // extract matching
> 
> (Seems to work, meaning it doesn't crash.)
> 
> Thanks for your time,
> Ben Strasser
> 
> 
> _______________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user