Récursivité sur 1 table

[skydig]

Bonjour,

J'ai une table dans laquelle je stocke des trajets d'un point A vers B. Exemple :
Trajet 1 : Paris Toulouse
Trajet 2 : Toulouse Montpellier
Trajet 3 : Paris Marseille
Trajet 4 : Montpellier Toulouse
Trajet 5 : Toulouse Paris

Je cherche à créer une requête qui soit capable de me retourner par exemple le chemin à emprunter pour aller de Montpellier à Paris (Trajet 4 + Trajet 5) ou de Montpellier à Marseille (Trajet 4 + Trajet 5 + Trajet 3).

J'arrive à construire ma requête en bidouillant un peu Mysql en faisant une auto-jointure :

Exemple pour un trajet à 3 branches :
La colonne stockant les départs s'appelle "from" et celle stockant les arrivées s'appelle "to" :

(Je sais qu'il ne faut pas faire un SELECT * mais c'est pour la démo) :

Code :

SELECT * FROM flight f1 JOIN flight f2 ON f1.to = f2.from JOIN flight f3 ON f2.to = f3.from WHERE f1.from = 'Montpellier' AND f3.to = 'Marseille'

Je sais que Doctrine est capable de créer des arborescences mais je n'arrive pas à trouver comment faire pour utiliser cette fonction pour créer mon trajet en n'utilisant qu'une seule table.

Pensez-vous que ça soit possible ?

[gene69]

Code :

Pensez-vous que ça soit possible ?

non. même si je ne connais pas Doctrine.

Pour plusieurs raison. La première c'est que mysql ne supporte pas les requêtes hiérarchiques, dans ton cas, même avec un arbre à segments je ne vois pas comment truander le système.

L'autre raison c'est que Mysql, avec requêtes hiérarchiques retourne toutes les combinaisons. Si ton graphe est un treillis un peu dense, le nombre de possibilité va croitre (à la louche) exponentiellement. Ce dont tu as besoin, ça existe déjà, ça marche bien en routage (OSPF) c'est de t'inspirer de l'algo de Dijkstra, ainsi tu trouves la meilleure solution et tu fournis un résultat dans un temps "polynomial", c'est à dire que si tu as beaucoup de points ça rame mais tu n'as pas besoin d'avoir toute la puissance de calcul de la terre pour trouver un résultat. Dijkstra en procédure stockée sql, tu n'y arriveras pas ou sinon tu es vraiment doué (et je veux voir).

Il est possible que quelqu'un d'autre ait une autre analyse du problème.

[skydig]

Merci pour l'algo, je n'avais jamais entendu parler de ça.

En fait je ne cherche pas à trouver la route la plus courte ! Je ne l'ai pas précisé dans ma présentation mais il s'agit de vols et j'ai ajouté d'autres conditions à ma requête à savoir que les vols doivent être effectués le même jour et l'heure de départ du suivant doit être au moins supérieure de 30 mn à l'heure d'arrivée du précédent (pour laisser le temps au passager de prendre sa correspondance).

Quand je fais ça, Mysql me retourne bien les différentes routes possibles, le passager choisira lui même le trajet qui lui conviendra le mieux. S'il passe par Johannesbourg pour faire un Paris Marseille à la limite je m'en fou

J'ai réussi à modifier mon schéma YAML pour spécifier la relation sur 1 seule table en mettant :
Flight:
...
relation:
Flight:
local: to
foreign : from

Doctrine ne me renvoie plus d'erreur et me retourne les tronçons contigus (arrivée du tronçon précédent = départ du tronçon suivant).

Je dois juste faire une boucle pour savoir en combien de tronçons je peux trouver un chemin, j'essaie donc d'abord avec 1 (si un vol direct existe), puis 2, puis 3, puis 4. Je me limite volontairement à 4 arrêts, car au-delà ce n'est plus intéressant pour le passager. Ca m'oblige à faire au maximum 4 requêtes pour trouver un vol, j'aurais préféré faire ça en 1 seule mais bon...

Par contre, je n'arrive pas à accéder à tous les résultats avec mon objet.
Si j'ai deux routes possibles, ma boucle foreach ne me retourne que la première route, alors que la requête exécutée dans mysql me retourne bien 2 lignes.
Voici mon foreach pour un trajet à 3 branches (je n'affiche que l'id de chaque vol) :

Code :

1
2
3
4
5
6
7
8
9
foreach ($flights as $flight)
	{
 
		echo $flight->getId().'-';
		echo $flight->getFlight()->getId().'-';
		echo $flight->getFlight()->getFlight()->getId();
 
 
	}

Qu'est-ce qui cloche ?