Boost graph, un truc à savoir ?
Bonjour à tous,
J'utilise PostgreSQL pour stocker des données géographiques et pgRouting pour calculer des itinéraires.
Vous pouvez trouver les sources (super simple à lire) de pgRouting ici
pgRouting, greffé à postgresql, utilise boost graph pour exécuter les divers algorythmes qu'il propose (Dijkstra, A* etc.). Un calcul d'itinéraire basé sur 3731571 segments, met 2 à 4 secondes à s'exécuter, tout compris, depuis le chargement des données du graphe, jusqu'à l'exécution de la recherche, en passant par la construction du graph boost.
Le problème, c'est qu'à chaque fois que l'on a besoin de calculer un itinéraire, on envoie à la librairie une requête SQL permettant de "sélectionner le graph", puis le module l'exécute, construit le graph et agit dessus.
Or, j'ai besoin de calcul d'itinéraire en masse, sur le même graph. Alors j'ai repris les sources, j'ai fait un service, qui au démarrage sélectionne les données et construit le graph, afin qu'une fois démarré, il n'y au plus qu'à "taper dedans".
Ça commence par ceci :
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
struct Vertex
{
int m_iId;
double m_dCost;
};
typedef adjacency_list < listS, vecS, directedS, no_property, Vertex> graph_t;
typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor;
typedef graph_traits < graph_t >::edge_descriptor edge_descriptor;
typedef std::pair<int, int> Edge;
graph_t mGraph; |
Jusque là, rien d'anormale. Puis vient, à l'initialisation, cette instruction :
Code:
1
2
3
|
mGraph = graph_t(num_nodes);
// où num_nodes vaut 3.731.571 |
Là, on a bien 10 minutes de temps d'exécution..
Ensuite vient le remplissage de graph, une série d'instructions comme ceci :
Code:
1
2
|
boost::tie(e, inserted) = add_edge(pEdges[j].m_iSource, pEdges[j].m_iTarget, mGraph); |
Et au début c'est super long, puis petit à petit, ça devient de plus en plus rapide. Dans l'ensemble, ça mets entre 5 à 7 minutes.
La seule différence, c'est que mon serveur PostgreSQL tourne sous linux, et les plugins viennent des dépôts linux, alors que mon service, tourne sous Windows, avec boost compilé sous Windows.
Pourquoi est-ce que c'est si long de mon côté, pour construire ce graph boost, et que c'est si rapide, sur le serveur ?
Aurait-je loupé quelque chose dans la compilation de boost, ou un flag quelque part ?
Merci pour votre aide,
A bientôt :)
