Boost Graph CRS: poids en vrac et Dijkstra

Question

J'essaie de construire un graphe aussi efficacement que possible, et comme je n'ai pas besoin de changer mon graphe à l'exécution, j'ai opté pour un boost::compressed_sparse_row_graph. Maintenant, la question est simple: comment puis-je ajouter des poids aux bords et appeler boost::dijkstra_shortest_paths? Jusqu'ici j'ai réussi à créer un graphique, mais je ne sais pas comment procéder. Mes besoins sont: gaspiller le moins de mémoire et de temps possible. Je suis confronté à des graphes avec un nombre de nœuds pouvant atteindre 10^6. Je suis cette entrée wiki, mais j'ai peur que les cartes de la propriété, index des cartes & Co., comme je vois dans le wiki, sera un fardeau supplémentaire à mon programme.

Pensez-vous qu'il existe un moyen de minimiser l'empreinte mémoire?

Merci pour votre aide!

// Properties: weights 
typedef boost::property<boost::edge_weight_t, int> edge_weight; 

// The graph itself as a compressed sparse row matrix 
typedef boost::compressed_sparse_row_graph<boost::bidirectionalS, boost::no_property, edge_weight> boost_graph; 

// Vertex iterator 
typedef boost::graph_traits<boost_graph>::vertex_iterator vertex_iterator; 

// Edge iterator 
typedef boost::graph_traits<boost_graph>::edge_iterator edge_iterator; 

// Adjacent nodes iterator 
typedef boost::graph_traits<boost_graph>::adjacency_iterator adjacency_iterator; 
typedef boost::graph_traits<boost_graph>::out_edge_iterator outward_iterator; 
typedef boost::graph_traits<boost_graph>::in_edge_iterator inward_iterator; 

int main(int argc, const char * argv[]) 
{ 
    std::vector<std::pair<std::size_t, std::size_t>> graph_edges; 
    std::vector<int>         edge_weight; 

    graph_edges.push_back(std::make_pair(0, 1)); edge_weight.push_back(1); 
    graph_edges.push_back(std::make_pair(0, 3)); edge_weight.push_back(2); 
    graph_edges.push_back(std::make_pair(1, 4)); edge_weight.push_back(2); 
    graph_edges.push_back(std::make_pair(2, 4)); edge_weight.push_back(3); 
    graph_edges.push_back(std::make_pair(3, 4)); edge_weight.push_back(1); 
    graph_edges.push_back(std::make_pair(4, 5)); edge_weight.push_back(1); 
    graph_edges.push_back(std::make_pair(4, 6)); edge_weight.push_back(5); 
    graph_edges.push_back(std::make_pair(5, 7)); edge_weight.push_back(4); 
    graph_edges.push_back(std::make_pair(7, 8)); edge_weight.push_back(1); 
    graph_edges.push_back(std::make_pair(8, 9)); edge_weight.push_back(3); 
    graph_edges.push_back(std::make_pair(8, 11)); edge_weight.push_back(2); 
    graph_edges.push_back(std::make_pair(8, 12)); edge_weight.push_back(3); 
    graph_edges.push_back(std::make_pair(9, 10)); edge_weight.push_back(2); 
    graph_edges.push_back(std::make_pair(12, 10)); edge_weight.push_back(4); 

    // Create the graph 
    boost_graph graph(boost::edges_are_unsorted_multi_pass, graph_edges.begin(), graph_edges.end(), 13); 
    // ... 

} 

Answer 1

Définition d'un graphique en vrac est possible avec des conteneurs contigus tels que std::vector:

boost_graph graph(boost::edges_are_unsorted_multi_pass, graph_edges.begin(), graph_edges.end(), edge_weight.data(), 13);