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

Thanks, Jeremiah. I found that the bundled property works ok with adjacency_list 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 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 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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

-- Best Regards, Yinghai ========================== Lu Yinghai ICCAD Lab., Fudan University Mobile: 13816976593