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

Python Discussion :

Adjacence et graphe


Sujet :

Python

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre averti
    Femme Profil pro
    Étudiant
    Inscrit en
    Décembre 2019
    Messages
    23
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Décembre 2019
    Messages : 23
    Par défaut Adjacence et graphe
    Bonjour,

    J'ai un travail d'informatique qui consiste à modéliser le réseau du métro parisien par un graphe.

    Donc là l'objectif c'est de savoir, pour chaque station, à quelles autres stations elle est reliée.

    Pour être plus concret, voici donc ce que j'ai. J'ai une liste nommée "métros" contenant 16 listes. Chacune des 16 listes contenue dans "métros" est une liste contenant la succession des stations de métro d'une ligne.

    Voici un extrait de la liste "métros" :

    métros=[[’La Défense Grande Arche’,’Esplanade de La Défense’,’Pont de Neuilly’,’Les Sablons’,’Jardin d'Acclimatation’,’Porte Maillot’,’Palais des Congrès’,’Argentine’,’Charles de Gaulle – Étoile’,’George V’,’Franklin D. Roosevelt’,’Champs-Élysées – Clemenceau’,’Grand Palais’,’Concorde’,’Tuileries’,’Palais-Royal - Musée du Louvre’,’Louvre – Rivoli’,’Châtelet’,’Hôtel de Ville’,’Saint-Paul’,’Le Marais’,’Bastille’,’Gare de Lyon’,’Reuilly – Diderot’,’Nation’,’Porte de Vincennes’,’Saint-Mandé’,’Bérault’,’Château de Vincennes’],[’Charles de Gaulle – Étoile’,’Ternes’,’Courcelles’,’Monceau’,’Villiers’,’Rome’,’Place de Clichy’,’Blanche’,’Pigalle’,’Anvers’,’Sacré-Cœur’,’Barbès - Rochechouart’,’Chapelle’,’Stalingrad’,’Jaurès’,’Colonel Fabien’,’Belleville’,’Couronnes’,’Ménilmontant’,’Père Lachaise’,’Philippe Auguste’,’Alexandre Dumas’,’Avron’,’Nation’],...]

    métros[0] est donc la liste des stations de métro de la ligne 1 du métro de Paris. Et là, on voit déjà quelque chose de pas cool : métros[0] alors que c'est la ligne 1...

    métros[13] est donc la liste des stations de métro de la ligne 14.

    Il faut aussi savoir que j'ai un fichier Excel avec la distance de chaque station par rapport à un des terminus de la ligne. J'ai ça pour toutes les lignes.

    Maintenant je veux donc créer le graphe des lignes de métro de Paris : comment faire ?

    Je pense faire un dictionnaire... Avec en clé le nom d'une station, mais que mettre en valeur ? Et comment faire ça en Python surtout ? Automatiser la création d'un dictionnaire pour chaque station ?

    Merci beaucoup par avance pour votre aide, cela fait longtemps que je suis sur ce travail, et je commence à être désemparée.....

  2. #2
    Expert éminent
    Homme Profil pro
    Architecte technique retraité
    Inscrit en
    Juin 2008
    Messages
    21 741
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Manche (Basse Normandie)

    Informations professionnelles :
    Activité : Architecte technique retraité
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2008
    Messages : 21 741
    Par défaut
    Salut,

    Vous devriez commencer par simplifier i.e. prendre 2 lignes de métro fictives où la première ligne à 3 stations A, B, C et croise la deuxième ligne D, B, E en B.
    Vous voyez bien qu'aller de A en C sans changer de ligne sera à traiter différemment qu'aller de A en E en changeant de ligne en B.
    Car même si on dit que les métros roulent à vitesse constante, changer de ligne n'est aussi indolore (côté durée) que tourner à la première à gauche lorsqu'on se déplace à pied ou en voiture.

    Tout çà pour dire que votre représentation de donnée doit être adaptée aux contraintes que vous voulez prendre en compte et aux opérations que vous allez vouloir réaliser. Et que si vous voulez visualiser un peu ce dont vous avez besoin, vous avez intérêt à réfléchir à tout çà sur un modèle réduit avant de généraliser.

    Et là vous êtes dans la conception et encore loin de vous poser la question de traduire çà en structures de données (dictionnaires, listes,...).
    De toutes façons, pour résoudre ce genre de problème, on apprendra à utiliser networkx, mais sans avoir fait le boulot de conception préalable vous ne saurez pas plus comment construire votre graphe...

    - W
    Architectures post-modernes.
    Python sur DVP c'est aussi des FAQs, des cours et tutoriels

  3. #3
    Membre averti
    Femme Profil pro
    Étudiant
    Inscrit en
    Décembre 2019
    Messages
    23
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Décembre 2019
    Messages : 23
    Par défaut
    Merci beaucoup !


    Deux lignes : L1=["A","B","C"] et L2=["B","D","E"]. Soit L=[["A","B","C"],["B","D","E"]].
    L[0] est donc la liste des stations de la ligne 1...

    A partir de cette liste L, je dois donc construire les dictionnaires pour chaque gare.

    Donc, construisons ces dictionnaires pour chaque gare A, B, C, D et E à partir de la liste L.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    dic={}
    for i in range (len(L)):
        for j in range (len(L[i])):
            station=L[i][j]
    Avec ça, on a donc, la liste des stations, non ? Comment continuer pour avoir les dictionnaires attendus ? C'est-à-dire dictionnaire avec en entrée une station de métro, et chaque valeur associée est la liste des stations sur la même ligne ainsi que les distances les séparant de la station de départ (terminus).

    Merci beaucoup.

  4. #4
    Membre averti
    Femme Profil pro
    Étudiant
    Inscrit en
    Décembre 2019
    Messages
    23
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Décembre 2019
    Messages : 23
    Par défaut
    Je précise que voici le genre de données que j'ai pour chaque ligne de métro :

    Nom : stations_tableau.png
Affichages : 472
Taille : 4,1 Ko

  5. #5
    Expert éminent
    Homme Profil pro
    Architecte technique retraité
    Inscrit en
    Juin 2008
    Messages
    21 741
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Manche (Basse Normandie)

    Informations professionnelles :
    Activité : Architecte technique retraité
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2008
    Messages : 21 741
    Par défaut
    Salut,

    Citation Envoyé par etudiante0020 Voir le message
    Avec ça, on a donc, la liste des stations, non ? Comment continuer pour avoir les dictionnaires attendus ? C'est-à-dire dictionnaire avec en entrée une station de métro, et chaque valeur associée est la liste des stations sur la même ligne ainsi que les distances les séparant de la station de départ (terminus).
    Parler de "dictionnaires attendus" suppose que vous ayez décrit ces choses là.
    Essayez décrire (sur une feuille de papier) ce que vous voulez obtenir à partir de L=[["A","B","C"],["B","D","E"]].

    Et vérifiez que cette représentation là vous aide à traduire ce que vous voulez avant d'imaginer quelles seraient les structures de données les plus adaptées et éventuellement coder.

    - W
    Architectures post-modernes.
    Python sur DVP c'est aussi des FAQs, des cours et tutoriels

  6. #6
    Membre averti
    Femme Profil pro
    Étudiant
    Inscrit en
    Décembre 2019
    Messages
    23
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Décembre 2019
    Messages : 23
    Par défaut
    Citation Envoyé par wiztricks Voir le message
    Salut,

    Essayez décrire (sur une feuille de papier) ce que vous voulez obtenir à partir de L=[["A","B","C"],["B","D","E"]].
    Vous avez raison, je n'y arrive pas...

    C'est parce que la structure de données (le dictionnaire) n'est pas adaptée ?

  7. #7
    Expert confirmé Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    Septembre 2005
    Messages
    5 287
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : Septembre 2005
    Messages : 5 287
    Par défaut
    Bonjour

    Dans une base de données, j'aurais fait une colonne pour la station de départ et une colonne pour la station adjacente. Soit 2 colonnes.
    Exemple :
    A B
    A C
    A D
    ...
    
    Mais en python, avec dictionnaire, la valeur serait la liste des stations adjacentes atteintes à partir de la station d'indice.
    Exemple :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    >>> dic={}
    >>> dic['A']=['B','C','D']
    >>> dic
    {'A': ['B', 'C', 'D']}
    >>> len(dic['A'])
    3
    >>>
    La dernière commande dit que la station 'A' a 3 voisins.

    Il te reste à parcourir les listes des lignes pour déterminer les voisins. Attention ! Les lignes n'ont pas forcément le même retour que l'aller.

  8. #8
    Expert éminent
    Homme Profil pro
    Architecte technique retraité
    Inscrit en
    Juin 2008
    Messages
    21 741
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Manche (Basse Normandie)

    Informations professionnelles :
    Activité : Architecte technique retraité
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2008
    Messages : 21 741
    Par défaut
    Citation Envoyé par etudiante0020 Voir le message
    Vous avez raison, je n'y arrive pas...

    C'est parce que la structure de données (le dictionnaire) n'est pas adaptée ?
    Non: c'est parce que vous ne savez pas ce que vous voulez... et tant que vous n'y arriverez pas, pas la peine de coder.

    - W
    Architectures post-modernes.
    Python sur DVP c'est aussi des FAQs, des cours et tutoriels

Discussions similaires

  1. Transformer matrice d'adjacence en graphe non orienté
    Par Samarita dans le forum MATLAB
    Réponses: 0
    Dernier message: 17/04/2014, 12h00
  2. Djikstra sur un graphe représenté par une liste d'adjacence
    Par gnouz dans le forum Algorithmes et structures de données
    Réponses: 1
    Dernier message: 27/01/2008, 23h03
  3. Matrice d'adjacence et graphe
    Par xavhawk dans le forum Images
    Réponses: 4
    Dernier message: 19/10/2007, 09h11
  4. Graphe d'adjacence des regions
    Par Darkcristal dans le forum Traitement d'images
    Réponses: 4
    Dernier message: 27/07/2007, 16h52
  5. Théorie des graphes : Représentation GRAPHIQUE d'une matrice d'adjacence
    Par jm_gouy dans le forum Algorithmes et structures de données
    Réponses: 3
    Dernier message: 03/05/2006, 16h53

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