COIN-OR::LEMON - Graph Library

Opened 6 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: hoytak Owned by: alpar
Priority: major Milestone: LEMON 1.4 release
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description

Hello,

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 hoytak 6 years ago.
patch for static_graph

Download all attachments as: .zip

Change History (4)

Changed 6 years ago by hoytak

patch for static_graph

comment:1 Changed 6 years ago by alpar

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 6 years ago by hoytak

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 5 years ago by alpar

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