AuD 2020: dünnbesetzte Adjazenzmatrix & ADT

als letzte datenstruktur sehen wir uns einen spezialfall von adia zenz matrizen an und zwar können wir die lizenz matrizen gegebenenfalls mit hilfe von dünn besetzten matrizen implementieren auf englisch spaß matrices und lohnend ist das immer dann wenn unsere matrix nur relativ wenige einträge hat die tatsächlich um gleich null sind die datenstrukturen für dünn besetzte matrizen werden nur diese einträge gespeichert die nullen einfach implizit als nullen angenommen und nicht explizit gespeichert bedeutet das für die lizenz matrizen beziehungsweise die darstellung von graphen wenn ich für einen grafen davon ausgehen kann dass jeder knoten nur mit relativ wenigen knoten durch eine kante verbunden ist relativ wenig bedeutet insgesamt habe ich in knoten in jeder mit jedem verbunden das habe ich in quadrath kanten und jetzt gehe ich davon aus dass jeder knoten nur mit einer konstanten anzahl oder im schnitten mit einer konstanten anzahl von nachbar knoten verbunden ist so dass die anzahl kanten deutlich kleiner als ein quadrat ist also deutlich kleiner ist als die möglichen einträge in der adac matrix dann ist es sinnvoll so eine dünn besetzte matrix zu verwenden für dünn besetzte matrizen gibt's tatsächlich standard darstellungen verwendet werden die in aller regel in der den jahren all gebracht also ich möchte mit diesem matrizen tatsächlich rechnen wir können auch mit adia zenz matrizen rechnen dass soll uns an der stelle gar nicht so arg interessieren wenn ein kleines beispiel noch ansehen wir können diese daten strukturen aber auch einfach verwenden um grafen darzustellen sinnvoll kann dass insbesondere dann sein wenn ich mit einer programmiersprache arbeiten muss die sich nicht so wirklich eigene datenstrukturen zu implementieren matlab so ein typisches beispiel die mir aber gleichzeitig weil es eine sehr spezielle sprache ist um den jahre all gebracht vor allem zu machen die mir aber gleichzeitig eine dünn besetzte matrix fertig an die hand gibt in dem fall muss ich wenig machen um die graf datenstruktur zu implementieren ich kann einfach diese dünn besetzten matrizen verwenden in den code beispiele gebe ich euch eine implementierung für eine graf datenstruktur die diese idee von dünn besetzten matrizen aufgreift gleichzeitig ist die grenze zur lizenz listen allerdings zugegebenermaßen fließend wir wollen mit dieser datenstruktur nicht rechnen ich komme aus der gruppe visual computing wir machen computergrafik wissenschaftliche visualisierung wir rechnen auch viel insbesondere mit linearer all gebracht das heißt wir haben es tatsächlich oft mit matratzen auch mit dünn besetzten nach tritten zu tun und möchte euch ein beispiel zeigen in dem fall erst mal von einem grafen wie er in der computergrafik typischerweise vorkommt haben geometrisches objekt diese gar gold skulptur und solche geometrische objekte wenn üblicherweise mit polygon netzen beziehungsweise hier mit drei ex netzen dargestellt tatsächlich wenn wir uns dieses dreiecks netz vorstellen als einen grafen der aus 1 den knoten besteht wir sagen hier explizit wird es dazu und diese knoten sind durch bekannten miteinander verbunden so dass ich einzelne dreiecke geben ohne dass wenn es detail gehen man sieht hier dass es offensichtlich so ist das wenn ich mir einen bestimmten wörz ex anschauen der zwar viele nachbar wird dieses haben kann aber dass es im vergleich zur gesamtanzahl wird ist es relativ wenige sind tatsächlich können wir zeigen dass wir ein geschlossenes netz oder wenn man allgemein von drei ex netz im schnitt mit sechs nachbarn protex rechnen können das heißt wir haben tatsächlich zumindest im mittel eine konstante anzahl von nachbarn das wiederum heißt das wenn ich mir jetzt in der adia zenz liste eine zeile anschau tatsächlich nur von all diesen einträgen sechs stück gesetzt sind all diese einträge bedeutet für dieses modell das wir hier sehen dass wir 10. 000 wird dieses haben das heißt wenn man tatsächlich exakt 10. 000 annehmen und von null durchnummerieren dann haben wir hier ein der länge 10.

000 in dem aber nur insgesamt ein paar wenige 1 1 stehen für dieses beispiel hier eins zwei drei vier fünf sechs sieben nachbarn und wenn alle zeilen in dieser matrix so aussehen dann ist klar das ist eine dünn besetzte matrix weil die meisten einträge in dieser matrix 0 sind und diese nullen speichere ich nicht explizit sondern die denken wir uns einfach wenn man sich die a-lizenz patricks diesem modell anschaut dann könnte die zum beispiel so aussehen hier darf man sich nicht täuschen lassen wir gehen hier tatsächlich von 0 nach 10. 000 jetzt schon achse leider anders herum als ich es gerne gehabt hätte aber spielt keine rolle also von null bis 10. 000 nach unten also die matrix steht kopf sondern sie nicht stören wir haben also eine 10.

000 kreuz 10. 000 matrix wir haben also insgesamt 100 millionen mögliche einträge hinter matrix und gleichzeitig haben wir hier tatsächlich kommt relativ genau hin probe tags im mittel 6 nachbarn also kümmern insgesamt mit 6 x 10. 000 nicht nullen einträgen rechnen die kürzliche hat mit in entschuldigung in nz number of museums als wir haben insgesamt nur 60.

000 einträge die uhr gleich null sind von 100 millionen möglichen anträgen das ist das ist nicht ganz leicht das zu glauben wenn man dieses bild sieht aber müssen immer uns vor augen halten dass wir gehen hier von null bis 10. 000 das ist weit jenseits der bildschirmauflösung das heißt jeder punkt den wir hier gezeichnet 10 selbst wenn es nur ein einzelner pixel wäre und die punkte nicht größer werden deckt einfach auf dem bildschirm hier auf der visualisierung viel zu viel ab ich kann die wird ist es die knoten einfach umsortieren oder von mir aus auch um nennen das heißt die vertauschte in dieser matrix zeilen und spalten wie ich das mach' nach welche regel spielte gar keine rolle aber wenn man das auf die eine oder andere geschickte art und weise macht dann sieht diese agents matrix plötzlich so aus man kann jetzt immer noch nicht gut rein schauen weil die punkte natürlich immer noch zu groß sind aber man sieht jetzt ganz deutlich okay es gibt hier offensichtlich ganz große bereiche wo wir null einträge haben und es gibt verhältnismäßig wenige einträge die tatsächlich ungleich 0 wenn man mich dünn besetzten matrizen rechnen möchte mit matlab arbeitet dann muss man sich keine gedanken über die implementierung machen dünn besetzt die matratzen sind einfach da als sagen struktur wenn man damit rechnet dann wird intern eine datenstruktur verwendet die ist sehr einfach sehr ähnlich der knoten liste die nur mit zwei race implementieren wie wir sie schon gesprochen kann wenn man eine lizenz liste verwenden wollen um den grafen darzustellen und den anspruch haben dass wir ja alle kooperationen auch inhaltlich vernünftiger zeit ausführen können und dazu gehört auch das einfügen oder löschen von neuen kanten oder auch neuen goethes dann sollte man das vielleicht ein kleines bisschen anders machen und eine mögliche implementierung ist diese ich betrachte hier kannten als paare und jedes paar die j gibt mir einen index in dieser matrix an der zeile spalte j die eine möglichkeit ist ich realisiert diese matrix als eine abbildung von diesem paar auf entweder die null oder die einst kannte existiert nicht oder kannte existiert wobei wir die null einträge natürlich nicht explizit speichern müssen sprich ich verwende zb ein hash tabelle in dieser hash tabelle zügig haare ein ich brauche also eine hash funktion auf pan und für jedes paar das mir die koordinate von einem eintrag in der matrix beschreibt der ungleich 0 für die allianz matrix der einst ist speichere ich einen eintrag in der hash tabelle das schöne an der sache ist ich kann meine knoten einfach durchnummerieren wenn ich einen knoten lösche da müssen wir wieder ein kleines bisschen aufpassen muss ich entsprechend alle paare finden dieser knoten vorkommt kann man gleich noch mal dazu wenn ich einen knoten einfüge füge ich einfach neues paar ein wenn ich dabei indizes überspringe ist das eigentlich völlig egal das heißt ich muss mir keine gedanken über die dimension dieser matrix machen die wächst einfach und wenn man es als matrix betrachten als effizienz matrix betrachten dann ist die dimension immer der größte knoten index kreuz dieser größte knoten index also ich kann meine knoten sozusagen endlos durchnummerieren ich muss einfach nur diese passion einfügen die zweite idee ist ich verwende auch wieder eine map eine abbildung aber ich möchte diese paare zusätzlich geordnet halten und ich ordne lexika grafisch als auch nachteile bei gleicher zeile nach spalte auf die art und weise habe ich in den zeilen stehen die ausgehenden kanten auf die art und weise habe ich bereiche mit gleichem zeilen index die für die ausgehenden kanten für einen knoten stehen das heißt ich kann einfach mit einem range literat ohr auf die zeilen oder spalten der matrix zugreifen kann die einträge in diesen zeilen oder spalten aufzählen ich habe gerade von zeilen gesprochen haben ich bin es gewohnt dass wir wenn man mit matrizen rechnenden jahre algebra machen das material matratzen spalten weise gespeichert werden so steht es auch hier auf der folie im prinzip ist es egal ich muss mir nur einmal überlegen ob ich zeilen oder spalten speichere ich muss mich für eins entscheiden und entsprechend einsortieren bedeutet wenn ich spalten kann kann ich noch nicht zeilen oder wenig falten effizient kann dann kann noch nicht effizient auf zeilen zu greifen naja wenn ich das auch will dann speicher ich zusätzlich noch die transportierte der matrix das heißt ich habe zwei abbildungen eine wo alle paare j drin stehen und eine wo alle paare j drinnen stehen das ist ein bisschen plump weil ich damit natürlich auch die anzahl meiner daten verdoppelt aber es funktioniert und speicher am ende regel genug oder noch anders wenn ich in dieser map die über den java basierten baum zum beispiel über den rot schwarz baum implementiert ist eine kante such als entscheiden möchte ob eine kante existiert oder nicht habe ich hier kosten von von locken ist die anzahl einträge im baum also die anzahl wird ist die tatsächlich im graphen gespeichert wird wenn ich das als hash mettmach wie oben dann habe ich kann ich mit konstanten kosten rechnen auch hier wenn ich vielleicht viele solche abfragen habe es hindert mich niemand einfach beides zu benutzen da muss ich nur beim einfügen und beim löschen jeweils auch in beide abbildungen einfügen beziehungsweise aus beiden abbildungen löschen kostet mich auch wieder speicher aber ich kann bestimmte abfragen dann schneller machen weil ich suche mir immer die datenstruktur auch diese datenstruktur aus so dass das was ich will am schnellsten geht oder im fall von den range literaturen ganze zeile ganze spalte auf zählen eben überhaupt möglich ist das geht mit der hashtag nicht auf die art und weise wie komme ich das sehr einfache datenstruktur für den grafen die dinge verwendet die wir schon kennen nach esch map und zb den rot-schwarz bauen und diese einfache datenstruktur ist auch leidlich effizient es kann auch nicht so arg viel schiefgehen wenn ich weiß dass meine hash web funktioniert und dass mein rot-schwarz baum funktioniert oder dass meine map datenstruktur funktioniert und benutzt die einfach konsequenz konsequenz statt neue datenstruktur zu implementieren dann kann ich auch relativ sicher sein dass ich wenig oder zumindest weniger chancen habe in meine neue graf datenstruktur noch irgendwelche fehler einzubauen also auch hier ist informatik das immer oft frauen wenn man eine sache gemacht haben dann verwendet man die auf spart uns zeit und hindert uns auch daran noch mal neue fehler einzubauen die varianten hier sind die erste das was ich gerade gesagt habe ich kann redundanz speichern also wenn nicht konkurrierende datenstrukturen habe die mir verschiedene eigenschaften bieten und ich möchte aber alles haben dann kann es eine möglichkeit seien einfach alle datenstrukturen simultan zu verwenden an irgendeiner stelle zahle ich natürlich den preis dafür hier beim einfügen und beim löschen dafür gebe ich die abfragen entsprechend schneller wenn ich mir das leisten kann vom speicher hier und auch den zusatzaufwand beim einfügen dann ist das eine valide und sehr einfache möglichkeit die klassische datenstruktur für dünn besetzte matrizen ist so genanntes compressed column storage oder com press trust oric format und das entspricht fast eins zu eins der knoten liste mit den zwei feldern für dünn besetzte matrizen kommt dann noch ein drittes feld dazu dass die werte speichert denn wir wollen nicht nur die absenz vertreten darstellen sondern beliebige matrizen oder verkaufen vielleicht gewichtete grafen das ist relativ einfach diese daten strukturen sind tatsächlich sehr sehr einfach es sind einfach nur airways und ich muss mit indizes arbeiten sowie was im letzten teil der vorlesung uns auch angeschaut der preis ging hier zahle ist ich kann hier recht effizient durch die einträge der matrix laufen ich kann effizient entweder spalten oder zeilen also entweder ganz oder ross aufzählen aber ich kann die matrix nicht einfach manipulieren also ich kann nicht mal eben mal schnell eine neue kannte einfügen das kostet mich tatsächlich ihnen beispielen findet ihr eine datenstruktur jason symmetrics die ist aufgebaut oder verwendet die spaß metrics die ich einen peg die ich in einem package graf metrics implementieren und das wiederum dient zur implementierung einer graf datenstruktur die nämliche graf und das a m steht für jason cm tricks und hier gehe ich eben davon aus dass wir grafen betrachten die nicht voll vernetzt sind also wo ich davon ausgehen kann dass jeder knoten nur mit relativ wenigen nachbar knoten verbunden ist und dann lohnt sich so eine dünn besetzte hat jahrzehnts matrix tatsächlich ist die implementierung wirklich nicht schwierig der schlüssel ist dass wir uns viel arbeit eben vorher schon gemacht haben weil man has tabelle balancierte bäume und so weiter haben bzw wenn man das nicht hätten weil wir die entsprechenden klassen aus dem cover collections verwenden würden jetzt schauen uns doch noch mal eine eigenschaft von magazins matrizen egal ob du oder dicht an wenn man von matrizen sprechen dann wollen wir mit diesen matrizen ja vielleicht doch rechnen bzw sie auf fassen als das was in der mathematik in der regel darstellen nämlich lineare operatoren wenn eine hat jahrzehnts matrix für einen graphen ist wobei diese lizenz matrix 01 einträge enthalten soll die matrix die dimensionen kreuz erkennen ist die anzahl knoten im graphen dann wollen wir jetzt potenzen von ah betrachten wobei man matrix potenzierung so definieren wie man es auch annehmen dass sie funktioniert also hoch 1 ist einfach die matrix a-ha hoch +1 für nk größer null ist einfach auch mal die matrix a bzw das ist dann nichts anderes als einfach a mal a und so weiter x h und das ganze plus 1mal wenn man solche potenzen bildern kann man sich natürlich fragen was bedeutet das denn jetzt ja dass ich mir so ein hoch ansehe dann kann man sich überlegen dass diese ein dass die einträge in der matrix hoch kann sich auch interpretieren lassen und zwar in dem fall als die anzahl verschiedener wege über kanten vom knoten ii zum knoten j wobei über kanten bedeutet hier über genau kannten ich weiß deshalb darauf hin weil wenn ak zeile spalte j und gleich null ist dann muss das nicht bedeuten dass auch die ursprüngliche matrix an der stelle j einen eintrag und gleich null hatte ein einfaches gegenbeispiel wir haben einen grafen mit zwei knoten wir sprechen immer von gerichteten grafen und wir haben zwei kranken eine vom einen zum anderen und eine wieder zurück die entsprechende lizenz patricks würde so aussehen hier 0 also ich komme dass der knoten 1 ist dass der knoten 2421 zeile 2 gegen die andere farbe dafür knoten 12 21 22 spalte 1 spalte 2 dann habe ich natürlich keine verbindung von der einst zu sich selber ich habe hier keine schleife aber von der eins zu zwei und ich habe die verbindung von der 221 aber eben nicht von der 22 wenn ich jetzt das produkt 01. 10.