p
u
b
l
i
c
i
t
é
publicité

Discussion: Gérer les graphes

  1. #1
    Membre à l'essai
    Homme Profil pro
    Inscrit en
    avril 2011
    Messages
    79
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations forums :
    Inscription : avril 2011
    Messages : 79
    Points : 21
    Points
    21

    Par défaut Gérer les graphes

    Bonjour,
    Je suis un peu désespéré aujourd'hui, ca fait un moment que je suis sur les graphes et je n'y arrive absolument pas...

    Voici l'état de mon code actuel:

    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
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    (define graphe '(  ( 1 ((2 3) (5 2)) )
                       ( 2 ((1 3) (3 5)) )
                       ( 3 ((2 3) (4 1)) )
                       ( 4 ((5 4)) )
                       ( 5 ((1 3) (3 2)) )
                       )
      )
    
    (define graphe2 '(  ( 1 ((2 3)) )
                       ( 2 ((3 3)) )
                       ( 3 ((4 3)) )
                       ( 4 ((5 4)) )
                       ( 5 () )
                       )
      )
    
    (define belongs
      (lambda (Liste X)
        (if (null? Liste)
            #f
            (if (eq? (car Liste) X)
                #t
                (belongs (cdr Liste) X)
                )
            )
      )
    )
    
    (define supp
      (lambda (Liste X)
        (if (null? Liste)
            ()
            (if (eq? (car Liste) X)
                (supp (cdr Liste) X)
                (cons (car Liste) (supp (cdr Liste) X))
                )
            )
        )
      )
    
    
    (define BListe
      (lambda (Graphe)
        (if (null? Graphe)
            ()
            (cons (caar Graphe) (BListe (cdr Graphe)))
            )
        )
      )
    
    
    (define succ
      (lambda (Liste)
        (cadr Liste) 
        )
      )
    
    (define nbSucc
      (lambda (Succ)
        (if (null? Succ)
            0
            (+ (nbSucc (cdr Succ)) 1)
            )
        )
      )
    
    (define cherchePivot
      (lambda (Graphe Pivot)
        (if (eqv? Pivot (caar Graphe))
            (car Graphe)
            (cherchePivot (cdr Graphe) Pivot)
            )
        )
      )
    
    (define chemin2?
      (lambda (Graphe Pivot Sf BListe)
        (if (or (null? Graphe) (not (belongs BListe (car Pivot) )))
            ()
            (if (eqv? (car Pivot) Sf)
                Pivot
              (let((NBsucc (nbSucc (succ (cherchePivot Graphe (car Pivot))))))
                   (if (= NBsucc 0)
                       Pivot 
                     (if (= NBsucc 1)
                              (cons Pivot (chemin2? Graphe (car (succ (cherchePivot Graphe (car Pivot)))) Sf (supp BListe (car Pivot))))
                                 () )     
            ))
         )
      )
    )
    )
    
    (define chemin?
      (lambda (Graphe Pivot Sf )
        (if (null? Graphe)
            ()
            (map (lambda (X) 
                   (list  Pivot (chemin2? Graphe X Sf (supp (BListe Graphe) (car Pivot)))))
                   (succ (cherchePivot Graphe (car Pivot))))
            )
        )
      )
    Déjà que je me suis limité au cas avec 1 seul successeur, et bien je n'arrive pas à obtenir la forme de liste que je voudrais:

    ( (Chemin1) (Chemin2) .... )

    Quelqu'un pourrait m'aiguiller un peu svp? je déprime un peu la
    Bonne Journée

  2. #2
    Rédacteur/Modérateur
    Avatar de Trap D
    Inscrit en
    septembre 2003
    Messages
    4 657
    Détails du profil
    Informations forums :
    Inscription : septembre 2003
    Messages : 4 657
    Points : 5 910
    Points
    5 910

    Par défaut

    Une petite explication sur le but du code serait bienvenue !
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : Intérieur avec jeune femme de Vilhelm Hammershoi

  3. #3
    Membre à l'essai
    Homme Profil pro
    Inscrit en
    avril 2011
    Messages
    79
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations forums :
    Inscription : avril 2011
    Messages : 79
    Points : 21
    Points
    21

    Par défaut

    ah désolé, le but du code est de trouver l'ensemble des chemins d'un graphe (représenté en haut du code), j’avoue que en plus le nom de la fonction est très mal choisi désolé ^^"

  4. #4
    Rédacteur/Modérateur
    Avatar de Trap D
    Inscrit en
    septembre 2003
    Messages
    4 657
    Détails du profil
    Informations forums :
    Inscription : septembre 2003
    Messages : 4 657
    Points : 5 910
    Points
    5 910

    Par défaut

    J'ai un peu regardé le code, pas compris grand chose à ce que tu cherchais à faire.
    Simplement, j'ai remarqué que
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    (define BListe
      (lambda (Graphe)
        (if (null? Graphe)
            ()
            (cons (caar Graphe) (BListe (cdr Graphe)))
            )
        )
      )
    Peut-être remplacé par
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    (define BListe
      (lambda (Graphe)
        (map car Graphe)))
    et que dans la dernière fonction, tu ferais mieux de faire un append plutot qu'un list, tu auras plus de chance d'avoir ce que tu recherches.
    Donnes un exemple d'appel à ta fonction chemin? et le résultat attendu, ce sera plus simple.

    Dernière chose, que se passe-t-il dans cette fonction
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    (define cherchePivot
      (lambda (Graphe Pivot)
        (if (eqv? Pivot (caar Graphe))
            (car Graphe)
            (cherchePivot (cdr Graphe) Pivot)
            )
        )
      )
    si on ne trouve pas le pivot ?
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : Intérieur avec jeune femme de Vilhelm Hammershoi

  5. #5
    Membre à l'essai
    Homme Profil pro
    Inscrit en
    avril 2011
    Messages
    79
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations forums :
    Inscription : avril 2011
    Messages : 79
    Points : 21
    Points
    21

    Par défaut

    J'ai fait exprès de ne pas traiter tous les cas ou de faire toutes les vérifications, car je dois développer les améliorations possibles, en gros la le code marche et ça suffit.
    Le but du code est de renvoyer la liste de tous les chemins possible entre 2 sommets, mais je n'arrive pas a avoir un rendu correct, je testé append et list mais je ne trouve pas =/

    petit exemple:
    (chemin? graphe2 '(1 0) 3)
    => ( ( (1 0) (2 3) (3 3) ) )

  6. #6
    Rédacteur/Modérateur
    Avatar de Trap D
    Inscrit en
    septembre 2003
    Messages
    4 657
    Détails du profil
    Informations forums :
    Inscription : septembre 2003
    Messages : 4 657
    Points : 5 910
    Points
    5 910

    Par défaut

    Citation Envoyé par Celes_Vongola Voir le message
    Jpetit exemple:
    (chemin? graphe2 '(1 0) 3)
    => ( ( (1 0) (2 3) (3 3) ) )
    Effectivement c'est ce que donne ton code, ce que je voudrais savoir c'est ce que tu voudrais obtenir avec (chemin? graphe2 '(1 0) 3)

    Excuse-moi d'insister, mais j'ai du mal à m'y retrouver dans ton prog.
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : Intérieur avec jeune femme de Vilhelm Hammershoi

Discussions similaires

  1. Réponses: 2
    Dernier message: 05/06/2007, 14h17
  2. Gérer les clics sur les boutons
    Par cyberlewis dans le forum Windows
    Réponses: 4
    Dernier message: 08/02/2004, 15h34
  3. Comment gérer les espaces blancs?
    Par Lambo dans le forum XML/XSL et SOAP
    Réponses: 10
    Dernier message: 16/05/2003, 09h44
  4. Concerne les graphes
    Par mcr dans le forum Général Algorithmique
    Réponses: 10
    Dernier message: 12/11/2002, 11h02
  5. gérer les jpg dans une fenetre directdraw???
    Par Anonymous dans le forum DirectX
    Réponses: 1
    Dernier message: 14/06/2002, 13h39

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