Re: [Boost-users] Graph Library Random Access Iterators?

Subject: Re: [Boost-users] Graph Library Random Access Iterators?
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-03-06 12:03:53

On Sat, 6 Mar 2010, Theodore McCormack wrote:

> Hello all, I am trying to iterate through a list of edges in the boost graph library, but i would like
> to advance more than one at a time or be able to use random access to an edge in the set. For example:
> 
> Currently, to find the edge at index in the edge set I have to iterate through all the edges:
> 
> Edge e;
> int count = 0;
> for (edge_range_t er = edges(graph); er.first != er.second; er.first++)
> {
> e = (*er.first);
> if (count == index)
> break;
> count++;
> }
> return e;
> 
> I would like something like:
> 
> Edge e;
> edge_range_t er = edges(graph);
> e = (*er[index].first);
> return e;
> 
> Is there a way to index with iterators?

Do you need mutability in your graph, or can you create it with a complete 
edge set at one time?  If you do need mutability, passing vecS as the last 
template argument to adjacency_list (EdgeList) might make it random 
access, although the documentation does not say so and I am not sure.  If 
you do not need mutability, compressed_sparse_row_graph has an 
O(lg(E))-time edge_from_index function that takes an index (from 0 to 
num_edges(g)-1) and returns the corresponding edge.  Why do you need 
random access, though?  Maybe there is an alternative way to do what you 
want.

-- Jeremiah Willcock