[Lemon-user] Static Digraph build

[Alpár Jüttner]

Hi,
> >
> > 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.

The point is basically that StaticDiraph needs to know the number of
arcs leaving each nodes in advance so that they can build up its
compressed data structure. In fact, StaticDiraph could do this sorting
by itself, but this interface allows the user applying a more efficient
way of doing it in some cases.

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

It may take. Sorting is an O(n*log(n)) operation in general, while
StaticDigraph buildup is O(n). Note, however that
      * you only have to order the arcs according to the first node, the
        value of which is from the range [0,n-1]. Therefore e.g. bucket
        sorting can be done in O(n).
      * the build() function takes an iterator as input, thus
        implementing an own one, you may provide the data "on-the-fly"
        instead of allocating a full sorted vector.

Regards,
Alpar