[Lemon-user] Static Digraph build

[Kovács Péter]

Hi,

> In the static_digraph.h, one can read from the build function :
>
>       /// The list of the arcs must be given in the range <tt>[begin,
> end)</tt>
>       /// specified by STL compatible itartors whose \c value_type must be
>       /// <tt>std::pair<int,int></tt>.
>       /// Each arc must be specified by a pair of integer indices
>       /// from the range <tt>[0..n-1]</tt>. <i>The pairs must be in a
>       /// non-decreasing order with respect to their first values.</i>
>       /// If the k-th pair in the list is <tt>(i,j)</tt>, then
>       /// <tt>arc(k-1)</tt> will connect <tt>node(i)</tt> to
> <tt>node(j)</tt>.
>
>
> I want to make sure this must be understood such that the arc list cannot be
>
> (0, 1)
> (0, 2)
> (2, 1)   <- 2 comes before 1
> (1, 2)

As the documentation says, it is not a valid input. The build() function 
utilizes the required ordering, so you have to sort your vector.

> I'm losing a lot of time to sort my arc vector by first index and I'm
> wondering what I could do save save that cpu time.

Does it really take a lot of time to sort the vector (e.g. compared to 
the time of the build() function)?

Regards,
Peter