COIN-OR::LEMON - Graph Library

Opened 12 years ago

Last modified 5 years ago

#427 new enhancement

Create build() routine for StaticDigraph that allows # of arcs to be set explicitly

Reported by: Hoyt Koepke Owned by: Alpar Juttner
Priority: major Milestone: LEMON 1.4 release
Component: core Version: hg main
Keywords: Cc:
Revision id:



I recently tried used StaticDigraph? with an iterator that used a forward-only traversal concept, as it was a thin wrapper to some rather complicated underlying structures. The problem is that the std::distance() call cause the iterator to run through the entire set to get the number of arcs, even though this was something I knew beforehand. Rather than create some sort of clumsy workaround, I found it easy to add another version of build() that permitted one to pass in the number of arcs explicitly. It's possible that mine is a rare case, but in case people are interested, here is a patch that does this. It's complete with appropriate documentation changes.

Attachments (1)

StaticDigraph.patch (4.3 KB) - added by Hoyt Koepke 12 years ago.
patch for static_graph

Download all attachments as: .zip

Change History (5)

Changed 12 years ago by Hoyt Koepke

Attachment: StaticDigraph.patch added

patch for static_graph

comment:1 Changed 12 years ago by Alpar Juttner

Thanks for the nice and clean patch.

I'm just curious about its real purpose. Do you mean that the superfluous std::distance() call causes a considerable increment in running time in your use case?

comment:2 Changed 12 years ago by Hoyt Koepke

Unless the iterator conforms to the random access iterator concept, or has a special overloaded implementation available, std::distance works by copying the first iterator, then incrementing it until first == second. This is how it works in the case of std::list, for example. It allows it to work on iterators where only copy construction, equality testing, and forward increments are supported. The patch allows the basic iterator concept to be used without the O(n) step of computing the distance. In the case of std::list, this is reasonable, as you know the size of the list, but std::distance doesn't know that information.

In my case, it would have perhaps made more sense to implement routines buildStart, setArc, and buildEnd. This kind of construction is used in sparse matrices, e.g. those in Eigen. In buildStart, you would set the number of nodes/arcs, you would set them sequentially using setArc, then buildEnd would clean up.

comment:3 Changed 11 years ago by Alpar Juttner

Milestone: LEMON 1.3 releaseLEMON 1.4 release

comment:4 Changed 5 years ago by Peter Kovacs

If #377 will be accepted, then this proposal should be applied consistently for both static graph implementations.

Note: See TracTickets for help on using tickets.