COIN-OR::LEMON - Graph Library

Opened 11 years ago

Closed 11 years ago

Last modified 10 years ago

#81 closed task (wontfix)

Port demo files

Reported by: Peter Kovacs Owned by: Peter Kovacs
Priority: major Milestone: LEMON 1.1 release
Component: other Version:
Keywords: Cc:
Revision id:

Description

The demo files that demonstrate the basic data structures, concepts, algorithms and tools should be ported and revised. See also ticket #27.

Attachments (5)

lgf_demo_merge_abc5b9d0c67e.patch (2.3 KB) - added by Peter Kovacs 11 years ago.
lgf_demo.cc is merged with reader_writer_demo.cc [abc5b9d0c67e]
port_hello_lemon_9309a3751e39.patch (4.1 KB) - added by Peter Kovacs 11 years ago.
Port demo/hello_lemon.cc
port_dijkstra_demo_21b33e184d46.patch (3.9 KB) - added by Peter Kovacs 11 years ago.
Port demo/dijkstra_demo.cc
port_topological_ordering_0c44cf0a18b1.patch (4.4 KB) - added by Peter Kovacs 11 years ago.
Port demo/topological_ordering.cc + improve implementation
mod_dijkstra_demo_9b052679a797.patch (3.7 KB) - added by Peter Kovacs 11 years ago.
Redesign dijkstra_demo.cc to read the graph from digraph.lgf

Download all attachments as: .zip

Change History (29)

comment:1 Changed 11 years ago by Peter Kovacs

Type: defecttask

comment:2 Changed 11 years ago by Alpar Juttner

Currently the following demo progs could be ported (the others depends on non ported tools).

dijkstra_demo.cc::

We certainly need this, but it should probably read a .lgf file instead of using a hard-coded graph.

kruskal_demo::

This should also read a file. Alternatively, it could generate random dim2::Points and compute the minimum cost spanning tree over these points. As a second stage, we could also compute an other tree which is as disjoint from the first one as possible, and of minimum cost amongst them. This is a nice example of using the arithmetic map adaptors.

graph_orientation::

Currently it cannot ported because the IterableBoolMap hasn't ported yet, but we certainly need this demo because it is the far most documented one and it also shows the power of LEMON.

hello_lemon.cc, hello_word.cc::

These should be merged together.

reader_writer_demo.cc::

This is again must-to-have.

maps_summary::

This demo code seems unfinished. I don't think we need it.

min_route.cc::

This could also be made into a nice demo, but it needs some work. The motivations/purpose of this demo should also be documented in much more details.

comment:3 Changed 11 years ago by Alpar Juttner

Owner: changed from Alpar Juttner to Peter Kovacs

comment:4 Changed 11 years ago by Peter Kovacs

Status: newassigned

comment:5 in reply to:  2 ; Changed 11 years ago by Peter Kovacs

Replying to alpar:

graph_orientation::

Currently it cannot ported because the IterableBoolMap hasn't ported yet, but we certainly need this demo because it is the far most documented one and it also shows the power of LEMON.

I don't think so, its documentation seems to be very poor. Even the purpose of the program cannot be figured out according to it.

hello_lemon.cc, hello_world.cc::

These should be merged together.

hello_world.cc seems to be a very artificial example, moreover it shows nothing intresting that is not covered by hello_lemon.cc. I suggest to omit this file.

maps_summary::

This demo code seems unfinished. I don't think we need it.

I agree, we don't need this one.

reader_writer_demo.cc::

This is again must-to-have.

It is almost the same as lgf_demo.cc. They should be merged together.

comment:6 in reply to:  5 ; Changed 11 years ago by Alpar Juttner

Replying to kpeter:

Replying to alpar:

graph_orientation::

Currently it cannot ported because the IterableBoolMap hasn't ported yet, but we certainly need this demo because it is the far most documented one and it also shows the power of LEMON.

I don't think so, its documentation seems to be very poor. Even the purpose of the program cannot be figured out according to it.

What are you talking about? Of course, it is a matter of taste to some extent, and it is probably still not perfect, but it is hard to say that it is poorly documented.

comment:7 Changed 11 years ago by Peter Kovacs

I uploaded patch files.

  • arg_parser_doc.patch and lgf_doc.patch contain doc improvements that were done starting form the corresponding demo files. (Actually, they don't belong to this ticket.)
  • lgf_demo_merge.patch merges lgf_demo.cc and reader_writer_demo.cc. The main change is the exception handling for the reading process.

comment:8 in reply to:  6 ; Changed 11 years ago by Peter Kovacs

Replying to alpar:

What are you talking about? Of course, it is a matter of taste to some extent, and it is probably still not perfect, but it is hard to say that it is poorly documented.

Do we talk about the same file?
I talk about demo/graph_orientation.cc in the svn trunk repository (currently -r3501):
http://lemon.cs.elte.hu/svn/lemon/trunk/demo/graph_orientation.cc
It is hard to say that it is not poorly documented.

comment:9 in reply to:  8 ; Changed 11 years ago by Alpar Juttner

Replying to kpeter:

http://lemon.cs.elte.hu/svn/lemon/trunk/demo/graph_orientation.cc
It is hard to say that it is not poorly documented.

We are talking about documentation, aren't we? What about checking the documentation then:

http://lemon.cs.elte.hu/pub/doc/0.7/a00623.html

If someone says it is very well documented, what about assuming first that he knows what he is talking about?

comment:10 in reply to:  7 Changed 11 years ago by Alpar Juttner

Replying to kpeter:

I uploaded patch files.

  • arg_parser_doc.patch and lgf_doc.patch contain doc improvements that were done starting form the corresponding demo files. (Actually, they don't belong to this ticket.)

Why are they here then? We even have open tickets for both.

comment:11 in reply to:  9 ; Changed 11 years ago by Peter Kovacs

Replying to alpar:

We are talking about documentation, aren't we? What about checking the documentation then:

Okay. You are right. I did not find the corresponding .dox file. More exactly I did not search for .dox files at all.

For me a well documented demo file means a demo file with good comments in the file itself. This demo file contains no doc, but the library documentation has a page that documents the file. If I were a user and I browsed the demo directory and found this demo file, I could not understand it easily, since the lack of the documentation in the file itself. That's why it is not so good in my oppinion, and that's why I did not find the doc. At least a link would be important in the file.

Replying to alpar:

Why are they here then? We even have open tickets for both.

I did not find them.

comment:12 in reply to:  11 ; Changed 11 years ago by Alpar Juttner

Replying to kpeter:

For me a well documented demo file means a demo file with good comments in the file itself.

This doesn't work well with Doxygen. It could be there of course in theory, but it cannot in practice.

This demo file contains no doc, but the library documentation has a page that documents the file. If I were a user and I browsed the demo directory and found this demo file, I could not understand it easily, since the lack of the documentation in the file itself.

I don't think it is really a problem. For example if you have Lemon installed on your system, the only way of finding the demo file is through the documentation. And they are well exposed there.

A more important question is where to put the demo file? Into the lemon documentation itself (which is indeed a kind of reference manual) or they should be incorporated into the tutorial?

Once we have a tutorial, there is no too high need of having a lot of demos in the main lemon repo, however

  • Is some sense they also serve as a tester of the library
  • Many of the demos would be quite independent from the logical flow of the tutorial, as well.

comment:13 in reply to:  11 Changed 11 years ago by Alpar Juttner

Replying to kpeter:

Replying to alpar:

Why are they here then? We even have open tickets for both.

I did not find them.

See e.g. #109, #93, #104, or #91, #35. You are also free to open new tickets for them, but they are really irrelevant here (therefore prone to forget about).

Changed 11 years ago by Peter Kovacs

lgf_demo.cc is merged with reader_writer_demo.cc [abc5b9d0c67e]

comment:14 Changed 11 years ago by Peter Kovacs

Replying to alpar:

See e.g. #109, #93, #104, or #91, #35. You are also free to open new tickets for them, but they are really irrelevant here (therefore prone to forget about).

I'm sorry, you are right. I removed these irrelevant patches.

comment:15 in reply to:  12 ; Changed 11 years ago by Peter Kovacs

Replying to alpar:

A more important question is where to put the demo file? Into the lemon documentation itself (which is indeed a kind of reference manual) or they should be incorporated into the tutorial?

Yes, it is a really important question, so it would worth another ticket. But as long as we don't have a detailed tutorial, we should keep these demo files in the library.

I think later we should merge the basic demo files (e.g. hello_lemon.cc, lgf_demo.cc, dijkstra_demo.cc, kruskal_demo.cc, topological_ordering.cc etc.) into the tutorial/book. The more complcated ones (e.g. min_route.cc) could be kept in the doc for showing the library working, demonstrating the power of Lemon, and for test purposes, too.

We should find a good balance between the sample codes involved in the doc, the tutorial and the demo files. E.g. without the demo files arg_parser_demo.cc and lgf_demo.cc, similar code examples should be inserted into the doc itself.

I think test files can also be questionable. I could imagine three main categories instead of the currently used two:

  1. test files for validity checking of almost all tools,
  2. benchmark test files,
  3. demo programs (some not too simple one).

comment:16 in reply to:  15 Changed 11 years ago by Alpar Juttner

Replying to kpeter:

I think test files can also be questionable. I could imagine three main categories instead of the currently used two:

  1. test files for validity checking of almost all tools,
  2. benchmark test files,
  3. demo programs (some not too simple one).

It currently works in this way (at least in the svn). However, I start to think that only the test progs should belong to repository. (And perhaps some demo progs, but only a very limited number.)

The most important reason is that in this way we can separate the development of these auxiliary stuffs (the tutorial and the benchmark) from the base package. It means that

  • they will not be a show-stopper of the core Lemon releases
  • any improvements can be published sooner that the next Lemon version is released.

comment:17 in reply to:  15 Changed 11 years ago by Alpar Juttner

Replying to kpeter:

Replying to alpar: Yes, it is a really important question, so it would worth another ticket. But as long as we don't have a detailed tutorial, we should keep these demo files in the library.

I'm not sure about it. Remember that the hg repo is not the public storage of all the stuff we have ever created but something that will soon lead to the released version.

We've created a separate repository for the tutorial exactly because we wanted to clean up the repo from the loosely related things.

I don't think it is a serious problem if we won't have a large set of nice and tidy demos (or a complete tutorial) when lemon-1.0 is released. If fact it is much better to have it some time later than either to include something half-done into the release or to prolong the development of lemon-1.0 just because of this.

Changed 11 years ago by Peter Kovacs

Port demo/hello_lemon.cc

Changed 11 years ago by Peter Kovacs

Port demo/dijkstra_demo.cc

Changed 11 years ago by Peter Kovacs

Port demo/topological_ordering.cc + improve implementation

comment:18 Changed 11 years ago by Peter Kovacs

I attached 4 patch files. 3 of them are independent port commits, but mod_dijkstra_demo_32758c21f246.patch depends on port_dijkstra_demo_21b33e184d46.patch.

comment:19 in reply to:  2 Changed 11 years ago by Peter Kovacs

Replying to alpar:

kruskal_demo:: Alternatively, it could generate random dim2::Points and compute the minimum cost spanning tree over these points.

How do you imagaine the implementation?

Explicitly build a full graph and calculate all edge costs according to the distances? Or use a FullGraph of appropriate size and create an own map type that calculates the distances implicitly whenever they are used? I think, the later one would be nicer, but FullGraph have not been ported yet.

As a second stage, we could also compute an other tree which is as disjoint from the first one as possible, and of minimum cost amongst them. This is a nice example of using the arithmetic map adaptors.

How did you imagine this implementation?

I have two ideas. Which one would be better? Or do you have other idea?

  • Use e.g. std::pair<bool, int> type for edge costs, where the first value is true if and only if the edge belongs to the former spanning tree, and write a functor that implements lexicographical comparison for this type.
  • Adding a sufficiently large constant to the costs of each edge that belongs to the former spanning tree.

comment:20 in reply to:  18 ; Changed 11 years ago by Alpar Juttner

Replying to kpeter:

I attached 4 patch files. 3 of them are independent port commits, but mod_dijkstra_demo_32758c21f246.patch depends on port_dijkstra_demo_21b33e184d46.patch.

I cannot import --exact attachment:mod_dijkstra_demo_32758c21f246.patch Could you check it?

comment:21 Changed 11 years ago by Alpar Juttner

Milestone: LEMON 1.0 releasePost 1.0

Now, as we decided to have a separate tutorial, it is unclear what kind of demos do we really need in the main lemon repo. Currently we have the following

  • arg_parser_demo.cc
  • graph_to_eps_demo.cc
  • lgf_demo.cc

I think, it is not a problem if it remains as is in release 1.0. There is no reason for deleting them, and later we may want to extend this list, of course.

Thus I leave the ticket open but remove from the release milestone.

Changed 11 years ago by Peter Kovacs

Redesign dijkstra_demo.cc to read the graph from digraph.lgf

comment:22 in reply to:  20 Changed 11 years ago by Peter Kovacs

Replying to alpar:

I cannot import --exact mod_dijkstra_demo_32758c21f246.patch Could you check it?

Use [9b052679a797] instead of [32758c21f246]. It contains the same changes, but it works with --exact.

I'm sorry for the damaged patch file. May I remove it?

comment:23 in reply to:  12 Changed 11 years ago by Peter Kovacs

Resolution: wontfix
Status: assignedclosed

These simple demo files will be moved to the tutorial, and probably some more complex or special demo files will be involved in the repo. So we could close this ticket.

comment:24 Changed 10 years ago by Alpar Juttner

Component: coreother
Note: See TracTickets for help on using tickets.