Construction d'un graphe étoilé à partir d'une matrice

Bonjour,

j'ai une matrice carré symétrique de coefficient compris entre 0 et 1, correpondant à la distance entre deux personnes par exemple (c'est une distance subjective, comme par exemple le degré d'amitié). Plus ca tend vers 1, plus ces personnes sont proches, et 0 correspond à deux personnes non amies.

la première ligne et colonne correspondant à l'élément central. à partir de cet élément central, je vais placer le second élément par rapport à l'élément central en fonction du coefficient correspondant. Pareil ensuite pour le 3e en fonction des points placés précédemment (en privilégiant toujours la distance par rapport à l'élément central avant les autres), et ainsi de suite.

le problème réside dans la construction des coordonnées de tous les éléments: en effet, il est possible qu'il n'y ait pas de solution, et dans ce cas, il faudrait une forme de relaxation sur les "contraintes". deux cas où il n'y a pas de solution: une distance trop grande, ou, au contraire, une distance trop courte.

Ce que j'aimerais (si quelqu'un à une solution), c'est un algorithme qui puisse donner les coordonnées de chacune des personnes, en gérant les cas où il n'y a pas de solution, et s'il est possible de faire ça sous java.

Merci si quelqu'un a une piste...

Bonjour

Citation:

---

Envoyé par jyboo

la première ligne et colonne correspondant à l'élément central.

---

La première ligne ou la première colonne?????

Bref. Si j'ai bien compris (arrete moi si je me trompe), un élément va etre associé à un point. Et tu veux symbolisé graphiquement la distance entre ces différents éléments?
Si on associé ton élément central aux oordonnées (0,0), il suffirait de prendre les coefficients entre cet élément et les autres éléments, et de les transformer en coordonnées graphiques (tout en gardant la proportionnalité).
Par exemple, si A est mon élément central, et que le coefficient de distance de B est de 0,56, tu place ta représentation de B à (coordonnée de A + 56).
Et ainsi de suite.

C'est un truc comme ca que tu veux?

Cdlt

comme c'est une matrice symétrique, c'est la premiere colonne et la premiere ligne
en fait, le problème se situe dans la construction des points: il se peut que les coefficients ne permettent pas d'obtenir une "solution" (pas de point)
exemple: la distance par défaut est de 10 entre deux points. d'après la matrice de coefficient, on a des coefficients pour le point A de 0,4 avec le point B, et 0,4 pour le point C. la distance entre B et C est de 200=> pas de solution
c'est que j'aimerai, c'est une idée pour gérer ces problèmes par exemple, et donc avoir un algo pouvant gérer ca (si possible sous java tant qu'à faire)

Bonjour,

j'ai du mal à comprendre (désolé) mais je vais quand meme essayé.

Pour déterminer que tu n'as pas de solution, tu vas surement appliquer un critère (de distance de coeff si j'ai suivi).
Du coup, il te suffit de boucler sur tous tes éléments, tu les compare avec les autres éléments, tu testes ton critère et tu agis en conséquence.

Je ne vois pas trop où est le problème.

Cdlt

alors, je vais tenter de faire une explication claire et en expliquant bien ce que je voudrais :D
donc, en fait, je développe une application facebook en java, en récupérant des données sur les "amis" de l'utilisateur.
je détermine ensuite une première matrice carré symétrique, qui est la "matrice d'amitié" (qui représente l'utilisateur et ses amis, et s'il sont amis entre eux)
ca donne quelque chose comme ca

0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1
1 1 0 0 1 0 1 0 1 1 0 1 1 0 1 1 1 0 1 1 1 0 1 1 1
1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 1 1 1 0 1 0
1 1 1 1 0 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1
1 0 0 0 1 0 1 0 1 0 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 0 1 1 1 0 0 0 1 1 1 0 1 1 1 0 1 1 1 0 0 1 0
1 1 1 0 0 0 1 0 0 0 1 1 1 1 0 1 1 1 0 1 1 0 1 1 0
1 1 0 1 1 1 1 0 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 0 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 1 0
1 1 0 0 0 1 0 0 0 1 1 1 1 0 0 1 1 1 0 1 1 0 1 1 1
1 1 1 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 1
1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 0
1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1
1 1 0 0 1 1 1 0 0 1 1 1 0 1 0 1 1 0 1 1 1 1 1 1 1
1 1 1 0 1 0 1 0 1 0 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0
1 0 0 1 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1
1 1 1 0 0 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 0
1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1
1 1 1 0 1 1 1 0 0 0 1 1 0 1 1 0 1 1 1 1 0 1 0 1 0

à partir de cette matrice, je vais déterminer le "degré" d'amitié entre chacun,
c'est a dire que pour chaque couple de personnes, je vais déterminer le nombre d'amis commun rapporter à la moyenne du nombre d'amis qu'ils ont parmi les amis de l'utilisateur (c'est assez difficile de suivre la, je sais).
ci-dessous la matrice du nombre d'amis commun
0 19 16 9 19 16 21 0 15 14 20 20 19 14 11 19 21 17 18 22 21 15 17 22 15
19 0 16 9 16 16 18 1 14 14 17 18 16 13 11 18 18 15 17 19 18 14 15 19 13
16 16 0 8 14 13 16 1 13 11 16 15 14 12 11 15 15 14 15 16 15 12 12 16 10
9 9 8 0 9 10 9 1 9 8 9 10 9 7 6 9 9 9 10 9 9 9 9 9 8
19 16 14 9 0 14 19 1 15 13 17 17 16 13 11 16 18 14 17 19 18 14 16 19 14
16 16 13 10 14 0 15 1 11 13 16 16 14 12 9 14 16 14 16 16 15 13 13 16 11
21 18 16 9 19 15 0 1 15 13 19 19 18 15 11 18 20 16 18 21 20 15 16 21 14
0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
15 14 13 9 15 11 15 1 0 12 13 14 14 11 10 15 14 13 14 15 15 12 14 15 13
14 14 11 8 13 13 13 1 12 0 13 14 13 12 8 14 14 12 14 14 14 11 14 14 11
20 17 16 9 17 16 19 1 13 13 0 19 18 14 11 17 20 17 16 20 19 15 16 20 13
20 18 15 10 17 16 19 1 14 14 19 0 18 14 12 18 20 17 17 20 19 14 17 20 14
19 16 14 9 16 14 18 1 14 13 18 18 0 12 11 17 19 17 15 19 19 13 16 19 14
14 13 12 7 13 12 15 1 11 12 14 14 12 0 7 13 14 13 13 14 13 12 13 14 9
11 11 11 6 11 9 11 1 10 8 11 12 11 7 0 10 12 10 11 11 10 8 9 11 8
19 18 15 9 16 14 18 1 15 14 17 18 17 13 10 0 18 15 16 19 19 14 16 19 15
21 18 15 9 18 16 20 1 14 14 20 20 19 14 12 18 0 17 17 21 20 15 17 21 14
17 15 14 9 14 14 16 1 13 12 17 17 17 13 10 15 17 0 14 17 16 13 15 17 13
18 17 15 10 17 16 18 1 14 14 16 17 15 13 11 16 17 14 0 18 17 13 14 18 13
22 19 16 9 19 16 21 1 15 14 20 20 19 14 11 19 21 17 18 0 21 15 17 22 15
21 18 15 9 18 15 20 1 15 14 19 19 19 13 10 19 20 16 17 21 0 14 17 21 16
15 14 12 9 14 13 15 1 12 11 15 14 13 12 8 14 15 13 13 15 14 0 12 15 11
17 15 12 9 16 13 16 1 14 14 16 17 16 13 9 16 17 15 14 17 17 12 0 17 14
22 19 16 9 19 16 21 1 15 14 20 20 19 14 11 19 21 17 18 22 21 15 17 0 15
15 13 10 8 14 11 14 1 13 11 13 14 14 9 8 15 14 13 13 15 16 11 14 15 0

mais maintenant, à partir de cette matrice, il faudrait que je représente un graphe étoilé centré sur l'utilisateur en cours qui représente au mieux cette matrice. sauf que j'ai du mal à concevoir un algorithme efficace pour représenter tout ca, sachant que chacun des personnes sont représentées par des "pastilles" dont la taille dépend du nombre d'amis qu'ils ont.

l'idée, c'est de trouver un algorithme qui puisse positionner chacune des personnes en suivant au mieux cette matrice sur un graphe en 2D. Mais c'est sur ce point que je bloque.

voilà, merci merci pour tout:D

Bonjour,

Que de chiffres que chiffres...... Bref!

Pour voir si j'ai bien compris, matrice[0][1] représente le nombre d'amis commun qu'il a en commun avec matrice[0][0] et matrice[2][1] représente le nombre d'amis commun qu'il a avec matrice[2][0] ?????

Si "Utilisateur principal" est représenté au centre du dessin, tu peux essayer de jouer avec des distances linéaires pour les relations utilisateur principal <-> autres et avec des distances radiales pour les relation autres<-> autres.

Par exemple, prenons U l'utilisateur principal et a1, a2 et a3 les autres.
U <-> a1 = 20;
U <-> a2 = 10;
U <-> a3 = 15;
a1 <-> a2 = 3;
a1 <-> a3 = 8;
a2 <-> a3 = 5;
Parlons en pixel (par exemple).
Tu met a1 à 200 de distance avec U.
Tu met a2 à 100 de distance avec U.
Tu met a3 à 150 de distance avec U.

Tu met donc a1 sur l'axe des abcisses.
Et ensuite tu tournes autour de U pour placer tes autres.
Genre un truc comme
angle_de_la_droite_a2-U_par_rapport_aux_absicces = 3
angle_de_la_droite_a3-U_par_rapport_aux_absicces = 8.

Si tu relie toutes les pastilles, t'auras un graphe.

Un truc comme ca peut etre.

Cdlt

euh pas exactement...
la première matrice représente l'utilisateur et ses amis: si l'utilisateur est ami avec quelqu'un, c'est représenté par 1, mais aussi si un ami de l'utilisateur est ami avec un autre ami de celui-ci, c'est représenté par 1
par exemple, si l'utilisateur c'est A, qui a 3 amis B C et D, avec B ami de C et D, mais C pas ami avec D, on a:
A B C D
A 0 1 1 1
B 1 0 1 1
C 1 1 0 0
D 1 1 0 0

ensuite, avec ca, on va déterminer la seconde matrice, qui représente le nombre d'amis commun deux à deux
exempl: pour D et C, on regarde toute les valeurs communes pour lesquelles ils sont à 1. on a A et B, amis commun de D et C, donc ils ont 2 amis commun
de proche en proche, on a la seconde matrice:
A B C D
A 0 2 1 1
B 2 0 1 1
C 1 1 0 2
D 1 1 2 0
c'est cette seconde matrice qui va permettre de construire le graphique (tel que je le concois), car elle détermine les distances entre chacun (en les ramenantà une base commune, pour que ca soit relatif parce que quelqu'un qui a 1000 amis et qui a 50 amis commun avec un autre, on peut se douter de leur "proximité")

la difficulté, c'est de construire quelque chose qui respecte plus ou moins la seconde matrice
sauf que l'algorithme...
ton algorithme par contre ne marche pas piou1234, car entre (a1-a2) + (a2-a3) != (a1-a3), il n'y a aucun lien "logique" entre les 3 (c'est pourquoi je parlais de relaxation au départ).

Re,

Donc tu veux faire trois choses sur un meme graphique :
- représenter l'amitié entre tout le monde et le l'utitlisateur principal (ca c'est facile)
- représenter chaque personne parune pastille en fonction du nombre d'amis qu'il a
- représenter l'amitié de tout le monde entre eux (ca ca pose problème)

A moins de faire de la 3D, je vois pas trop comment tu peux faire ca. (D'un autre coté on est vendredi et j'ai l'esprit déjà en week-end....).

A tout hasard t'as une idée de comment serait ton dessin où tu cherche l'algorithme ET une facon de dessiner?

Cdlt

alors,
deja merci de m'aider hein ( ;) )
il s'agit en fait d'un problème de visualisation: c'est la représentation de beaucoup de données compréhensible d'un coup d'oeil
pour une idée de comment ca sera, c'est la:
http://dl.free.fr/jOG01rt8l/Sanstitre.bmp
c'est très schématique, là ou tous les traits se rejoignent c'est l'utilisateur courant, et dans chaque pastille il y aura une photo (obtenu par un traitement de données depuis facebook),sachant que les liens entre pastilles sont uniquement indiqué par survol de la pastille concerné: quand on survole une pastille, ca dessine les liens avec les autres pastilles.

pour ca, y a pas de problèmes, c'est gérable. mais en fait, c'est de savoir comment positionner les pastilles les unes par rapport aux autres.

je pense qu'il est possible de faire une sorte de relaxation sur les contraintes, pour avoir une marge de manoeuvre sur les distances de la matrice de distance, mais ensuite, je sais pas trop comment, et comment introduire un tel algorithme sous java (j'avais pensé à faire de la programmation par contraintes sous choco, mais beaucoup beaucoup trop lourd -pour ceux qui connaissent, hein...)

voila, je suis pourtant sur que ca a du être fait quelque part, mais je ne saurais dire ou...

merci encore pour l'aide !!! (et en espérant fortement qu'il y en ai encore ce we... :roll: )

Re,

Avoir toute ces informations du premier coup d'oeil, c'est difficile je pense.
Par contre, si (comme tu le dis), tu montre les relations entre les autres lorsque tu passe la souris dessus, ca change tout.

Tu pourrais par exemple ne pas t'occuper de la position des pastilles entre elles sur la vue de base (mais seulement afficher leur position en fonction de la pastille principale). Et lorsque tu passes sur une pastille, c'est là que tu introduis un système pour :
- montrer avec qui elle est en relation (ca tu le fais déjà)
- montrer les distances avec les autres (avec un peu de réflexion, c'est possible de donner des impression de distances meme sans toucher à leur position)

Ca correspond ou pas?

Cdlt

re
pas vraiment, parce que l'idée est de pouvoir visualiser directement les "groupes" d'amis, qui devraient être visible par interprétation de la matrice des distances...