Savoir qui connaît qui dans un forum/chat/...

Soyez le premier à donner votre avis sur cette source.

Snippet vu 20 106 fois - Téléchargée 24 fois

Contenu du snippet

Je cherchais à faire un forum avec une fonction comme LinkedIn.com, c'est-à-dire permettant de savoir qui connaît qui parmi les membres. Je me suis donc rabattu sur un peu de théorie des graphes et voici une fonction qui permet de savoir si deux personnes sont liées ou non (directement ou non d'ailleurs) dans un réseau.

Mon but avec ce code est de stimuler la création de contacts dans un forum que je développe.
Je pose simplement les bases ici, je ne propose pas tout le formulaire permettant de se mettre en réseau, etc. J'vais pas tout faire non plus :-)

Source / Exemple :


<?php

function connected($start,$end,$order,$connections){

	$bool = 0;
	$resultag = 0;
	$link= 0;
	$j=0;
	$arbre[$link] = $start;
	$trace[$link] = $start;
	$newtrace[$link] = $start;

	while($bool==0){

		$next = count($newtrace);
		$link = count($arbre);

		for ($j=0;$j<$next;$j++){

			$i=0;
			foreach ($order as $key => $val) {
				if ($val != $newtrace[$j]) $i++;
				else break;
			}

			$temp_arbre = $arbre[$j];
			$max = count($connections[$i]);

			for ($k=0;$k<$max;$k++){
				$m = 0;
				if (!in_array($connections[$i][$k],$trace)){ // j'ajoute seulement les points inconnus
					$m++;
					$trace[] = $connections[$i][$k];
					$newtrace[] = $connections[$i][$k];
					$arbre[] = $temp_arbre.$connections[$i][$k];
		
					if ($connections[$i][$k] == $end){
						$result = $arbre[count($arbre)-1];
						$resultag++;
						$bool = 1;
					}			
				}	
			}
		}
		if ($m == 0)
			$bool = 1;
	}

	if ($resultag > 0){
		echo 'Le chemin entre '.$start.' et '.$end.' est le suivant: ';

		for ($i=0; $i<strlen($result)-1; $i++)
			echo $result[$i].' => ';
		echo $result[strlen($result)-1];

	}
	else echo 'Pas de liens entre '.$start.' et '.$end;
}

// connections
//
// Il s'agit d'un arbre non valué

$connections = array();
$order = array();

$order = array('A','B','C','D','E','F','G');
$connections[0][0] =  'B';$connections[0][1] =  'C'; // A
$connections[1][0] =  'A';$connections[1][1] =  'C';$connections[1][2] =  'E'; // B
$connections[2][0] =  'A';$connections[2][1] =  'B';$connections[2][2] =  'D';$connections[2][3] =  'E';$connections[2][4] =  'F'; // C
$connections[3][0] =  'C';$connections[3][1] =  'F';$connections[3][2] =  'G'; // D
$connections[4][0] =  'B';$connections[4][1] =  'C'; // E
$connections[5][0] =  'B';$connections[5][1] =  'C';$connections[5][2] =  'D'; // F
$connections[6][1] =  'D'; // G

// Y a-t-il une connection dans l'arbre entre E et G?

$start = 'E';
$end = 'G';

connected($start,$end,$order,$connections);

?>

Conclusion :


L'exemple dans le code est celui d'un réseau de 7 personnes A, B, C, D, E, F et G.
A connaît B et C
B connait A, C, E et F
C connaît A, B, D, E et F
D connaît C, F et G
E connaît B et C
F connaît B, C et D
G connaît D

La question posées est: est-ce que E a un moyen de connaître G?
Ce code répond que oui: "Le chemin entre E et G est le suivant: E => C => D => G"

A voir également

Ajouter un commentaire

Commentaires

coucou747
Messages postés
12336
Date d'inscription
mardi 10 février 2004
Statut
Modérateur
Dernière intervention
30 juillet 2012
29 -
une bonne mise en cache, ça peut se faire évoluer non ? même un calcul de "pathfinding" entre deux personnes ?

selon moi, ça serait interessant de faire ça en mysql 5, et non en php, tu y gagnerais en vitesse, idée interessante, j'y penserais dans mes prochains projets (si j'ai le temps) faut voir ou ça peut menner...
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008
-
Disons que ça devient vite contraignant et que tu risques très fort de ne pas avoir tout le graphe en faisant comme ça: les gens ne vont inscrire que leurs contacts les plus proches, et certains vont même n'inscrire personne parce que ça les énerve. D'autres ne vont faire qu'inscrire les gens au début et puis oublier. Ca ne reflétera pas vraiment la réalité du terrain :).

Tu peux évidemment envisager un système qui "force" les inscriptions (impossibilité de parler avec une personne sinon etc), mais ça risque de dégouter les gens.

Enfin, tu pourrais considérer très simplement que sitôt que A envoie un PM à B, A et B se connaissent mutuellement. Pour plus de "sécurité", tu peux demander à ce que le PM soit lu, voire que B réponde. On peut tout faire varier :). Dans ce cas, ce serait assez restrictif aussi, mais pas contraignant pour l'utilisateur tout en étant "gratuit" d'un point de vue calcul, et tu auras ton graphe au grand complet.

Au grand complet parce que, par exemple, si je te citais dans un de mes messages, j'écrirais sans doute Malik, et pas Malik7934 -> même avec ma première idée on ne s'y retrouve pas tout à fait.

Si j'étais administrateur chez hotmail ou gmail, je sais ce que je ferais le weekend :D.
malik7934
Messages postés
1162
Date d'inscription
mardi 9 septembre 2003
Statut
Membre
Dernière intervention
15 août 2009
2 -
Salut Kirua,

Content que ça te plaise :-)

Moi je vois plutôt le principe de LinkedIn jusqu'au bout (devoir dire à un autre "veux-tu être mon ami?" en quelque sorte), mais c'est vrai que cela pourrait évoluer dans un autre sens... si t'as des specs à me proposer...
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008
-
Ah, et les composantes connexes c'est intéressant aussi: est-ce qu'il y a des groupes qui ne se connaissent pas du tout entre eux? i.e.: est-ce qu'il y a des groupes tels que aucune personne d'un groupe ne connait une quelconque personne de tous les autres groupes. C'est super con à programmer en plus :).
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008
-
j'adore ce genre de trucs :)

Je pense à qq chose: tu pourrais partiellement automatiser la création du graphe en parcourant la base de données des messages. Souvent, tu quoteras ou utiliseras le nom des personnes que tu connais dans certains de tes messages, pour les interpeler ou pour suggérer d'aller leur poser une certaine question à laquelle tu ne sais pas répondre. Evidemment, ça prendrait bcp bcp de temps de faire ça (faudrait faire uen recherche de tous les noms dans tous les messages!), donc le mieux est de le faire tourner une fois sur tout ce qui a déjà été posté et de retenir la date de la dernière màj. Après, tu ne fais l'update que sur les nouveaux messages depuis cette date.

Avec un forum open-source, on peut même imaginer de faire le traitement à chaque poste de message. Si ton forum a une fréquentation faible, ça répartira la charge de travail. Mais pour un gros forum par contre, ce serait pas du tout une bonne idée. Vaut mieux s'en tenir aux calculs périodiques, que tu peux d'ailleurs lancer sur une autre machine du réseau.

Ça m'intéresse ton truc :)

Ce serait cool que tu implémentes aussi les algos pour trouver les "cliques": groupes de gens qui se connaissent tous entre eux :)


Tu pourrais aussi exiger que A ait cité au moins n fois B avant de déclarer que A connaît B. On peut aussi se poser la question suivante: le graphe est-il dirigé ou non? Si A connait B, B connait-il A? C'est pas forcément clair. Mais le supposer simplifierais pas mal les choses :).

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.