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

C++ Discussion :

Chargement d'un graphe dans des classes


Sujet :

C++

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Nouveau candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2020
    Messages
    1
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 26
    Localisation : France, Hauts de Seine (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mars 2020
    Messages : 1
    Par défaut Chargement d'un graphe dans des classes
    Bonjour,
    Dans le cadre d'un exercice je souhaiterai charger un graphe depuis un fichier text sous le format suivant :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
     
    ordre
    num
    num
    …
    taille
    num1num2 poids
    num1num2 poids
    ......
    J'aimerai faire une classe graphe et une classe sommet, ce que j'avais fait dans un précédent exercice mais cette fois, je n'arrive pas à visualiser comment enregistrer l'information sur les arrêtes et les poids.
    J'avais précédemment fait une classe graphe possédant un vecteur de pointeurs sur sommet, et dans la classe sommet, un vecteur de sommet (pour la liste des sommets adjacents). Mais maintenant avec les poids je n'arrive vraiment pas trop à voir quoi en faire. Si quelqu'un aurait une petite piste... merci d'avance

  2. #2
    Responsable 2D/3D/Jeux


    Avatar de LittleWhite
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Mai 2008
    Messages
    27 121
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Mai 2008
    Messages : 27 121
    Billets dans le blog
    148
    Par défaut
    Bonjour,

    On peut imaginer une structure Lien qui contient le lien (un pointeur vers la destination, et un entier pour le poids) et ce Lien serait instancié dans chaque nœud (Il faut une structure Noeud aussi ).
    Vous souhaitez participer à la rubrique 2D/3D/Jeux ? Contactez-moi

    Ma page sur DVP
    Mon Portfolio

    Qui connaît l'erreur, connaît la solution.

  3. #3
    Expert confirmé
    Homme Profil pro
    Analyste/ Programmeur
    Inscrit en
    Juillet 2013
    Messages
    4 766
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Analyste/ Programmeur

    Informations forums :
    Inscription : Juillet 2013
    Messages : 4 766
    Par défaut
    Je n'ai plus de souvenirs mais il me semble qu'1 graphe c'est une liste de sommets et une liste d'arêtes.

    Un sommet c'est un couple (x, y, z)/ autre chose (avec en +, 1 identifiant qui est quand même recommandé) et une arête, 2 sommets et 1 poids (Édit : l'orientation est juste une contrainte en respectant l'origine (le sommet qui s'appelle soit from soit start soit src soit begin) et la destination (l'autre sommet soit to soit end soit dest))

    Là où je bloque c'est comment trouver toutes les arêtes d'1 sommet ?
    Mettre dans 1 sommet, 1 liste d'arêtes (les siennes cela va de soi, même pointeur) c'est lourd
    Faire la recherche dans la liste d'arêtes du graphe, c'est lourd

  4. #4
    Membre éclairé
    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    301
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 301
    Par défaut
    Il y a plusieurs manières de représenter un graphe.

    S'il est dense (c'est à dire que de nombreux sommets sont connectés les uns aux autres) on peut représenter le graphe sous la forme d'une matrice (autant de lignes et de colonnes que de sommets), l'élément Mat[i][j] représente les données liées à l'arc entre i et j. cf matrice d'adjacence

    Si le graphe est peu dense on peut partir d'une liste de sommets et à chaque sommet on associe une liste des arcs sortants cf liste d'adjacence

    Après il y a de nombreuse variantes (par exemple si le graphe est orienté ou non, s'il existe plusieurs arcs entre deux sommets, etc...)

  5. #5
    Expert éminent
    Avatar de koala01
    Homme Profil pro
    aucun
    Inscrit en
    Octobre 2004
    Messages
    11 644
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 53
    Localisation : Belgique

    Informations professionnelles :
    Activité : aucun

    Informations forums :
    Inscription : Octobre 2004
    Messages : 11 644
    Par défaut
    Salut,

    En fait, l'idéal est toujours de respecter le SRP, cela permet de se sortir des situations les plus complexes

    D'un coté, on a la notion de graphe, qui représente "des points reliés entre eux" selon une logique 0...N (un point peut être relié à 0 autre points... ou plus)

    La "liaison" ne se fait que "de un point vers un autre" peut -- potentiellement -- être orientée (je relie spécifiquement le premier point au deuxième, ou l'inverse... ou bien le sens n'a aucun intérêt) et est appelée arrête.

    L'arrête peut -- accessoirement -- présenter un poids: une valeur (quelque soit l'unité choisie) permettant d'évaluer "ce que cela nous coûte" de passer d'un point à l'autre.

    En outre, l'arrête peut éventuellement présenter des restrictions (par exemple, la vitesse maximale autorisée si notre graphe représente des portions de la voie publique) ... ou pas

    A priori, n'importe quel point peut être relié à n'importe quel autre: il n'y a strictement rien qui interdise d'avoir une arrête qui traverserait l'intégralité d'un graphe pour relier l'un des premiers points qui le composent à l'un des derniers.

    Enfin, à la notion de poids, à la base, elle correspond à n'importe quel type de donnée utilisable dans un référentiel donné et la valeur associée devra -- le plus souvent -- être évaluée (quitte à être mise en cache pour ne pas devoir être recalculée en permanence)

    Il nous faut donc au moins trois structures "de base", et potentiellement une quatrième:
    la structure point, qui pourrait la forme de
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    struct point{
        int id; // c'est plus facile pour déterminer de quel point on parle par la suite
                 // ce serait sans doute l'indice du point dans la liste maintenue par le
                 // graphe
        TYPE x;
        TYPE y;
       // TYPE z;
    };
    la structure arrete qui pourrait prendre la forme de
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    struct arrete{
        int a; // représente l'id du premier point
        int b; // l'id du deuxième point
        // direction sens; (direction étant sans doute une simple énumération)
        // type restriction
    };
    ou la forme de
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    struct arrete{
        point & a;   // parce que je préfère les références, mais un pointeur pourrait faire l'affaire :D
        point & b;
        // direction sens; (direction étant sans doute une simple énumération)
        // type restriction
    };
    et une structure grpahe qui permettra de maintenir la liste des points et la liste des arrête et qui pourrait ressembler à quelque chose comme
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    struct graphe{
        std::vector<point> points;
        std::vector<arrete> arretes;
        // some_type poids_des_arrêtes; // les poids mis en cache :D
    };
    Tout cela étant dit, lorsqu'il s'agit de charger un graphe existant, le plus facile est très certainement de travailler "avec ordre et méthode": comme une arrête ne peut exister que si elle relie effectivement deux points entre eux autant commencer par charger l'ensemble des points qui composent le graphe, ce qui implique que le fichier devrait sans doute commencer par quelque chose comme
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    N // le nombre de points à charger
    x1, y1, z1
    x2, y2, z2
    ...
    xN, yN, zN
    où N (le nombre de points) permettra essentiellement de faciliter la logique permettant de charger les différents points

    Ensuite, nous pourrons charger les différentes arrêtes. Mais, comme on ne peut pas garantir que les différents points se trouveront à la même adresse mémoire au travers des différents exécutions, il est préférable d'utiliser une donnée qui a peu de chance de varier pour représenter le point: l'indice du point lors de la lecture du graphe.

    Le fichier continuera donc sans doute sous une forme proche de
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    M // le nombre d'arrête
    point1_a, point1_b
    point2_a, point2_b
    ...
    pointM_a, pointM_b
    (pour sa forme la plus simple) , voire, sous la forme de
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    M // le nombre d'arrête
    point1_a, point1_b, direction1, restriction1
    point2_a, point2_b, direction2, restriction2
    ...
    pointM_a, pointM_b, direction1, restriction1
    en fonction des données disponible au niveau des arrêtes

    Le cas échéant, on pourrait aussi envisager de charger les poids mis en cache, mais cela dépendra forcément de ce qu'ils représentent et de la manière dont ils sont représentés.

    Ensuite, les choses pourront évoluer en fonction des besoins que l'on associe à chaque terme (par exemple : un noeud doit pouvoir la liste de toutes les arrêtes qui en partent) et la manière de mettre les différentes notions en relations les unes avec les autres dépendra très certainement de ces besoins plus "spécifiques"
    A méditer: La solution la plus simple est toujours la moins compliquée
    Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire vous viennent aisément. Nicolas Boileau
    Compiler Gcc sous windows avec MinGW
    Coder efficacement en C++ : dans les bacs le 17 février 2014
    mon tout nouveau blog

Discussions similaires

  1. [C#]Remonter des événements dans des classes imbriquées
    Par Kcirtap dans le forum Windows Forms
    Réponses: 9
    Dernier message: 14/12/2013, 12h43
  2. callback Win32 dans des classes perso
    Par NiamorH dans le forum Windows
    Réponses: 12
    Dernier message: 07/01/2007, 17h47
  3. distribution d'elements dans des classes
    Par christine1985 dans le forum Algorithmes et structures de données
    Réponses: 3
    Dernier message: 31/08/2006, 11h15
  4. distribution d'elements dans des classes
    Par christine1985 dans le forum VB 6 et antérieur
    Réponses: 1
    Dernier message: 28/08/2006, 17h57
  5. [WSDL][Axis] Récupération de valeur dans des classes java
    Par cosmos38240 dans le forum XML/XSL et SOAP
    Réponses: 3
    Dernier message: 09/01/2006, 17h38

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