Re: [Boost-users] Choosing the right GRAPH

From: Johan Oudinet (johan.oudinet_at_[hidden])
Date: 2007-09-12 10:19:43

Hi,

On 9/12/07, Jacques Papper <jpapper_at_[hidden]> wrote:
> Hi,
>
> I've been looking around the BGL for some time now, but I still can't
> decide which graph I should use.
>
> Here are my limitations :
>
> - Very large graph ( > 40 million vertices)
> - About 4 to 8 edge per vertex (Sparse)
>
> I want to associate to each edge a property P such that :
> edge (A,B)  returns P
> edge (B,A) returns -P  (Directed)
> BUT I do not want to duplicate the storage of P.
>
> If edge (A,B) exists then (B,A) also exists. (Bidirectional)
>
> I also want to be able to access all edges connected to vertex A as
> quickly as possible (so I guess using in_edges and out_edges in a
> directed adjacency list will be too slow).
>
> I think the compressed_sparse_row_graph might be the way to go by
> storing all duplicate edges (the only implementation for the moment is
> directedS), but I need a way to not duplicate the properties associated
> with each edge.
>
> All advice will be greatly appreciated !!

I agree with you, the only graph type you can use in BGL with very
large graphs is the compressed_sparse_row_graph.
You may use the singleton pattern for properties associated with each
edge, so you can avoid creating multiple instances of property object.

Otherwise, I use the BCG graph
(http://www.inrialpes.fr/vasy/cadp/man/bcg.html) to handle very large
graphs, but this graph format is not documented yet (a technical
report is on-going), so I have to use the BCG environment providing by
the CADP toolbox.

Regards,

-- 
Johan