+ Répondre à la discussion
Affichage des résultats 1 à 6 sur 6

Discussion: Gérer les graphes

  1. #1
    Futur Membre du Club
    Homme Profil pro
    Inscrit en
    avril 2011
    Messages
    78
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations forums :
    Inscription : avril 2011
    Messages : 78
    Points : 18
    Points
    18

    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 :
    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 581
    Détails du profil
    Informations forums :
    Inscription : septembre 2003
    Messages : 4 581
    Points : 6 016
    Points
    6 016

    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
    Futur Membre du Club
    Homme Profil pro
    Inscrit en
    avril 2011
    Messages
    78
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations forums :
    Inscription : avril 2011
    Messages : 78
    Points : 18
    Points
    18

    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 581
    Détails du profil
    Informations forums :
    Inscription : septembre 2003
    Messages : 4 581
    Points : 6 016
    Points
    6 016

    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 :
    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 :
    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 :
    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
    Futur Membre du Club
    Homme Profil pro
    Inscrit en
    avril 2011
    Messages
    78
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations forums :
    Inscription : avril 2011
    Messages : 78
    Points : 18
    Points
    18

    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 581
    Détails du profil
    Informations forums :
    Inscription : septembre 2003
    Messages : 4 581
    Points : 6 016
    Points
    6 016

    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

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •