Discussion :

[HAs891]

Bonjour,
je cherche á créer un programme en python qui me permettra de tracer un graphe manuellement, c’est á dire, en plaçant les points (sommet) et en cliquant sur deux sommet afin de les relier et ainsi former une arête et surtout je cherche á ce que ce graphe ne soit pas juste un dessin parce que je dois en extraire les matrices d'adjacence, d'incidence et aussi appliquer des algorithmes dessus (DFS, BFS, DJikstra).

j'ai essayé et cherché partout mais j'y arrive pas, je ne peux créer des sommets et arêtes que en utilisant les fonctions de la librairie Networkx ( add_node et add_edge) qui ne répondent pas a mon besoin car avec ceux ci je peux créer un graphe que par implémentions.
Voici l'interface du programme que je suis en train de faire, je veux que lorsque je clique sur l'option " Sommet " une nouvelle fenêtre s'ouvre et que je puisse placer les sommets et puis avec l'option " Arête " relier deux sommets.



Merci de m’aider .

[Invité]

Salut !

en cliquant sur deux sommet afin de les relier et ainsi former une arête et surtout je cherche á ce que ce graphe ne soit pas juste un dessin parce que je dois en extraire les matrices d'adjacence, d'incidence et aussi appliquer des algorithmes dessus (DFS, BFS, DJikstra).

Eh beh, vous avez vu ça les gens en terminale ? J'ai jamais entendu parlé de ça avant aujourd'hui.

C'est possible à faire en python mais ça va pas se faire en 2 coups de cuillère à pot.

Une idée de structure trouvé sur le net :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
G = { 
    'A' : ('B' , 'C') , 
    'B' : ('A' , 'C'),
    'C' : ('A' , 'B')
}

Lien

C'est un projet intéressant ! Je m'y colle.

[umfred]

qu'est-ce que tu entends par "placer mes sommets" ?
sinon creuser la doc pour la partie graphique (voir aussi la doc du canvas de tkinter (que tu semble utiliser) http://tkinter.fdex.eu/doc/caw.html
https://networkx.org/documentation/s...drawing-graphs
https://networkx.org/documentation/s...e/drawing.html

[Invité]

Eh beh ce ne fût pas simple de coder ça avec tkinter, je m'y perds dans les coordonnées relatives et les bindings foireux... Il y aura donc des ajustements à faire en fonction de ton projet, ajustements qui peuvent certainement être automatisés mais j'ai eu la flegme.

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
import tkinter as tk
import string, os
 
class v: #Variables
    #cursor = '' #normal cursor
    buttons = {}
    letters = string.ascii_uppercase
    selected = ''
    start_coord = ()
    canva_id = ''
    X, Y = 0, 0
 
def cursor(event):
    root.config(cursor="dot")
 
def place(event):
    if root['cursor'] == 'dot':
 
        '''Trouver un titre au sommet'''
        for l in v.letters:
            for w in canva.winfo_children():
                if l == w.cget('text'):
                    break
            else:
                title = l
                break
        '''__________________________'''
 
        b = tk.Button(canva, text=title, width=1)           #Créer un sommet / bouton
        b.place(x = event.x-8, y = event.y-17)              #Centrer le sommet sur la souris (à ajuster si besoin)
        b.bind('<ButtonPress-1>', select)                   #Sélectionner le bouton lorsque le bouton gauche de la souris est en bas
        b.bind('<Motion>', enter)                           #Finir le tracé
        b.bind('<Leave>', leave)                            #Gérer le curseur
        b.bind('<ButtonRelease-3>', del_button)             #Supprimer le bouton
        b.bind('<ButtonRelease-1>', bidouille)              #Permet de déclencher le bind ('<Motion>', enter) lorsqu'on relache le "drag"
        v.buttons[title]=[(event.x, event.y),[]]       #Ajouter dans le dictionnaire v.buttons les coordonnées du bouton
 
def del_button(event):
    v.buttons.pop(event.widget.cget('text'))
    event.widget.destroy()
 
def bidouille(event):
    root.event_generate('<Motion>', warp=True, x=event.widget.winfo_x()+1+event.x, y=event.widget.winfo_y()+event.y+40) #A ajuster si besoin
 
def select(event):
    if root['cursor'] == 'exchange':                                                    #Si boucler
        x = event.widget.winfo_x()+event.x
        y = event.widget.winfo_y()+event.y
        canva.create_oval(x-50,y-50, x, y)                                              # Créer un cercle / boucle sur un bouton
        v.buttons[event.widget.cget('text')][1].append(event.widget.cget('text'))  #Ajouter dans le dictionnaire le bouton qui boucle sur lui même
        display()
 
    else: 
        v.selected = event.widget
        v.start_coord = v.buttons[event.widget.cget('text')][0]
        v.canva_id = ''
 
def draw(event):        #Dessiner la ligne
    if not v.selected :
        return
 
    if v.canva_id:                             #Supprimer la précédente ligne si encore présente
        canva.delete(v.canva_id)
 
    v.X = v.start_coord[0]+event.x
    v.Y = v.start_coord[1]+event.y-11     #Ajustement
    v.canva_id = canva.create_line(v.start_coord[0], v.start_coord[1], v.X, v.Y)
 
    root.after(1000, canva.delete, v.canva_id) #Supprimer la ligne après 1000 msec
 
def enter(event):           #Finir la ligne
    if len(v.buttons) < 2 or root['cursor'] == 'exchange':
        return
 
    root.config(cursor="crosshair")
 
    if not v.selected:
        return
 
    if event.widget.cget('text') != v.selected.cget('text'):
        canva.create_line(v.start_coord[0], v.start_coord[1], v.X, v.Y)
        v.buttons[v.selected.cget('text')][1].append(event.widget.cget('text')) #On rajoute dans le dictionnaire les 2 sommets rattachés
        v.buttons[event.widget.cget('text')][1].append(v.selected.cget('text')) #On rajoute dans le dictionnaire les 2 sommets rattachés
        v.selected, v.start_coord, v.X, v.Y  = '', (), 0, 0
        display()
 
def display():              #Afficher dans la console le résultat du graph
    os.system('cls')
    for b in sorted(v.buttons):
        print(b, ':', sorted(v.buttons[b][1]))
 
    N = len(v.buttons)
    matrice_adj = [[] for _ in range(N)]
 
    print('\nMATRICE ADJACENTE :')
    for b1 in sorted(v.buttons):
        r = v.letters.index(b1)
        for b2 in sorted(v.buttons):
            n = v.buttons[b1][1].count(b2)
            matrice_adj[r].append(n)
 
    for r in matrice_adj:
        print(r)
 
def leave(event):
    if not v.selected and not root['cursor'] == 'exchange': #Afficher à nouveau le curseur de placement de bouton
        root.config(cursor="dot")
 
def remove_cursor(event):   #Lorsque l'on quitte le canvas
    root.config(cursor="")
 
def boucle(event):          #Curseur pour créer une boucle sur un bouton
    root.config(cursor="exchange")
 
def tracer(event):          #Curseur pour tracer la ligne
    root.config(cursor="crosshair")
 
def delete_all(event):      #Supprimer le contenu du canevas et des variables globales
    v.selected, v.start_coord, v.buttons, v.canva_id, v.X, v.Y = '', (), {}, '', 0, 0
    canva.delete('all')
    for w in canva.winfo_children():
        w.destroy()
    os.system('cls')
 
def deselect(event):        #Si on ne trace pas de ligne et que l'on bouge la souris alors on vide la variable v.selected
                            #Le "drag" depuis un bouton n'est pas détecté par le bind donc on n'est pas en train de tracer la ligne
    v.selected = ''
 
root = tk.Tk()
root.geometry("640x380+0+0")
root.resizable(False, False)
 
b0 = tk.Button(root, text = 'Placer sommet')
b0.bind('<ButtonRelease-1>', cursor)
b0.grid(row=0, column=0)
 
b1 = tk.Button(root, text = 'Tracer ✛')
b1.bind('<ButtonRelease-1>', tracer)
b1.grid(row=0, column=1)
 
b2 = tk.Button(root, text = 'Boucler ⟳')
b2.bind('<ButtonRelease-1>', boucle)
b2.grid(row=0, column=2)
 
b3 = tk.Button(root, text = 'Tout supprimer')
b3.bind('<ButtonRelease-1>', delete_all)
b3.grid(row=0, column=3)
 
canva = tk.Canvas(root, bg='white', width= 630, height=330)
canva.bind('<ButtonRelease-1>', place)
canva.bind('<Leave>', remove_cursor)
canva.bind('<Motion>', deselect)
canva.grid(row=1, column=0, columnspan = 4, pady=5)
 
root.bind('<B1-Motion>', draw) # Lorsqu'on "clique et déplace" ("drag") on dessine un trait
root.mainloop()