Gráfok mélységi bejárása

Az előző bejegyzésben gráfok szélességi bejárásával foglalkoztunk. Most gráfok mélységi bejárását (depth first traversal) fogjuk megvalósítani.

A mélységi bejárás alapelve: úgy járjuk be a gráfot, hogy egy kiinduló csúcstól kezdve először is az éppen aktuális csúcs szomszédait határozzuk meg, majd ezek közül a még meg nem látogatottakat vesszük nyilvántartásba egy LIFO konténerben, vagyis egy veremben. Utána e verem tetejéről vesszük a csúcsot (ha van) és innen haladunk tovább, vagyis ennek ismét megállapítjuk a szomszédait, azokból a még nemlátogatottakat betesszük a verembe. 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 derítjük fel (látogatjuk meg), azaz nem fogjuk újra felkutatni a szomszédait, hiszen egyszer már megtettük.

Az alapelv ismeretében a mélységi bejárás algoritmusa a következő:

Kiválasztjuk a gráf kezdőcsúcsát, ahonnan be akarjuk járni a gráfot.
Egy verem tároló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úcsokat tartalmazó veremben, akkor
- 4.1. Kivesszük a tetejéről a soron következő csúcsot é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 betesszük a vizsgálatra váró csúcsokat nyilvántartó verembe.
  - 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.

Ha összehasonlítjuk a fenti leírást az előző bejegyzésben szereplő szélességi bejárás leírásával és algoritmikus lépéseivel, akkor látható, hogy lényegében ugyanazokat a lépéseket kell megtenni, azzal a lényeges eltéréssel, hogy a még nem vizsgált csúcsok tárolója mélységi bejárásnál egy LIFO konténer, szemben a szélességi bejárással, ahol ez FIFO működésű.

Ez a hasonlóság a megvalósításban is tükröződik, amit alább láthatunk a depth_first_iterator nevű, generátorfüggvényt megvalósító 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. /


class Graph:
    # A korábban már elkészült metódusokat itt most nem jelenítjük meg.

    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, vagyis veremként.

        while unvisited:
            # A LIFO konténer legutoljára betett elemét vesszük ki mint aktuálisan vizsgálandó csúcsot.
            current = unvisited.pop()

            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)
                
                # # Kiválogatjuk a szomszédok közül a még nem vizsgáltakat. 
                neighbours = [neighbour for neighbour, weight in self.neighbors[current]]
                unvisited_neighbours = [neighbour for neighbour in neighbours if neighbour not in visited]
                
                # Ezeket betesszük a vizsgálatra váró csúcsokat tartalmazó verembe.
                unvisited.extend(unvisited_neighbours)
                
    def __call__(self, start_vertex_label: str, algo='breadth_first') -> 'Generátor-iterátor[Vertex]':
        """A példány meghívásakor első argumentumként megadva a kezdőcsúcsot, ebből indulva bejárja a 
        teljes gráfot a második argumentumban megadott algoritmus szerint. Alapértelmezésben szélességi
        bejárással, amihez a 'breadth_first' paraméterérték tartozik. Ha a 'depth_first' értéket adjuk meg, akkor
        mélységi bejárást hajt végre.
        """
        algo_iterators = dict(breadth_first=self.breadth_first_iterator,
                              depth_first=self.depth_first_iterator)
        return algo_iterators.get(algo)(start_vertex_label)

class Graph:

# A korábban már elkészült metódusokat itt most nem jelenítjük meg.

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, vagyis veremként.

while unvisited:

# A LIFO konténer legutoljára betett elemét vesszük ki mint aktuálisan vizsgálandó csúcsot.

current = unvisited.pop()

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)

# # Kiválogatjuk a szomszédok közül a még nem vizsgáltakat.

neighbours = [neighbour for neighbour, weight in self.neighbors[current]]

unvisited_neighbours = [neighbour for neighbour in neighbours if neighbour not in visited]

# Ezeket betesszük a vizsgálatra váró csúcsokat tartalmazó verembe.

unvisited.extend(unvisited_neighbours)

def __call__(self, start_vertex_label: str, algo='breadth_first') -> 'Generátor-iterátor[Vertex]':

"""A példány meghívásakor első argumentumként megadva a kezdőcsúcsot, ebből indulva bejárja a

teljes gráfot a második argumentumban megadott algoritmus szerint. Alapértelmezésben szélességi

bejárással, amihez a 'breadth_first' paraméterérték tartozik. Ha a 'depth_first' értéket adjuk meg, akkor

mélységi bejárást hajt végre.

"""

algo_iterators = dict(breadth_first=self.breadth_first_iterator,

depth_first=self.depth_first_iterator)

return algo_iterators.get(algo)(start_vertex_label)

Az előző bejegyzésben a szélességi bejárás kapcsán a példányt hívhatóvá tettük a __call__ speciális metódus definiálásával, ami meghíváskor egy iterátort eredményez, amely a gráf teljes bejárását végzi. Bejárási algoritmusnak akkor csak a szélességi állt rendelkezésre. Most, hogy már van mélységi bejárást végző metódus is, a __call__ metódust továbbfejleszthetjük úgy, hogy annak második argumentumaként választhatunk a szélességi és mélységi bejárási algoritmus között. Az így kiegészített __call__ metódus definícióját szintén a fenti kódban látjuk.

A mélységi bejárást gyakran rekurzív módon valósítják meg. Tegyük mi is ezt meg. A következő kódsorokban három metódusimplementációt is látunk. Ezek már nem csak a teljes bejárást végzik, hanem megadható, hogy milyen kezdőcsúcstól mely végcsúcsig történjen a bejárás. Az 1. és 2. változat között az eltérés, hogy while-ciklus helyett for-ciklus működik. A 3. változat pedig abban tér el a 2. változattól, hogy az eddig paraméterek alapértelmezett értékeként szereplő változtatható konténereket „elrejtettük” a metódustörzsben. Ezt úgy tudtuk megtenni, hogy a rekurzívan hívott függvényt beágyaztuk a metódustörzsben.


class Graph:
    # A korábban már elkészült metódusokat itt most nem jelenítjük meg.
    
    def depth_first_recursive1(self, start_label: str, end_label: str, path=[], visited=set()):
        path.append(start_label)
        visited.add(start_label)
        # Alapeset
        if start_label == end_label:
            return path

        # Rekurzív rész
        while neighbors := self.neighbors[start_label]:
            # Az aktuális csúcsnak vesszük egy még nem látogatott szomszédját, ami
            # az aktuális csúcs lesz. Ezzel rekurzívan meghívjuk a függvényt mindaddig, amíg
            # vagy meg nem találtuk a végcsúcsot, vagy az egyre távolabbi csúcsoknak van szomszédja.
            # Ha már nincs, akkor vesszük a korábbi csúcs egy még nem látogatott szomszédját.
            neighbor, weight = neighbors.pop()
            if neighbor not in visited:
                ret = self.depth_first_recursive(neighbor, end_label, path, visited)
                if ret is not None:
                    return ret

        # Ha nem található út a kezdő és végcsúcs között, akkor a visszatérési érték None és az útvonal lista üres.
        path.pop()
        return None

    def depth_first_recursive2(self, start_label: str, end_label: str, path=[], visited=set()):
        path.append(start_label)
        visited.add(start_label)
        # Alapeset
        if start_label == end_label:
            return path

        # Rekurzív rész
        for neighbor, weight in self.neighbors[start_label]:
            if neighbor not in visited:
                ret = self.depth_first_recursive(neighbor, end_label, path, visited)
                if ret is not None:
                    return ret
        path.pop()
        return None


    def depth_first_recursive3(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)

class Graph:

# A korábban már elkészült metódusokat itt most nem jelenítjük meg.

def depth_first_recursive1(self, start_label: str, end_label: str, path=[], visited=set()):

path.append(start_label)

visited.add(start_label)

# Alapeset

if start_label == end_label:

return path

# Rekurzív rész

while neighbors := self.neighbors[start_label]:

# Az aktuális csúcsnak vesszük egy még nem látogatott szomszédját, ami

# az aktuális csúcs lesz. Ezzel rekurzívan meghívjuk a függvényt mindaddig, amíg

# vagy meg nem találtuk a végcsúcsot, vagy az egyre távolabbi csúcsoknak van szomszédja.

# Ha már nincs, akkor vesszük a korábbi csúcs egy még nem látogatott szomszédját.

neighbor, weight = neighbors.pop()

if neighbor not in visited:

ret = self.depth_first_recursive(neighbor, end_label, path, visited)

if ret is not None:

return ret

# Ha nem található út a kezdő és végcsúcs között, akkor a visszatérési érték None és az útvonal lista üres.

path.pop()

return None

def depth_first_recursive2(self, start_label: str, end_label: str, path=[], visited=set()):

path.append(start_label)

visited.add(start_label)

# Alapeset

if start_label == end_label:

return path

# Rekurzív rész

for neighbor, weight in self.neighbors[start_label]:

if neighbor not in visited:

ret = self.depth_first_recursive(neighbor, end_label, path, visited)

if ret is not None:

return ret

path.pop()

return None

def depth_first_recursive3(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)

Mindezek után, a teszteléshez fogaljuk össze a Vertex és Graph osztályok teljes definícióját, amik így néznek ki:


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)

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

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)

A mélységi bejárás működését egy labirintus bejárásának, illetve útkeresésének példáján keretében teszteljük. Az ábrán egy négyszög alakú labirintus (maze) látható, amelynek egymást követő mezőin, cellái lehet haladni, amennyiben két mezőt nem választ el egy fal. Ha a mezőket azonosítókkal látjuk el, pl. számokkal, ahogy az ábrán, akkor a labirintus modellezhető egy gráffal. A gráf csúcsai az egyes mezők. Két csúcs között pedig akkor van él, ha a megfelelő, oldalukkal szomszédos mezők között lehetéséges haladás. Az így kialakított gráfot is mutatja az ábra.

Alább láthatók a tesztsorok. Itt a labirintus mint gráfpéldány létrehozása után egy listában definiáljuk a mezők közötti egymást követő járható kapcsolatokat. Ezek alapján létrehozzuk a gráf éleit.

Első tesztként meghívjuk a labirintus példányt, megadva egy kezdőcsúcs azonosítót és a második argumentumban jelezzük, hogy mélységi bejárást szeretnénk. A bejárás eredményét a csúcsok sorszámának egymást követő sorozatával megjelenítjük.

Második tesztként a rekurzív megvalósítást ellenőrizzük. Itt meghívjuk a depth_first_recursive metódust megadva egy tetszőleges kiinduló mezőt (csúcsot) és egy célmezőt. Utána a kezdőmezőtől a célmezőig vezető utat kiírjuk. Mivel a gráf megvalósításában a szomszédos csúcsok egy halmazban vannak, ami nem sorrendtartó, így az útkeresést többször futtatva eltérő utakat kaphatunk. Ezt mutatják az eredményben a vagylagos sorok.


# TESZT
maze = Graph()

# A labirintus mezői közötti egymást követő járható kapcsolatok megadása.
maze_links = ['1-2-3-4-12-11-10-18', '1-9-17-18-19-27-26-25', '27-35-34-33-41-42-43-44-45-37-36-35',
              '42-50-49', '50-51-52-53', '52-60-59-58-57', '5-13-21-20-28-36-37-29-28', '21-22-14-6-7-8-16-24',
              '14-15-23-31-39-47-55', '31-32-40-48', '45-46-38-30-31', '55-56', '55-54-62-61', '62-63-64']

# Segédfüggvény a csúcsok közötti élek létrehozásához.
def add_edges(graph, links_str: str):
    links = links_str.split('-')
    for i in range(len(links)):
        if i < len(links) - 1:
            graph.add_connection(links[i], links[i + 1])
            graph.add_connection(links[i + 1], links[i])

# A gráf éleinek létrehozása.
for maze_link in maze_links:
    add_edges(maze, maze_link)

print('A labirintus gráf teljes mélységi bejárása.')
print(*[vertex.label if i % 18 != 0 else vertex.label + '\n'
        for i, vertex in enumerate(maze('1', 'depth_first'), 1)], sep=chr(0x279E))

# Eredmény:
# A labirintus gráf teljes mélységi bejárása.
# 1➞2➞3➞4➞12➞11➞10➞18➞17➞9➞19➞27➞35➞36➞37➞29➞28➞20
# ➞21➞22➞14➞15➞23➞31➞32➞40➞48➞30➞38➞46➞45➞44➞43➞42➞41➞33
# ➞34➞50➞49➞51➞52➞60➞59➞58➞57➞53➞39➞47➞55➞56➞54➞62➞61➞63
# ➞64➞6➞7➞8➞16➞24➞13➞5➞26➞25

kezdet, vég = '4', '57'
print('Az {}. mezőtől a {}. mezőig eljutás egy lehetséges útvonala:'.format(kezdet, vég))
print(*[v if i % 18 != 0 else v + '\n' for i, v in enumerate(maze.depth_first_recursive(kezdet, vég), 1)],
      sep=chr(0x279E))

# Eredmény:
# Az 4. mezőtől a 57. mezőig eljutás egy lehetséges útvonala:
# 4➞12➞11➞10➞18➞19➞27➞35➞34➞33➞41➞42➞50➞51➞52➞60➞59➞58➞57
# vagy
# 4➞12➞11➞10➞18➞19➞27➞35➞36➞37➞29➞28➞20➞21➞22➞14➞15➞23
# ➞31➞30➞38➞46➞45➞44➞43➞42➞50➞51➞52➞60➞59➞58➞57
# vagy
# 4➞3➞2➞1➞9➞17➞18➞19➞27➞35➞36➞37➞45➞44➞43➞42➞50➞51
# ➞52➞60➞59➞58➞57

# TESZT

maze = Graph()

# A labirintus mezői közötti egymást követő járható kapcsolatok megadása.

maze_links = ['1-2-3-4-12-11-10-18', '1-9-17-18-19-27-26-25', '27-35-34-33-41-42-43-44-45-37-36-35',

'42-50-49', '50-51-52-53', '52-60-59-58-57', '5-13-21-20-28-36-37-29-28', '21-22-14-6-7-8-16-24',

'14-15-23-31-39-47-55', '31-32-40-48', '45-46-38-30-31', '55-56', '55-54-62-61', '62-63-64']

# Segédfüggvény a csúcsok közötti élek létrehozásához.

def add_edges(graph, links_str: str):

links = links_str.split('-')

for i in range(len(links)):

if i < len(links) - 1:

graph.add_connection(links[i], links[i + 1])

graph.add_connection(links[i + 1], links[i])

# A gráf éleinek létrehozása.

for maze_link in maze_links:

add_edges(maze, maze_link)

print('A labirintus gráf teljes mélységi bejárása.')

print(*[vertex.label if i % 18 != 0 else vertex.label + '\n'

for i, vertex in enumerate(maze('1', 'depth_first'), 1)], sep=chr(0x279E))

# Eredmény:

# A labirintus gráf teljes mélységi bejárása.

# 1➞2➞3➞4➞12➞11➞10➞18➞17➞9➞19➞27➞35➞36➞37➞29➞28➞20

# ➞21➞22➞14➞15➞23➞31➞32➞40➞48➞30➞38➞46➞45➞44➞43➞42➞41➞33

# ➞34➞50➞49➞51➞52➞60➞59➞58➞57➞53➞39➞47➞55➞56➞54➞62➞61➞63

# ➞64➞6➞7➞8➞16➞24➞13➞5➞26➞25

kezdet, vég = '4', '57'

print('Az {}. mezőtől a {}. mezőig eljutás egy lehetséges útvonala:'.format(kezdet, vég))

print(*[v if i % 18 != 0 else v + '\n' for i, v in enumerate(maze.depth_first_recursive(kezdet, vég), 1)],

sep=chr(0x279E))

# Eredmény:

# Az 4. mezőtől a 57. mezőig eljutás egy lehetséges útvonala:

# 4➞12➞11➞10➞18➞19➞27➞35➞34➞33➞41➞42➞50➞51➞52➞60➞59➞58➞57

# vagy

# 4➞12➞11➞10➞18➞19➞27➞35➞36➞37➞29➞28➞20➞21➞22➞14➞15➞23

# ➞31➞30➞38➞46➞45➞44➞43➞42➞50➞51➞52➞60➞59➞58➞57

# vagy

# 4➞3➞2➞1➞9➞17➞18➞19➞27➞35➞36➞37➞45➞44➞43➞42➞50➞51

# ➞52➞60➞59➞58➞57

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, a „Különleges függvénydefiníciók” fejezetben az „Amikor a kígyó a farkába harap – függvényrekurzió” és „Álom az álomban – egymásba ágyazott függvények” alfejezetek.

Gráfok mélységi bejárása

Érdekel a Python tudásépítés lépésről lépésre az alapoktól az első asztali alkalmazásig című e-könyv.