COIN-OR::LEMON - Graph Library

Opened 9 years ago

Last modified 5 years ago

#252 assigned enhancement

Smaller iterator classes for some graph structures

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

Description

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.

Attachments (2)

252-b483e15fab8e.patch (22.2 KB) - added by kpeter 8 years ago.
252-staticdigraph-05b444bfc02b.patch (697 bytes) - added by kpeter 8 years ago.

Download all attachments as: .zip

Change History (12)

comment:1 Changed 9 years ago by kpeter

  • Type changed from defect to enhancement

Changed 8 years ago by kpeter

comment:2 Changed 8 years ago by kpeter

  • Owner changed from deba to kpeter
  • Status changed from new to assigned

[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

comment:3 follow-up: Changed 8 years ago by kpeter

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

comment:4 in reply to: ↑ 3 ; follow-ups: Changed 8 years ago by alpar

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.

comment:5 in reply to: ↑ 4 Changed 8 years ago by kpeter

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.

comment:6 Changed 8 years ago by kpeter

  • Milestone changed from LEMON 1.2 release to LEMON 1.3 release
  • Revision id 07ed3735ce1b deleted

comment:7 in reply to: ↑ 4 Changed 8 years ago by kpeter

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.

Changed 8 years ago by kpeter

comment:8 Changed 8 years ago by kpeter

I attached [05b444bfc02b] from #68.

comment:9 Changed 5 years ago by kpeter

What shall we do with this ticket?

comment:10 Changed 5 years ago by kpeter

  • Milestone changed from LEMON 1.3 release to LEMON 1.4 release
Note: See TracTickets for help on using tickets.