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 :

Graphe orienté et graphe non orienté pour modélisation de réseau de routes et traffic


Sujet :

Algorithmes et structures de données

  1. #1
    Membre éclairé Avatar de guitz
    Homme Profil pro
    Webdesigner
    Inscrit en
    Juillet 2006
    Messages
    717
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Webdesigner

    Informations forums :
    Inscription : Juillet 2006
    Messages : 717
    Points : 741
    Points
    741
    Par défaut Graphe orienté et graphe non orienté pour modélisation de réseau de routes et traffic
    Bonjour,

    J'essaie de développer un réseau de routes et son traffic.

    Pour se faire j'ai pensé deux graphe : G1 et G2.

    G1 étant un graphe non orienté (en vert sur le shéma) qui servirait uniquement à l'affichage des routes (splines, etc....)
    G2 étant un graphe orienté (sommets en noir et arêtes en bleu) qui servirait pour pour un algorithme de pathfinding genre A*.

    Nom : graphs.jpg
Affichages : 82
Taille : 41,1 Ko

    Est ce la meilleure façon de procéder sachant que G1 contiendra maximum 5000 sommets et 8 arêtes adjacentes par sommet et G2 contiendra maximum 5000 x 9= 45000 sommets et 7 arêtes adjacentes par sommet.
    Dois-je utiliser deux graphes indépendants ? Ou est ce plus propre d'utiliser un graphe et son sous-graphe ?

  2. #2
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    Août 2008
    Messages
    26 603
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : Août 2008
    Messages : 26 603
    Points : 188 672
    Points
    188 672
    Par défaut


    As-tu besoin d'un graphe pour l'affichage ? N'est-ce pas plutôt un ensemble de segments (dans une structure de données appropriée) ? Je ne vois pas en quoi le graphe apporte quelque chose dans ce cas. A priori, la liste des segments sera plus utile sur GPU qu'en RAM, alors que les GPU n'apprécient pas fortement les graphes et structures de données pas hyper compactes.
    Vous souhaitez participer aux rubriques Qt (tutoriels, FAQ, traductions) ou HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  3. #3
    Membre éclairé Avatar de guitz
    Homme Profil pro
    Webdesigner
    Inscrit en
    Juillet 2006
    Messages
    717
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Webdesigner

    Informations forums :
    Inscription : Juillet 2006
    Messages : 717
    Points : 741
    Points
    741
    Par défaut
    Salut Dourouc05,

    Nom : image.jpg
Affichages : 39
Taille : 35,4 Ko

    Commet tu le vois je dois afficher aussi bien des arêtes que des sommets du graphe (encerclés de rouge).

    J'ai créé une classe MySpline qui entre autres comme propriétés :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    bool IsOnANode; //vaut true si cette spline correspond à un sommet, sinon elle correspond à une arête
    int NodeArrayIndex; //index du tableau de structs GraphNodes correspondant au sommet en question
    int EdgeArrayIndex; //index du tableau de structs GraphEdges correspondant à l'arête en question
    TArray<FVector> SplinesControlPoints; //tableau de vecteurs servant à dessiner la spline
    Peut être que je me trompe, mais pour l'affichage j'ai besoin ET d'un ensemble d'arêtes ET d'un ensemble de sommets ?

  4. #4
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    Août 2008
    Messages
    26 603
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : Août 2008
    Messages : 26 603
    Points : 188 672
    Points
    188 672
    Par défaut
    Citation Envoyé par guitz Voir le message
    Peut être que je me trompe, mais pour l'affichage j'ai besoin ET d'un ensemble d'arêtes ET d'un ensemble de sommets ?
    À moins d'avoir des segments qui se superposent et des modèles 3D qui marchent bien dans ce cas (j'en doute !), oui.
    Vous souhaitez participer aux rubriques Qt (tutoriels, FAQ, traductions) ou HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  5. #5
    Membre éclairé Avatar de guitz
    Homme Profil pro
    Webdesigner
    Inscrit en
    Juillet 2006
    Messages
    717
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Webdesigner

    Informations forums :
    Inscription : Juillet 2006
    Messages : 717
    Points : 741
    Points
    741
    Par défaut
    Merci encore dourouc05, je vais rester sur une graphe unique (orienté) et plusieurs arêtes ou sommets pointeront vers le meme objet Spline pour l'affichage.

Discussions similaires

  1. City cuilder : utiliser la théorie des graphes pour modéliser le réseau routier ?
    Par guitz dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 03/08/2017, 20h34
  2. [Graphe non orienté] Arêtes à enlever pour rendre un nœud non accessible
    Par PeiJar dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 28/05/2017, 19h57
  3. getfolder() non fonctionnelle pour une adresse réseau
    Par thefutureisnow dans le forum VB 6 et antérieur
    Réponses: 2
    Dernier message: 16/02/2011, 18h28
  4. Plus court chemin - graphe NON orienté et pondéré
    Par Nicodemus dans le forum Algorithmes et structures de données
    Réponses: 5
    Dernier message: 14/03/2006, 16h32
  5. algos sur graphes non orientés
    Par lechewal dans le forum Algorithmes et structures de données
    Réponses: 9
    Dernier message: 05/01/2006, 15h06

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