Re: [Boost-users] [boost][graph] Efficiency problems in boost::adjacency_list

Subject: Re: [Boost-users] [boost][graph] Efficiency problems in boost::adjacency_list
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2009-06-22 15:18:16

On Tue, 23 Jun 2009, Yinghai Lu wrote:

> hi, erveryone,
> I'm building a graph incrementally using boost::adjacency_list with bundled properties. I did the following typedef:
> typedef boost::adjacency_list<setS, vecS, bidirectionalS, EdgeClass, NodeClass> Graph;
> 
> EdgeClass and NodeClass is some classes holding the properties of edges and nodes so that I can access them by using
> g[u].some_property = 1;
> 
> My problem is that I'm building the graph incrementally and the graph is huge. And with the definition I'm using the
> vector to hold the vertices, which results in many memory relocation and copy and makes the program stagnate. I wanted to
> use listS/mapS for the vertex list instead. However, the bundled property seems to work only with vecS only. Otherwise,
> compilation error will be thrown. So does anyone know how to solve this problem? Thanks.

How incrementally are you building the graph?  Do you have the graph data 
up-front but in an unknown order?  Is it possible for you to make two 
passes over the input data to build the graph?  Or do you need to look at 
the graph being built before it is fully finished?  Normally, for memory 
and efficiency issues for read-only graphs, I recommend using the 
compressed sparse row graph format.  It can be built from edges in an 
arbitrary order (in the trunk or 1.40 release branches), and supports 
bundled properties (only).  Would that be useful for you?

If you do need more dynamic capabilities, you would need an adjacency_list 
and might need to switch to non-bundled properties (I do not know about 
the issue with listS and mapS preventing bundled properties).  Note that 
you can have a single non-bundled property whose value type is just your 
bundle structure.

-- Jeremiah Willcock