Salut, j'ai un TP à faire (le dernier TP de ma vie normalement... ) et j'avoue que même après y avoir réfléchi je cale un peu :

Le but est de créer un graphe aléatoire dynamique et d'y implémenter un algo de comptage (distribué). J'y réfléchi depuis une bonne semaine et j'avoue qu'autant un comptage sur un graphe statique semble facile avec un algo récursif, j'ai du mal à voir comment passer au "mode dynamique".

Rien que la condition d'arrêt de l'algo me semble floue

qu'est ce que tu appelle "distribue" qu'est ce que tu appelle "comptage"?

comptage c'est connaitre le nombre de noeud dans un graphe
distribué (c'est possible que j'emploie un mauvais terme ici) dans le sens ou on se place "du point de vue d'un noeud" : il ne connait pas la typologie du graphe. C'est à eux de se compter tout seul

et à part l'intitulé d'un projet de 2011 par mon univ et une thèse à la limite du lisible j'ai pas trouvé grand chose..

Avec un marquage ?
Je dis peut-être de la merde hein.
Mais en gros tu propages une marque (et à chaque marque t'incrémentes un compteur). Et tu fais ça en récursif.

Comptage (i):
Marquer i.
compteur++
Pour tout voisin j de i,
Si j non marqué, Comptage(j)

Nan ?

ah, je vois. Ce n'est pas un probleme de graph traversal sur une machine a memoire distribuer. C'est plus proche d'un probleme de reseau ad-hoc.

Tu as des ID unique sur les noeud de ton graph? Je suppose que le graphe est symetrique (undirected)?

Ca ressemble a un probleme d'election de representant comme dans un algo de detection de composante connexe avec path compression.
Je partirais sur cette idee. Chaque noeud commence par etre un "connected component" avec un poids de 1 et le noeud est sont propre representant. Tu fusionne deux "connected component" en elisant un representatif parmi les representatifs des deux "connected components" son nouveau poids est la somme des poids des deux "components".

Apres il y a des questions de routage pour que les representant communiquent, mais j'imagine que tu as deja resolu des problemes comme ca.

Gay-Lussac, tu suppose que tu as de la memoire partage ici. Le probleme que se pose OP est plus proche des problemes de routage dans les reseaux.

Trop high-level pour moi

C'est plus proche d'un problème de réseau ad-hoc.

exactement oui jvais regarder ta réponse en détail ce midi pendant la pause

Apres il y a des questions de routage pour que les representant communiquent, mais j'imagine que tu as deja resolu des problemes comme ca.

J'étais globalement dans ta démarche que tu as décrite. Le fait est qu'il n'y a pas que des union de plusieurs composantes connexes mais aussi des déconnexions. Serais-ce judicieux de maintenir finalement une genre de liste dans chaque noeud, qui se mettrais à jours ?

Exemple concert : un noeud qui se déconnecte de sa composante connexe, va voir ailleurs et en rejoint une autre, revient dans la première et permet de mettre à jours la liste des noeuds que possède les noeuds de la première composante à laquelle il était relié ?

A priori ça me parait pas mal, le problème étant de savoir a quel moment arrêter l'algo, cad comment les noeuds peuvent 'savoir' qu'ils ont fini le comptage... ?

Tu veux dire que le graphe n'est pas statique?

Si le graphe est statique, tu ne veux pas deplacer les noeuds d'une composante a l'autre. Il ne faut que fusionner les composantes en ayant le representant de la composante effectuer le changement pour tous les noeuds qu'il represente.

Note que si tu as un noeud source a ton probleme, alors le probleme est plus simple et peut se faire avec un algo recursif. Mais j'imagine qu'il n'y a pas de noeud "source" dans ton cas. (en general, il n'y en a pas).

Dans le cas du graphe statique, il est facil de savoir si le comptage est termine.

Le representant d'une composante envoie un message en broadcast de comptage/terminaison en donnant son identifiant unique. Chaque noeud qui le recoit contacte les voisins et demande quel est l'identifiant unique de leur representant. Si il y a une difference, tu renvoie un message d'erreur dans le reseau. Sinon, tu renvoie "1" dans le reseau vers ton representant.

Comme le representant connait le nombre de noeud dans sa composante, si il recoit autant de 1 que sa taille, alors l'algo est termine et il peut broadcaster le resultat dans le reseau. Sinon il recevra un message d'erreur.

Le graph est malheureusement dynamique et les noeuds se déplacent de manière aléatoire et un arc est créé entre deux noeuds si ils sont à une distance assez petite :/

Si le graphe est dynamique, je ne suis meme pas bien sur de ce que ca veut dire "compter".

moi non plus... je regrette deja d'avoir pris l'option graphe dynamique pour esquiver les base de données distribuées...

enfin si, je suppose que c'est énumérer le nombre de noeuds présent dans le graphe, mais sachant que certains noeuds vont peut être rester solitaire...

C'est surtout qu'entre le moment ou tu commences a compter et ou tu fini de compter, le graphe pourrait bien ne plus etre le meme.

Quand tu dis distribué est ce que ça veut dire que tous les processus du graphe sont sur la même machine ou distribué sur un réseau? Vu que vous avez parlé de réseau Ad Hoc je suppose que c'est sur réseau. Mais ça rend la problématique totalement incertaine...

Comme l'a dis Godrik, on ne peut pas compter le nombre de noeud d'un graphe distribué dynamique de façon certaine... Peux tu instaurer un paramètre d'estimation? Ou tu dois apporter une preuve à chaque fois?

[stefo], j'imagine qu'il simule ca sur une machine unique. Mais c'est une problematique de reseau mobile ad-hoc.

Il y a des facon de faire du routage dans les reseau mobile/dynamique/ad-hoc, mais c'est un peu la mort. Perso, j'ai pas bien compris comment ca marchait.

Les garanties que tu peux avoir sur ce type reseaux sont assez faible. Je commencerais certainement par un algo simple dans ce genre.

A emet un message a tous ces voisins qui contient un numero unique ID (genere aleatoirement).
Quand je recois un message je marque l'arete par laquelle je l'ai recu et je retient le numero unique.
Si je recois un nouveau message avec le meme numero unique, je l'ignore et renvoie (ID,0)
Eventuellement, mes voisins vont me repondre et m'envoyer un nombre
quand tous les voisins ont repondu, je somme leur reponse et ajoute un. et je renvoie (ID,somme+1) sur le lien original.
Si un de mes voisins n'est plus visible a un moment donne, je considere sa reponse comme 0.

Oui je simule ça sur une machine unique. Ma fac est "spécialisée" dans les algo sur graphes, et le labo s'intéresse beaucoup aux réseaux ad-hoc et à développé sa bibliothèque java (open-source je crois) dédiée à la gestion de graphe (GraphStream).

Avec ça on peut assez facilement créer un graphe aléatoire dynamique.

(double post inc quand j'aurais compris ton algo godrik )