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