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

[Hoyt Koepke]

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.

[Hoyt Koepke]

patch for static_graph

[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?

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

[Peter Kovacs]

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