Discussion :

[Celes_Vongola]

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

[Trap D]

Une petite explication sur le but du code serait bienvenue !

[Celes_Vongola]

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é ^^"

[Trap D]

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 ?

[Celes_Vongola]

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) ) )

[Trap D]

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.