Revise function-type interface of BFS/DFS/Dijkstra

[Alpar Juttner]

As far as I remember, some concern have arisen about the function-type interface of BFS/DFS/Dijkstra. We must clarify it before the release of lemon-1.0.

[Peter Kovacs]

Maybe it is worth another ticket since it is about the class interface, but I do suggest using SetXyz for named parameters instead of DefXyz, e.g. SetReachedMap, SetDistMap etc..

[Alpar Juttner]

Replying to kpeter:

I do suggest using SetXyz for named parameters instead of DefXyz, e.g. SetReachedMap, SetDistMap etc..

It is indeed better in some sense, but

• these stuff do not set the map, but instead their type. Thus they should be called something like SetReachedMapType.
• On the other hand our coding style convention has a general policy of not using Type in type names. I don't know if it applies here. (Syntactically it does, but semantically it doesn't).

[Peter Kovacs]

Replying to alpar:

• these stuff do not set the map, but instead their type. Thus they should be called something like SetReachedMapType.

I see, Def means define in the currently used names, but it rather reminds me of default. A really extreme example is DefProcessedMapToBeDefaultMap, which is hardly acceptable for me.

So I think they should be called something like SetXyzMap, SetXyzMapType or just XyzMapType.

[Balazs Dezso]

With the function interface a shortest path between two nodes should be computable (distance and the path) in most efficient way (if the shortest path is already known, then the algorithm should be interrupted). In my opinion, this is a blocking problem for the LEMON 1.0.

[Alpar Juttner]

Replying to deba:

With the function interface a shortest path between two nodes should be computable (distance and the path) in most efficient way (if the shortest path is already known, then the algorithm should be interrupted). In my opinion, this is a blocking problem for the LEMON 1.0.

I agree, but I would refine this statement a bit. We actually do not strictly need this feature in LEMON 1.0, but we must have a concept (an API) that makes is possible to implement it later.

[Peter Kovacs]

After some discussions on email, we have agreed to keep the usage of named parameters instead of overloaded bfs(), dfs(), dijkstra() function variants.

For searching s-t paths there are two concepts from which we have to choose. Both of them seems to be correct and easy to use.

1. The run() function gives back a path.
   • bool reached = dijkstra(g,len,s).run(t).empty();
   • p = dijkstra(g,len,s).run(t);
   • p = dijkstra(g,len,s).dist(di).run(t);

2. The run() function gives back a bool value:
   • bool reached = dijkstra(g,len,s).run(t);
   • dijkstra(g,len,s).path(p).run(t);
   • dijkstra(g,len,s).path(p).dist(di).run(t);

Another question is the passing of the target node. I think it would be better if node t was given as the parameter of dijkstra() instead of run(), because it would be easier to differentiate "s-t" searches from "s-all nodes" searches, and the parameters of dijkstra() would determine which named parameters could follow it (e.g. path(), dist() or predMap(), distMap()).

[Peter Kovacs]

Replying to kpeter:

For searching s-t paths there are two concepts from which we have to choose. Both of them seems to be correct and easy to use.

I prefer the second one (bool type run() function).

The most important reason for me is that we want to use the same interface for bfs, dfs and dijkstra. In case of dijkstra returning the path is also a good idea, but in case of dfs it is really strange. Bfs is usually used for checking if two nodes are connected or not. In these cases it is not logical (for me) that the return value is the path, I would prefer a simpler return value, since the following code is a bit strange and so obvious for me.

bool connected = bfs(g,s).run(t).empty();

On the other hand the following code seems to be obvious and simple.

bool connected = bfs(g,s).run(t);

And if other data is needed (distance, path) then named parameters should be used.

Could anyone show examples where the other concept (run() returns the path) is simpler, more obvious or more practical? Is there any significant advantage of that concept?

[Balazs Dezso]

I also prefer the bool result type for run(), if there is a target or maybe a target map. The distance, the path and if a target map is specified, then the reached node should be retrievable with some named parameter member functions.

[Peter Kovacs]

Replying to kpeter:

bool reached = dijkstra(g,len,s).run(t).empty();

...

bool connected = bfs(g,s).run(t).empty();

I made a mistake in these examples. Of course a ! operator is needed in the above lines. Correctly they are:

bool reached = !dijkstra(g,len,s).run(t).empty();
...
bool connected = !bfs(g,s).run(t).empty();

Which is more intresting that we also used such bad codes in our email discussion without noticing that it is not correct. I think this is a significant reason why not choose this concept. Making mistakes is really easy and noticing it is harder using this concept.

[Peter Kovacs]

Replying to deba:

I also prefer the bool result type for run(), if there is a target or maybe a target map. The distance, the path and if a target map is specified, then the reached node should be retrievable with some named parameter member functions.

So the concept could be designed as follows.

Declarations:

  ListDigraph g;
  Node s, t, n;
  Path p;
  int d;
  bool b;
  IntArcMap length(g);
  BoolNodeMap targets(g);
  ArcNodeMap pred(g);
  IntNodeMap dist(g);
  BoolNodeMap proc(g);

The following syntax forms work now. (Of course the order of the named parameters are arbitrary.)

 1. dijkstra(g, length, s)[.predMap(pred)][.distMap(dist)].run();
 2. dijkstra(g, length)[.predMap(pred)][.distMap(dist)].run(s);
 3. dijkstra(g, length)[.predMap(pred)][.distMap(dist)].source(s).run();

There is another named parameter for setting ProcessedMap, but it doesn't seem to work.

Apart from that I suggest the following forms. (The order of the named parameters are arbitrary.)

 4. b = dijkstra(g, length, s, t)[.dist(d)][.path(p)].run();
 5. b = dijkstra(g, length, s)[.dist(d)][.path(p)].run(t);
 6. b = dijkstra(g, length, s)[.dist(d)][.path(p)].target(t).run();
 7. b = dijkstra(g, length)[.dist(d)][.path(p)].source(s).target(t).run();
 8. b = dijkstra(g, length)[.dist(d)][.path(p)].target(t).run(s);
 9. b = dijkstra(g, length)[.dist(d)][.path(p)].run(s, t);
      
10. b = dijkstra(g, length, s, targets)[.reachedNode(n)]
          [.dist(d)][.path(p)].run();
11. b = dijkstra(g, length, s)[.reachedNode(n)]
          [.dist(d)][.path(p)].run(targets);
12. b = dijkstra(g, length, s)[.reachedNode(n)]
          [.dist(d)][.path(p)].targetMap(targets).run();
13. b = dijkstra(g, length)[.reachedNode(n)]
          [.dist(d)][.path(p)].source(s).targetMap(targets).run();
14. b = dijkstra(g, length)[.reachedNode(n)]
          [.dist(d)][.path(p)].targetMap(targets).run(s);
15. b = dijkstra(g, length)[.reachedNode(n)]
          [.dist(d)][.path(p)].run(s, targets);

And I suggest another named parameter called reached(), which would provide an alternative way for getting the bool result.

bfs() and dfs() could be used exactly the same way, except for the parameter length.

What is your opinion?

[Peter Kovacs]

Replying to kpeter:

Apart from that I suggest the following forms. (The order of the named parameters are arbitrary.)

I made a mistake. The 5th form conflicts with the 8th, 14th and even the 2nd, since if DijkstraWizard has a run(Node n) function, then this node should always be considered as source node or as target node.

So I suggest not to support the 5th form. Then the 11th form could also be skipped, but it does not conflict with others.

[Peter Kovacs]

Replying to kpeter:

There is another named parameter for setting ProcessedMap, but it doesn't seem to work.

See #140.

[Alpar Juttner]

Replying to kpeter:

I made a mistake. The 5th form conflicts with the 8th, 14th and even the 2nd, since if DijkstraWizard has a run(Node n) function, then this node should always be considered as source node or as target node.

So I suggest not to support the 5th form. Then the 11th form could also be skipped, but it does not conflict with others.

This is again a very strange way of arguing against something. The forms 2nd, 8th and 14th really seam to be put in the list in order to conflict with 5th. If we don't like the target node as a parameter of run() why would we like the source node at the same place?

Anyway, I strongly prefer to put the source node in the main parameter list (like dijkstra(g,len,s)) for the source is mandatory, and in this way we can spare a run time checking (which is never as efficient as the compile time checks).

The .source(s2) named parameter is still useful for adding extra sources.

[Peter Kovacs]

Replying to alpar:

This is again a very strange way of arguing against something. The forms 2nd, 8th and 14th really seam to be put in the list in order to conflict with 5th.

Absolutely not. First of all, I noticed these conflicts one day later than I suggested the various forms. Secondly, the form 2nd is no working and used in test programs as forms 1st and 3rd, too. See:

• source:test/bfs_test.cc#L91
• source:test/dfs_test.cc#L91
• source:test/dijkstra_test.cc#L94

I regarded these forms and usage cases as samples for the new ones that will be introduced. Forms 8th and 14th are just the analogous to 2nd. So form 5th seems to conflict with the currently supported forms both in the function and the class interface, since Bfs, Dfs, Dijkstra classes also have "run(source)" type functions but they do not have "run(target)" type ones, only "run(source, target)" ones.

If we don't like the target node as a parameter of run() why would we like the source node at the same place?

It is the current concept in both the function and class interface: source node is supported, target node isn't (only as second parameter).

[Alpar Juttner]

Replying to kpeter:

If we don't like the target node as a parameter of run() why would we like the source node at the same place?

It is the current concept in both the function and class interface: source node is supported, target node isn't (only as second parameter).

Passing the source to run() make sense in case of the class implementation as it can be run several times from different (maybe from all) nodes. This kind of usage of the function type interface is impossible.

I could accept that the source node is the parameter of run(), but then it must be mandatory there. Still I prefer to see the source node as a mandatory parameter of dijkstra()/bfs()/dfs() itself, even if it is slightly incompatible with the class implementations.

[Alpar Juttner]

Replying to deba:

I also prefer the bool result type for run(),

Let's use the bool return value, otherwise -- taking the amount of stubbornness in the group into account -- we will never release LEMON 1.0.

if there is a target or maybe a target map. The distance, the path and if a target map is specified, then the reached node should be retrievable with some named parameter member functions.

Sometime in the future, maybe... I'm generally a bit reluctant to add features which would hardly be used by anyone.

[Peter Kovacs]

So here is a new suggestion for the concept.

Declarations:

  ListDigraph g;
  Node s, t;
  Path p;
  int d;
  bool b;
  IntArcMap length(g);
  ArcNodeMap pred(g);
  IntNodeMap dist(g);
  BoolNodeMap proc(g);

For s-all paths only the following form will be supported. (The order of the named parameters are arbitrary.)

  1. dijkstra(g, length, s)
       [.predMap(pred)][.distMap(dist)][.processedMap(proc)]
       .run();

So the following forms (that are working now) will be disabled.

  2. dijkstra(g, length)[...].run(s);
  3. dijkstra(g, length)[...].source(s).run();

For s-t paths the following forms will be supported.

  4. b = dijkstra(g, length, s, t)
           [.dist(d)][.path(p)]
           [.predMap(pred)][.distMap(dist)][.processedMap(proc)]
           .run();
  5. b = dijkstra(g, length, s)
           [.dist(d)][.path(p)]
           [.predMap(pred)][.distMap(dist)][.processedMap(proc)]
           .run(t);

I think these forms (1, 4, 5) cover the most important simple usage cases, for which we would like to use the function interface.

Giving more than one source and/or target nodes won't be supported with the function interface, yet. But these funcionalities can be introduced in later releases without modifing or disabling any of the above usage forms.

Moreover I suggest another named parameter called reached(), which would provide an alternative way for getting the bool result.

bfs() and dfs() could be used exactly the same way, except for the parameter length.

[Peter Kovacs]

[e8e874ee792b] contains a preliminary version of the necessary changes in dijkstra.h to realize the above concept.

Please review it. It still needs doc improvements but if you find it correct otherwise, then I can make the analogous changes in both bfs.h and dfs.h.

[Peter Kovacs]

Replying to kpeter:

[e8e874ee792b] contains a preliminary version of the necessary changes in dijkstra.h to realize the above concept.

For s-t searches it is necessary to use real maps as both PredMap and DistMap even if predMap() and/or distMap() named parameter functions are not used. In [e8e874ee792b] the same default traits class is used for both s-t and s-all searches, so I changed DijkstraWizardDefaultTraits to use real maps as PredMap and DistMap instead of NullMaps.

What do you think, is it okay?

[Balazs Dezso]

Replying to kpeter:

Replying to kpeter:

[e8e874ee792b] contains a preliminary version of the necessary changes in dijkstra.h to realize the above concept.

For s-t searches it is necessary to use real maps as both PredMap and DistMap even if predMap() and/or distMap() named parameter functions are not used. In [e8e874ee792b] the same default traits class is used for both s-t and s-all searches, so I changed DijkstraWizardDefaultTraits to use real maps as PredMap and DistMap instead of NullMaps.

What do you think, is it okay?

I rather suggest an other solution, iff at least one s-t path search is queried, real pred map should be defined, and iff at least one length of an s-t path queried, real dist map should be used. It could be done with the ForkMaps?.

[Peter Kovacs]

Replying to deba:

I rather suggest an other solution, iff at least one s-t path search is queried, real pred map should be defined, and iff at least one length of an s-t path queried, real dist map should be used. It could be done with the ForkMaps?.

It seems to be a little bit difficult. E.g. the path() named parameter should change both the Path type and the PredMap type (PredMap will be a ForkMap). Would both .path(p).predMap(pred) and .predMap(pred).path(p) work properly?

Would this solution be better? I think in most cases both path/predMap and dist/distMap is queried. Would it really be worth to avoid using real local maps in those special cases when we run dijkstra but we do not want to query path/pred or distances? Would it be really faster?

Comparing these two variants seems to be a benchmark question (but I do not suppose that there would be a big difference, just like in #32), so I suggest creating a post-1.0 ticket about it.

[Alpar Juttner]

Replying to deba:

Replying to kpeter:

Replying to kpeter:

[e8e874ee792b] contains a preliminary version of the necessary changes in dijkstra.h to realize the above concept.

For s-t searches it is necessary to use real maps as both

Could anyone tell what "real map" means? I haven't heard this name in connection with LEMON before.

[Peter Kovacs]

Replying to alpar:

Could anyone tell what "real map" means? I haven't heard this name in connection with LEMON before.

I'm sorry for using that name, it just means (for me): "not NullMap".

[Alpar Juttner]

Replying to kpeter:

It seems to be a little bit difficult. E.g. the path() named parameter should change both the Path type and the PredMap type (PredMap will be a ForkMap).

Well, the real problem here is that the Path API is designed to make it easy to get it back as a return value and not as a reference, and there is good reasons for having this desing.

[Peter Kovacs]

Replying to alpar:

Well, the real problem here is that the Path API is designed to make it easy to get it back as a return value and not as a reference, and there is good reasons for having this desing.

I do not really understand the problem.

In [e8e874ee792b] DijkstraWizard gets the path from a Dijkstra object as a return value and assigns it to the variable that was given by the path() function (a pointer is stored for it).

In DijkstraWizard::run() there is a code like this.

Dijkstra<Digraph,LengthMap,TR> dij(...);
...
dij.run(_source, _target);
if (_path) *_path = dij.path(_target); 
if (_di)   *_di   = dij.dist(_target);

So no path is given back as a reference.

[Alpar Juttner]

Replying to kpeter:

Replying to alpar:

Well, the real problem here is that the Path API is designed to make it easy to get it back as a return value and not as a reference, and there is good reasons for having this desing.

I do not really understand the problem.

So no path is given back as a reference.

The problem is when you want to query the path in the function interface. There (path(p)) the path is given as a reference, and it must store this reference. That's why it must be a template function and it should set the type of both PredMap and Path. If the path were a returned as a return value, it wouldn't be a problem.

[Peter Kovacs]

Replying to alpar:

The problem is when you want to query the path in the function interface. There (path(p)) the path is given as a reference, and it must store this reference. That's why it must be a template function and it should set the type of both PredMap and Path. If the path were a returned as a return value, it wouldn't be a problem.

In my solution path() function is template (of course), but changes only the Path type of the traits class, because I set PredMap to be NodeMap<Arc> by defult. Balazs suggested to use NodeMap instead of NullMap only if it is necessary, so b = dijkstra(g,l,s).run(t) would use NullMap, while b = dijkstra(g,l,s).path(p).run(t) would use NodeMap<Arc> (and b = dijkstra(g,l,s).predMap(mymap).path(p).run(t) would use ForkMap<NodeMap<Arc>, MyMap>), which is more difficult to implement, and maybe not really more efficient. However it can be implemented and tested later, while using path return value I think it would be impossible, because we can't make a difference between dijkstra(g,l,s).run(t) and p = dijkstra(g,l,s).run(t). We would have to use NodeMap<Arc> by default. Moreover the analgous problem about dist() and DistMap would be the same in both concepts.

That's why I think that path return value wouldn't be easier to handle and would provide less opportunities for the implementation.

[Peter Kovacs]

[4a3bfa4577a5] contains the full changeset that modifies the function interface of bfs, dfs, and dijkstra.

Could anyone please review it?

[Alpar Juttner]

Replying to kpeter:

[4a3bfa4577a5] contains the full changeset that modifies the function interface of bfs, dfs, and dijkstra.

Could anyone please review it?

I like this changeset. Just two minor comments.

• The paragraphs starting with "Simplicity means" in the doc of *Wizard are quite confusing for me (and probably even more confusing for those are new the to LEMON). I suggest just removing these paragraphs.
• the parameter run() currently has no meaningful return value, therefore we should either
  • explicitly declare it as void run() or
  • define some meaningful return value. For example it can return the number of the evaluated nodes, which can sometimes be useful (e.g. for testing the connectivity). I haven't checked if we can query this directly.

Note, that if we use void return value, then we can still introduce some useful return value later without braking the API, thus this might be the right choice for us.

[Alpar Juttner]

Replying to alpar:

Replying to kpeter:

[4a3bfa4577a5] contains the full changeset that modifies the function interface of bfs, dfs, and dijkstra.

Could anyone please review it?

I like this changeset. Just two minor comments.

... and a third one:

• Shouldn't we use the same return values in case of Dijkstra::run(s[,t]) &Co.?

[Peter Kovacs]

Replying to alpar:

• The paragraphs starting with "Simplicity means" ... I suggest just removing these paragraphs.

Okay, let's remove it.

• the parameter run() currently has no meaningful return value, therefore we should either

It is true only for the s-all case. For s-t searches it returns an important value: the reached status. If we would like to keep this concept (as we agreed before) and use the same class ( DijkstraWizard) for both s-t and s-all searches, then we can't use neither of the choices you suggested.

Note, that if we use void return value, then we can still introduce some useful return value later without braking the API, thus this might be the right choice for us.

For s-t searches it returns useful value and for s-all searches it can be used as a void function.

[Peter Kovacs]

Replying to alpar:

... and a third one:

• Shouldn't we use the same return values in case of Dijkstra::run(s[,t]) &Co.?

Yes, it would be much better. If the distance wouldn't have been a good choice for the return value in the function interface, then it is probably a bad choice for the Dijkstra::run(s,t), too. So I suggest using bool run(s,t) in the class interface, too. (There are functions for getting every data.)

[Alpar Juttner]

Replying to kpeter:

Replying to alpar:

• The paragraphs starting with "Simplicity means" ... I suggest just removing these paragraphs.

Okay, let's remove it.

• the parameter run() currently has no meaningful return value, therefore we should either

It is true only for the s-all case. For s-t searches it returns an important value: the reached status.

That's absolutely clear, of course. What I mean is that run(t) should return a status bool (or status anything), and run() should return void or (maybe in the next release) something meaningful.

Of course, it implicitly mean, that we must get rid of the form dijkstra(g,len,s,t).run(), which decision I would also very welcome. For example, I don't know what happens currently when I write this

dijkstra(g,len,s,t).run(t);

or this

dijkstra(g,len,s,t1).run(t2);

I see no use of and reason for this kind of freedom.

Nota bene, compile time check is always better than the runtime one.

If we would like to keep this concept (as we agreed before) and use the same class ( DijkstraWizard) for both s-t and s-all searches, then we can't use neither of the choices you suggested.

It could be done somehow, even if we wanted to keep the form dijkstra(g,len,s,t).run(), (which we probably shouldn't) is various ways

• dijkstra(g,len,s,t) and dijkstra(g,len,s) could give back different classes thus the return value type of run() can be different (they can have different declaration/definition)
• In reality, there is no such a thing as bool in C++. It just pretend that is has. Therefore we can return an integer in both case and can define any useful meaning to it.

Note, that if we use void return value, then we can still introduce some useful return value later without braking the API, thus this might be the right choice for us.

For s-t searches it returns useful value and for s-all searches it can be used as a void function.

I was not talking about the s-t searches here.

[Peter Kovacs]

Replying to alpar:

Of course, it implicitly mean, that we must get rid of the form dijkstra(g,len,s,t).run(), which decision I would also very welcome.

I see. This is an important point that wasn't mentioned in your former comment.

For me this form seems to be a little bit more logical, since the parameters of dijkstra() determines which named parameters can be used. However using run(t) is more analogous to the class interface.

For example, I don't know what happens currently when I write this dijkstra(g,len,s,t1).run(t2);

Then t2 is used as the target node.

I see no use of and reason for this kind of freedom.

The only advantage is that you can use the form which is more logical or comfortable for you, since both works. But you are right that this kind of freedom could cause some problems, so maybe it would be better to allow only one of these forms.

So please vote:

1. Allowing only dijkstra(g,l,s).run(t) form.
2. Allowing only dijkstra(g,l,s,t).run() form.
3. Allowing both forms.

Choosing 1. (as you suggested) would solve all the problems you noted.

[Peter Kovacs]

Replying to kpeter:

So please vote:

1. Allowing only dijkstra(g,l,s).run(t) form.
   
2. Allowing only dijkstra(g,l,s,t).run() form.
   
3. Allowing both forms.

The problems of choosing 3. are noted above, but choosing 1. (or 2.) is also problematic, since it is not clear and difficult to remember where the target node should be given.

Balazs offered another concept, that seems to be better. dijkstra() would have excatly two parameters: g and l, which are clearly necessary. All the other paramaters, that are optional, go to the run() function. So we could use the following forms:

1. dijkstra(g,l).run(s);
2. b=dijkstra(g,l).run(s,t);

It is a clear concept and easy to remember, and it is fully analogous with the class interface! Moreover it has another advantage, that for bfs() and dfs() it allows new use cases: bfs(g).run(), dfs(g).run(), which visit all nodes in the digraph as Bfs/Dfs::run().

So the function interface would have exactly the same two or three run(...) functions as the class interface.

[Peter Kovacs]

[931190050520] implements the function-type interfaces so that both source and target nodes have to be given as the parameter of run().

It turned out that this concept is not only more clear and more analogous to the class interface, but it is also more easier to implement, since wizard classes do not have to store source and target nodes.

I really like this concept. What do you think? Could someone please check the changeset?

[Peter Kovacs]

[931190050520] went to the main branch.

I created a new ticket about Balazs's suggestion., see: #151. So I think there isn't any other open issues in this ticket.