Revise class and visitor interfaces of Bfs/Dfs/Dijkstra

[Peter Kovacs]

The class and the visitor interfaces must be clarified before the release of lemon-1.0.

[Peter Kovacs]

A naming question have arisen in ticket #96. How should we call the named parameters for changing different map types?

In #96 ​alpar said:

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]

I would like to fix my comment:

In #96 alpar said:

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]

What do you think, would XyzMap name be able to used? So XyzMap would be the name for reading and setting, too. Is it possible to implement?

If it is not possible or if you don't like it, I can only suggest SetXyzMap, SetXyzMapType or XyzMapType, but I do not like the third one. I support SetXyzMap, because it is understandable, easy to remember, clear and short. DefXyzMap seems to be really confusing for me.

[Peter Kovacs]

The other questionable thing is the visitor interfaces for Bfs and Dfs.

1. BfsVisit and DfsVisit classes are very similar to Bfs and Dfs, so there is a very huge amount of duplications in the code and in the doc. Couldn't we merge these classes in some way without making the implementation slower? Btw. do we have benchmark test results comparing Bfs/Dfs? and BfsVisit/DfsVisit?
2. In BfsVisit and DfsVisit only one map type (ReachedMap) can be set and there is only one query function in it. Why? Shouldn't we extend these parts of the interface to be (almost) the same as the one in Bfs/Dfs? (like the "Execution Control" group)?

[Peter Kovacs]

Replying to kpeter:

2. In BfsVisit and DfsVisit only one map type (ReachedMap) can be set and there is only one query function in it. Why? Shouldn't we extend these parts of the interface to be (almost) the same as the one in Bfs/Dfs? (like the "Execution Control" group)?

On the other hand there is a special run() function, which can be found in BfsVisit and Dfs, DfsVisit classes, but not in Bfs. This variant runs the algorithm to visit all nodes in the digraph and computes a forest of shortest paths (or DFS paths). Shouldn't Bfs class contain this variant, too?

If it is only a mistake that this function is missing from Bfs, then it is another reason why Bfs and BfsVisit should be merged.

[Balazs Dezso]

Replying to kpeter:

The other questionable thing is the visitor interfaces for Bfs and Dfs.

1. BfsVisit and DfsVisit classes are very similar to Bfs and Dfs, so there is a very huge amount of duplications in the code and in the doc. Couldn't we merge these classes in some way without making the implementation slower? Btw. do we have benchmark test results comparing Bfs/Dfs? and BfsVisit/DfsVisit?

In my opinion, it would be possible, but I'm not sure about, that it would be the proper solution. If we merged the two interfaces, then two kind of different execution model would be mixed. The primary aim of Dfs or Bfs is two compute several map values, however it could be used in more complected cases with special map types, but this usage is limited and sometimes it needs some workarounds to make working. The DfsVisit/BfsVisit? works with callback methods, these classes should be defined in a visitor class. Each event during the execution is signaled to the visitor, so other maps like processed, distance and pred map should not calculated, because these can be processed with callbacks. (if you see the boost graph library, they have similarly two implementations)

2. In BfsVisit and DfsVisit only one map type (ReachedMap) can be set and there is only one query function in it. Why? Shouldn't we extend these parts of the interface to be (almost) the same as the one in Bfs/Dfs? (like the "Execution Control" group)?

Surely, it should not be extended. The interface and the computed maps should be minimized, the visitor class should be used to define computation tasks with the user callbacks. You may see the topology.h or strongly_connected_orientation.cc demi in the svn repository, where you can see some applications of the visitor based interface.

[Balazs Dezso]

Replying to kpeter:

Replying to kpeter:

2. In BfsVisit and DfsVisit only one map type (ReachedMap) can be set and there is only one query function in it. Why? Shouldn't we extend these parts of the interface to be (almost) the same as the one in Bfs/Dfs? (like the "Execution Control" group)?

On the other hand there is a special run() function, which can be found in BfsVisit and Dfs, DfsVisit classes, but not in Bfs. This variant runs the algorithm to visit all nodes in the digraph and computes a forest of shortest paths (or DFS paths). Shouldn't Bfs class contain this variant, too?

If it is only a mistake that this function is missing from Bfs, then it is another reason why Bfs and BfsVisit should be merged.

Yes, this function should be also included into Bfs, however, because these classes has different execution model, in my point of view, these classes should not be merged. Perhaps the Bfs and Dfs could be implemented with the BfsVisit? and DfsVisit?, but I do not know the the efficiency issues of this change.

[Alpar Juttner]

Replying to kpeter:

If it is only a mistake that this function is missing from Bfs, then it is another reason why Bfs and BfsVisit should be merged.

IMHO, a very weak reason.

[Peter Kovacs]

Replying to deba:

In my opinion, it would be possible, but I'm not sure about, that it would be the proper solution. If we merged the two interfaces, then two kind of different execution model would be mixed. The primary aim of Dfs or Bfs is two compute several map values, however it could be used in more complected cases with special map types, but this usage is limited and sometimes it needs some workarounds to make working. The DfsVisit/BfsVisit? works with callback methods, these classes should be defined in a visitor class. Each event during the execution is signaled to the visitor, so other maps like processed, distance and pred map should not calculated, because these can be processed with callbacks. (if you see the boost graph library, they have similarly two implementations)

I see, they should not be merged then. However it would be nice if we have some notes like that in the doc of BfsVisit and DfsVisit classes.

[Peter Kovacs]

Replying to deba:

Yes, this function should be also included into Bfs,

Okay, I will do it.

Perhaps the Bfs and Dfs could be implemented with the BfsVisit and DfsVisit, but I do not know the efficiency issues of this change.

I think it is an important question what should be tested in the future, but it does not cause changes in the interface, so it is a post-1.0 issue.

[Peter Kovacs]

Replying to alpar:

Replying to kpeter:

If it is only a mistake that this function is missing from Bfs, then it is another reason why Bfs and BfsVisit should be merged.

IMHO, a very weak reason.

Reading Balazs's comments I agree.

[Peter Kovacs]

What about the first question of this ticket?

[Alpar Juttner]

Replying to kpeter:

What do you think, would XyzMap name be able to used? So XyzMap would be the name for reading and setting, too. Is it possible to implement?

Could you have a try?

[Peter Kovacs]

[c30731a37f91] contains many improvements in bfs.h, dfs.h and dijkstra.h.

[Peter Kovacs]

Replying to alpar:

Could you have a try?

I tried it, but unfortunately it does not work.

/lemon/dfs.h:298: error: using typedef-name ‘lemon::Dfs<GR, TR>::ProcessedMap’ after ‘struct’
/lemon/dfs.h:168: error: ‘lemon::Dfs<GR, TR>::ProcessedMap’ has a previous declaration here

[Alpar Juttner]

Replying to kpeter:

[c30731a37f91] contains many improvements in bfs.h, dfs.h and dijkstra.h.

It is in the main branch.

[Peter Kovacs]

Replying to kpeter:

Replying to alpar:

Could you have a try?

I tried it, but unfortunately it does not work.

So I suggest using the SetXyzMap form, and DefProcessedMapToBeDefaultMap could be SetStandardProcessedMap/SetBasicProcessedMap or UseProcessedMap/WithProcessedMap or something similar.

What do you think?

[Peter Kovacs]

[a2a7c764f3b5] renames the classes as follows:

• DefXyzMap --> SetXyzMap
• DefHeap --> SetHeap
• DefOperationTraits --> SetOperationTraits
• DefProcessedMapToBeDefaultMap --> SetStandardProcessedMap

I used the SetStandardProcessedMap name because SetProcessedMap/SetStandardProcessedMap are analogous to SetHeap/SetStandardHeap.

[Peter Kovacs]

[66644b9cd9eb] contains doc improvements for BfsVisit and DfsVisit.

[Alpar Juttner]

Replying to kpeter:

[a2a7c764f3b5] renames the classes as follows: ...

make check fails on [a2a7c764f3b5].

[Peter Kovacs]

Replying to alpar:

make check fails on [a2a7c764f3b5].

Yes, I missed the heap_test.cc file, because I forgot that it uses Dijkstra. [8d76a7bf9961] is the fixed changeset.

[Alpar Juttner]

Replying to kpeter:

Yes, I missed the heap_test.cc file, because I forgot that it uses Dijkstra. [8d76a7bf9961] is the fixed changeset.

It went to the main branch. We can close the ticket, can't we?

[Peter Kovacs]

Replying to alpar:

It went to the main branch. We can close the ticket, can't we?

Yes we can.