[Lemon-devel] Development suggestions (long letter)

[Kovács Péter]

Dear Developers,

I've collected some errors, ideas and development suggestions for LEMON. I
would be pleased if you may answer or solve as many of them as you can (it is
not urgent of course).


DOCUMENTATION
=============
A1. A good tutorial is very important. This is the starting point for a new
user, and maybe it is worth to read for those who are still using LEMON, too.
The current tutorial is very good, it is clear, understandable and presents a
lot of LEMON. That is why I think it should be underlined more, e.g. it should
be placed to the top navigation bar as a new tab.

The following points are about the Tutorial: 
	A1.1. Maybe the "How to start using LEMON" page should also be involved in
the Tutorial, somewhere in the beginning.
	A1.2. Graphs page should also be involved in the Tutorial, and this page
should be merged with the Basic concepts page. 
	A1.3. Algroithms, Basic concepts, Getting Started, LEMON Graph File Format,
Maps I., Maps II., and Background of Reading and Writing pages should be
involved only in the Tutorial, because in this way there are too many related
pages, so they are confused.  
	A1.4. The Maps page should be removed and all of its contents should be
revised and moved to Maps I. or Maps II. page.
	A1.5. Maybe a FAQ and/or tips&tricks page would be useful in the Tutorial.
There are tipical problems, difficulties with using LEMON or such libraries
(e.g. for users with less c++ experiance). For example I often forget that
NodeIt<>, EdgeIt<>, NodeMap<>, EdgeMap<> types don't have default constructor
(which is clear otherwise) and we could advise useful tips such as using -O2
option for g++.
	A1.6. The Tutorial page should be linked from the starting page of the
documentation, after "Quick Tour to LEMON" or after "How to start using LEMON"
(and maybe it could be placed to the top navigation bar as a new tab).

A2. I think a page on which we compare LEMON to other libraries (mainly Boost
BGL and LEDA) would be very important. We should promote our library and we
should present the points of view in which LEMON is better than the others. As
far as I know Balazs have very good benchmark tests with Dijkstra and Preflow.
I think these results and some charts would be great in the documentation. 
And just to be fair we should presents aspects in which LEDA or Boost is
better or different, e.g. algorithms that are involved in LEDA or Boost, but
missing from LEMON (yet) or the fact that Boost BGL is much more similar to
STL (in naming convention, using functors, etc.).

A3. A page with the developers of LEMON should be written. I think a list of
names with from-to years would be good enough (without further details). This
would be a kind of history and "thanks to" page.

A4. It would useful if all the source files (*.h) could also be seen from the
documentation, not only the demo files.

A5. For the problems that have more than one solution in LEMON there should be
a comparing page in the documentation (differences/similarities in using,
advantages/disadvantages of each solution, theoretical running times and
efficiency in practice).

A6. Maybe the documentation should contain notes on the implementation of
significant data structures (and even significant algorithms). For exapmle the
relative size of sturctures like Node, Edge, NodeIt, EdgeIt, etc. is good to
know in a lot of cases.  

A7. If we start developing "LEMON 1.0", I think we should pay more attention
to the documentation. I found some important points about this:
	A7.1. The documentation should be more uniform. For example "check",
"return", etc. or "checks", "returns", etc. should be used for describing a
method. Doxygen generates "returns" form \return, so I suggest using "checks",
"returns", etc. everywhere. And I also suggest using \param, \pre, \return,
\retval, \warning, etc. more.
	A7.2. There should be more source code examples for classes (showing the
usual way(s) to use) or links to the corresponding part of the tutorial (e.g.
Bfs, Dfs, Dijkstra).
	A7.3. There should be exact formal definitions of the corresponding problem
or external links to wiki pages or something similar for algorithms (e.g.
Circulation documentation).
	A7.4. I think the documentation of algorithms should contain what kind of
graph/map/etc. concepts are expected for the parameters. I think it would be
important, I miss it.
	A7.5. It would be good if the theoretical running times of class member
functions were noted (e.g. constant/linear time a query functions, start() and
run() methods, etc.). 
	A7.6. In some classes the doxygen template interface are differ from the
normal interface, the default template parameters are usually missing. However
this isn't uniform, e.g. the template interface is different in Preflow and
EdmondsKarp. I think default template parameters should also be marked.
Although this version is longer and maybe more confused, but shows important
and useful information.

A8. I found some concrete errors, too:
	A8.1. graph_io.dox is the union of lemon_file_format.dox and
read_write_bg.dox, so graph_io.dox should be removed from the repository (I
think this is the older version).
	A8.2. On "Algorithms" page (algorithms.dox), in the second section (DFS) the
code samples are missing. Maybe something is wrong with the linking of the
demo file topological_ordering.cc.
	A8.3. "Developers' interface to graph structures" and "Undirected graph
structures" pages should be written or removed (they are empty now).
	A8.4. The \file command is missing from some source files, so they are not
listed on the "Files" page, only on the "Directories" page, but as a simple
text (without description) not as a link:
		demo/mip_demo.cc, demo/arg_parser_demo.cc, demo/steiner_demo.cc, 
		lemon/arg_parser.cc, lemon/concept_check.h, 
		lemon/eps.cc, lemon/lp_utils.h, lemon/static_graph.h,
		lemon/bits/lp_id.h, lemon/bits/path_dump.h,
		lemon/bits/mingw32_time.h, lemon/bits/mingw32_time.cc
	The following two files are very simple config files, so I think \file
command is not necessary, but I think the usual header should be placed into
them too: lemon/config.h.in, lemon/config.h.
	A8.5. On "Maps I." page: "If a new node is added a default value is mapped to
it. You can define the default value by passing a second argument to the map's
constructor." It is wrong. The default value is always made by the default
constructor of the corresponding type.
	A8.6. This is a question: the DIMACS to LGF converter was a demo before, but
now it is in the tools directory. However I can't find it in the
documentation. Why?
	A8.7. I think there should be a link to "Graph Structure Concepts" on the
"Graph Structures" page.



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.

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.

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

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.

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?

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.

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.

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.

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?


LEMON SITE
==========
C1. There are some pages that should be revised (e.g. "local info" pages,
"topics and problem groups", etc.) nad the site should be made more up-to-date.

C2. Google ranking could be better, but it isn't so bad now. My results:
	lemon optimization | lemon optimization library  -->  1st hit
	lemon library  -->  2nd and 3rd hit
	lemon graph | lemon graph library  -->  10th hit
	lemon network library | lemon network  -->  nothing (why?)
	lemon networks | lemon networks library  -->  4th hit

C3. What about www.lemonlibrary.com or www.lemonlibrary.org? :)

C4. A lighter background image would be better. What about this one?
	http://people.inf.elte.hu/kpeter/lemon/lemon-bg.png


I apologize for this long letter, but I hope you find most of the mentioned
points relevant and sensible.

In one of his letters Balazs inquired about suggestions for the basic graph
structures. I think B2, B3 (and B4) is relevant for this.

Best, Peter