COIN-OR::LEMON - Graph Library

Opened 11 years ago

Closed 11 years ago

#134 closed task (fixed)

Revise class and visitor interfaces of Bfs/Dfs/Dijkstra

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

Description

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

Attachments (4)

bfs-dfs-dijkstra_c30731a37f91.patch (179.8 KB) - added by Peter Kovacs 11 years ago.
a2a7c764f3b5.patch (24.1 KB) - added by Peter Kovacs 11 years ago.
66644b9cd9eb.patch (1.7 KB) - added by Peter Kovacs 11 years ago.
8d76a7bf9961.patch (24.7 KB) - added by Peter Kovacs 11 years ago.

Download all attachments as: .zip

Change History (28)

comment:1 Changed 11 years ago by 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).

comment:2 in reply to:  1 ; Changed 11 years ago by 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).

comment:3 Changed 11 years ago by 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.

comment:4 Changed 11 years ago by 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)?

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

Replying to kpeter:

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

comment:6 in reply to:  4 ; Changed 11 years ago by 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)

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

comment:7 in reply to:  5 ; Changed 11 years ago by Balazs Dezso

Replying to kpeter:

Replying to kpeter:

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

comment:8 in reply to:  5 ; Changed 11 years ago by 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.

comment:9 in reply to:  6 Changed 11 years ago by 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.

comment:10 in reply to:  7 Changed 11 years ago by 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.

comment:11 in reply to:  8 Changed 11 years ago by 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.

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

What about the first question of this ticket?

comment:13 in reply to:  3 ; Changed 11 years ago by 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?

Changed 11 years ago by Peter Kovacs

comment:14 Changed 11 years ago by Peter Kovacs

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

comment:15 in reply to:  13 ; Changed 11 years ago by 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

comment:16 Changed 11 years ago by Peter Kovacs

Status: newassigned

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

Replying to kpeter:

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

It is in the main branch.

comment:18 in reply to:  15 Changed 11 years ago by 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?

comment:19 Changed 11 years ago by 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.

Changed 11 years ago by Peter Kovacs

Attachment: a2a7c764f3b5.patch added

Changed 11 years ago by Peter Kovacs

Attachment: 66644b9cd9eb.patch added

comment:20 Changed 11 years ago by Peter Kovacs

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

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

Replying to kpeter:

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

make check fails on [a2a7c764f3b5].

comment:22 in reply to:  21 ; Changed 11 years ago by 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.

Changed 11 years ago by Peter Kovacs

Attachment: 8d76a7bf9961.patch added

comment:23 in reply to:  22 ; Changed 11 years ago by 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?

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

Resolution: fixed
Status: assignedclosed

Replying to alpar:

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

Yes we can.

Note: See TracTickets for help on using tickets.