Smaller iterator classes for some graph structures

[Peter Kovacs]

All the NodeIt, ArcIt, EdgeIt etc. iterator classes stores a pointer for the underlying (di)graph. However it wouldn't be necessary in some cases.

E.g. SmartDigraph::next(Node&) and SmartDigraph::next(Arc&) are static functions. Thus SmartDigraph::NodeIt and SmartDigraph::ArcIt could be implemented without a pointer to the graph. The three next() functions of SmartGraph are not static, but they could/should be. The special graph structures (FullGraph, HypercubeGraph, GridGraph) also have static next() functions.

[Peter Kovacs]

[b483e15fab8e] redesigns the extenders for graph and arc/edge set structures and specializes NodeIt, ArcIt and EdgeIt to be smaller whenever it is possible. It means that a pointer to the underlying graph structure is not stored in these itartor classes when the corresponding next() function is static. A new bool direction() const function is intorduced in IncEdgeIt for the sake of easier implementation. For the specialization of the template classes, three new tags are introduced: StaticNextNodeTag, StaticNextArcTag, StaticNextEdgeTag.

As a result the size of the following iterator classes became 4 byte instead of 16 byte (tested on lime.cs.elte.hu):

• SmartDigraph:: NodeIt, ArcIt
• SmartGraph:: NodeIt, ArcIt, EdgeIt
• FullDigraph:: NodeIt, ArcIt
• FullGraph:: NodeIt, ArcIt, EdgeIt
• GridGraph:: NodeIt, ArcIt, EdgeIt
• HypercubeGraph:: NodeIt, ArcIt, EdgeIt
• SmartArcSet:: ArcIt
• SmartEdgeSet:: ArcIt, EdgeIt

[Peter Kovacs]

This changeset is rather a decorating modification than an important performance issue. I don't know such applications in which we would like to store many NodeIt or ArcIt iterators. Unfortunately, the size of OutArcIt and InArcIt classes cannot be reduced.

However the proposed changeset has no drawbacks comperd to the current solution (running time efficiency was tested).

[Alpar Juttner]

Replying to kpeter:

However the proposed changeset has no drawbacks comperd to the current solution (running time efficiency was tested).

Except for the increased maintenance costs due to the newly introduced tags. One more thing to take care of, one more place where people can make a mistake (when implementing new graph structures or when modifying the iterator implementation). I would like to understand whether or not it is an issue in reality.

And besides, I'm quite skeptic towards all kinds of "I can't really see why it is good, but certainly is isn't wrong, so let's do it" type modifications.

[Peter Kovacs]

Replying to alpar:

Except for the increased maintenance costs due to the newly introduced tags. One more thing to take care of, one more place where people can make a mistake (when implementing new graph structures or when modifying the iterator implementation).

I think, it is not a big deal. Using these tags are not necessary even if the next() functions are static. On the other hand, this changeset reduces the code duplications, since the iterator classes are defined only once (they are removed form edge_set_extender.h).

I would like to understand whether or not it is an issue in reality.

I see.

And besides, I'm quite skeptic towards all kinds of "I can't really see why it is good, but certainly is isn't wrong, so let's do it" type modifications.

Its advantage is clear, but it is not significant. A user hardly (or never?) uses more than a few iterators of classes NodeIt, ArcIt and EdgeIt.

I agree that this patch is not of particular importance, thus I accept if it will be postponed or rejected.

[Peter Kovacs]

Replying to alpar:

Except for the increased maintenance costs due to the newly introduced tags.

On the other hand, it reduces the code duplications, the iterator classes are defined only once. Thus it helps implementing possible extensions/improvements proposed in e.g. #325 and #94.

[Peter Kovacs]

I attached [05b444bfc02b] from #68.

[Peter Kovacs]

What shall we do with this ticket?