IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

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


Sujet :

Algorithmes et structures de données

  1. #1
    Nouveau Candidat au Club
    Profil pro
    Inscrit en
    Mai 2006
    Messages
    2
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mai 2006
    Messages : 2
    Points : 1
    Points
    1
    Par défaut 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

  2. #2
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 42
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Points : 20 970
    Points
    20 970
    Par défaut
    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é ?

  3. #3
    Nouveau Candidat au Club
    Profil pro
    Inscrit en
    Mai 2006
    Messages
    2
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mai 2006
    Messages : 2
    Points : 1
    Points
    1
    Par défaut
    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 :/

  4. #4
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 42
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Points : 20 970
    Points
    20 970
    Par défaut
    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.

Discussions similaires

  1. Représentation graphique d'une matrice
    Par Mail4444 dans le forum Autres Logiciels
    Réponses: 0
    Dernier message: 30/06/2010, 16h57
  2. Création d'une bibliothèque de théorie des graphes
    Par The Void dans le forum Algorithmes et structures de données
    Réponses: 0
    Dernier message: 11/06/2010, 18h09
  3. [Théorie des Graphes] Les opérateurs AND et OR
    Par bitou dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 18/03/2007, 04h01
  4. [ODBC] Affichage (représentation) graphique d'une base
    Par Atchoum_002 dans le forum PHP & Base de données
    Réponses: 3
    Dernier message: 19/09/2005, 16h34
  5. [conseil logiciel] Représentation graphique d'une BDD
    Par ShinJava dans le forum Décisions SGBD
    Réponses: 2
    Dernier message: 27/02/2005, 09h41

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo