begin process at 2010 03 15 17:26:26
  Trouver un code source :
 
dans
 
Accueil > 

Code

 > 

Maths & Algorithmes

 > SAVOIR QUI CONNAÎT QUI DANS UN FORUM/CHAT/...

SAVOIR QUI CONNAÎT QUI DANS UN FORUM/CHAT/...


 Information sur la source

Note :
8 / 10 - par 2 personnes
8,00 / 10

  • 1

  • 2

  • 3

  • 4

  • 5

  • 6

  • 7

  • 8

  • 9

  • 10
Catégorie :Maths & Algorithmes Classé sous :forum, chat Niveau :Initié Date de création :16/12/2006 Date de mise à jour :16/12/2006 16:23:17 Vu :11 174

Auteur : malik7934

Ecrire un message privé
Commentaire sur cette source (5)
Ajouter un commentaire et/ou une note

 Description

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

  • <?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);
  • ?>
<?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"


 Historique

16 décembre 2006 16:23:17 :
erreur dans le code corrigée ($temp_arbre = $arbre[$j];)

 Sources du même auteur

Source avec Zip Source avec une capture EXÉCUTER UN SCRIPT AU-DELÀ DU TIMEOUT DE PHP
Source avec une capture SAUVEGARDE AUTOMATISÉE DE VOS BASES DE DONNÉES
Source avec une capture CACHER UNE SIGNATURE DANS UNE IMAGE
NOUVEAUX MESSAGES SUR YAHOO MAIL
EXÉCUTER UNE FONCTION SI C'EN EST UNE

 Sources de la même categorie

Source avec une capture CALCUL DE TVA MARGE AVEC REMISE FOURNISSEUR SPÉCIALE POUR LE... par lcomb
Source avec Zip EVALUER UNE EXPRESSION À PARTIR D'UNE CHAINE DE CARACTÈRE par TheWeasel47
FONCTION EQUATION LÉGÈRE par ff5
Source avec Zip Source avec une capture TRACEUR DE COURBE EN COORDONNÉES CARTÉSIENNES (MAJ) par fredbonmatin
CONVERTIR LES RÉFÉRENCES DE COLONNE EXCEL DE CHIFFRE EN LETT... par computman007

 Sources en rapport avec celle ci

Source avec Zip Source avec une capture FORUM PHP/MYSQL (EVOLUTION ASSUREE) par dsyann
Source avec Zip CLIENT CHAT (MESSAGERIE PRIVÉE) AJAX ET PHP par zniko07
Source avec Zip MESSENGER ONLIVE 1.0 par windows972
Source avec une capture CHAT PHP/AJAX SIMPLE ET COMPACT par SuperChouquette
Source avec Zip Source avec une capture MINI FORUM OU CHATBOX OU SHOUTBOX par p3x

Commentaires et avis

Commentaire de Kirua le 17/12/2006 12:18:26

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 :).

Commentaire de Kirua le 17/12/2006 12:24:17

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 :).

Commentaire de malik7934 le 17/12/2006 12:30:12

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...

Commentaire de Kirua le 17/12/2006 12:40:37

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.

Commentaire de coucou747 le 18/12/2006 09:35:12

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...

 Ajouter un commentaire


Discussions en rapport avec ce code source dans le forum

Chat à partir du login et mdp du forum [ par jmobylette ] Bonjour ! G un forum phpBB2 et je voudrais faire un chat à part mais en utilisant les mêmes pseudos et mdp ! J'ai donc fait un formulaire : http://jmo integrer un t'chat sur forum phpbb3 [ par champi39 ] Bonjour, Je voudrais savoir si il est possible d'integrer a un forum (version phpbb3), un mini chat, ou une shoutbox, sans toucher au Mysql.Merci de v Forum et chat sans base de donné sans cookies Java script !! [ par hackolique ] regarde ce forum !Bon ben vous allez dire que c'est de la pub je c ce vreme j'ai construis ce forum et un chat sans base de donné ce que tout le mond Forum très simple [ par fabiin ] Salut,je cherche un forum très simple.Utilisant mysql mais n'ayant besoin que d'une table pour fonctionner.Avec une petite administration toute gentil Webring [ par nico606 ] Salut j'aimerai savoir ou je pourrait trouver un bon script (webring)si y a quelqu'un qui sais !!!.:Nico606:.[<a href="http://nico606.free.fr" t BANNIR IP DUN CHAT URGENT [ par Wars007 ] salut je voudrais savoir un code php pour bannir une simple adresse ip dun chat sans connecion mysql.merci :)PS:(je ve le bannir car il floof tlt!) Script chat audio [ par glamrani ] Bonjour tt le monde,Je veut savoir, c'est possible de créer un script, qui une fois intégrer à une page Web, elle permit de capturer la voix provenant Problème de changement de style sur un forum [ par Inepsy11 ] Bonjour à tous,   Je suis étudiant en bts IG1 et je dois créer un forum php. Il se pose à moi un problème: lorsque je me suis authentifié, je dispose mise en page du forum [ par jreaux62 ] C'est une suggestion plutot qu'une question, et qui s'adresse au team qui s'occupe de la mise en page de ce site :--&gt; sur la page http://www.phpcs. Problème avec une requête contenant LEFT JOIN. [ par MonPied ] Bonjour, j'explique mon problème, après un sujet ou je demandais de l'aide pour éviter de faire plein de fois une requête un Zéro me proposa d'uti


Nos sponsors


Sondage...

Comparez les prix

CalendriCode

Mars 2010
LMMJVSD
1234567
891011121314
15161718192021
22232425262728
293031    

Consulter la suite du CalendriCode

Photothèque

 
Développement réalisé par Nicolas SOREL (Nix) avec l'aide de : Cyril DURAND et Emmanuel (EBArtSoft), Merci à Vincent pour ses précieux conseils.
CodeS-SourceS.com© Toute reproduction même partielle est interdite sauf accord écrit du Webmaster
CodeS-SourceS.com© est une marque déposée tous droits réservés

Google Coop CodeS-SourceS Google Coop CodeS-SourceS
Temps d'éxécution de la page : 0,718 sec (3)

Nous contacter | Annoncer sur CodeS-SourceS | Mentions légales