Avoid using INVALID for LEMON iterators and STL style iterarors

[Peter Kovacs]

INVALID is used many times in LEMON codes and it could be annoying (we have to write capital letters using the Shift key). However, it could be avoided if the iterator classes converted to bool, thus we could write

for(NodeIt n(g); n; ++n)

instead of

for(NodeIt n(g); n!=INVALID; ++n)

Of course, this interface would be just an alternative for the current one.

This ticket is a follow-up of #246.

[jwalter]

A different suggestion:

Could you make Lemon work with C++11 range-based for loops?

Something like this:

for (Node &node : g.nodes()) {
    cout << g.id(node) << endl;
}

This requires regular begin()/end() style iterators, and operator*().

For a minimal implementation, g.nodes() could create a NodeIt. NodeIt gets three new methods: begin() could simply return *this, end() could return INVALID, and operator*() could return the current Node object.

As a side-effect, this would also allow graphs to be used with STL algorithms.

[Alpar Juttner]

Replying to jwalter:

A different suggestion:

This idea has already been emerged in the past, someone has even made a proof of the concept. I try so involve him in this discussion.

But I think the two approach is somewhat complementary. For me the most important aspect of the implementing C++11 range-based for loops is the compatibility and interoperability with C++11. This form of the for loop isn't really more compact than what is proposed by the ticket. But it is sometime quite restricting (you don't have a direct access to the graph iterator.)

Note that C++11 range-based for loops is basically a workaround to the problem of the verbosity of C++ iterators and to the constant need of using operator*. Neither is really a problem with LEMON.

Could you make Lemon work with C++11 range-based for loops?

Something like this:

for (Node &node : g.nodes()) {
    cout << g.id(node) << endl;
}

This requires regular begin()/end() style iterators, and operator*().

For a minimal implementation, g.nodes() could create a NodeIt. NodeIt gets three new methods: begin() could simply return *this, end() could return INVALID, and operator*() could return the current Node object.

Conceptually, I would prefer an implementation in which g.nodes() returns a special class with begin()/end() instead of just a NodeIt.

Can you see any pros/conds of the two approaches?

As a side-effect, this would also allow graphs to be used with STL algorithms.

Which specific STL algorithms are you thinking of?

[jwalter]

Range-based for loops may be a workaround, but at the same time they communicate a certain intent. They clearly say "iterate through this container". Depending on the type declaration ([const] reference or not) they also show the kind of operation (read-only, read-write) more clearly, which might otherwise be hidden deep in the loop. Think "self-documenting code" (as far as that is possible with C++ ).

As for the algorithms: std::transform was my use case, generating a processed list from the nodes of a graph. Just by looking at the list of algorithms, std::any_of/all_of/none_of look useful, as do the *_copy* ones, and probably others.

[Gábor Gévay]

I attached a proof of concept implementation of the range-based for loop friendly iterators. [be9aea8c23ae]

The iterator wrapper header file compiles without C++11, so if someone doesn't have a C++11 compiler, then she can still at least use the STL algorithms with the new iterators.

I created a generic wrapper, which makes it easy to create an STL version of a Lemon iterator. As a start, I used it to make wrappers for Digraph::NodeIt? and Digraph::OutArcIt?. Am I right that the closest iterator concept in the STL to Lemon style iterators is an InputIterator?? (A ForwardIterator? would need to support modification of the elements, which doesn't seem possible with Lemon nodes, arcs, etc., because they seem immutable to me.)

There are a few special cases among the Lemon iterators: -IterableValueMap? and CrossRefMap? have beginValue and endValue functions. We could just create functions begin() and end() which call the previous ones. -CoeffIt? has operator*, so the implementation for that will be a little different. -We could create a version of the OutArcIt? wrapper, that iterates through the targets of the outgoing arcs. This spares a .target() call for the user

One last thing: Do we want to support Boost.Range? I think it would just need one or two typedefs.

[Balazs Dezso]

I like the proof-of-concept implementation, I think with a few modifications, it could be added to the main repository.

• I would move all the implementation classes to lemon/bits/
• The ToStlit? should be ToStlIt? by the coding convention, but I would use LemonItWrapper? for this class
• I would use static_cast in the operator* and operator-> to convert to the value type
• Instead of reimplementing the prefix increment operator, you can try to use the using directive
• Instead of the LemonitWrapper?, I would use LemonRangeWrapper? (since this represent an iterable range)
• I think the c++11 solution can be removed :(, since we want to keep the support for c++98
• Is there something against calling these functions in graph extender nodes(), arcs(), edges(), outArcs(), inArcs() and incEdges()? I would prefer these names, if it does not require to change the public interface. Changing private members looks OK.

[Gábor Gévay]

I made all the above said modifications. The last one required some renamings of private members. [15af6cbd7751]

I also added STL style iterators for bipartite graphs, paths, Bellman-Ford ActiveIt?, maps and Lp.

I didn't do ConArcIt? and ConEdgeIt? because there were two problems:

1. stl_iterators.h would have to be moved into core.h
2. ConArcIt? doesn't have a constructor that takes an Invalid parameter, and I couldn't simply make one, because the compiler complained that I didn't initialize the Graph reference in my constructor.

I didn't do EulerIt? and DiEulerIt? because they are not copy constructible because of the map they contain. (I think move constructors would probably solve this.) I had the same problem with the GrossoLocatelliPullanMc::CliqueNodeIt?.

I didn't do BlossomIt? and MinCostArborescence::DualIt? because they are not convertible from Invalid. (Actually, I don't see any reason for this, so it would probably be easy to just add a constructor that takes Invalid.)

Could you please check if I used appropriate names for the new iterators everywhere?

I ran the tests. tsp_test fails, but this is an unrelated issue, because it also fails with a fresh clone of lemon-main.

[Peter Kovacs]

I ran the tests. tsp_test fails, but this is an unrelated issue, because it also fails with a fresh clone of lemon-main.

Yes, it is most likely the same as #476.

[Alpar Juttner]

• I think the c++11 solution can be removed :(, since we want to keep the support for c++98

What do you exactly mean by "c++11 solution"? Can't we enable it (whatever it is) only if c++11 is enabled?

[Gábor Gévay]

Replying to alpar:

• I think the c++11 solution can be removed :(, since we want to keep the support for c++98

What do you exactly mean by "c++11 solution"? Can't we enable it (whatever it is) only if c++11 is enabled?

I think he meant the variadic template version of LemonRangeWrapper? (at the end of stl_iterators.h in the first version). At the moment, I don't see any advantage of taking the trouble to enable it when we are under C++11.

[Alpar Juttner]

I'm working on merging these changes into the main branch. But I got stuck. Why are these STL iterators unavailable for e.g. ReverseDigraph?

[Gábor Gévay]

Sorry, they should also be added to graph_adaptor_extender.h. I attached a patch.

[Alpar Juttner]

The attached path​ consists of 3 changesets:

• [0759d974de81] consists of everything in the changes above except for the test code under the contrib directory,
• [4add05447ca0] adds tests, a framework for conditionally switching off C++11 dependent tests, adds iterators to lemon/bits/edge_set_extender.h and fixes a couple of errors, finally
• [72af84645ac2] Fixes some compilation problems with clang and compiler option -std=c++11

It compiles well end all the tests runs correctly, however (TBC)

[Alpar Juttner]

There is a very disturbing problems - valgrind reports a Conditional jump or move depends on uninitialised value(s) error in test/maps_test.cc. I spent couple of hours investigating the issue, but I'm completely stuck.

Please help me!

You can easily reproduce the problem by compiling LEMON in Maintainer mode

  mkdir build
  cd build
  cmake -DCMAKE_BUILD_TYPE=Maintainer ..
  make

then running test/maps_test with valgrind:

  valgrind --vgdb-error=1 --track-origins=yes ./test/maps_test

[Alpar Juttner]

Balazs helped me to solve the problem above, and as a result all these changes went to the main branch as follows.

• [0759d974de81] consists of everything in the changes above except for the test code under the contrib directory,
• [4add05447ca0] adds tests, a framework for conditionally switching off C++11 dependent tests, adds iterators to lemon/bits/edge_set_extender.h and fixes a couple of errors, finally
• [0998f70d0b2d] Fixes some compilation problems with clang and compiler option -std=c++11
• [93d455c647be] Fixes the problem above.

STL style iterators could also implementes at other places. I created a separate ticket for those features, see #594.