Re: [Boost-users] [BGL] Auto Connect vertexes by predicate?

Subject: Re: [Boost-users] [BGL] Auto Connect vertexes by predicate?
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2009-05-08 16:58:05

On Fri, 8 May 2009, arm2arm wrote:

> Hello,
> Are there ways to generate Graph with edges by the user defined function?
> Should I generate Vertex relations by hand then put it in to Graph?
> I would like to feed graph by points 3d and each point is linked to its
> closest neighbor by distance. Then as a next step I would like to dig in the
> graph the sub-graphs with the given linking length.

There are two basic, efficient ways to do this: use an implicit graph, or 
create a pair of edge iterators and use those to create a concrete graph. 
You could also add edges one at a time using a loop, but that is likely to 
be less efficient.

1. Implicit graph: if you are not mutating the structure of the graph at 
all and your relation is fairly simple (which yours appears to be), you do 
not need to create an adjacency_list data structure at all.  Just define 
your own graph type: your type would have coordinate triples as vertex 
descriptors, and an out_edges function that returns all adjacent triples. 
You would not store the edges explicitly at all, but could still define 
external properties on them that you could mutate (if you created an 
edge_index property map for your graph type).  I believe an example of 
this is in chapter 9 of the BGL book.  I was not able to find a good 
example online, but some related comments are at:

http://www.nabble.com/-Graph--is-it-possible-to-define-my-own-edge_descriptor-td21904703.html

2. Edge iterators: there are many graph generators in BGL that are 
implemented as iterator ranges over pairs of vertices.  Look in 
<boost/graph/plod_generator.hpp> or 
<boost/graph/erdos_renyi_generator.hpp> for examples.  For this, you would 
create a pair of iterators (potentially using the Boost.Iterator library) 
that walks over your edges, with the vertices encoded as integers in some 
way.  You can create several BGL graph types from such iterator pairs. 
Note that for the compressed sparse row graph type (the most 
memory-efficient for unchanging sparse graphs), the edges must be 
lexicographically sorted in the range in Boost 1.39; SVN head no longer 
requires that.  The adjacency_list class also does not have this 
restriction.  You can also create a large STL vector or similar of pairs 
and pass iterators into that to your graph constructor.

3. Adding edges one at a time: this is the slowest option, but might be 
the easiest.  This option is to do basically what you suggested: create an 
empty graph and call add_edge() many times on it.  Many memory allocations 
are required to add all of the edges.

The option I would recommend is based on what level of performance and 
memory efficiency you need and how much time you have to create an elegant 
implementation.  Option #1 uses the least memory and has the best 
performance, but also takes the most time to develop.  Option #2 is 
slightly easier, but requires an explicit graph to be created.  This graph 
could be mutated, though, which option #1 does not allow.  Using option #2 
with a vector is like repeated calls to add_edge(), but somewhat faster 
and using less memory.  I would not recommend option #3, but I included it 
for completeness.

If you do choose to go with options #1 or #2 (with a new iterator type), 
a grid graph class or generator would be a useful addition to the BGL.

-- Jeremiah Willcock