Boost graph, un truc à savoir ? [Résolu]

[mister3957]

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

[mister3957]

Trouvé !

Au départ mon graph est une suite de segments de deux points. J'applique une routing qui va positionner un identifiant de "début" et "fin" de chaque segments.

A ce stade, un virage sur une route unique peut contenir une dizaine de segments.

J'ai donc simplifié le graph pour éliminer tous les points ne faisant que relier un segment à un autre, en mettant à jour les données calculées (distance, temps et géométrie).

Au final, je me retrouve avec un graph réduit, mais les identifiants "départ/fin" sont conservés à l'original pour les segments "qui restent".

Or, boost considère que les identifiants sont contiguës et qu'il n'y a pas de "trou". Ainsi, si on lui envoie un segment avec un identifiant de vertex "50.000", il considère qu'il y aura au moins 50.000 vertex dans le graph, et cherche à ré allouer la mémoire, ce qui le fait peiner lors des premiers ajouts, puis le fait crasher par la suite, dans la démesure.

La solution a été de réindexer les index de début/fin des segments, devenus tronçons.

Résultat, sur un PC de particulier, l'algo A* calcul 30 à 40 calcul d'itinéraire, sur la France entière, par seconde

Problème résolu