Maps don't initialize subseqnetly added graph elements to the map-constructor's initial value.

[Charles Wilcox]

Greetings all.

I'm experiencing a ( perceived ) problem with Maps. Maps "know" when new elements in a graph are added, and provide a default value. One of the two constructors for a map allows a user ( me ) to specify this default value. I expect that, all elements of a graph will receive that value upon map-construction, and I expect subsequent graph element additions to also take on that value. I observe that, all elements of a graph *do* receive the default value upon map-construction, but *do not* set my specified default-value when new elements are subsequently added to the graph.

I have a test program, which I will attach.

I also have a diff against lemon/bits/{array,vector}_map.h that attempt to remedy this situation, and hopefully reinforce my expected behaviour.

Please advise on if this is in fact a bit, or if it is intentional by design and my understanding is incorrect.

[Charles Wilcox]

Output of my test program running.

[Charles Wilcox]

Test .cpp file to demonstrate my observed behavior, and my expected behavior.

[Charles Wilcox]

'diff -u' showing local code changes to get the observed behavior to match the expected behavior.

[Alpar Juttner]

This is not a bug in the sense that this is the intended and known behavior. But is does not mean we can't change it.

The reasons for this design was

• a kind of "minimalism",
• possible performance issues (they have never been evaluated) and
• similarity with std::vector. (When you resize() an std::vector, it will be filled with default constructed elements, even if it was initialized like std::vector<int> v(12,15);)

I have also experienced that this behavior may sometimes be inconvenient and/or error-prone. So I am open to rethink the question.

We have a policy to keep backward compatibility as much as we can. The proposal of this ticket is on the borderline in this respect, as it may break codes that rely on the fact that newly added elements are default constructed even if an initial value was given. I would never utilize this feature, I hope neither have done other people.

[Charles Wilcox]

Hrm. This is unfortunate for me. I was under the impression that maps would always take on this value.

Regarding performance, AFAIK with my relative inexperience with the inner-workings of Lemon, my code patch does not perform any more memory writes than the previous code, it simply uses "const Value initval" instead of "Value()" as the value to write.

I'm personally of the opinion that the current behaviour is mis-leading and error-prone, not to mention very inconvenient. ( I have a stack of graph adaptors, maps based on adapted-graphs and map-adaptors of other maps; setting all of these derived maps consistently and correctly becomes much more difficult if maps don't set new graph-element's values to my construction-time parameter. )

I completely understand changing existing behavior and "breaking" other people's code.

Perhaps another constructor API that enabled the user to say, Map( Graph, Init_value, bool set_future_graph_elements_to_the_init_value )? Although I'd rather the current API do what I expected. :-(

Looking at the tutorial, the end of the map section does mention this behvaior:

• http://lemon.cs.elte.hu/pub/tutorial/sec_basics.html#sec_digraph_maps

It would be really nice if the Doxygen clarified this. Currently, I've found no mention of this there. For example, the Digraph::NodeMap? concept page:

• http://lemon.cs.elte.hu/pub/doc/1.2.1/a00238.html

[Alpar Juttner]

Replying to willo:

Regarding performance, AFAIK with my relative inexperience with the inner-workings of Lemon, my code patch does not perform any more memory writes than the previous code, it simply uses "const Value initval" instead of "Value()" as the value to write.

I mean default constructor may be cheaper than copying for some data types (e.g. for the fundamental types or for complex classes). But once again, it has never been thought over, nor was it evaluated in practice. It's simply that we (or at least me) are tend to over worrying about the performance of the basic building blocks (see e.g. #3 for and especially hot similar dispute). I'm (slowly) working on #33 which will probably fasten the evaluation and acceptance of all these change requests.

It would be really nice if the Doxygen clarified this. Currently, I've found no mention of this there. For example, the Digraph::NodeMap? concept page:

• http://lemon.cs.elte.hu/pub/doc/1.2.1/a00238.html

It is actually a good new - there is no obligation to keep backward compatibility with undocumented features.

[Charles Wilcox]

I understand the concern about incurring unintended overhead of extra copy-constructors vs. default-constructors. However, the patch I provided simply changes the input-param of the vector<T>::resize(...) ( for vector_map.h ) and of Allocator::construct(...) ( for array_map.h ) from a default-constructed Value to a reference to an already-constructed Value; this should not increase the number of copy-constructions.

I just ran a quick test; I modified my test program to have a class that simply prints out a message specific to the default-construction, copy-construction, assignment-operator and destructor. I stored this class as the Value in the map and ran before and after my patch. I observe that there is one extra copy-constructor and destructor call for the added vector_map::initval member, and two less default-constructions and two less destructions ( which happens for the nodes added to the graph after the map is created. ) Otherwise, every graph-node addition causes a copy-constructor and a destructor to happen within the map.

As you undertake #33, hopefully these things will be flushed out.

I like your point regarding the documentation; no explicit behaviour means the currently behaviour can change a bit easier.

I intend to patch my version of Lemon as described earlier. Hopefully one day this will be the default.

P.S. This is a great library, BTW. I don't mean my comments to seen

[Charles Wilcox]

Test .cpp file with verbose output and a custom class to output construction, assignment and destruction events.

[Charles Wilcox]

Output of the verbose test program before my patch.

[Charles Wilcox]

Output of the verbose test program after my patch.