[Lemon-devel] Development suggestions (long letter)

[Balazs Dezso]

Dear Developers,

I have decided to answer some questions and suggestions Peter.
 
> SOURCE FILES
> ============
> B1. First of all: the current TODO list should be revised and as many tasks
> as possible should be done. I know that this isn't an intresting idea from
> me, but it is very important.

This is really an important topic, in the past we made todo-killer development 
days. It is a hard work because it is quite boring, but it have to be done.

> B2. In ListGraph and SmartGraph structures inserted nodes and edges are
> placed to a std::vector<> in the order of the insertion, but they are
> linked according to the reverse order.
> I checked the source files in detail but I didn't find any reason for this.
> I think it would be much better if the nodes and edges were linked in the
> insertion order, because than the iteration of nodes/edges gives this
> order, not the reverse one.
> May someone tell me, why is the order reversed (Balazs or Alpar)? If there
> isn't any efficiency reason for that, I think it should be changed.

It has also performance reasons, the push operation of a list is easier at the 
begining. But it makes harder to debug and read the output of the programs.

> B3. In ListGraph and SmartGraph using separate vectors could be better,
> because: B3.1. It may cause speed-up (it should be checked!).
> 	B3.2. It could make memory allocations esier.
> I think the efficiency of both versions should be compared both using graph
> building/manipulating operations and using significant algorithms (Bfs,
> Dfs, Dijkstra, Preflow, etc.).

It is a known issue, there is a StaticGraph which makes the separation of the 
data, and it is faster than the other graphs (it has ordered out edge lists 
additionally).

> B4. If a Node or an Edge is passed as an argument, which version is better
> "Node u" or "const Node& u"? I think the latter one is more efficient, or
> they are same. However the other version is used sometimes (e.g. Edge
> ListGraph::addEdge(Node u, Node v)).
> If "const Node&" is better, I correct it in every such function I found.

I hope the compiler known it. In most case the node and the edge is an int 
(gnu compiler 4 byte). Just a few adaptor makes bigger item types, but I do 
not know such real case when the item type is bigger than 16 byte.

I think the passing by value is not dangerous, but the correct way should be 
in the coding style.

> B5. In the documentation of ListGraph, SmartGraph, etc. or in the
> documentation of countNodes(), countEdges(), etc. we should state which
> functions run in constant time and which ones run in linear time for each
> implementation.


> B6. I think more concept checks and type checks would be useful for a lot
> of class functions (mainly in complie time). Can graph and map concepts be
> checked in compile time? If they can, I think they should be checked more.
> And in some cases other template parameters should also be checked. For
> example in minimum cost flow algorithms I would like to check if the value
> type of the edge maps are integer (in compile time). Is it possible?

The concept checking is possible:
checkConcept<concept::Graph, ParamGraph>();

It should be used in each algorithm where we use template graphs or maps...

> B7. Is there any way to use Boost and LEDA graphs in LEMON? Do we have
> adaptors for that? I think it would be important.

I think Marci had a LedaGraphAdaptor, but that might be really old. Do you 
have access to the local repository? It may be there:
https://lemon.cs.elte.hu/repos/lemon_loc/

> B8. The nodeMap(), edgeMap(), etc. functions for the graph copying classes
> have two parameters which names are SourceMap and TargetMap but we use
> these names for something really different, so it is annoying.
It is a misnaming. I will modify to FromMap and to ToMap. It is clearer.

> B9. By chance could we implement maps more efficiently without registering
> them to the graph? They could be useful in classes that have a "const
> Graph&" parameter and use additional temporary maps during the computation
> of the algorithm.
I do not think that it could be a great improvement. Each map registering is a 
push into a list and a virtual function call. The memory allocation should be 
much more time consumer than these operations. The current map handling has 
bad performance just when we build a graph by items and the maps are already 
constructed.

> B10. I think Windows platform is more important than it is supported by
> LEMON (and not only with Cygwin). The linux specific modules, tools should
> be separated and there should be warning in the documentation for them. I
> tried to use LEMON under Windows and I didn't have problem unless I would
> like to use time measuring tools or LP tools. Time measuring would be very
> important under Windows too.
> Is there any LP solver that can be used under Windows instead of
> GLPK/CPLEX/SOPLEX?
> Can we adopt the installation checks (make check) under Windows?

I think the lpsolve works on windows too. There is some branched solution to 
provide mingw compatibility (I think we are compatible with mingw(devc++), 
but I have not tried in the recent time). The visual c++ would be a great 
goal, but I do not know how standardized is the current microsoft compiler.

Best, Balazs