A mátrixok egy speciális fajtája az, ahol a mátrixelemek csak 0 vagy 1 értéket vehetnek fel. Az ilyen mátrixoknak több elnevezése ismert: bináris mátrix, logikai mátrix, relációs mátrix, vagy (0,1) mátrix.
A bináris mátrixoknak számos alkalmazási területe van, többek között például: gráfok szomszédsági mátrixa, relációk jellemzése, kétszínű képek (pl. xbm típusú képfájlok) leírása, valamint olyan játékoknál, ahol a játékmező táblázatos, és az érdemi információt az jelenti, hogy egy adott cellában van-e valami vagy nincs (pl.: aknakereső, torpedó játék).
Mivel a bináris mátrix elemei csak két értéket vehetnek fel, ezért a mátrixot le lehet írni egy listával is, ha a sor- és oszlopindexeket megfeleltetjük a listaindexeknek. Ez azért jó, mert a listát és összes elemét nem kell tárolni, hiszen elegendő a csak a listaindexeket. Mivel a listaindexek egyediek, ezért azok tárolására egy halmaz megfelelő. Ha a bináris mátrix ritka mátrix, vagyis jóval több a 0, mint az 1 értékű elem, akkor ezzel a módszerrel a mátrix a memóriaigény szempontjából hatékony tárolható. Mindezt szemléletesen mutatja a következő ábra:
A bináris mátrix e reprezentációját alkalmazva a megvalósító osztály definíciója alább látható. Az egyes metódusok logikája nem túl bonyolult, a megértést a kommentek segítik.
|
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 |
from __future__ import annotations from itertools import product, starmap from random import randint from operator import and_ from typing import Iterable class BinaryMatrix: def __init__(self, rowcount, columncount): self.rowcount, self.columncount = rowcount, columncount self._indexes_of_set_elements = set() # Az 1 értékek indexei def __str__(self): return ''.join([str(self.get(*self._row_and_column_index(i))) + ('\n' if (i + 1) % self.columncount == 0 else ' ') for i in range(len(self))]) def __len__(self): """A mátrix elemszámát adja vissza.""" return self.columncount * self.rowcount def _check_indexes(self, row_index: int, column_index: int): """A sor- és oszlopindexek helyességét ellenőrző segédmetódus.""" if not isinstance(row_index, int): raise TypeError('A sorindex nem egész szám.') if not isinstance(column_index, int): raise TypeError('Az oszlopindex nem egész szám.') if row_index not in range(self.rowcount): raise IndexError(f'A sorindex a 0..{self.rowcount - 1} tartományon kívül esik.') if column_index not in range(self.columncount): raise IndexError(f'Az oszlopindex a 0..{self.columncount - 1} tartományon kívül esik.') def __getitem__(self, index): """Lehetővé teszi, hogy a mátrix sor- és oszlopindexszel meghatározott elemét a mátrix[sorindex][oszlopindex] szintaxisú indexelésével megkapjuk.""" if self.rowcount > 1: row_binmx = type(self)(1, self.columncount) for ci, element in enumerate(self.row_elements(index)): if element: row_binmx.set(0, ci) return row_binmx return self.get(0, index) def _sequence_index(self, row_index: int, column_index: int): """A megadott sor- és oszlopindex alapján az ekvivalens virtuális lista megfelelő indexével tér vissza.""" if row_index not in range(self.rowcount) or column_index not in range(self.columncount): raise IndexError return column_index + self.columncount * row_index def _row_and_column_index(self, index: int): """A megadott ekvivalens virtuális lista indexe alapján a mátrix megfelelő sor- és oszlopindexével tér vissza.""" if index not in range(self.rowcount * self.columncount): raise IndexError return divmod(index, self.columncount) def set(self, row_index, column_index): """A megadott sor- és oszlopindex szerinti mátrixelemet 1 értékre állítja.""" self._check_indexes(row_index, column_index) self._indexes_of_set_elements.add(self._sequence_index(row_index, column_index)) def set_elements(self, *row_col_indexpairs): for ri, ci in row_col_indexpairs: self.set(ri, ci) def clear(self, row_index, column_index): """A megadott sor- és oszlopindex szerinti mátrixelemet 0 értékre állítja.""" self._check_indexes(row_index, column_index) self._indexes_of_set_elements.discard(self._sequence_index(row_index, column_index)) def swap(self, row_index, column_index): """A megadott sor- és oszlopindex szerinti mátrixelemet az aktuális érték ellentetjére állítja. Vagyis, ha eddig 0 volt, akkor az 1 lesz és fordítva. """ self._check_indexes(row_index, column_index) self.clear(row_index, column_index) if self.get(row_index, column_index) else self.set(row_index, column_index) def clear_all(self): """Minden mátrixelemet 0 értékre állít.""" self._indexes_of_set_elements.clear() def swap_all(self): """Minden mátrixelemet az aktuális érték ellentetjére állítja. Vagyis, ahol eddig 0 volt, ott az érték 1 lesz és fordítva.""" for row_index, column_index in product(range(self.rowcount), range(self.columncount)): self.swap(row_index, column_index) def get(self, row_index, column_index): """A megadott sor- és oszlopindex szerinti mátrixelemmel tér vissza.""" self._check_indexes(row_index, column_index) return 1 if self._sequence_index(row_index, column_index) in self._indexes_of_set_elements else 0 def row_elements(self, row_index): """Egy olyan generátorobjektummal tér vissza, amely a megadott sorindex szerinti sor elemeit szolgáltatja.""" self._check_indexes(row_index, 0) return (self.get(row_index, column_index) for column_index in range(self.columncount)) def column_elements(self, column_index): """Egy olyan generátorobjektummal tér vissza, amely a megadott oszlopindex szerinti oszlop elemeit szolgáltatja.""" self._check_indexes(0, column_index) return (self.get(row_index, column_index) for row_index in range(self.rowcount)) def clone(self): """Egy független másolatot ad vissza.""" clone_bin_mx = type(self)(self.rowcount, self.columncount) clone_bin_mx._indexes_of_set_elements = set(self._indexes_of_set_elements) return clone_bin_mx def complement(self): """A komplementer mátrixot adja vissza. A komplementer mátrixban minden elem a self azonos pozíciójában levő elemének ellentéte. """ bin_mx = self.clone() bin_mx.swap_all() return bin_mx def populate_randomly(self, num_of_set_elements: int): """A mátrixot az argumentumban megadott számú 1 értékű elemmel véletlenszerűen tölti fel. A korábbi értékek, ha voltak, elvesznek.""" self._indexes_of_set_elements.clear() while len(self._indexes_of_set_elements) != num_of_set_elements: self._indexes_of_set_elements.add(randint(0, len(self) - 1)) def __matmul__(self, binary_matrix: BinaryMatrix): """A @ operátor bal oldalán levő mátrix és a jobb oldalán levő másik bináris mátrix szorzatmátrixát adja vissza.""" if self.columncount != binary_matrix.rowcount: raise ValueError('A mátrixok dimenziói nem megfelelők a szorzáshoz.') product_mx = type(self)(self.rowcount, binary_matrix.columncount) for _ri, _ci in product(range(self.rowcount), range(binary_matrix.columncount)): e = max(starmap(and_, zip(self.row_elements(_ri), binary_matrix.column_elements(_ci)))) if e: product_mx.set(_ri, _ci) return product_mx def __add__(self, binary_matrix: BinaryMatrix): """A + operátor bal és jobb oldalán levő mátrixok összegmátrixát adja vissza.""" if self.columncount != binary_matrix.columncount or self.rowcount != binary_matrix.rowcount: raise ValueError('A mátrixok dimenziói eltérnek, ezért nem lehet összeadni azokat.') sum_mx = self.clone() sum_mx.clear_all() for _ri, _ci in product(range(self.rowcount), range(self.columncount)): if self.get(_ri, _ci) | binary_matrix.get(_ri, _ci): sum_mx.set(_ri, _ci) return sum_mx |
Alkalmazási példaként használjuk e BinaryMatrix osztályt egyszerű, súlyozatlan, irányított vagy írányítatlan gráfok szomszédsági mátrixának előállítására. Ehhez definiálunk egy AdjacencyMatrix nevű osztályt, amely a BinaryMatrix osztályt örökli. A szomszédsági mátrix ugyanis bináris mátrix, de négyzetes mátrix, vagyis a AdjacencyMatrix konstruktora csak egyetlen mátrixdimenziót fogad.
|
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 |
class AdjacencyMatrix(BinaryMatrix): """Bináris szomszédsági mátrix, amely egy egyszerű, súlyozatlan, irányított és/vagy irányítatlan élekkel rendelkező gráf csúcsainak szomszéd csúcsait, vagyis adott csúcsból az élek mentén elérhető csúcsokat írja le. """ def __init__(self, row_and_column_count): super().__init__(row_and_column_count, row_and_column_count) def to_adjacency_dict(self, vertex_names: Iterable | None = None) -> dict: """A szomszédsági mátrix alapján meghatározza a gráf szomszédsági listáját, és ezt egy olyan szótárban adja vissza, amelynek kulcsai a gráf argumentumként megadott címkéi (csúcsok azonosítói), a kulcsokhoz tartozó értékek listák, amelyek elemei az adott csúcsból az élek mentén elérhető csúcsok azonosítói. Ha nincs argumentum megadva vagy az None, akkor a kulcsok, illetve a listák elemei a mátrix sorindexei lesznek. """ if vertex_names is None: vertex_names = range(self.rowcount) vnames = tuple(vertex_names) if self.columncount != len(vnames): raise ValueError('A csúcsazonosítók száma nem egyezik a mátrix dimenziójával.') adj_dict = {} for vname in vnames: i = vnames.index(vname) # Az adott csúcscímkéhez tartozó sorindex. # A sorindex alapján kiválasztjuk a mátrix megfelelő sorát, és annak 1 értékű elemeihez tartozó # címkéket az éppen aktuális csúcsazonosítóhoz rendelt lista eleiként felvesszük. adj_dict.setdefault(vname, []).extend((vnames[k] for k, e in enumerate(self.row_elements(i)) if e)) return adj_dict |
A szomszédsági mátrix ismeretében elő lehet állítani a szomszédsági listát, pontosabban annak szótárral való megvalósítását. Ezt külön függvényben is meg lehet tenni, vagy az AdjacencyMatrix egy metódusaként is, ahogy azt az előbb osztálydefinícióban tettük, hiszen ekkor a szomszédsági mátrix példány mint első argumentum (self) eleve rendelkezésre áll.
Mivel a szomszédsági mátrix és a szomszédsági szótár között egyértelmű a megfeleltetés, azaz egyikből a másik származtatható, valósítsuk meg a fordított konverziót is. Ehhez az adjacency_dict_to_matrix() nevű függvényt definiáltuk, ami tehát egy szomszédsági szótár alapján előállítja a szomszédsági mátrixot.
|
1 2 3 4 5 6 7 8 9 10 11 |
def adjacency_dict_to_matrix(adj_dict: dict): dim = len(adj_dict) labels = tuple(adj_dict.keys()) adj_mx = AdjacencyMatrix(dim) for row_index, item in enumerate(adj_dict.items()): label, neighbors = item for vertex in neighbors: adj_mx.set(row_index, labels.index(vertex)) return adj_mx |
Teszteljük le az eddigi alkotásainkat! A teszteredmények helyes működést igazolnak vissza:
|
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 |
if __name__ == '__main__': adjmx1 = AdjacencyMatrix(5) adjmx1.set_elements((0, 1), (0, 2), (1, 0), (2, 0), (2, 3), (2, 4), (3, 2), (4, 2)) print(adjmx1) print(adjmx1.to_adjacency_dict('ABCDE')) # Eredmény: # 0 1 1 0 0 # 1 0 0 0 0 # 1 0 0 1 1 # 0 0 1 0 0 # 0 0 1 0 0 # {'A': ['B', 'C'], 'B': ['A'], 'C': ['A', 'D', 'E'], 'D': ['C'], 'E': ['C']} adjmx2 = AdjacencyMatrix(6) adjmx2.set_elements((0, 1), (0, 2), (0, 5), (1, 0), (1, 2), (2, 0), (2, 3), (2, 4), (4, 2), (5, 4)) print(adjmx2) print(adjmx2.to_adjacency_dict('ABCDEF')) # Eredmény: # 0 1 1 0 0 1 # 1 0 1 0 0 0 # 1 0 0 1 1 0 # 0 0 0 0 0 0 # 0 0 1 0 0 0 # 0 0 0 0 1 0 # {'A': ['B', 'C', 'F'], 'B': ['A', 'C'], 'C': ['A', 'D', 'E'], 'D': [], 'E': ['C'], 'F': ['E']} print(adjacency_dict_to_matrix(adjmx2.to_adjacency_dict('ABCDEF'))) # Eredmény: # 0 1 1 0 0 1 # 1 0 1 0 0 0 # 1 0 0 1 1 0 # 0 0 0 0 0 0 # 0 0 1 0 0 0 # 0 0 0 0 1 0 print(adjacency_dict_to_matrix({'A': ['B', 'C'], 'B': ['A'], 'C': ['A', 'D', 'E'], 'D': ['C'], 'E': ['C']})) # Eredmény: # 0 1 1 0 0 # 1 0 0 0 0 # 1 0 0 1 1 # 0 0 1 0 0 # 0 0 1 0 0 |
A teszteseteket vizuálisan a következő ábra mutatja:
E feladatban nyelvi szempontból az osztályok létrehozása, öröklése és a speciális metódusok (mágikus metódusok) alkalmazása volt a fókuszban. Ezekkel részletesen a Python tudásépítés lépésről lépésre című e-könyv „Osztály vigyázz! – típuslétrehozás osztályokkal”, „Öröklődés”, és „Mágikus metódusok egyedi igényre szabott osztályokban” fejezetei foglalkoznak.