Théorie des graphes : Représentation GRAPHIQUE d'une matrice d'adjacence

Salut,

A partir d'une liste de sommets et de liens, formant un graphe, représenté par une matrice d'adjacence, je souhaite créer une représentation GRAPHIQUE de l'ensemble.

De plus, les liens sont valués, ce qui implique que des sommets reliés par un lien faiblement valué sont plus éloignés que ceux par un lien plus fort.

D'autre part, les noeuds n'étant pas liés ensembles doivent être éloignés au moins d'une certaine distance (sinon ils seraient connectés).

Voilà mon problème, pour le moment j'ai une représentation très moyenne car les sommets non connectés entre eux ne respectent pas la distance minimum de 'connexion', et le graphe est très "fouilli".

Bref, je pense ne pas avoir utilisé un algorithme optimal, bien qu'il soit rapide, et je voulais simplement savoir si quelqu'un n'a pas déjà rencontré un algorithme pouvant effectuer ce type de traitement.

Je cherche un algorithme rapide, car ce graphe doit être généré à la volé (la stabilité des liens depend du temps), qui limite le nombre d'intersections des liens dans un souci de lisibilité, et qui prenne en compte l'éloignement des sommets.

si, vous avez quelques idées d'algorithmes n'hésitez pas ;)

Arf... Ca me fait penser au travail de thèse que j'effectue en ce moment. J'essaie de projeter dans un espace de taille réduite des points dont les distances doivent être respectées.
1h pour faire les calculs.
Autant dire que si tu veux faire ça de manière exacte, c'est impossible, ou même de manière approchée.
Quel est la dimension de l'espace sur lequel tu travailles. 2D, 3D ?
Quels sont les compromis que tu peux faire ? Est-ce que tu dois avoir une représentation très proche de la réalité ?

C'est en 2D, ouf :)

La représentation a principalement pour objectif de montrer les liens existant entre les sommets et leur qualité.
Le but est surtout d'obtenir une representation harmonieuse, comme c'est expliqué sur cette page : http://www.enseignement.polytechniqu...rot/trace.html

En réalité, dans tous ces sommets de positions initialement inconnues, je dispose de quelques sommets dont la position est connue et qui doivent servir de base au calcul.

Les sommets "mobiles dans le temps" peuvent avoir n'importe quel nombre de voisins :
- 0 voisin : qui donnerait un position aléatoire, estimée en regardant la position dans le passé et dans le futur et en réalisant une interpolation linéaire entre les deux.
- 1 voisin : le sommet serait placé sur un cercle autour du sommet de référence, avec une estimation supplémentaire en utilisant les positions précédentes/suivantes.
- 2 voisins : une moyenne
- 3 voisins ou plus : un barycentre.

donc avec ce type de contrainte, la représentation ne sera pas toujours exacte. Le but c'est quelle soit optimale, et lisible :
- sans superposition de sommets en particulier
- et en minimisant un peu les intersections de liens

pour le moment j'ai un algo en O(n^3), je pense que cela pourrait être plus rapide, mais je ne trouve pas d'ouvrage sur le sujet :/

Ca ressemble bougrement à des fragments de mon travail, même si c'est pas forcément la même chose.
Regarde du côté de l'ACP ou du MDS classique qui revient après transformation des distances à de l'ACP, les vecteurs propres principaux donnent les directions principales et conservent au mieux les distances que tu essaies de conserver.