[Lemon-devel] Lemon plans

[Balazs Dezso]

Dear Developers,

I would like to summarize a few plans about the direction of lemon 
development.

1) The lemon-stable renaming. After many mails, discussions and chats I would 
like to finalize the lemon renaming. The deadline, when I will commit my 
variant of names is 31 of October. Any agreement would be if it gets the 
majority of the developers.

2) There are some codes to be revised and moved into the library:
Please contribution in the topics (a-c).
a) Isomorphicity checking by Mark Szabadkai.
Mark have finished this algorithm, but I could not check detailed yet. The 
problem is not known to be in co-NP, so the code should be revised more 
stringent than other algorithm codes, because it is hard to test by result. 

b) Flow algorithms based on dynamic trees by Tamas Hamori.
I think this code is quite good, but there are some anomalies with the running 
times. I found some issues about that these type of implementations are 
inferior to the original push-relabel algorithms (leda book, some articles of 
Mehlhorn). I also found a reference to an other master thesis in this topic, 
but I could not found on the internet. The code needs some renaming and 
clarifying.

c) Minimum cover set problem by Janos Nagy
This work contains more heuristic solution for minimum cover set and similar 
problems. Some class should be merged, renamed and clarified.

d) Min cost flows by Peter Kovacs
The c++ macro based solutions should be changed to template based solutions 
(possibility to use two different variant in the same program). Some revision 
on the different Value types (floating point types) should be done.

3) Documentation revisions
There are syntactical faults in the documentations, and in the most point it 
should be revised, extended and clarified. The tutorial would be extremely 
important.

4) New algorithms
a) Weighted matching problems in bipartite graphs by Gabor Juhasz
Improving the successive shortest path approach based algorithm and 
implementing some other algorithms like cost-scaling or Hungarian method with 
priority queues.

b) Minimum cost cycle cover (it is not assigned to developer yet)
This topic is quite easy with the current algorithms of the library. One 
adaptor should be implemented on the base of SplitGraphAdaptor and the 
minimum cost bipartite matching could be used to implement this algorithm. It 
has great importance in the asymmetric TSP problem and in the fractional 
solution of the general weighted matching problem (it could be used to find a 
good initial matching for the integral matching).

c) Heuristic algorithms for "not to be known in P" problems by Mark Szabadkai
He already done the isomorphicity checking algorithm for directed graphs. He 
will do hammiltonian path, vertex coloring, independent set and max clique 
problems with backtrack based solutions.

d) Cost-scaling algorithm for min cost flow by Peter Kovacs
It is one of the most effective min cost flow algorithm.

e) weighted general matching (I made some steps, but I'm quite far from the 
target)
I have found a master thesis by Schaefer about the LEDA O(nmlog(n)) 
implementation. Some preliminary data structure are done (mergeable-splitable 
priority queue). Any contribution is welcomed.

d) graph layout in to eps (it is not assigned to developer yet)
I seen the gui layout could not be used directly in eps drawer.

5) GUI
Importing new algorithms
Different types for maps by Akos.

6) Lemon site, servers
Some upgrades should be made on the lemon related servers. Development of our 
sites and google rank.

Please inform me, if you could make some code revisions, or if you could 
develop algorithms in the unassigned topics, or if you could contribute in 
some works.

Best, Balazs