COIN-OR::LEMON - Graph Library

Opened 10 years ago

Closed 10 years ago

#36 closed task (fixed)

Revise StoreBoolMap implementation

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

Description

  1. StoreBoolMap is now write-only, but it is said to be read-write map in the documentation.
  1. 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.

Attachments (1)

store_bool_map.patch (5.1 KB) - added by kpeter 10 years ago.

Download all attachments as: .zip

Change History (21)

comment:1 Changed 10 years ago by alpar

  • Owner changed from alpar to kpeter

comment:2 Changed 10 years ago by kpeter

  • Status changed from new to assigned

comment:3 Changed 10 years ago by alpar

  • Version set to hg main

comment:4 follow-ups: Changed 10 years ago by deba

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);

comment:5 in reply to: ↑ 4 ; follow-up: Changed 10 years ago by kpeter

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.

comment:6 in reply to: ↑ 4 Changed 10 years ago by alpar

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.

comment:7 in reply to: ↑ 5 Changed 10 years ago by alpar

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.

comment:8 follow-up: Changed 10 years ago by alpar

  • 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?

comment:9 in reply to: ↑ 8 ; follow-up: Changed 10 years ago by 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().

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.

comment:10 in reply to: ↑ 9 ; follow-up: Changed 10 years ago by alpar

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.

comment:11 in reply to: ↑ 10 Changed 10 years ago by kpeter

Replying to alpar:

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

It works, see: test/kruskal_test.cc.

comment:12 Changed 10 years ago by kpeter

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();

comment:13 follow-up: Changed 10 years ago by deba

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.

comment:14 follow-up: Changed 10 years ago by 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?

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

comment:15 in reply to: ↑ 13 Changed 10 years ago by kpeter

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.

comment:16 in reply to: ↑ 14 ; follow-up: Changed 10 years ago by deba

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.

comment:17 in reply to: ↑ 16 ; follow-up: Changed 10 years ago by deba

Sorry, Ticket #95.

comment:18 in reply to: ↑ 17 Changed 10 years ago by kpeter

Replying to deba:

Sorry, Ticket #95.

Thanks.

Changed 10 years ago by kpeter

comment:19 follow-up: Changed 10 years ago by kpeter

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.

comment:20 in reply to: ↑ 19 Changed 10 years ago by alpar

  • Resolution set to fixed
  • Status changed from assigned to closed

Replying to kpeter:

I uploaded an improved patch for this class.

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

Note: See TracTickets for help on using tickets.