Re: [Boost-users] [graph] Optimizing graph definition

Subject: Re: [Boost-users] [graph] Optimizing graph definition
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2009-09-26 10:50:42

On Sat, 26 Sep 2009, Maxime van Noppen wrote:

> 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 ?

For read-only directed graphs, you might want to use the compressed sparse 
row graph.  It is designed for fast access with no modifications, and 
(with the old interface) keeps the out edges of each edge sorted for fast 
edge() operations.  Creation time still should be reasonable.  If you can 
avoid using edge() too often you can use the new version of the graph that 
offers more constructors but does not sort the out edge lists.

-- Jeremiah Willcock