[Lemon-user] Getting an iterator to the nth node of a ListGraph

[Alpár Jüttner]

On Fri, 2010-02-26 at 13:25 +0200, Tunc Bahcecioglu wrote:
> Dear All,
> 
> I would like to get an iterator to the nth node of a ListGraph
> (not the node with id n, but the nth node according to the storage order).
> 
> Node iterator has the ++ operator but no addition support.
> 
> Is there anyway to accomplish this without using a series of ++
> operation on a node iterator?

Unfortunately it is not possible in general. The nodes are supposed to
form a list, therefore it impossible to achieve sublinear time indexing.
However, some graph structure may do better. E.g.

- SmartGraph ensures that the ids of the nodes are always from the
interval [0 .. n-1].
- Similar is true for ListGraph as far as no node is deleted.

If your graph does not change, then a general solution is to setup an
std::vector<Node> containing the nodes:

std::vector<Listgraph::Node> nodes;
for(ListGraph::NodeIt n(g);n!=INVALID;++n)
  nodes.push_back(n);

Regards,
Alpar