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 :

Numéroter la place des noeud dans un graphe


Sujet :

Python

  1. #1
    Membre confirmé
    Femme Profil pro
    Étudiant
    Inscrit en
    Décembre 2018
    Messages
    76
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Cantal (Auvergne)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Décembre 2018
    Messages : 76
    Par défaut Numéroter la place des noeud dans un graphe
    Bonjour,
    Je cherche à noter la placer des nœud dans un grâce c'est à dire que si un nœud dans un graphe a 0 prédécesseur il est a la place 1, si il en a un il est a la place 2 est ainsi de suite. J'ai réussi pour le premier cas (le noeud n'as pas de successeur) mais je bloque totalement pour la seconde partie... Pourriez vous m'aider s'il vous plait ?
    Voici mon code :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
     
     
     
    def placeDansGraphe(directed_graph):
     
        nbPred = 0
        noeudSansPred = []
        tabDePredessesseur = []
        passe = [] 
     
        for n in directed_graph.nodes(): 
            for pred in directed_graph.predecessors(n): 
                directed_graph.nodes[n]['estampille']=10
            if 'estampille' not in directed_graph.nodes[n]: 
                directed_graph.nodes[n]['estampille']=1
                noeudSansPred.append(n)
        for n in directed_graph.nodes(): 
            est = 1
            for suiv in directed_graph.nodes(): 
                if suiv not in noeudSansPred:
                    est = est +1
                    passe.append(n)
                    directed_graph.nodes[suiv]['estampille']=est
     
     
    edges_list=[('p_0_1', 'p_0_2'),('p_0_2', 'p_0_3'),('p_1_1','p_1_2'),('p_1_2','p_1_3'),('p_1_3','p_0_2'),('p_2_1','p_2_2'),('p_2_1','p_1_2'),('p_2_2','p_2_3')]
    Merci d'avance pour vos réponse.

    Cordialement.

  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,

    Dans un graphe orienté la notion de prédécesseur et de successeur est "locale". Chaque nœud pourra avoir n prédécesseurs et m successeurs, mais je ne vois pas trop comment vous allez pouvoir en sortir une "place" i.e. une position dans un chemin.

    Et si vous écrivez un code comme:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
        for n in directed_graph.nodes(): 
            for pred in directed_graph.predecessors(n): 
                directed_graph.nodes[n]['estampille']=10
            if 'estampille' not in directed_graph.nodes[n]: 
                directed_graph.nodes[n]['estampille']=1
                noeudSansPred.append(n)
    Quel est l’intérêt d'exécuter directed_graph.nodes[n]['estampille']=10 pour chaque prédecesseur? Il serait plus simple de regarder len(directed_graph.predecessors(n)).

    Puis:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
        for n in directed_graph.nodes(): 
            est = 1
            for suiv in directed_graph.nodes(): 
                if suiv not in noeudSansPred:
                    est = est +1
                    passe.append(n)
                    directed_graph.nodes[suiv]['estampille']=est
    n'éclaire pas plus sur ce que vous voulez faire.

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

  3. #3
    Membre confirmé
    Femme Profil pro
    Étudiant
    Inscrit en
    Décembre 2018
    Messages
    76
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Cantal (Auvergne)

    Informations professionnelles :
    Activité : Étudiant

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

    Dans un graphe orienté la notion ....
    La partie du code suivant :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
        for n in directed_graph.nodes(): 
            for pred in directed_graph.predecessors(n): 
                directed_graph.nodes[n]['estampille']=10
            if 'estampille' not in directed_graph.nodes[n]: 
                directed_graph.nodes[n]['estampille']=1
                noeudSansPred.append(n)
    Me permet de trouver les sommet sans prédécesseur et de les retenir grace au tableau "noeudSansPred".

    La seconde partie du code :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
        for n in directed_graph.nodes(): 
            est = 1
            for suiv in directed_graph.nodes(): 
                if suiv not in noeudSansPred:
                    est = est +1
                    passe.append(n)
                    directed_graph.nodes[suiv]['estampille']=est
    et la partie qui est censé numéroter les successeurs, mais ça numérote seulement en fonction du parcours ...

  4. #4
    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 hamster18 Voir le message
    et la partie qui est censé numéroter les successeurs, mais ça numérote seulement en fonction du parcours ...
    Censée peut être mais outre que çà ne marche pas, çà n'éclaire pas sur ce que vous voulez, c'est insensé: c'est supposé faire quelque chose dont on ne comprend peut être pas le sens.

    Dessiner un graphe avec quelques nœuds et arcs et essayer de visualiser ce que vous cherchez à faire pourrait vous aider...

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

Discussions similaires

  1. Trouver tous les chemins entre deux noeuds dans un graphe qui contient des boucles
    Par GayaStudent dans le forum Algorithmes et structures de données
    Réponses: 5
    Dernier message: 21/11/2014, 21h31
  2. Gestion automatique des positions des noeuds dans un graph
    Par maissaab dans le forum Général Python
    Réponses: 7
    Dernier message: 30/04/2011, 22h32
  3. Positionnement automatique des noeuds dans un graphe
    Par Zoook dans le forum Algorithmes et structures de données
    Réponses: 1
    Dernier message: 11/12/2008, 14h25
  4. [XSD] Problème d'order sur des noeuds dans un schema
    Par jesus144 dans le forum Valider
    Réponses: 2
    Dernier message: 13/04/2006, 15h59
  5. Pbs pour Glisser-Deplacer des noeuds dans un TreeView.
    Par psau dans le forum C++Builder
    Réponses: 3
    Dernier message: 08/09/2004, 21h02

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