Grafikonok Java-ban

1. Áttekintés

Ebben az oktatóanyagban meg fogjuk érteni a grafikon alapfogalmait mint adatstruktúrát.

Megvizsgáljuk a Java-ban való megvalósítását, a grafikonon lehetséges különféle műveletekkel együtt. Megbeszéljük a gráf implementációkat kínáló Java könyvtárakat is.

2. Grafikon adatszerkezete

A grafikon a adatstruktúra összekapcsolt adatok tárolásához mint az emberek hálózata a közösségi média platformján.

A grafikon csúcsokból és élekből áll. Egy csúcs képviseli az entitást (például emberek) és egy él képviseli az entitások közötti kapcsolatot (például egy személy barátságai).

Készítsünk egy egyszerű grafikont, hogy ezt jobban megértsük:

Itt meghatároztunk egy egyszerű gráfot, amely öt csúccsal és hat éllel rendelkezik. A körök az embereket ábrázoló csúcsok, a két csúcsot összekötő vonalak pedig a barátokat ábrázoló élek egy online portálon.

Ennek az egyszerű grafikonnak van néhány változata az élek tulajdonságaitól függően. Nézzük át röviden őket a következő szakaszokban.

Azonban csak az itt bemutatott egyszerű grafikonra összpontosítunk az ebben az oktatóanyagban szereplő Java példákhoz.

2.1. Irányított grafikon

Az eddig definiált grafikonnak élei vannak irány nélkül. Ha ezek az élek irányt mutatnak bennük, a kapott gráfot irányított gráfnak nevezzük.

Erre példa lehet annak képviselete, hogy kik küldik a baráti kérelmet barátságban az online portálon:

Itt láthatjuk, hogy az élek fix irányúak. Az élek kétirányúak is lehetnek.

2.2. Súlyozott grafikon

Ismételten elmondhatjuk, hogy egyszerű grafikonunknak vannak elfogulatlan vagy súlyozatlan élei. Ha ezek helyett az élek viszonylagos súlyt hordoznak, ezt a gráfot súlyozott gráfnak nevezzük.

Ennek gyakorlati alkalmazására példa lehet annak bemutatása, hogy az online portálon mennyire régi a barátság:

Itt láthatjuk, hogy az élek súlyokkal vannak társítva. Ez relatív jelentést ad ezeknek az éleknek.

3. Grafikonábrázolások

A grafikonok különböző formában ábrázolhatók, például szomszédsági mátrix és szomszédsági lista. Mindegyiknek különböző elrendezésben vannak előnyei és hátrányai.

Ezeket a grafikonábrázolásokat ebben a szakaszban mutatjuk be.

3.1. Adjacency Matrix

Egy szomszédsági mátrix az négyzetmátrix, amelynek méretei megegyeznek a csúcsok számával a grafikonon.

A mátrix elemeinek értéke általában „0” vagy „1”. Az „1” érték a sorban és az oszlopban lévő csúcsok közötti szomszédságot jelöli, különben pedig a „0” értéket.

Lássuk, hogyan néz ki a szomszédsági mátrix az előző szakasz egyszerű grafikonja számára:

Ez az ábrázolás igazságos könnyebben megvalósítható és hatékony a lekérdezés is. Azonban az kevésbé hatékony a foglalt hely tekintetében.

3.2. Adjacency List

A szomszédsági lista nem más, mint listák tömbje. A tömb mérete megegyezik a grafikon csúcsainak számával.

A tömb egy adott indexén található lista a csúcs szomszédos csúcsait ábrázolja, amelyet a tömb index képvisel.

Lássuk, hogyan néz ki a szomszédsági lista az előző szakasz egyszerű grafikonja számára:

Ez az ábrázolás az viszonylag nehéz létrehozni és kevésbé hatékony lekérdezni. Azonban kínál jobb helyhatékonyság.

A szomszédsági listát használjuk a grafikon ábrázolásához ebben az oktatóanyagban.

4. Grafikonok Java-ban

A Java nem rendelkezik alapértelmezett megvalósítással a grafikon adatszerkezetén.

A grafikont azonban Java-gyűjtemények segítségével valósíthatjuk meg.

Kezdjük egy csúcs definiálásával:

class Vertex {String label; Csúcs (String label) {this.label = label; } // egyenlő és hashCode}

A csúcs fenti definíciója csak tartalmaz egy címkét, de ez képviselhet minden lehetséges entitást, például Személy vagy Város.

Ezt is vegye figyelembe felül kell írnunk a egyenlő () és hash kód() módszerek, mivel ezek szükségesek a Java gyűjteményekkel való együttműködéshez.

Amint azt korábban megbeszéltük, a grafikon nem más, mint csúcsok és élek gyűjteménye, amelyek akár szomszédsági mátrixként, akár szomszédsági listaként ábrázolhatók.

Nézzük meg, hogyan definiálhatjuk ezt egy szomszédsági lista segítségével itt:

osztály Grafikon {privát térkép adjVertices; // szabványos kivitelező, mérőeszközök, beállítók}

Mint itt láthatjuk, az osztály Grafikon használ Térkép a Java gyűjteményekből a szomszédsági lista meghatározásához.

A grafikon adatstruktúráján számos művelet lehetséges, például létrehozása, frissítése vagy keresése a grafikonon keresztül.

Végigcsinálunk néhány gyakoribb műveletet, és megnézzük, hogyan tudjuk ezeket megvalósítani a Java-ban.

5. Grafikon mutációs műveletek

Először is meghatározunk néhány módszert a grafikon adatszerkezetének megváltoztatására.

Határozzunk meg módszereket a csúcsok hozzáadásához és eltávolításához:

void addVertex (String címke) {adjVertices.putIfAbsent (új csúcs (címke), új ArrayList ()); } void removeVertex (String label) {Vertex v = new Vertex (label); adjVertices.values ​​(). stream (). forEach (e -> e.remove (v)); adjVertices.remove (új Vertex (címke)); }

Ezek a módszerek egyszerűen hozzáadják és eltávolítják az elemeket a csúcsok beállítása.

Most adjunk meg egy módszert egy él hozzáadásához:

void addEdge (String label1, String label2) {Vertex v1 = új Vertex (label1); Vertex v2 = új Vertex (label2); adjVertices.get (v1) .add (v2); adjVertices.get (v2) .add (v1); }

Ez a módszer újat hoz létre Él és frissíti a szomszédos csúcsokat Térkép.

Hasonló módon definiáljuk a removeEdge () módszer:

void removeEdge (String label1, String label2) {Vertex v1 = új Vertex (label1); Vertex v2 = új Vertex (label2); EV1 = adjVertices.get (v1) lista; EV2 = adjVertices.get (v2) lista; if (eV1! = null) eV1.remove (v2); if (eV2! = null) eV2.remove (v1); }

Ezután nézzük meg, hogyan hozhatjuk létre a korábban rajzolt egyszerű grafikont az eddig definiált módszerekkel:

Grafikon createGraph () {Grafikon grafikon = új Grafikon (); graph.addVertex ("Bob"); graph.addVertex ("Alice"); graph.addVertex ("Mark"); graph.addVertex ("Rob"); graph.addVertex ("Maria"); graph.addEdge ("Bob", "Alice"); graph.addEdge ("Bob", "Rob"); graph.addEdge ("Alice", "Mark"); graph.addEdge ("Rob", "Mark"); graph.addEdge ("Alice", "Maria"); graph.addEdge ("Rob", "Maria"); visszatérő grafikon; }

Végül meghatározunk egy módszert egy adott csúcs szomszédos csúcsainak megszerzésére:

List getAdjVertices (String label) {return adjVertices.get (new Vertex (label)); }

6. Grafikon bejárása

Most, hogy rendelkezünk a grafikon adatszerkezetével és függvényeivel annak létrehozásához és frissítéséhez, definiálhatunk néhány további függvényt a grafikon áthaladásához. Át kell haladnunk egy grafikonon bármilyen értelmes művelet végrehajtásához, például a grafikonon belüli kereséshez.

Vannak a gráf áthaladásának két lehetséges módja, a mélység-első és a szélesség-első bejárás.

6.1. Mélység-első bejárás

A mélység-első áthaladás egy tetszőleges gyökércsúcsból indul a csúcsokat a lehető legmélyebben kutatja az egyes elágazások mentén, mielőtt az azonos szintű csúcsokat vizsgálná.

Határozzunk meg egy módszert a legmélyebb átjárás végrehajtására:

Set depthFirstTraversal (Grafikondiagram, Karakterlánc-gyökér) {Meglátogatott készlet = új LinkedHashSet (); Verem verem = új Verem (); verem.push (gyökér); while (! stack.isEmpty ()) {String vertex = stack.pop (); ha (! meglátogatott.tartalmaz (csúcs)) {meglátogatott.add (csúcs); for (Vertex v: graph.getAdjVertices (vertex)) {stack.push (v.label); }}} visszatérő látogatás; }

Itt, használunk egy Kazal az áthaladandó csúcsok tárolására.

Futtassuk ezt az előző alfejezetben létrehozott grafikonon:

assertEquals ("[Bob, Rob, Maria, Alice, Mark]", depthFirstTraversal (grafikon, "Bob"). toString ());

Felhívjuk figyelmét, hogy itt a „Bob” csúcsot használjuk gyökérként az átjáráshoz, de ez bármely más csúcs lehet.

6.2. Szélesség-első bejárás

Összehasonlításképpen, a szélesség első bejárása egy tetszőleges gyökércsúcsból indul és az összes szomszédos csúcsot azonos szinten tárja fel, mielőtt mélyebbre megy a grafikonon.

Most határozzunk meg egy módszert a legelső átjárás végrehajtására:

Állítsa be a breadthFirstTraversal (Grafikondiagram, Karakterlánc gyökér) {Készlet meglátogatása = új LinkedHashSet (); Várólista = új LinkedList (); queue.add (root); látogatott.add (gyökér); while (! queue.isEmpty ()) {String csúcs = queue.poll (); mert (Vertex v: graph.getAdjVertices (csúcs)) {if (! látogatott.tartalmaz (v.label)) {látogatott.add (v.label); queue.add (v.label); }}} visszatérő látogatás; }

Ne feledje, hogy a szélesség első bejárása felhasználja Sor a bejárandó csúcsok tárolására.

Futtassuk újra ezt az áthaladást ugyanazon a grafikonon:

assertEquals ("[Bob, Alice, Rob, Mark, Maria]", widthFirstTraversal (grafikon, "Bob"). toString ());

Ismételten a gyökércsúcs, amely itt „Bob” lehet, bármely más csúcs is lehet.

7. Java könyvtárak grafikonokhoz

Nem szükséges a grafikont mindig a nulláról megvalósítani a Java-ban. Számos nyílt forráskódú és érett könyvtár áll rendelkezésre, amelyek grafikonok megvalósítását kínálják.

A következő néhány alfejezetben áttekintjük ezeket a könyvtárakat.

7.1. JGraphT

A JGraphT a Java egyik legnépszerűbb könyvtára a grafikon adatszerkezete szempontjából. Ez lehetővé teszi többek között egy egyszerű grafikon, irányított gráf, súlyozott gráf létrehozását.

Ezenkívül számos lehetséges algoritmust kínál a gráf adatszerkezetén. Egyik korábbi oktatóanyagunk sokkal részletesebben foglalkozik a JGraphT-vel.

7.2. Google Guava

A Google Guava egy sor Java könyvtár, amely számos funkciót kínál, beleértve a grafikon adatszerkezetét és algoritmusait.

Támogatja az egyszerű létrehozást Grafikon, ValueGraph, és Hálózat. Ezeket úgy definiálhatjuk Változékony vagy Változhatatlan.

7.3. Apache Commons

Az Apache Commons egy Apache projekt, amely újrafelhasználható Java-összetevőket kínál. Ide tartozik a Commons Graph, amely eszköztárat kínál a grafikon adatstruktúrájának létrehozására és kezelésére. Ez általános grafikonalgoritmusokat is biztosít az adatszerkezet működéséhez.

7.4. Sourceforge JUNG

A Java Universal Network / Graph (JUNG) egy Java keretrendszer, amely kiterjeszthető nyelvet biztosít bármilyen grafikonként ábrázolható adat modellezéséhez, elemzéséhez és megjelenítéséhez.

A JUNG számos algoritmust támogat, amelyek olyan rutinokat tartalmaznak, mint a fürtözés, a bontás és az optimalizálás.

Ezek a könyvtárak számos megvalósítást biztosítanak a grafikon adatszerkezete alapján. Vannak még erősebb keretek grafikonok alapján, például az Apache Giraph, amelyet jelenleg a Facebookon használnak a felhasználók által alkotott grafikon elemzésére, és az Apache TinkerPop, amelyet általában a grafikon adatbázisok felett használnak.

8. Következtetés

Ebben a cikkben a grafikont mint adatstruktúrát és annak ábrázolásait vitattuk meg. Meghatároztunk egy nagyon egyszerű gráfot a Java-ban a Java Gyűjtemények felhasználásával, és meghatároztuk a grafikon közös bejárásait is.

Röviden beszéltünk a Java-ban elérhető különféle könyvtárakról is a Java platformon kívül, amelyek grafikonok megvalósítását biztosítják.

Mint mindig, a példák kódja elérhető a GitHub oldalon.