streamalism.org

1. Áttekintés

Legtöbbször gráfalapú algoritmusok megvalósításakor néhány segédfunkciót is végre kell hajtanunk.

A JGraphT egy nyílt forráskódú Java osztálykönyvtár, amely nemcsak különféle típusú grafikonokat nyújt számunkra, hanem számos hasznos algoritmust is kínál a leggyakrabban előforduló grafikonproblémák megoldására.

Ebben a cikkben megtudjuk, hogyan hozhatunk létre különféle típusú grafikonokat, és mennyire kényelmes használni a megadott segédprogramokat.

2. Maven-függőség

Kezdjük azzal, hogy hozzáadjuk a Maven projekt függőségét:

 org.jgrapht jgrapht-core 1.0.1 

A legújabb verzió megtalálható a Maven Central oldalán.

3. Grafikonok készítése

A JGraphT különféle típusú grafikonokat támogat.

3.1. Egyszerű grafikonok

Kezdőként készítsünk egy egyszerű grafikont egy tipusú csúccsal Húr:

G grafikon = new SimpleGraph (DefaultEdge.class); g.addVertex („v1”); g.addVertex („v2”); g.addEdge (v1, v2);

3.2. Irányított / Irányítatlan grafikonok

Ez lehetővé teszi számunkra irányított / irányítatlan grafikonok létrehozását is.

Példánkban létrehozunk egy irányított gráfot, és felhasználjuk más segédfunkciók és algoritmusok bemutatására:

DirectedGraph directionGraph = új DefaultDirectedGraph (DefaultEdge.class); directionGraph.addVertex ("v1"); directionGraph.addVertex ("v2"); directionGraph.addVertex ("v3"); directionGraph.addEdge ("v1", "v2"); // Adja meg a fennmaradó csúcsokat és éleket

3.3. Teljes grafikonok

Hasonlóképpen létrehozhatunk egy teljes grafikont is:

public void createCompleteGraph () {completeGraph = new SimpleWeightedGraph (DefaultEdge.class); CompleteGraphGenerator completeGenerator = új CompleteGraphGenerator (méret); VertexFactory vFactory = new VertexFactory () {private int id = 0; public String createVertex () {return "v" + id ++; }}; completeGenerator.generateGraph (teljesGraph, vFactory, null); }

3.4. Több grafikon

Az egyszerű grafikonokon kívül az API többgráfokat is biztosít (két csúcs között több utat tartalmazó grafikonok).

Ezenkívül bármilyen gráfban lehetnek súlyozott / súlyozatlan vagy felhasználó által definiált élek.

Hozzunk létre egy multigráfot súlyozott élekkel:

public void createMultiGraphWithWeightedEdges () {multiGraph = new Multigraph (DefaultWeightedEdge.class); multiGraph.addVertex ("v1"); multiGraph.addVertex ("v2"); DefaultWeightedEdge edge1 = multiGraph.addEdge ("v1", "v2"); multiGraph.setEdgeWeight (1., 5. él); DefaultWeightedEdge edge2 = multiGraph.addEdge ("v1", "v2"); multiGraph.setEdgeWeight (2., 3. él); }

Ezen felül rendelkezhetünk módosíthatatlan (csak olvasható) és hallgatható (lehetővé teszi a külső hallgatók számára a módosítások nyomon követését) grafikonokkal, valamint algráfokkal. Ezen grafikonokból mindig elkészíthetjük az összes kompozíciót.

További API-részletek itt találhatók.

4. API algoritmusok

Most, hogy teljes értékű gráfobjektumokkal rendelkezünk, nézzünk meg néhány gyakori problémát és azok megoldásait.

4.1. Grafikon ismétlés

A grafikonon különböző iterátorok, például BreadthFirstIterator, DepthFirstIterator, ClosestFirstIterator, RandomWalkIterator a követelmény szerint.

Egyszerűen létre kell hoznunk a megfelelő iterátorok példányát gráfobjektumok átadásával:

DepthFirstIterator depthFirstIterator = új DepthFirstIterator (directionGraph); BreadthFirstIterator widththFirstIterator = új BreadthFirstIterator (directionGraph);

Miután megkaptuk az iterátorobjektumokat, az iterációt a segítségével tudjuk végrehajtani hasNext () és következő() mód.

4.2. A legrövidebb út megtalálása

Különféle algoritmusok, például Dijkstra, Bellman-Ford, Astar és FloydWarshall megvalósítását biztosítja a org.jgrapht.alg.rövidebb út csomag.

Keressük meg a legrövidebb utat Dijkstra algoritmusa segítségével:

@Test public void whenGetDijkstraShortestPath_thenGetNotNullPath () {DijkstraShortestPath dijkstraShortestPath = new DijkstraShortestPath (directionGraph); List shortestPath = dijkstraShortestPath .getPath ("v1", "v4"). GetVertexList (); assertNotNull (shortestPath); }

Hasonlóképpen, hogy a legrövidebb utat megkapjuk a Bellman-Ford algoritmus használatával:

@Test public void whenGetBellmanFordShortestPath_thenGetNotNullPath () {BellmanFordShortestPath bellmanFordShortestPath = new BellmanFordShortestPath (directionGraph); List shortestPath = bellmanFordShortestPath .getPath ("v1", "v4") .getVertexList (); assertNotNull (shortestPath); }

4.3. Erősen összekapcsolt algráfok keresése

Mielőtt belevágnánk a megvalósításba, nézzük meg röviden, mit jelentenek az egymással szorosan összefüggő részgráfok. Azt mondják, hogy egy algráf csak akkor kapcsolódik szorosan egymáshoz, ha minden csúcspárja között van út.

Példánkban a {v1, v2, v3, v4} erősen összefüggő részgráfnak tekinthető, ha bármely csúcsra bejárhatunk, függetlenül attól, hogy mi az aktuális csúcs.

A fenti képen látható irányított gráfhoz négy ilyen algráfot sorolhatunk fel:

{v9}, {v8}, {v5, v6, v7}, {v1, v2, v3, v4}

Megvalósítás az összes erősen kapcsolódó algráf felsorolásához:

@Test public void whenGetStronglyConnectedSubgraphs_thenPathExists () {StrongConnectivityAlgorithm scAlg = new KosarajuStrongConnectivityInspector (directionGraph); Lista strongConnectedSubgraphs = scAlg.stronglyConnectedSubgraphs (); List erősenConnectedVertices = új ArrayList (strongConnectedSubgraphs.get (3) .vertexSet ()); String randomVertex1 = strongConnectedVertices.get (0); String randomVertex2 = strongConnectedVertices.get (3); AllDirectedPaths allDirectedPaths = új AllDirectedPaths (directionGraph); Lista lehetségesPathList = allDirectedPaths.getAllPaths (randomVertex1, randomVertex2, false, strongConnectedVertices.size ()); assertTrue (lehetségesPathList.size ()> 0); }

4.4. Euleriánus áramkör

Euleri áramkör egy grafikonon G egy olyan áramkör, amely magában foglalja a G. A gráf egy Eulerian-gráf.

Vessünk egy pillantást a grafikonra:

public void createGraphWithEulerianCircuit () {SimpleWeightedGraph simpleGraph = új SimpleWeightedGraph (DefaultEdge.class); IntStream.range (1,5) .forEach (i-> simpleGraph.addVertex ("v" + i)); IntStream.range (1,5) .forEach (i-> {int endVertexNo = (i + 1)> 5? 1: i + 1; simpleGraph.addEdge ("v" + i, "v" + endVertexNo);} ); }

Most tesztelhetjük, hogy egy grafikon tartalmaz-e Eulerian áramkört az API segítségével:

@Test public void givenGraph_whenCheckEluerianCycle_thenGetResult () {HierholzerEulerianCycle eulerianCycle = new HierholzerEulerianCycle (); assertTrue (eulerianCycle.isEulerian (simpleGraph)); } @Test public void whenGetEulerianCycle_thenGetGraphPath () {HierholzerEulerianCycle eulerianCycle = new HierholzerEulerianCycle (); GraphPath elérési útja = eulerianCycle.getEulerianCycle (simpleGraph); assertTrue (path.getEdgeList () .containsAll (simpleGraph.edgeSet ())); }

4.5. Hamilton-körút

A GraphPath amely pontosan meglátogatja az egyes csúcsokat pontosan, Hamilton-ösvényként ismerik.

A hamiltoni ciklus (vagy hamiltoni kör) olyan hamiltoni út, amelyen az út csúcsától az első csúcsáig van egy él (a grafikonon).

Megtalálhatjuk az optimális Hamilton-ciklust a teljes gráfhoz HamiltonianCycle.getApproximateOptimalForCompleteGraph () módszer.

Ez a módszer hozzávetőlegesen minimális utazási értékes turnét eredményez (hamiltoni ciklus). Az optimális megoldás NP-teljes, tehát ez egy megfelelő közelítés, amely polinomi időben fut:

public void whenGetHamiltonianCyclePath_thenGetVerticeSequence () {List verticeList = HamiltonianCycle .getApproximateOptimalForCompleteGraph (completeGraph); assertEquals (verticeList.size (), completeGraph.vertexSet (). size ()); }

4.6. Ciklusérzékelő

Azt is ellenőrizhetjük, hogy vannak-e ciklusok a grafikonon. Jelenleg CycleDetector csak irányított grafikonokat támogat:

@Test public void whenCheckCycles_thenDetectCycles () {CycleDetector cycleDetector = new CycleDetector (directionGraph); assertTrue (cycleDetector.detectCycles ()); Set cycleVertices = cycleDetector.findCycles (); assertTrue (cycleVertices.size ()> 0); }

5. Grafikonmegjelenítés

A JGraphT lehetővé teszi számunkra a grafikonok vizualizációinak létrehozását és képekként történő mentését, először adjuk hozzá a jgrapht-ext kiterjesztés függőségét a Maven Central-tól:

 org.jgrapht jgrapht-ext 1.0.1 

Ezután hozzunk létre egy egyszerű irányított gráfot 3 csúccsal és 3 éllel:

@A nyilvános void létrehozása előtt createGraph () {File imgFile = new File ("src / test / resources / graph.png"); imgFile.createNewFile (); DefaultDirectedGraph g = new DefaultDirectedGraph (DefaultEdge.class); Karakterlánc x1 = "x1"; Karakterlánc x2 = "x2"; Karakterlánc x3 = "x3"; g.addVertex (x1); g.addVertex (x2); g.addVertex (x3); g.addEdge (x1, x2); g.addEdge (x2, x3); g.addEdge (x3, x1); }

Most már láthatóvá tehetjük ezt a grafikont:

@Test public void givenAdaptedGraph_whenWriteBufferedImage_thenFileShouldExist () dobja az IOException {JGraphXAdapter graphAdapter = új JGraphXAdapter (g); mxIGraphLayout layout = new mxCircleLayout (graphAdapter); layout.execute (graphAdapter.getDefaultParent ()); BufferedImage image = mxCellRenderer.createBufferedImage (graphAdapter, null, 2, Color.WHITE, true, null); File imgFile = new File ("src / test / resources / graph.png"); ImageIO.write (kép, "PNG", imgFile); assertTrue (imgFile.exists ()); }

Itt hoztuk létre a JGraphXAdapter amely konstruktor argumentumként kapja meg a gráfunkat, és alkalmaztuk a mxCircleLayout hozzá. Ez körkörösen határozza meg a vizualizációt.

Továbbá használjuk a mxCellRenderer létrehozni a BufferedImage majd írja a vizualizációt egy png fájlba.

Láthatjuk a végső képet egy böngészőben vagy a kedvenc megjelenítőnkben:

További részleteket a hivatalos dokumentációban találhatunk.

6. Következtetés

A JGraphT szinte minden típusú grafikont és sokféle algoritmust kínál. Kitértünk arra, hogyan lehet néhány népszerű API-t használni. A könyvtárat azonban mindig megismerheti a hivatalos oldalon.

Mindezen példák és kódrészletek megvalósítása megtalálható a Github-on.