Revise StoreBoolMap implementation

[Peter Kovacs]

1. StoreBoolMap is now write-only, but it is said to be read-write map in the documentation.

2. The set() function is const, which is strange. That is why _end iterator is declared mutable. I suggest a non-const set() function, a const _begin and a non-const _end iterator.

[Balazs Dezso]

The question is not is not so easy, I explain why the set() is const. Sometimes we would like to write similar codes: kruskal(g, c, StoreBoolMap?(back_inserter(st)));

Because the created StoreBoolMap? is temporary, it cannot be converted to non-const reference. The right solution would be that, if normal map is taken as parameter, then it should be get as normal reference, while in other case as value should be get and not as const reference. But it hard to implement such solution, therefore in such case instead of value argument a const reference argument is used, and in this case the set() of the map should be const.

The current solution is a hack, so it might be deleted, as I uploaded a patch for it. But in this case loading a vector as a bool map is hard because the following code should be used: StoreBoolMap?<back_insert_iterator<vecto<Edge> > > sbm(back_inserter(v)); kruskal(g, c, sbm);

[Peter Kovacs]

Replying to deba:

Sometimes we would like to write similar codes: kruskal(g, c, StoreBoolMap(back_inserter(st)));

I do not agree with it. If kruskal() takes a WriteMap as third parameter, then it must be a reference parameter and not a const reference, otherwise kruskal() cannot be used with other WriteMaps.

So I do not support the current solution. I think it is an ugly hack, moreover it makes impossible to use the kruskal() function with the most WriteMaps. I suggest using

  StoreBoolMap<back_insert_iterator<vector<Edge> > > sbm(back_inserter(v));
  kruskal(g, c, sbm);

even if it is less comfortable.

[Alpar Juttner]

Replying to deba:

Sometimes we would like to write similar codes: kruskal(g, c, StoreBoolMap?(back_inserter(st)));

We do not want to write this, for it can be written as kruskal(g, c, back_insterter(st)));. At least, I hope.

[Alpar Juttner]

Replying to kpeter:

I suggest using

  StoreBoolMap<back_insert_iterator<vector<Edge> > > sbm(back_inserter(v));
  kruskal(g, c, sbm);

even if it is less comfortable.

It must be avoided at any cost if it is possible.

[Alpar Juttner]

• For me, an "ugly hack" is a hack that shows a bad programming practice. This is not the case here, but the purpose of this hack is to overcome a major conceptual design failure of C++. Therefore the only question is whether it endangers the reliability and safety of the code. The answer for this is clearly no.
• I want to make it possible to use temporal map adaptors wherever we can.
• What we have to find out is how to do it with non-const set() functions. Isn't it possible to use const reference as a parameter of kruskal(), apply a const_cast<> in the main code block and pass trough this non-const write-map?

[Peter Kovacs]

Replying to alpar:

We do not want to write this, for it can be written as kruskal(g, c, back_insterter(st)));. At least, I hope.

I support this variant of kruskal().

However if kruskal() (or another function) has a parameter that is a WriteMap, there should be such variant of the function that takes the map as non-const reference, too.

[Alpar Juttner]

Replying to kpeter:

Replying to alpar:

We do not want to write this, for it can be written as kruskal(g, c, back_insterter(st)));. At least, I hope.

I support this variant of kruskal().

It currently works in this way, doesn't it? Please confirm.

However if kruskal() (or another function) has a parameter that is a WriteMap, there should be such variant of the function that takes the map as non-const reference, too.

You are completely right, kruskal() should support both const and non-const third parameter. Hopefully, it can be done.

[Peter Kovacs]

Replying to alpar:

It currently works in this way, doesn't it? Please confirm.

It works, see: test/kruskal_test.cc​.

[Peter Kovacs]

So after all do we need const StoreBoolMap?
For kruskal() it is not necessary. Is there any other important usage? For example if I would like to use StoreBoolMap as ReachedMap or ProcessedMap for bfs(), dfs() or dijkstra() (the function interface), could I use a non-const StoreBoolMap, or do I need the const variant?

For example, would the following code work with the non-const variant?

bfs(gr,s)
  .reachedMap(StoreBoolMap(back_inserter(v)))
  .run();

[Balazs Dezso]

In my point of view, the implementation without mutable iterators can be go to the main repo. The main question of this ticket is whether constant temporary variables should passed as write map parameter. I'm rather to protest at this kind of parameter passing because the following reason. It would be necessary, that on each place, where a write or a read-write map is passed, the parameter should be changed to const, and const_cast should be used, or at least the function should be duplicated. It would cause code duplications or a very bad design.

[Peter Kovacs]

I tried to run the following code on the small graph used in hello_lemon.cc.

std::vector<Node> x;
dfs(g,s).processedMap(
  StoreBoolMap<std::back_insert_iterator<std::vector<Node> > >
  (std::back_inserter(x)) ).run();

The compilation was successful, but it caused segmentation error. If I replace the *_end++ = key; line with something else (e.g. std::cout << value;) in the implementation of StoreBoolMap::set() then it works. What is the problem? Do you have an idea?

It is also interesting that the above example can be compiled with non-const set() function and non-mutable _end. So I think this variant is sufficient to be a public tool.

Moreover I suggest a storeBoolMap() function to make the usage of StoreBoolMap easier. For example:

std::vector<Node> x;
dfs(g,s).processedMap(storeBoolMap(std::back_inserter(x))).run();

Is there any other convenient way to store the nodes in the processed order using dfs() function? This would be much easier than creating an own writemap as in the demo file topological_ordering.cc (in the svn repo).

[Peter Kovacs]

Replying to deba:

The main question of this ticket is whether constant temporary variables should passed as write map parameter. I'm rather to protest at this kind of parameter passing because the following reason.

I do agree with Balazs.

However another important usage is shown in my above comment.

[Balazs Dezso]

Replying to kpeter:

I tried to run the following code on the small graph used in hello_lemon.cc.

std::vector<Node> x;
dfs(g,s).processedMap(
  StoreBoolMap<std::back_insert_iterator<std::vector<Node> > >
  (std::back_inserter(x)) ).run();

The compilation was successful, but it caused segmentation error. If I replace the *_end++ = key; line with something else (e.g. std::cout << value;) in the implementation of StoreBoolMap::set() then it works. What is the problem? Do you have an idea?

See Ticket #96.

[Balazs Dezso]

Sorry, Ticket #95.

[Peter Kovacs]

Replying to deba:

Sorry, Ticket #95.

Thanks.

[Peter Kovacs]

I uploaded an improved patch for this class.

1. The set() function is non-const and the iterator is non-mutable.
2. The documentation is improved (examples added).
3. A storeBoolMap() function is added.
4. Test cases are added to maps_test.cc.

Now the following codes works properly.

std::vector<Node> v; 
dfs(g,s).processedMap(storeBoolMap(std::back_inserter(v))).run();

std::vector<Node> v(countNodes(g)); 
dfs(g,s).processedMap(storeBoolMap(v.begin())).run();

I think applying the patch we can close this ticket. What do you think? Please check the documentation changes.

[Alpar Juttner]

Replying to kpeter:

I uploaded an improved patch for this class.

The changeset went to the main branch, see [c7d30f7810e5].