Az előző bejegyzésekben (itt és itt) gráfok ábrázolásával és alapimplementációjával foglalkoztunk és ezt bővítettük ki azzal a képességgel, hogy egy adott csúcspontból meg tudjuk határozni a többi csúcshoz vezető legrövidebb utat.
Most gráfok bejárásával fogunk foglalkozni. Egy gráf bejárása azt jelenti, hogy egy kiinduló csúcstól, az élek által meghatározott irányokban levő csúcsokat valamilyen logika szerinti sorrendben elérjük annak érdekében, hogy a csúcshoz tartozó adatokat feldolgozhassuk. Ez például abban nyilvánul meg, hogy milyen sorrendben kapjuk meg egy gráf csúcsait, ha iterációval kikérjük azokat.
A speciális gráfnak tekinthető láncolt listával ellentétben, ahol egy kezdőelemtől mindig ugyanolyan sorrendben kaphatjuk meg az elemeket, vagyis egyféle módon járhatjuk be, egy általános gráfban a csúcsokból történő elágazások miatt több bejárási lehetőség adódik. Ezekből az egyik az úgynevezett szélességi bejárás (breadth first traversal).
A szélességi bejárás alapelve: úgy járjuk be a gráfot, hogy egy kiinduló csúcstól kezdve az éppen aktuális csúcs szomszédait derítjük fel (látogatjuk meg). Utána e szomszédokat vesszük sorban egymás után, és ezek szomszédait látogatjuk meg, ha valamelyik még nem volt meglátogatva. A már meglátogatottakat nyilvántartásba vesszük. Mindezt addig folytatjuk, amíg van nem felderített (nem meglátogatott) csúcs.
Az eljárásból következik, hogy kétszer ugyanazt a csúcsot nem látogatjuk meg, azaz nem fogjuk újra felkutatni a szomszédait, hiszen egyszer már megtettük.
Az alapelv ismeretében a szélességi bejárás algoritmusának lépései a következők:
- Kiválasztjuk a gráf kezdőcsúcsát, ahonnan be akarjuk járni a gráfot.
- Egy listában nyilvántartást vezetünk a még nem vizsgált (nem meglátogatott) csúcsokról, amelynek kezdetben egyetlen eleme a kiinduló csúcs.
- Egy listában nyilvántartást vezetünk a már vizsgált (meglátogatott) csúcsokról, amely kezdetben nem tartalmaz csúcsot.
- Amennyiben van vizsgálatra váró csúcs a még nem vizsgált csúcsok listájában, akkor
- 4.1 Kivesszük a soron következő csúcsot a nyilvántartási listából és ez lesz az éppen aktuálisan vizsgált és feldolgozott csúcs.
- 4.2 Ha ez az aktuálisan feldolgozott csúcs még nem szerepel meglátogatottként, akkor
- 4.2.1 Ezt az aktuálisan vizsgált csúcsot hozzáadjuk a már vizsgált csúcsok listájához.
- 4.2.2 Összegyűjtjük az aktuálisan vizsgált csúcs szomszédait.
- 4.2.3 Kiválogatjuk a szomszédok közül a még nem vizsgáltakat.
- 4.2.4 Ezeket hozzáadjuk a vizsgálatra váró csúcsok listájához.
- 4.2.5 Folytatjuk az eljárást a 4. ponttól
- Az eljárás eredménye a meglátogatott csúcsok listája, amely a bejárási sorrendet is mutatja.
Az eljárás eredményeképpen nem feltétlenül szükséges az 5. pontban előálló sorozatot egy listában megkapni. Helyette megvalósíthajuk az algoritmust iterátorként, ahol minden egyes meglátogatott csúcsot egy-egy kérésre kiadunk. Ha iterátorral valósítjuk meg, akkor a már meglátogatott és feldolgozott csúcsokat lista helyett halmazban is nyilvántarthatjuk, hiszen ilyenkor nem számít a sorrend.
Alább láthatjuk mindkét megvalósítást egy-egy metódusban. A működést a részletes kommentek írják le, összhangban az előbbi eljárási lépésekkel. /A Graph osztály egyéb metódusait, amelyeket az előző bejegyzésekben dolgozunk ki itt most nem jelenítettük meg. Hasonlóan, a Vertex osztály definíciója sem jelenik meg itt. /
|
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 |
class Graph: # A korábban már elkészült metódusokat itt most nem jelenítjük meg. 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) # Visszaadjuk a csúcsok címkéit a bejárási sorrendben tartalmazó listát. 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] # A csúcsok data attribútuma tárolja a kezdőcsúcstól való távolságot élszámban mérve. # Ennek kezdőértéke 0 lesz minden csúcsra. 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) # A csúcsok kezdőcsúcstól mért távolságértékének aktualizálása. for nb in unvisited_neighbours: self.vertices.get(nb).data = self.vertices.get(current).data+1 def __call__(self, start_vertex_label: str, algo='breadth_first') -> 'Generátor-iterátor[Vertex]': algo_iterators = dict(breadth_first=self.breadth_first_iterator) return algo_iterators.get(algo)(start_vertex_label) |
A breadth_first_traversal nevű metódus adja vissza azt a listát, amely a csúcsok címkéit a bejárási sorrendben tartalmazza az argumentumként megadott kezdőcsúcstól.
A breadth_first_iterator nevű metódus egy generátorfüggvény, amely egy iterációban, illetve minden egyes next() kérésre az argumentumként megadott kezdőcsúcstól számított szélességi bejárás sorrendje szerint szolgáltat ki egy csúcsot. Alaplogikája hasonló a breadth_first_traversal metóduséhoz, ezért nincsenek már mindenütt kommentek. Eltér viszont abban, hogy a már megvizsgált (meglátogatott) csúcsokat lista helyett halmazban tartjuk nyilván és a bejárási sorrendben soron következő csúcsot mint csúcsobjektumot szolgáltatja ki egy yield utasítással. Ezzel a csúcs adatai feldolgozható válnak.
A kódban az is látszik, hogy a csúcsok iterációval való kiadását úgy is megvalósítottuk, hogy a példányt hívhatóvá tettük a __call__ speciális metódus definiálásával. Ez arra jó, hogy argumentumként megadhatjuk, hogy milyen bejárási algoritmust kívánunk alkalmazni. Jelen esetben még csak egyet, a szélességi bejárást ismerjük, ezért csak ez lesz használható. Ha a gráf példányát egy kezdőcsúcspont címkéjével meghívjuk, akkor ugyanazt a hatást érjük el, mint ha a breadth_first_iterator() metódust hívtuk volna meg.
A szélességi bejárás képességével felruházott Graph osztályt egy példa keretében teszteljük. A következő ábrán látható gráf egy olyan családfát modellez, ahol egy csúcs a rokonság egy adott személye, nevével és jelenlegi életkorával jellemezve. Ha már nem élő, akkor ezt is jelezzük. A csúcsok közötti élek szülő-gyerek, azaz vérségi viszonyt határoznak meg. Ezért van az, hogy az apa és anya között ebben a modellben nincs kapcsolati él.
A kódban való megvalósítást a családfát és a személyeket jelentő osztályok definiálásával kezdjük, amelyek rendre a Graph, illetve a Vertex osztályok alosztályai. Ezt követően létrehozzuk a családfa egy példányát és feltöltjük a személyekkel, majd pedig létrehozzuk a közöttük levő kapcsolatokat. Ezután megnézzük, hogy milyen a szélességi bejárása a családfának. Ezt a fenti kódban látható mindhárom metódus kínálta lehetőséggel kiírjuk, amelyek nem meglepő módon ugyanazt az eredményt adjá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 |
# TESZT class Person(Vertex): def __init__(self, name, age): super().__init__(name, 0) self.name, self.age = name, age def __str__(self): return f'{self.name}({self.age})' class FamilyTree(Graph): pass # A családfa példány létrehozása. family_tree = FamilyTree() people_str = '''Irma-23, Éva-25, János-31, Béla-32, Ferenc-31, Ernő-29, Zsolt-27, Géza-55, József-57, Gizi-53, Mária-54, György-57, Péter-66, Áron-84, Katalin-elhunyt, Miklós-elhunyt, Jolán-89''' people = [Person(*p.strip(' \n').split('-')) for p in people_str.split(',')] # Személyek, mint gráf csúcsok megadása. for person in people: family_tree.vertices[person.label] = person # A szülő-gyerek kétirányú kapcsolatokat létrehozó segédfüggvény. def parent_child_links(graph, parents, children): for parent in parents: for child in children: graph.add_connection(child, parent) graph.add_connection(parent, child) # A szülő-gyerek kétirányú kapcsolatok létrehozása a gráfban. parent_child_links(family_tree, ('József', 'Gizi'), ('Irma', 'Éva', 'János', 'Béla')) parent_child_links(family_tree, ('Mária', 'György'), ('Ferenc', 'Ernő', 'Zsolt')) parent_child_links(family_tree, ('Áron', 'Katalin'), ('Géza', 'József', 'Mária')) parent_child_links(family_tree, ('Miklós', 'Jolán'), ('György', 'Péter')) # A szélességi bejárással kapott csúcsok sorrendjének meghatározása és kiírása három módon. print(f' {chr(0x279E)} '.join(family_tree.breadth_first_traversal('Áron'))) print(f' {chr(0x279E)} '.join(person.name for person in family_tree.breadth_first_iterator('Áron'))) print(f' {chr(0x279E)} '.join(person.name for person in family_tree('Áron'))) # Eredmény mindhárom esetben: # Áron ➞ József ➞ Géza ➞ Mária ➞ János ➞ Éva ➞ Béla ➞ Irma ➞ Katalin ➞ Ferenc ➞ Ernő ➞ Zsolt ➞ # Gizi ➞ György ➞ Jolán ➞ Miklós ➞ Péter |
Az alábbi tesztekben olyan esetek szerepelnek, amelyeknek már több gyakorlati haszna lehet.
|
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 |
from itertools import groupby # TESZT # Felsoroljuk a családfában szereplő személyeket Árontól kezdve úgy csoportosítva, hogy az azonos # távolságban levő rokonok egy csoportban szerepelnek. for dist, relatives in groupby(sorted(family_tree('Áron'), key= lambda p:p.data), key= lambda p:p.data): print(dist, *relatives) # Eredmény: # 0 Áron(84) # 1 József(57) Géza(55) Mária(54) # 2 Éva(25) Katalin(elhunyt) Béla(32) Irma(23) János(31) Ferenc(31) Zsolt(27) Ernő(29) # 3 Gizi(53) György(57) # 4 Miklós(elhunyt) Jolán(89) # 5 Péter(66) # Arra vagyunk kíváncsiak, hogy Áronnak melyek azok a legközelebbi rokonai, akik egy adott kornál idősebbek. source = 'Áron' age = 55 print('{} {} évnél idősebb rokonai a kapcsolat közelsége szerinti sorrendben:\n'.format(source, age), *[person for person in family_tree(source) if person.label != source if person.age != 'elhunyt' and int(person.age) > age ] ) # Eredmény: # Áron 55 évnél idősebb rokonai a kapcsolat közelsége szerinti sorrendben: # József(57) György(57) Jolán(89) Péter(66) # Most pedig arra vagyunk kíváncsiak, hogy Áronnak melyek azok a rokonai, akik egy adott kornál idősebbek, és # egy megadot rokoni távolságnál nincsenek messzebb. print('{} {} évnél idősebb rokonai a kapcsolat közelsége szerinti sorrendben:\n'.format(source, age), *[person for person in family_tree(source) if person.label != source if person.age != 'elhunyt' and int(person.age) > age if person.data <= 3 ] ) # Eredmény: # Áron 55 évnél idősebb rokonai a kapcsolat közelsége szerinti sorrendben: # József(57) György(57) |
Itt először megnézzük, hogy a családfában szereplő személyek Árontól kezdve milyen hosszú vérségi kapcsolati úton érhetők el, és az azonos távolságban levő rokonokat egyazon csoportban szerepeltetve jelenítjük meg.
A következő tesztben arra adtunk választ, hogy Áronnak melyek azok a legközelebbi rokonai, akik egy megadott kornál idősebbek. Ugyanezt vizsgájuk utána is, de azzal a kiegészítő feltétellel, hogy a rokoni távolság nem lehet egy adott mértéknél hosszabb. Ha a gráf ábrájával összevetjük az eredményeket, látható, hogy a szélességi bejárást megvalósító metódusok helyesen működnek.
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 különösen: a „ „Kérem a következőt! – iterálható objektumok” fejezet, a „Iterátorok és elemeik kinyerésének nyelvi megvalósítása” fejezet, a „Kifogyhatatlan sorozatlövők – generátorfüggvények” fejezet, a „Műveletek” fejezet „Konténerépítés” alfejezete, a „Beépített típusok nyilvános metódusai”, valamint a „Mágikus metódusok egyedi igényre szabott osztályokban” fejezet „Osztálypéldány hívhatóvá tétele” alfejezete.