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

Commenter

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

S'inscrire maintenant

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.

Du même auteur (malik7934)