Az előző bejegyzésekben gráfok reprezentációjával és az alapvető gráfalgoritmusokkal (szélességi és mélységi bejárás, legrövidebb út) foglalkoztunk. Ennek során a csúcsokat képviselő Vertex osztály mellett kifejlesztettük a gráfot modellező Graph osztályt. E két osztályt mint gráfmodellt fogjuk használni a továbbiakban, és ehhez ezeket egy graph_model nevű modulba helyezzük. E modul tartalma tehát ez:
|
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 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 |
# modul: graph_model from collections import defaultdict class Vertex: def __init__(self, label, data=None): self.label = label self.data = data def __repr__(self): args = f'{self.label}, {self.data}' \ if self.data is not None else f'{self.label}' return f'{type(self).__name__}({args})' class Graph: def __init__(self): self.vertices: dict[str, Vertex] = dict() self.neighbors: dict[str, set[tuple[str, int | float]]] = defaultdict(set) def __str__(self): w = max(len(vname) for vname in self.neighbors) graph_string = [] for vertex_label, neighbors in self.neighbors.items(): nbrs = str(neighbors).strip("{}") if neighbors else '' graph_string.append(f'{vertex_label:{w}} {chr(0x279E)} {nbrs}\n') return ''.join(graph_string) def add_connection(self, start_vertex_label: str, end_vertex_label: str, weight=1): """A megadott kezdő- és végcsúcs közötti élt határozza meg a gráfban. Opcionálisan az élhez rendelhető egy súly is. Ha a csúcsok nem léteznek még, akkor azokat létrehozza. """ # Hozzáadjuk az adott induló csúcshoz tartozó halmazhoz a végcsúcs és az él súlyából képzett párost. # Ha az adott csúcs még nincs a szótárban, akkor felveszi, és rögtön hozzárendel egy halmaz konténert. self.neighbors[start_vertex_label].add((end_vertex_label, weight)) # Felvesszük a szomszédságot leíró szótárba a végcsúcsot, ha az nem létezik még, és amihez # rögtön hozzárendelünk egy halmaz konténert. self.neighbors[end_vertex_label] # A tényleges csúcs objektumokat is létrehozzuk és eltároljuk, ha még nem léteznek. if start_vertex_label not in self.vertices: self.vertices.update({start_vertex_label: Vertex(start_vertex_label)}) if end_vertex_label not in self.vertices: self.vertices.update({end_vertex_label: Vertex(end_vertex_label)}) def remove_edge(self, start_vertex_label: str, end_vertex_label: str): """A megadott kezdő- és végcsúcs közötti élt eltávolítja.""" self.neighbors[start_vertex_label] = set(item for item in self.neighbors[start_vertex_label] if item[0] != end_vertex_label) def remove_vertex(self, vertex_label: str): """A megadott csúcsot eltávolítja a gráfból.""" # A csúcs objektumok közül eltávolítjuk a csúcsot. self.vertices.pop(vertex_label) # A szomszédságot leíró szótárból eltávolítjuk a megadott csúcsot. self.neighbors.pop(vertex_label) # Minden olyan csúcs esetén, amelynek szomszédja volt, kivesszük a szomszéd csúcsok közül. for vxl, nbs in self.neighbors.items(): self.neighbors[vxl] = set(item for item in nbs if item[0] != vertex_label) def set_vertex_data(self, vertex_label, vertex_data): """Egy adott csúcshoz értéket rendel.""" if vx := self.vertices.get(vertex_label): vx.data = vertex_data @staticmethod def check_edge_weight_values(fn): def inner(self, start_vertex_label: str): # Ellenőrizni kell, hogy minden élsúly szám-e, és nem negatív. try: for vertex_label, neightbor_set in self.neighbors.items(): for neighbor_label, edge_distance_to_neighbor in neightbor_set: # Ha a konverzió nem lehetséges, akkor az azt jelenti, hogy a súly nem szám, vagy # számnak nem tekinthető karaktersorozat a súly. Ekkor típushibát jelző kivétel dobódik. weight_num = float(edge_distance_to_neighbor) # Ha ugyan a súly szám, de negatív, akkor ezt jelző kivétel keletkezik. if weight_num < 0: raise ValueError('Minden élsúly nem negatív valós szám kell, hogy legyen') except (TypeError, ValueError): raise TypeError( f'{vertex_label}-{neighbor_label} csúcsok közötti él súlya:{edge_distance_to_neighbor}. ' f'Minden él súlyának valós számnak kell lenni.') return fn(self, start_vertex_label) return inner @check_edge_weight_values def shortest_paths(self, start_vertex_label: str): """Visszaadja egy szótárban a megadott csúcstól számított legrövidebb út hosszát, valamint az összes csúcshoz vezető legrövidebb útvonalat. """ # Minden kiinduló ponttól számított, eddig ismert legrövidebb úthosszat minden csúcsra végtelenre # állítjuk, hiszen ezeket kezdetben nem ismerjük még. for vertex_label in self.vertices: self.set_vertex_data(vertex_label, [float('inf'), None]) # A kiinduló csúcs eddig ismert legrövidebb úthosszát 0-ra állítjuk, hiszen önmagától nulla távra van. self.set_vertex_data(start_vertex_label, [0, None]) # Minden csúcsot még nem vizsgáltnak (nem látogatottnak) állítjuk be. unvisited: dict = {label: vertex for label, vertex in self.vertices.items()} while unvisited: # Egy olyan új aktuális vizsgálni kivánt csúcsot választunk a még nem látogatott csúcsok közül, amely # ezek közül a legrövidebb útvonallal rendelkezik. current = min(unvisited, key=lambda lbl: unvisited[lbl].data[0]) # Az aktuális csúcsra kiszámítjuk a távolságot az összes nem látogatott szomszédjától. for neighbor, edge_distance_to_neighbor in self.neighbors[current]: if neighbor in unvisited: neighbor_vertex_obj = self.vertices[neighbor] # Ha a szomszéd csúcs eddig ismert legrövidebb úthossza nagyobb, mint a jelenlegi csúcs # eddig ismert legrövidebb úthossza + a közöttük levő út hossza, akkor a szomszéd csúcs eddig # ismert legrövidebb úthosszát erre az összegre módosítjuk. if (distance := self.vertices[current].data[0] + float(edge_distance_to_neighbor)) < \ neighbor_vertex_obj.data[0]: neighbor_vertex_obj.data = [distance, current] # Miután az aktuális csúcs minden szomszédját megvizsgáltuk és aktulizáltuk a szomszéd legrövidebb # távolság adatát és az odavezető megelőző csúcsot, az aktuális csúcsot megvizsgáltnak tekintjük és # kivesszük a még meg nem látogatottak listájából. unvisited.pop(current) # Segédfüggvény def shortest_path(end_vertex_label: str): """A start_vertex-től az argumentumként megadott végcsúcshoz vezető legrövidebb úton levő csúcsok listáját adja vissza a csúcsok adatai alapján. """ path = [] path.append(end_vertex_label) while previous_vertex := self.vertices[end_vertex_label].data[1]: path.append(previous_vertex) end_vertex_label = previous_vertex return path[-1::-1] # A visszatérési értékként szolgáló szótár előállítása, amelynek kulcsai a célcsúcsok címkéi, az # ezekhez tartozó értékek olyan tuple konténerek, amelyek első eleme a célcsúcsig vezető legrövidebb # út hossza, második eleme pedig a legrövidebb útat jelentő csúcsok listája. shortest_distances_and_paths = {vx_label: (self.vertices[vx_label].data[0], shortest_path(vx_label)) for vx_label in self.vertices if self.vertices[vx_label].data[0] != float('inf')} return shortest_distances_and_paths def breadth_first_traversal(self, start_vertex_label: str) -> list[str]: visited = [] # A már bejárt (megvizsgált, feldolgozott) csúcsok listája. # A vizsgálatra váró csúcsok listája, ami kezdetben csak a kiinduló csúcsot tartalmazza. unvisited = [start_vertex_label] while unvisited: # A vizsgálatra váró csúcsok listájából vesszük a soron következőt. current = unvisited.pop(0) if current not in visited: # Ha az aktuálisan vizsgált csúcs nincs a meglátogatottak között, akkor felvesszük ezek listájába. visited.append(current) # Összegyűjtjük az aktuálisan vizsgált csúcs szomszédait. neighbours = [neighbour for neighbour, weight in self.neighbors[current]] # Kiválogatjuk a szomszédok közül a még nem vizsgáltakat. unvisited_neighbours = [neighbour for neighbour in neighbours if neighbour not in visited] # Ezeket hozzáadjuk a vizsgálatra váró csúcsok listájához. unvisited.extend(unvisited_neighbours) return visited def breadth_first_iterator(self, start_vertex_label: str) -> 'Generátor-iterátor[Vertex]': visited = set() # A már bejárt (megvizsgált, feldolgozott) csúcsok halmaza. # A vizsgálatra váró csúcsok listája, ami kezdetben csak a kiinduló csúcsot tartalmazza. unvisited = [start_vertex_label] for vx in self.vertices.values(): vx.data = 0 while unvisited: current = unvisited.pop(0) if current not in visited: # Ha az aktuálisan vizsgált csúcs nincs a meglátogatottak között, akkor felvesszük ezek halmazába. visited.add(current) # Kiadjuk a csúcsobjektumot. yield self.vertices.get(current) neighbours = [neighbour for neighbour, weight in self.neighbors[current]] unvisited_neighbours = [neighbour for neighbour in neighbours if neighbour not in visited] unvisited.extend(unvisited_neighbours) for nb in unvisited_neighbours: self.vertices.get(nb).data = self.vertices.get(current).data + 1 def depth_first_iterator(self, start_vertex_label: str) -> 'Generátor-iterátor[Vertex]': visited = set() # A már bejárt (megvizsgált, feldolgozott) csúcsok halmaza. # A vizsgálatra váró csúcsok listája, ami kezdetben csak a kiinduló csúcsot tartalmazza. unvisited = [start_vertex_label] # LIFO módban fogjuk használni (verem megvalósítása). while unvisited: current = unvisited.pop() # A LIFO konténer legutoljára betett elemét vesszük ki vizsgálatra. if current not in visited: # Ha az aktuálisan vizsgált csúcs nincs a meglátogatottak között, akkor felvesszük ezek halmazába. visited.add(current) # Kiadjuk a csúcsobjektumot. yield self.vertices.get(current) neighbours = [neighbour for neighbour, weight in self.neighbors[current]] unvisited_neighbours = [neighbour for neighbour in neighbours if neighbour not in visited] unvisited.extend(unvisited_neighbours) def __call__(self, start_vertex_label: str, algo='breadth_first') -> 'Generátor-iterátor[Vertex]': algo_iterators = dict(breadth_first=self.breadth_first_iterator, depth_first=self.depth_first_iterator) return algo_iterators.get(algo)(start_vertex_label) def depth_first_recursive(self, start_label: str, end_label: str): path, visited = [], set() def inner(start_lbl, end_lbl): path.append(start_lbl) visited.add(start_lbl) # Alapeset if start_lbl == end_lbl: return path # Rekurzív rész for neighbor, weight in self.neighbors[start_lbl]: if neighbor not in visited: ret = inner(neighbor, end_lbl) if ret is not None: return ret path.pop() return None return inner(start_label, end_label) |
Most e modellhez egy grafikus felhasználói interfészt (GUI) biztosító osztályt hozunk létre, amelyek együtt olyan alkalmazást adnak, amellyel gráfokat tudunk rajzolni és az alapvető algoritmusokat tudjuk a megrajzolt gráfon működtetni.
A GUI kivitelezését a tkinter modul segítségével valósítjuk meg, és alap kinézetét a következő kép mutatja.
A grafikus felület egy főablakból áll, ami három részre tagolódik, amelyeket egy-egy keret elem (Frame widget) határoz meg. A felső keretben helyezkednek el azok a nyomógombok, amelyekkel valamilyen hatást akarunk elérni a bal oldali keretben megrajzolt gráfra vonatkozóan. A Törlés nyomógombbal lehet törölni az eddig rajzolt gráfot és egy újat kezdeni. A további gombokkal az ablak jobb oldali keretében meg lehet jeleníteni a szomszédsági kapcsolatokat, valamint a csúcsok sorrendjét szélességi vagy mélységi bejárás esetén. A bejárás kiinduló csúcsát a beviteli mezőben lehet megadni.
A csúcsok felvételét a Ctrl + bal egérgombbal lehet megtenni. A megjelelő csúcsok címkéi automatikusan képződnek nemnegatív egész számok sorozatának formájában.
A csúcsokat összekötő élek lehetnek nem irányítottak és irányítottak. Nem irányított élt úgy tudunk létrehozni, ha a két csúcsra a jobb egérgombbal kattintunk. Az összekötő vonal a második csúcsra való kattintás után kirajzolódik. Irányított élt hasonló módon hozhatunk létre, de ilyenkor Ctrl+jobb egérgombbal kell kattintani.
Az éleket törölni is lehet. Ehhez a törlendő élt először ki kell jelölni. Ezt a bal egérgombbal duplán kattintva tehetjük meg. A kijelölést az él színének megváltozása mutatja. A kijelölés után, a jobb egérgomb kattintás hatására törlődik az él.
A grafikus megjelenítést végző osztályt egy graph_visualizer_gui_application.py nevű modulban definiáljuk, amely egyben a főmodul is, vagyis ezt kell majd futtatni, és ez használja a korábban említett graph_model modult.
A graph_visualizer_gui_application.py modul, illetve a benne definiált GraphApp osztály kódját a követhetőség könnyítése érdekében részletekben mutatjuk az alábbiakban. A működés megértését a részletes kommentek segítik.
Elsőként az __init__ tartalmát mutatjuk, ahol a gráfmodell egy példányát és a szükséges grafikus elemeket hozzuk létre. Szintén itt hozzuk létre a csúcsok numerikus címkéihez a számsorozatot előállító generátort.
|
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 |
import tkinter as tk from itertools import count from graph_model import Vertex, Graph class GraphApp(tk.Tk): def __init__(self): super().__init__() # A modellből létrehozzuk a gráf példányt. self.graph = Graph() # A főablak címe és mérete. self.title('Gráf rajzoló') self.geometry('1200x600') # Három keretbe rendezzük a grafikus felületet. Az egyik a parancsgombokat tárolja, a másik a vásznat, # a harmadik pedig az eredményeket megjelenítő felületet. self.frame0 = tk.Frame(self, height=50) self.frame1, self.frame2 = tk.Frame(self, width=600, bg='silver'), tk.Frame(self, width=600, bg='silver') self.frame1.pack_propagate(False) self.frame2.pack_propagate(False) # A vászon és az eredménymegjelenítés grafikus elemei. self.cnv = tk.Canvas(self.frame1, bg='LightSkyBlue1') self.output_var = tk.StringVar(self) self.output_label = tk.Label(self.frame2, bg='white', font=('Consolas', 14, 'bold'), justify=tk.LEFT, anchor='nw', textvariable=self.output_var) # A különféle parancsokhoz a nyomógombok létrehozása és a megfelelő metódusok hozzárendelése. common_configs = dict(font=('Segoe UI', 10, 'bold')) self.buttons = [tk.Button(self.frame0, text='Törlés', command=self.clear, **common_configs), tk.Button(self.frame0, text='Szomszédsági kapcsolatok', **common_configs, command=lambda: self.output_var.set(self.get_adjacency())), tk.Button(self.frame0, text='Szélességi bejárás', **common_configs, command=lambda: self.output_var.set(self.get_bfs(self.start_vertex_entry.get()))), tk.Button(self.frame0, text='Mélységi bejárás', **common_configs, command=lambda: self.output_var.set(self.get_dfs(self.start_vertex_entry.get())))] # A teljes gráfbejáráshoz meg lehet adni a kezdő csúcsot egy beviteli mezőben. self.entry_lbl = tk.Label(self.frame0, text='Kezdőcsúcs: ', **common_configs) self.start_vertex_entry = tk.Entry(self.frame0, width=5, font=('Consolas', 14, 'bold')) self.start_vertex_entry.insert(0, '0') self.vertex_label_gen = count() # A csúcsok címkéinek azonosítóit kiadó generátor. self.r = 20 # A csúcsokat megjelenítő körök sugara. # Grafikus elemek lehelyezése. self.place_widgets() # Grafikus elemek, események és eseménykezelők összerendelése. self.bind_event_handlers() # Az összekötéshez kijelölt kezdő- és végcsúcs. Ha None, akkor nincs kijelölt csúcs. self.selected_vertex1 = self.selected_vertex2 = None |
A következő kódsorokban az __init__-ben meghívott két azon metódus definícióját láthatjuk, amelyek a grafikus elemek lehelyezését és az események és eseménykezelők hozzárendelését végzik.
|
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 |
class GraphApp(tk.Tk): # Egyéb metódusok itt nincsenek feltüntetve. def place_widgets(self): """Az egyes grafikus elemek lehelyezése a főablakban és a keretekben.""" self.frame0.pack(side=tk.TOP, fill=tk.X, expand=False, padx=3, pady=1) self.frame1.pack(side=tk.LEFT, fill=tk.BOTH, expand=True, padx=(3, 1), pady=1) self.frame2.pack(side=tk.LEFT, fill=tk.BOTH, expand=True, padx=(1, 3), pady=1) for widget in (*self.buttons, self.entry_lbl, self.start_vertex_entry): widget.pack(side=tk.LEFT, fill=tk.X, expand=False, padx=2, pady=2) self.cnv.pack(side=tk.LEFT, fill=tk.BOTH, expand=True, padx=2, pady=2) self.output_label.pack(side=tk.LEFT, fill=tk.BOTH, expand=True, padx=2, pady=2) def bind_event_handlers(self): """Grafikus elemek, események és eseménykezelők összerendelése.""" # Vászon felett Ctrl+bal egér -> csúcs lehelyezés self.cnv.bind('<Control Button 1>', self.add_vertex) # A csúcsok összekötéséhez a csúcsokat ki kell jelölni. Ehhez a csúcsot reprezentáló kör és címke # elemekhez eseményeket és a kijelölést végző eseménykezelőt rendeljük. # A jobb egérgomb lenyomásával kijelölt csúcsok között nem irányított élt tudunk létrehozni. self.cnv.tag_bind('vertex', '<Button 3>', self.select_vertices_to_connect) self.cnv.tag_bind('vertex_label', '<Button 3>', self.select_vertices_to_connect) # A Ctrl+jobb egérgomb lenyomásával kijelölt csúcsok között irányított élt tudunk létrehozni. self.cnv.tag_bind('vertex', '<Control Button 3>', lambda e: self.select_vertices_to_connect(e, directed=True)) self.cnv.tag_bind('vertex_label', '<Control Button 3>', lambda e: self.select_vertices_to_connect(e, directed=True)) # Dupla bal egérgomb kattintással kijelölhető egy él. self.cnv.tag_bind('edge', '<Double Button 1>', self.select_edge) # Kijelölt él jobb egérgomb kattintással törölhető. self.cnv.tag_bind('edge', '<Button 3>', self.remove_edge) |
Az alábbi kódrészletben a fent említett nyomógombok által meghívott metódusok definíciói vannak felsorolva.
|
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 |
class GraphApp(tk.Tk): # Egyéb metódusok itt nincsenek feltüntetve. # A nyomógombok által meghívott metódusok. def clear(self): """Az aktuális gráf és megjelenítésének törlése, ami egy új gráf készítését teszi lehetővé.""" self.graph = Graph() self.vertex_label_gen = count() self.cnv.delete('all') self.output_var.set('') def get_adjacency(self): """Az aktuális gráf szomszédsági viszonyait reprezentáló karakterláncot ad vissza.""" txt = '' if self.graph.vertices: txt = 'Szomszédsági kapcsolatok:\n' txt += str(self.graph) return txt def get_bfs(self, start_label: str): """Az aktuális gráf adott csúcstól kezdődő teljes szélességi bejárásának sorrendjét reprezentáló karakterláncot ad vissza. """ txt = '' if self.graph.vertices: txt = 'Szélességi bejárás:\n' txt += f' {chr(0x279E)} '.join( str(vertex.label) for vertex in self.graph.breadth_first_iterator(start_label)) return txt def get_dfs(self, start_label: str): """Az aktuális gráf adott csúcstól kezdődő teljes mélységi bejárásának sorrendjét reprezentáló karakterláncot ad vissza. """ txt = '' if self.graph.vertices: txt = 'Mélységi bejárás:\n' txt += f' {chr(0x279E)} '.join(str(vertex.label) for vertex in self.graph.depth_first_iterator(start_label)) return txt |
A a csúcsok lehelyezését és összekötését megvalósító metódusok kódjai a következők:
|
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 |
class GraphApp(tk.Tk): # Egyéb metódusok itt nincsenek feltüntetve. def add_vertex(self, event): """Csúcs felvétele a gráfba az egérmutató koordinátapozíciójában.""" x, y = event.x, event.y vertex_label:str = str(next(self.vertex_label_gen)) # A következő csúcscímke kikérése. # A csúcs egy körrel lesz ábrázolva, amelyben a csúcsazonosító címke mint szöveg látszik. self.cnv.create_oval(x - self.r, y - self.r, x + self.r, y + self.r, fill='white', width=3, tags=('vertex', vertex_label)) self.cnv.create_text(x, y, text=vertex_label, font=('Consolas', 16, 'bold'), tags='vertex_label') # Létrehozzuk a modellben is a csúcsobjektumot. self.graph.vertices[vertex_label] = Vertex(vertex_label) def get_vertex_and_label_item_ids(self, x, y): """Az x,y koordinátáknál található csúcs és címke rajzelemek azonosítóival tér vissza.""" overlapping_items = self.cnv.find_overlapping(x - self.r, y - self.r, x + self.r, y + self.r) vertex_ovalitem_id = [item_id for item_id in overlapping_items if self.cnv.type(item_id) == 'oval'][0] vertex_label_textitem_id = [item_id for item_id in overlapping_items if self.cnv.type(item_id) == 'text'][0] return vertex_ovalitem_id, vertex_label_textitem_id def select_vertices_and_connect(self, event, directed=False): """Csúcsok kijelölése éllel való összekötéshez. Ha mindkét csúcs ki van jelölve, akkor az összekötés is megtörténik. """ x, y = event.x, event.y # Az x,y helyen levő csúcs meghatározása. selected_vertex = self.get_vertex_and_label_item_ids(x, y)[0] if self.selected_vertex1 is None: self.selected_vertex1 = selected_vertex elif self.selected_vertex2 is None: self.selected_vertex2 = selected_vertex # Miután a második csúcs is ki van választva, összekötjük őket. self.connect_vertices(directed) # Ha megtörtént az összekötés, akkor a két csúcs kijelölt státuszát megszüntetjük. self.selected_vertex1 = self.selected_vertex2 = None def connect_vertices(self, directed=False): """A két kijelölt csúcs közé egy vonalat húz. Ha az él irányított, akkor a nyíl a korábban kijelölttől a később kijelöltig mutat. """ # Ellenőrizzük, hogy nincs-e már ilyen él. for edge_line_id in self.cnv.find_withtag('edge'): edge_line_tags = self.cnv.gettags(edge_line_id) v1_id, v2_id = edge_line_tags[1], edge_line_tags[2] if {v1_id, v2_id} == {str(self.selected_vertex1), str(self.selected_vertex2)}: return # Csúcsot önmagával nem kötünk össze. if self.selected_vertex1 == self.selected_vertex2: return # Az eltérő, összekötendő csúcskörök befoglaló koordinátái, és középpont koordinátái. v1_coords, v2_coords = self.cnv.coords(self.selected_vertex1), self.cnv.coords(self.selected_vertex2) v1x0, v1y0 = (v1_coords[0] + v1_coords[2]) / 2, (v1_coords[1] + v1_coords[3]) / 2 v2x0, v2y0 = (v2_coords[0] + v2_coords[2]) / 2, (v2_coords[1] + v2_coords[3]) / 2 # A csúcsok középpontjait összekötő vonal rajzolása, és felcímkézve a kezdő- és végcsúcs körök azonosítójával. edge_line_id = self.cnv.create_line(v1x0, v1y0, v2x0, v2y0, width=3, tags=('edge', str(self.selected_vertex1), str(self.selected_vertex2))) if directed: self.cnv.itemconfig(edge_line_id, arrow=tk.LAST, arrowshape=(10, 12, 5)) length = pow((v2x0 - v1x0) ** 2 + (v2y0 - v1y0) ** 2, 0.5) reduced_length = length - self.r - 15 scale_factor = reduced_length / length self.cnv.scale(edge_line_id, (v1x0 + v2x0) / 2, (v1y0 + v2y0) / 2, scale_factor, scale_factor) # Az összekötővonalat a megjelenítési lista legaljára helyezzük, hogy ne takarja el a csúcskört és címkét. self.cnv.tag_lower(edge_line_id) # Kikeressük az összekötendő csúcsok címkéit, hogy a modellben is össze tudjuk kötni egy éllel. v1_lbl, v2_lbl = self.cnv.gettags(self.selected_vertex1)[1], self.cnv.gettags(self.selected_vertex2)[1] # Csúcsok összekötése a gráf modellben. Ha nem irányított az él, akkor mindkét irányban. self.graph.add_connection(v1_lbl, v2_lbl) if not directed: self.graph.add_connection(v2_lbl, v1_lbl) |
És végül, az él törlését, illetve a törlés előtti kijelölést lehetővé tevő metódusok láthatók alább, valamint az osztály példányosítása és a grafikus alkalmazás indítása.
|
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 |
class GraphApp(tk.Tk): # Egyéb metódusok itt nincsenek feltüntetve. def select_edge(self, event): """Az egérmutatóhoz legközelebb eső élt kijelöltnek címkéz, és megváltoztatja a színét. Ha egy már kijelölt él a legközelebbi él, akkor a kijelölést érvényteleníti. """ x, y = event.x, event.y # Megnézzük, hogy van-e már kijelölt él. Ha van, akkor azt nem kijelöltté tesszük. if old_edges := self.cnv.find_withtag('selected_edge'): self.cnv.dtag(old_edges[0], 'selected_edge') self.cnv.itemconfig(old_edges[0], fill='black') # Az egérmutatónál levő élt kijelöltnek nyilvánítjuk egy taggel, és # megváltoztatjuk a vonal alapszínét. new_edges = self.cnv.find_closest(x, y) if new_edges != old_edges: self.cnv.addtag_closest('selected_edge', x, y) self.cnv.itemconfig(new_edges[0], fill='red') def remove_edge(self, event): """A kijelöltnek címkézett élt eltávolítja a vászonról és a gráfmodellből.""" x, y = event.x, event.y if self.cnv.find_withtag('selected_edge'): edge_to_remove = self.cnv.find_withtag('selected_edge')[0] # A kijelölt él eltávolítása a vászonról. x1, y1, x2, y2 = self.cnv.coords(edge_to_remove) v1_id, v1_lbl_id = self.get_vertex_and_label_item_ids(x1, y1) v2_id, v2_lbl_id = self.get_vertex_and_label_item_ids(x2, y2) self.cnv.delete(edge_to_remove) # A kijelölt él eltávolítása a modellből. v1_lbl, v2_lbl = self.cnv.itemcget(v1_lbl_id, 'text'), self.cnv.itemcget(v2_lbl_id, 'text') self.graph.remove_edge(v1_lbl, v2_lbl) def run(self): self.mainloop() # Alkalmazás indítása graph_app = GraphApp() graph_app.run() |
A kódrészletek után a teszteléshez és használathoz alább láthatjuk a graph_visualizer_gui_application modul teljes tartalmát:
|
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 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 |
# modul: graph_visualizer_gui_application import tkinter as tk from itertools import count from graph_model import Vertex, Graph class GraphApp(tk.Tk): def __init__(self): super().__init__() # A modellből létrehozzuk a gráf példányt. self.graph = Graph() # A főablak címe és mérete. self.title('Gráf rajzoló') self.geometry('1200x600') # Három keretbe rendezzük a grafikus felületet. Az egyik a parancsgombokat tárolja, a másik a vásznat, # a harmadik pedig az eredményeket megjelenítő felületet. self.frame0 = tk.Frame(self, height=50) self.frame1, self.frame2 = tk.Frame(self, width=600, bg='silver'), tk.Frame(self, width=600, bg='silver') self.frame1.pack_propagate(False) self.frame2.pack_propagate(False) # A vászon és az eredménymegjelenítés grafikus elemei. self.cnv = tk.Canvas(self.frame1, bg='LightSkyBlue1') self.output_var = tk.StringVar(self) self.output_label = tk.Label(self.frame2, bg='white', font=('Consolas', 14, 'bold'), justify=tk.LEFT, anchor='nw', textvariable=self.output_var) # A különféle parancsokhoz a nyomógombok létrehozása és a megfelelő metódusok hozzárendelése. common_configs = dict(font=('Segoe UI', 10, 'bold')) self.buttons = [tk.Button(self.frame0, text='Törlés', command=self.clear, **common_configs), tk.Button(self.frame0, text='Szomszédsági kapcsolatok', **common_configs, command=lambda: self.output_var.set(self.get_adjacency())), tk.Button(self.frame0, text='Szélességi bejárás', **common_configs, command=lambda: self.output_var.set(self.get_bfs(self.start_vertex_entry.get()))), tk.Button(self.frame0, text='Mélységi bejárás', **common_configs, command=lambda: self.output_var.set(self.get_dfs(self.start_vertex_entry.get())))] # A teljes gráfbejáráshoz meg lehet adni a kezdő csúcsot egy beviteli mezőben. self.entry_lbl = tk.Label(self.frame0, text='Kezdőcsúcs: ', **common_configs) self.start_vertex_entry = tk.Entry(self.frame0, width=5, font=('Consolas', 14, 'bold')) self.start_vertex_entry.insert(0, '0') self.vertex_label_gen = count() # A csúcsok címkéinek azonosítóit kiadó generátor. self.r = 20 # A csúcsokat megjelenítő körök sugara. # Grafikus elemek lehelyezése. self.place_widgets() # Grafikus elemek, események és eseménykezelők összerendelése. self.bind_event_handlers() # Az összekötéshez kijelölt kezdő- és végcsúcs. Ha None, akkor nincs kijelölt csúcs. self.selected_vertex1 = self.selected_vertex2 = None def place_widgets(self): """Az egyes grafikus elemek lehelyezése a főablakban és a keretekben.""" self.frame0.pack(side=tk.TOP, fill=tk.X, expand=False, padx=3, pady=1) self.frame1.pack(side=tk.LEFT, fill=tk.BOTH, expand=True, padx=(3, 1), pady=1) self.frame2.pack(side=tk.LEFT, fill=tk.BOTH, expand=True, padx=(1, 3), pady=1) for widget in (*self.buttons, self.entry_lbl, self.start_vertex_entry): widget.pack(side=tk.LEFT, fill=tk.X, expand=False, padx=2, pady=2) self.cnv.pack(side=tk.LEFT, fill=tk.BOTH, expand=True, padx=2, pady=2) self.output_label.pack(side=tk.LEFT, fill=tk.BOTH, expand=True, padx=2, pady=2) def bind_event_handlers(self): """Grafikus elemek, események és eseménykezelők összerendelése.""" # Vászon felett Ctrl+bal egér -> csúcs lehelyezés self.cnv.bind('<Control Button 1>', self.add_vertex) # A csúcsok összekötéséhez a csúcsokat ki kell jelölni. Ehhez a csúcsot reprezentáló kör és címke # elemekhez eseményeket és a kijelölést végző eseménykezelőt rendeljük. # A jobb egérgomb lenyomásával kijelölt csúcsok között nem irányított élt tudunk létrehozni. self.cnv.tag_bind('vertex', '<Button 3>', self.select_vertices_and_connect) self.cnv.tag_bind('vertex_label', '<Button 3>', self.select_vertices_and_connect) # A Ctrl+jobb egérgomb lenyomásával kijelölt csúcsok között irányított élt tudunk létrehozni. self.cnv.tag_bind('vertex', '<Control Button 3>', lambda e: self.select_vertices_and_connect(e, directed=True)) self.cnv.tag_bind('vertex_label', '<Control Button 3>', lambda e: self.select_vertices_and_connect(e, directed=True)) # Dupla bal egérgomb kattintással kijelölhető egy él. csúcsok között irányított élt tudunk létrehozni. self.cnv.tag_bind('edge', '<Double Button 1>', self.select_edge) # Kijelölt él jobb egérgomb kattintással törölhető. self.cnv.tag_bind('edge', '<Button 3>', self.remove_edge) def clear(self): """Az aktuális gráf és megjelenítésének törlése, ami egy új gráf készítését teszi lehetővé.""" self.graph = Graph() self.vertex_label_gen = count() self.cnv.delete('all') self.output_var.set('') def get_adjacency(self): """Az aktuális gráf szomszédsági viszonyait reprezentáló karakterláncot ad vissza.""" txt = '' if self.graph.vertices: txt = 'Szomszédsági kapcsolatok:\n' txt += str(self.graph) return txt def get_bfs(self, start_label: str): """Az aktuális gráf adott csúcstól kezdődő teljes szélességi bejárásának sorrendjét reprezentáló karakterláncot ad vissza. """ txt = '' if self.graph.vertices: txt = 'Szélességi bejárás:\n' txt += f' {chr(0x279E)} '.join( str(vertex.label) for vertex in self.graph.breadth_first_iterator(start_label)) return txt def get_dfs(self, start_label: str): """Az aktuális gráf adott csúcstól kezdődő teljes mélységi bejárásának sorrendjét reprezentáló karakterláncot ad vissza. """ txt = '' if self.graph.vertices: txt = 'Mélységi bejárás:\n' txt += f' {chr(0x279E)} '.join(str(vertex.label) for vertex in self.graph.depth_first_iterator(start_label)) return txt def add_vertex(self, event): """Csúcs felvétele a gráfba az egérmutató koordinátapozíciójában.""" x, y = event.x, event.y vertex_label:str = str(next(self.vertex_label_gen)) # A következő csúcscímke kikérése. # A csúcs egy körrel lesz ábrázolva, amelyben a csúcsazonosító címke mint szöveg látszik. self.cnv.create_oval(x - self.r, y - self.r, x + self.r, y + self.r, fill='white', width=3, tags=('vertex', vertex_label)) self.cnv.create_text(x, y, text=vertex_label, font=('Consolas', 16, 'bold'), tags='vertex_label') # Létrehozzuk a modellben is a csúcsobjektumot. self.graph.vertices[vertex_label] = Vertex(vertex_label) def get_vertex_and_label_item_ids(self, x, y): """Az x,y koordinátáknál található csúcs és címke elem azonosítóival tér vissza.""" overlapping_items = self.cnv.find_overlapping(x - self.r, y - self.r, x + self.r, y + self.r) vertex_ovalitem_id = [item_id for item_id in overlapping_items if self.cnv.type(item_id) == 'oval'][0] vertex_label_textitem_id = [item_id for item_id in overlapping_items if self.cnv.type(item_id) == 'text'][0] return vertex_ovalitem_id, vertex_label_textitem_id def select_vertices_and_connect(self, event, directed=False): """Csúcsok kijelölése éllel való összekötéshez. Ha mindkét csúcs ki van jelölve, akkor az összekötés is megtörténik. """ x, y = event.x, event.y # Az x,y helyen levő csúcs meghatározása. selected_vertex = self.get_vertex_and_label_item_ids(x, y)[0] if self.selected_vertex1 is None: self.selected_vertex1 = selected_vertex elif self.selected_vertex2 is None: self.selected_vertex2 = selected_vertex self.connect_vertices(directed) # Miután a második csúcs is ki van választva, összekötjük őket. # Ha megtörtént az összekötés, akkor a két csúcs kijelölt státuszát megszüntetjük. self.selected_vertex1 = self.selected_vertex2 = None def connect_vertices(self, directed=False): """A két kijelölt csúcs közé egy vonalat húz. Ha az él irányított, akkor a nyíl a korábban kijelölttől a később kijelöltig mutat. """ # Ellenőrizzük, hogy nincs-e már ilyen él. for edge_line_id in self.cnv.find_withtag('edge'): edge_line_tags = self.cnv.gettags(edge_line_id) v1_id, v2_id = edge_line_tags[1], edge_line_tags[2] if {v1_id, v2_id} == {str(self.selected_vertex1), str(self.selected_vertex2)}: return # Csúcsot önmagával nem kötünk össze. if self.selected_vertex1 == self.selected_vertex2: return # Az eltérő, összekötendő csúcskörök befoglaló koordinátái, és középpont koordinátái. v1_coords, v2_coords = self.cnv.coords(self.selected_vertex1), self.cnv.coords(self.selected_vertex2) v1x0, v1y0 = (v1_coords[0] + v1_coords[2]) / 2, (v1_coords[1] + v1_coords[3]) / 2 v2x0, v2y0 = (v2_coords[0] + v2_coords[2]) / 2, (v2_coords[1] + v2_coords[3]) / 2 # A csúcsok középpontjait összekötő vonal rajzolása, és felcímkézve a kezdő- és végcsúcs körök azonosítójával. edge_line_id = self.cnv.create_line(v1x0, v1y0, v2x0, v2y0, width=3, tags=('edge', str(self.selected_vertex1), str(self.selected_vertex2))) if directed: self.cnv.itemconfig(edge_line_id, arrow=tk.LAST, arrowshape=(10, 12, 5)) length = pow((v2x0 - v1x0) ** 2 + (v2y0 - v1y0) ** 2, 0.5) reduced_length = length - self.r - 15 scale_factor = reduced_length / length self.cnv.scale(edge_line_id, (v1x0 + v2x0) / 2, (v1y0 + v2y0) / 2, scale_factor, scale_factor) # Az összekötővonalat a megjelenítési lista legaljára helyezzük, hogy ne takarja el a csúcskört és címkét. self.cnv.tag_lower(edge_line_id) # Kikeressük az összekötendő csúcsok címkéit, hogy a modellben is össze tudjuk kötni egy éllel. v1_lbl, v2_lbl = self.cnv.gettags(self.selected_vertex1)[1], self.cnv.gettags(self.selected_vertex2)[1] # Csúcsok összekötése a gráf modellben. Ha nem irányított az él, akkor mindkét irányban. self.graph.add_connection(v1_lbl, v2_lbl) if not directed: self.graph.add_connection(v2_lbl, v1_lbl) def select_edge(self, event): """Az egérmutatóhoz legközelebb eső élt kijelöltnek címkéz, és megváltoztatja a színét. Ha egy már kijelölt él a legközelebbi él, akkor a kijelölést érvényteleníti. """ x, y = event.x, event.y # Megnézzük, hogy van-e már kijelölt él. Ha van, akkor azt nem kijelöltté tesszük. if old_edges := self.cnv.find_withtag('selected_edge'): self.cnv.dtag(old_edges[0], 'selected_edge') self.cnv.itemconfig(old_edges[0], fill='black') # Az egérmutatónál levő élt kijelöltnek nyilvánítjuk egy taggel, és # megváltoztatjuk a vonal alapszínét. new_edges = self.cnv.find_closest(x, y) if new_edges != old_edges: self.cnv.addtag_closest('selected_edge', x, y) self.cnv.itemconfig(new_edges[0], fill='red') def remove_edge(self, event): x, y = event.x, event.y if self.cnv.find_withtag('selected_edge'): edge_to_remove = self.cnv.find_withtag('selected_edge')[0] # A kijelölt él eltávolítása a vászonról. x1, y1, x2, y2 = self.cnv.coords(edge_to_remove) v1_id, v1_lbl_id = self.get_vertex_and_label_item_ids(x1, y1) v2_id, v2_lbl_id = self.get_vertex_and_label_item_ids(x2, y2) self.cnv.delete(edge_to_remove) # A kijelölt él eltávolítása a modellből. v1_lbl, v2_lbl = self.cnv.itemcget(v1_lbl_id, 'text'), self.cnv.itemcget(v2_lbl_id, 'text') self.graph.remove_edge(v1_lbl, v2_lbl) def run(self): self.mainloop() # Alkalmazás indítás graph_app = GraphApp() graph_app.run() |
A teljes programkód ezen github linken is megtekinthető és letölthető: https://github.com/pythontudasepites/graph_visualizer
A következő ábrán egy példafuttatás eredményének képernyőképei láthatók. A bal oldali keretben megrajzolt gráfhoz a jobb oldalon kiírattuk a szomszédsági viszonyokat, valamint a szélességi és mélységi bejárást a 0 jelű csúcstól. A mélységi bejárást egy másik csúcstól kezdve is lekértük.
A gráfmodellben látható, hogy az képes legrövidebb utat számolni, vagy akár csúcsot törölni, hiszen ezeket fejlesztettük ki a korábbi bejegyzések során. A GUI mégsem biztosít ezekhez felületet. Ez szándékos. Mégpedig azért, hogy a meglévő kódok kiegészítésével vagy módosításával gyakorolni lehessen a grafikus interfész fejlesztését úgy, hogy van már egy megjelenítésre képes, használható alap.
A továbbfejlesztésre számtalan lehetőség van. Az előbb említetteken felül például lehessen a csúcsoknak tetszőleges címkét adni, vagy az élekhez súlyt rendelni, és a kezdőcsúcs mellett egy végcsúcsot is megadni, ami feltétel ahhoz, hogy a legrövidebb út algoritmust érdemben lehessen használni; vagy lehessen a gráfot elmenteni és betölteni. Természetesen a modell is bővíthető úgy, hogy további algoritmusok kezelésére vagy műveletek végzésére legyen képes. Nyilván ilyekor a grafikus interfészt is bővíteni kell.
E bejegyzés témájához a Python tudásépítés lépésről lépésre című e-könyv következő részei kapcsolódnak elsősorban: a „Grafikus felhasználói felület készítése” fejezet, illetve ebben a „A grafikus elemek fajtái, létrehozásuk és konfigurálásuk” alfejezet. Ezen belül pedig különösen a „Vászon” alcím