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

Subject: Re: [Boost-users] [boost][graph] Efficiency problems in boost::adjacency_list
From: Yinghai Lu (elvis.lu_at_[hidden])
Date: 2009-06-22 22:22:43

Thanks, Jeremiah. I found that the bundled property works ok with
adjacency_list<setS, setS,...> or other vertex/edge list. I found the
problem is due to the usage of boost::topological_sort. topological_sort
requires vertex_index_t property which seems to be predefined only in vecS.
Now I provided my own vertex_index_map by using a member of bundled class
like this:
topological_sort(g, std::back_inserter(c),
vertex_index_map(get(&VertexClass::id, g)));

and it works out fine now.

On Tue, Jun 23, 2009 at 3:18 AM, Jeremiah Willcock <jewillco_at_[hidden]>wrote:

> 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
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>

-- 
Best Regards,
Yinghai
==========================
Lu Yinghai
ICCAD Lab., Fudan University
Mobile: [phone]