[Boost-users] [graph] Optimizing graph definition

Subject: [Boost-users] [graph] Optimizing graph definition
From: Maxime van Noppen (maxime_at_[hidden])
Date: 2009-09-26 10:36:08

Hi,

I'm using a quite large boost::graph (~ 100 000 vertices with 8 to 10
edges each) and am trying to get the best of the structure to be able to
 increase vertices & edges.

The graph is mainly read-only. I add 99.99% of the vertices & edges in a
big loop at the beginning. I never delete vertices or edges.

After that I mainly use dijkstra and A* algorithms with some full
traversals.

I use very often the edge(v1, v2, g) function to get the edge (if it
exists) between two vertices.

My priority is to optimize the use of the graph rather than the creation
but I'd like to keep the creation time reasonable.

For now I use :

typedef boost::adjacency_list< boost::vecS, boost::vecS,
                               boost::directedS, my_vertex, my_edge >
        graph_t;

I didn't find enough informations about complexity of functions and
algorithms regarding to the graph definition to find out be myself what
would be the best parameters for my use case.

Is something improvable here ?

Thanks !

-- 
Maxime