Discussion :

[morgan47]

Bonjour à tous,

Je suis en train de réaliser un site de recherche de permutant.

J'aimerai mettre en place une recherche par triangulaire, je m'explique.
Un employé qui travaille sur paris cherche un permutant sur bordeaux.

J'aimerai rechercher les employés qui voudraient permuter de bordeaux vers paris, bon ça ça va c'est facile.
Cependant, j'aimerai rajouté les triangulaires tel que :
Un employé veut permuter de bordeaux à marseille.
Un employé veut permuter de marseille à paris.
Un employé veut permuter de paris à bordeaux.

Je ne sais pas si j'ai été trés clair, mais je n'ai aucune idée de comment me débrouiller pour faire cette recherche.

Avez vous des idées?
Cordialement,
Morgan

[Dendrite]

Passionnant comme problématique !

Mon premier jet donne ceci, je vais chercher à l'améliorer.

imaginons que tu as cette table (p pour paris etc...). Bien sûr, à l'arrivée, que des id avec clés étrangères sur d'autres tables, mais là, pour plus de lisibilté, j'ai simplifié.

Code SQL :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
SELECT
a1.id as id_1,a1.employe as emp_1, a1.lieu as lieu_1, a1.voeu as voeu_1,
a2.id as id_2,a2.employe as emp_2, a2.lieu as lieu_2, a2.voeu as voeu_2,
a3.id as id_3,a3.employe as emp_3, a3.lieu as lieu_3, a3.voeu as voeu_3
 
 FROM `avant` a1
inner join avant a2 on a1.voeu=a2.lieu
inner join avant a3 on a2.voeu=a3.lieu and a3.voeu=a1.lieu

Donne ceci, qu'il faut après filtrer de façon pertinente.



Problème 1 : comment filtrer (en PHP peut-être ?)
Problème 2 : comment aller plus loin et introduire de la récursivité de façon à ce que tous les employés puissent voir leurs voeux accordés au delà d'un niveau 3 : ie 4, 5 ou +, tant que la boucle est bouclée au niveau des voeux ?

[morgan47]

Merci pour ta réponse.

J'avais pensé à faire un chose comme ceci :

Première requête pour récupérer les personnes voulant partir de bordeaux, on stocke dans un tableau ou elles veulent aller.
Deuxième requête pour récupérer les personnes voulant aller à Paris et dans un second tableau on stocke leur ville d'origine.

Ensuite croiser les 2 tableaux afin de détecter le personne du premier tableau qui veulent aller dans les villes des second tableau.

[Spartacusply]

Sympa comme problème.

Ta problématique peut se représenter sous la forme d'un graphe orienté dans lequel il te faudrait chercher les cycles.

C'est une approche possible de ton problème (il me semble en tout cas) : tout d'abord trouver comment représenter un graphe en PhP, puis comment le parcourir pour y trouver les cycles les plus pertinents afin d'enlever à ton graphe els sommets qui composent le cycle, puis recommencer jusqu'à ce que ton graphe ne contienne plus aucun cycle. Tu peux aller voir ce site, il y a des articles intéressants à ce sujet.