Úvod do programu JGraphT

1. Prehľad

Väčšinu času, keď implementujeme grafové algoritmy, musíme tiež implementovať niektoré pomocné funkcie.

JGraphT je open-source knižnica triedy Java, ktorá nám poskytuje nielen rôzne typy grafov, ale aj veľa užitočných algoritmov na riešenie najčastejšie sa vyskytujúcich problémov s grafmi.

V tomto článku sa dozvieme, ako vytvárať rôzne typy grafov a aké pohodlné je používanie poskytovaných obslužných programov.

2. Závislosť od Maven

Začnime pridaním závislosti do nášho projektu Maven:

 org.jgrapht jgrapht-core 1.0.1 

Najnovšiu verziu nájdete v Maven Central.

3. Vytváranie grafov

JGraphT podporuje rôzne typy grafov.

3.1. Jednoduché grafy

Pre začiatočníkov vytvorme jednoduchý graf s vrcholom písma String:

Graf g = nový SimpleGraph (DefaultEdge.class); g.addVertex („v1“); g.addVertex („v2“); g.addEdge (v1, v2);

3.2. Usmernené / neusmernené grafy

Umožňuje nám tiež vytvárať usmernené / neusmernené grafy.

V našom príklade vytvoríme usmernený graf a použijeme ho na demonštráciu ďalších užitočných funkcií a algoritmov:

DirectedGraphirectGraph = nový DefaultDirectedGraph (DefaultEdge.class); irectGraph.addVertex ("v1"); irectGraph.addVertex ("v2"); irectGraph.addVertex ("v3"); irectGraph.addEdge ("v1", "v2"); // Pridajte zostávajúce vrcholy a hrany

3.3. Kompletné grafy

Podobne môžeme vygenerovať aj kompletný graf:

public void createCompleteGraph () {completeGraph = nový SimpleWeightedGraph (DefaultEdge.class); CompleteGraphGenerator completeGenerator = nový CompleteGraphGenerator (veľkosť); VertexFactory vFactory = nový VertexFactory () {private int id = 0; public String createVertex () {return "v" + id ++; }}; completeGenerator.generateGraph (completeGraph, vFactory, null); }

3.4. Multi-grafy

Okrem jednoduchých grafov nám API poskytuje aj multigrafy (grafy s viacerými cestami medzi dvoma vrcholmi).

Okrem toho môžeme mať v ľubovoľnom grafe vážené / nevážené alebo používateľom definované hrany.

Vytvorme multigraf so váženými okrajmi:

public void createMultiGraphWithWeightedEdges () {multiGraph = nový Multigraf (DefaultWeightedEdge.class); multiGraph.addVertex ("v1"); multiGraph.addVertex ("v2"); DefaultWeightedEdge edge1 = multiGraph.addEdge ("v1", "v2"); multiGraph.setEdgeWeight (edge1, 5); DefaultWeightedEdge edge2 = multiGraph.addEdge ("v1", "v2"); multiGraph.setEdgeWeight (edge2, 3); }

Okrem toho môžeme mať nemodifikovateľné (iba na čítanie) a poslušné (umožňuje externým poslucháčom sledovať úpravy) grafy aj podgrafy. Tiež môžeme kedykoľvek vytvoriť všetky kompozície týchto grafov.

Ďalšie podrobnosti o rozhraní API nájdete tu.

4. Algoritmy API

Teraz, keď máme objekty grafu s úplnou oporou, pozrime sa na niektoré bežné problémy a ich riešenia.

4.1. Iterácia grafov

Grafom môžeme prechádzať pomocou rôznych iterátorov ako napr BreadthFirstIterator, DepthFirstIterator, ClosestFirstIterator, RandomWalkIterator podľa požiadavky.

Jednoducho musíme vytvoriť inštanciu príslušných iterátorov odovzdaním objektov grafu:

DepthFirstIterator depthFirstIterator = nový DepthFirstIterator (directGraph); BreadthFirstIterator breadthFirstIterator = nový BreadthFirstIterator (directGraph);

Keď dostaneme iteračné objekty, môžeme vykonať iteráciu pomocou hasNext () a Ďalšie() metódy.

4.2. Nájdenie najkratšej cesty

Poskytuje implementácie rôznych algoritmov, ako sú Dijkstra, Bellman-Ford, Astar a FloydWarshall v org.jgrapht.alg.shortestpath balíček.

Poďme nájsť najkratšiu cestu pomocou Dijkstrovho algoritmu:

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

Podobne, aby ste dostali najkratšiu cestu pomocou algoritmu Bellman-Ford:

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

4.3. Nájdenie silne prepojených podgrafov

Predtým, ako sa pustíme do implementácie, sa krátko pozrime na to, čo znamenajú silne prepojené podgrafy. Podgraf je údajne pevne spojený, iba ak je medzi každou dvojicou jeho vrcholov cesta.

V našom príklade {v1, v2, v3, v4} možno považovať za silne prepojený podgraf, ak môžeme prejsť na akýkoľvek vrchol bez ohľadu na to, aký je aktuálny vrchol.

Môžeme uviesť štyri takéto podgrafy pre smerovaný graf zobrazený na obrázku vyššie:

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

Implementácia na zoznam všetkých silne pripojených podgrafov:

@Test public void whenGetStronglyConnectedSubgraphs_thenPathExists () {StrongConnectivityAlgorithm scAlg = new KosarajuStrongConnectivityInspector (irectGraph); Zoznam strongConnectedSubgraphs = scAlg.stronglyConnectedSubgraphs (); Zoznam strongConnectedVertices = nový ArrayList (strongConnectedSubgraphs.get (3) .vertexSet ()); Reťazec randomVertex1 = strongConnectedVertices.get (0); Reťazec randomVertex2 = strongConnectedVertices.get (3); AllDirectedPaths allDirectedPaths = nový AllDirectedPaths (irectGraph); Zoznam possiblePathList = allDirectedPaths.getAllPaths (randomVertex1, randomVertex2, false, strongConnectedVertices.size ()); assertTrue (possiblePathList.size ()> 0); }

4.4. Euleriánsky okruh

Euleriánsky obvod v grafe G je obvod, ktorý obsahuje všetky vrcholy a hrany čísla G. Graf, ktorý ho má, je Euleriánsky graf.

Pozrime sa na graf:

public void createGraphWithEulerianCircuit () {SimpleWeightedGraph simpleGraph = nový 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);} ); }

Teraz môžeme pomocou API vyskúšať, či graf obsahuje Euleriánsky okruh:

@Test public void givenGraph_whenCheckEluerianCycle_thenGetResult () {HierholzerEulerianCycle eulerianCycle = nový HierholzerEulerianCycle (); assertTrue (eulerianCycle.isEulerian (simpleGraph)); } @Test public void whenGetEulerianCycle_thenGetGraphPath () {HierholzerEulerianCycle eulerianCycle = new HierholzerEulerianCycle (); Cesta GraphPath = eulerianCycle.getEulerianCycle (simpleGraph); assertTrue (path.getEdgeList () .containsAll (simpleGraph.edgeSet ())); }

4.5. Hamiltonovský okruh

A GraphPath ktorý navštevuje každý vrchol presne raz, je známy ako Hamiltonova cesta.

Hamiltonovský cyklus (alebo Hamiltonov okruh) je Hamiltonovská cesta taká, že existuje hrana (v grafe) od posledného vrcholu k prvému vrcholu cesty.

Nájdeme optimálny Hamiltonov cyklus pre kompletný graf s HamiltonianCycle.getApproximateOptimalForCompleteGraph () metóda.

Táto metóda vráti približnú minimálnu cestu obchodného cestujúceho (Hamiltonov cyklus). Optimálne riešenie je NP-úplné, takže toto je slušná aproximácia, ktorá beží v polynomiálnom čase:

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

4.6. Detektor cyklu

Môžeme tiež skontrolovať, či sú v grafe nejaké cykly. V súčasnosti CycleDetector podporuje iba smerované grafy:

@Test public void whenCheckCycles_thenDetectCycles () {CycleDetector cycleDetector = nový CycleDetector (directGraph); assertTrue (cycleDetector.detectCycles ()); Nastaviť cycleVertices = cycleDetector.findCycles (); assertTrue (cycleVertices.size ()> 0); }

5. Vizualizácia grafov

JGraphT nám umožňuje generovať vizualizácie grafov a ukladať ich ako obrázky, najskôr pridajme závislosť rozšírenia jgrapht-ext z Maven Central:

 org.jgrapht jgrapht-ext 1.0.1 

Ďalej vytvoríme jednoduchý smerovaný graf s 3 vrcholmi a 3 hranami:

@Before public void createGraph () {File imgFile = new File ("src / test / resources / graph.png"); imgFile.createNewFile (); DefaultDirectedGraph g = nový DefaultDirectedGraph (DefaultEdge.class); Reťazec x1 = "x1"; Reťazec x2 = "x2"; Reťazec x3 = "x3"; g.addVertex (x1); g.addVertex (x2); g.addVertex (x3); g.addEdge (x1, x2); g.addEdge (x2, x3); g.addEdge (x3, x1); }

Teraz môžeme tento graf vizualizovať:

@Test public void givenAdaptedGraph_whenWriteBufferedImage_thenFileShouldExist () vyvolá IOException {JGraphXAdapter graphAdapter = nový JGraphXAdapter (g); rozloženie mxIGraphLayout = nové mxCircleLayout (graphAdapter); layout.execute (graphAdapter.getDefaultParent ()); BufferedImage image = mxCellRenderer.createBufferedImage (graphAdapter, null, 2, Color.WHITE, true, null); Súbor imgFile = nový súbor ("src / test / resources / graph.png"); ImageIO.write (obrázok, "PNG", imgFile); assertTrue (imgFile.exists ()); }

Tu sme vytvorili a JGraphXAdapter ktorý prijíma náš graf ako argument konštruktora a použili sme a mxCircleLayout k tomu. Týmto sa vizualizácia nastaví kruhovým spôsobom.

Ďalej používame a mxCellRenderer vytvoriť BufferedImage a potom vizualizáciu zapíšte do súboru png.

Výsledný obrázok môžeme vidieť v prehliadači alebo na našom obľúbenom renderovacom stroji:

Viac podrobností nájdeme v oficiálnej dokumentácii.

6. Záver

JGraphT poskytuje takmer všetky typy grafov a rôzne algoritmy grafov. Vysvetlili sme, ako používať niekoľko populárnych API. Knižnicu však môžete kedykoľvek preskúmať na oficiálnej stránke.

Implementáciu všetkých týchto príkladov a útržkov kódu nájdete na serveri Github.


$config[zx-auto] not found$config[zx-overlay] not found