COIN-OR::LEMON - Graph Library

Opened 15 years ago

Closed 15 years ago

#149 closed task (fixed)

Removing \todo commands

Reported by: Peter Kovacs Owned by: Alpar Juttner
Priority: major Milestone: LEMON 1.0 release
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description

We still have a lot of \todo commands in the main repository (mainly in bfs.h, dfs.h, dijkstra.h). Each of these commands should be revised and removed. The ones that are easy to do, should be done immediately, the other ones (that are too difficult or not clear or just needs too much time) should be noted in tickets.

Attachments (1)

e7f8647ce760.patch (12.3 KB) - added by Alpar Juttner 15 years ago.

Download all attachments as: .zip

Change History (22)

comment:1 Changed 15 years ago by Alpar Juttner

Owner: changed from Alpar Juttner to Peter Kovacs

comment:2 Changed 15 years ago by Peter Kovacs

Status: newassigned

comment:3 Changed 15 years ago by Alpar Juttner

Owner: changed from Peter Kovacs to Alpar Juttner
Status: assignednew

I've started to work on this now (in fact I started that long long ago, but now I've refreshed the patch and I'm about to finish it).

A patch is coming soon, but I still have couple of questions. For example:

  • Here is a todo in lemon/concept_check.h:
    ///\todo Are we still using BOOST concept checking utility?
    ///Is the BOOST copyright notice necessary?
    
    Is this still relevant?
  • This command appears in dfs.h/bfs.h/dijkstra.h at the function createPredMap().
     ///\todo The digraph alone may be insufficient to initialize
    
    It was me who wrote this todo, and as I remember I found some realistic use case for some special map (or default value???), when we need to pass more parameter, but I cannot recall what it was. Could anyone help me?

comment:4 Changed 15 years ago by Alpar Juttner

We also have the following todo at two places in lemon/dijkstra.h

    ///\todo If it is set to a real map,
    ///Dijkstra::processed() should read this.

What does it mean? Does it indicate a bug? Or a feature request? What does "real map" mean here?

comment:5 in reply to:  3 ; Changed 15 years ago by Alpar Juttner

Replying to alpar:

 ///\todo The digraph alone may be insufficient to initialize

This also appears at createHeapMap(), and it really makes sense there. The graph alone sometimes is not enough to create the heap I guess.

comment:6 in reply to:  4 ; Changed 15 years ago by Peter Kovacs

Replying to alpar:

What does it mean? Does it indicate a bug? Or a feature request? What does "real map" mean here?

It is not a bug, just a feature request. "Real map" means exactly the same as in #96 (see comments 26 and 27): not a NullMap.

Now Dijkstra::processed() uses the heap to determine the return value whether or not the current ProcessedMap type is NullMap or not and whether it uses local map or not. The todo ask for using the given processed map (_processed) if it is not of type NullMap and using the heap otherwise.

I think it would need some template tricks to implement or we could introduce a bool flag that shows whether SetProcessedMap or SetStandardProcessedMap named class parameters were used. But in the the later case extra codes in DijkstraWizard would also be needed, since it does not use the above named class parameters but defining a traits class explicitly.

comment:7 in reply to:  5 ; Changed 15 years ago by Peter Kovacs

Replying to alpar:

This also appears at createHeapMap(), and it really makes sense there. The graph alone sometimes is not enough to create the heap I guess.

What could we do then? I think we could wait until a real use-case appears in which it is really needed. In this case we would see the possible options and could make better decision. Maybe there wouldn't be such request or it could be solved in a way that not breaks the Dijkstra API.

comment:8 in reply to:  7 ; Changed 15 years ago by Alpar Juttner

Replying to kpeter:

What could we do then? I think we could wait until a real use-case appears in which it is really needed. In this case we would see the possible options and could make better decision. Maybe there wouldn't be such request or it could be solved in a way that not breaks the Dijkstra API.

Please check and confirm whether we can do such a change without breaking the API.

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

Replying to alpar:

Please check and confirm whether we can do such a change without breaking the API.

I do not understand the whole question exactly. Unless I see a reliable use-case for which the current API is insufficient, I can't say anything.

comment:10 in reply to:  9 ; Changed 15 years ago by Alpar Juttner

Replying to kpeter:

I do not understand the whole question exactly. Unless I see a reliable use-case for which the current API is insufficient, I can't say anything.

The question is: can we add new parameters to that function without breaking the API?

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

Replying to alpar:

The question is: can we add new parameters to that function without breaking the API?

Why not? They could have default values, or we can overload the function. Could it cause any problem?

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

Replying to kpeter:

Could it cause any problem?

Well, we are slowly progressing. This is I would like to have someone to check.

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

Replying to alpar:

Well, we are slowly progressing. This is I would like to have someone to check.

I tested it. I added some new parameters to createXyzMap() functions with default values, and everything compiles without any problem.

comment:14 in reply to:  6 ; Changed 15 years ago by Alpar Juttner

Replying to kpeter:

Replying to alpar:

What does it mean? Does it indicate a bug? Or a feature request? What does "real map" mean here?

It is not a bug, just a feature request.

Would you be so kind as to create an "enhancement" ticket on this issue? Many thanks in advance.

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

Replying to kpeter:

Replying to alpar:

Well, we are slowly progressing. This is I would like to have someone to check.

I tested it. I added some new parameters to createXyzMap() functions with default values, and everything compiles without any problem.

I've investigated a bit too, the situation is not so easy. createXyzMap()s are there to be called by create_maps(). Therefore this later functions should decide which version createXyzMap() is to be used, which is impossible.

On the other hand I see no good solution at this moment, thus I leave it as is.

Changed 15 years ago by Alpar Juttner

Attachment: e7f8647ce760.patch added

comment:16 Changed 15 years ago by Alpar Juttner

[e7f8647ce760] is a changeset removing all \todo commands. Could anyone review it?

As far as I see all significant items are already in the trac, but please check this, too.

comment:17 in reply to:  16 Changed 15 years ago by Peter Kovacs

Replying to alpar:

[e7f8647ce760] is a changeset removing all \todo commands. Could anyone review it? As far as I see all significant items are already in the trac, but please check this, too.

It's okay. If the changeset goes to the main branch, the ticket can be closed.

comment:18 in reply to:  14 Changed 15 years ago by Peter Kovacs

Replying to alpar:

Would you be so kind as to create an "enhancement" ticket on this issue? Many thanks in advance.

See #152.

comment:19 in reply to:  3 ; Changed 15 years ago by Balazs Dezso

Replying to alpar:

I've started to work on this now (in fact I started that long long ago, but now I've refreshed the patch and I'm about to finish it).

A patch is coming soon, but I still have couple of questions. For example:

  • Here is a todo in lemon/concept_check.h:
    ///\todo Are we still using BOOST concept checking utility?
    ///Is the BOOST copyright notice necessary?
    
    Is this still relevant?

Our solution is very similar to the boost code, but it is a complete rewriting of the same idea. The function_requires is used also in boost, but it differs slightly from out implementation.

  • This command appears in dfs.h/bfs.h/dijkstra.h at the function createPredMap().
     ///\todo The digraph alone may be insufficient to initialize
    
    It was me who wrote this todo, and as I remember I found some realistic use case for some special map (or default value???), when we need to pass more parameter, but I cannot recall what it was. Could anyone help me?

I know an example for heap initialization. In that case the heap reference map is not always sufficient to create a heap. For r-ary heaps the theoretical best degree is (m / n + 2), which could be calculated only from the graph. But in my point of view, it is not a problem, because the non-default pred-map or heap could be a local variable, which can be passed to the algorithm.

comment:20 in reply to:  19 Changed 15 years ago by Alpar Juttner

Replying to deba:

Our solution is very similar to the boost code, but it is a complete rewriting of the same idea. The function_requires is used also in boost, but it differs slightly from out implementation.

So, I changed to the Boost copyright notices to a credit mentioning, that this part of LEMON was inspired by Boost. See [d8dc5acf739b].

comment:21 Changed 15 years ago by Alpar Juttner

Resolution: fixed
Status: newclosed

As far as I see every issues here has been satisfactorily solved, so I close the ticket.

Note: See TracTickets for help on using tickets.