Re: [Boost-users] Another BGL question

Subject: Re: [Boost-users] Another BGL question
From: Michael Olea (oleaj_at_[hidden])
Date: 2009-04-28 19:44:27

On Apr 28, 2009, at 3:40 PM, Lindley M French wrote:

> Here's my problem. I've got a very large graph (say a few thousand  
> nodes). This graph is planar, although that doesn't really affect  
> much.
>
> Small clusters of vertices are grouped into "regions". The edges  
> within a region are marked as "on", and those between regions are  
> marked as "off".
>
> I need to be able to pull all vertices from a region and some or  
> all of its neighboring regions, as well as all induced edges, into  
> a local graph that I do work on.
>
> At first I thought of using the subgraph function together with  
> copy_graph, but the subgraph interface is pretty unintuitive, so  
> I'm avoiding it for now.
>
> I have a mechanism to iterate over all the vertices in a region,  
> but not the edges. How can I get an iterator to the edges around a  
> given vertex or set of vertices? adjacency_iterator isn't the right  
> tool. Is there an exhaustive list of all iterators available in BGL  
> somewhere?

The function out_edges(u, g) returns an iterator range for the edges  
around a vertex (all incident edges for an undirected graph, just  
out_edges for a directed graph), for a graph that models the  
IncidenceGraph concept:

http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/IncidenceGraph.html

The "graph concepts" document what interfaces define a concept:

http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/graph_concepts.html

Individual graph classes, like the adjacency_list class template,  
document what concepts they "model", and individual graph algorithms  
document which concepts they require, for example:

http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/adjacency_list.html
http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/ 
kruskal_min_spanning_tree.html

Personally, I find the book "The Boost Graph Library: User Guide and  
Reference Manual" essential for an overview, even if it is getting a  
bit dated.

-- Michael