Uvod u JGraphT

1. Pregled

Većinu vremena, kada implementiramo algoritme temeljene na grafovima, trebamo implementirati i neke korisne funkcije.

JGraphT je biblioteka Java s otvorenim kodom koja nam ne pruža samo razne tipove grafova već i mnoge korisne algoritme za rješavanje problema s grafovima koji se najčešće susreću.

U ovom ćemo članku vidjeti kako stvoriti različite vrste grafikona i koliko je prikladno koristiti pružene uslužne programe.

2. Ovisnost Mavena

Počnimo s dodavanjem ovisnosti našem projektu Maven:

 org.jgrapht jgrapht-core 1.0.1 

Najnoviju verziju možete pronaći na Maven Central.

3. Izrada grafikona

JGraphT podržava razne vrste grafova.

3.1. Jednostavni grafikoni

Za početak, stvorimo jednostavan graf s vrhom tipa Niz:

Grafikon g = novi SimpleGraph (DefaultEdge.class); g.addVertex (“v1”); g.addVertex (“v2”); g.addEdge (v1, v2);

3.2. Usmjereni / neusmjereni grafikoni

Također nam omogućuje stvaranje usmjerenih / neusmjerenih grafova.

U našem ćemo primjeru izraditi usmjereni grafikon i pomoću njega demonstrirati druge korisne funkcije i algoritme:

DirectedGraph directionGraph = novi DefaultDirectedGraph (DefaultEdge.class); directGraph.addVertex ("v1"); directGraph.addVertex ("v2"); directGraph.addVertex ("v3"); directGraph.addEdge ("v1", "v2"); // Dodajte preostale vrhove i rubove

3.3. Kompletni grafikoni

Slično tome, možemo generirati i cjeloviti graf:

javna praznina createCompleteGraph () {completeGraph = novi SimpleWeightedGraph (DefaultEdge.class); CompleteGraphGenerator completeGenerator = novi CompleteGraphGenerator (veličina); VertexFactory vFactory = novi VertexFactory () {private int id = 0; javni String createVertex () {return "v" + id ++; }}; completeGenerator.generateGraph (completeGraph, vFactory, null); }

3.4. Višegrafovi

Osim jednostavnih grafova, API također nudi i multigrafe (grafikone s više staza između dva vrha).

Osim toga, na bilo kojem grafu možemo imati ponderirane / neponderirane ili korisnički definirane rubove.

Stvorimo multigraf s ponderiranim rubovima:

javna praznina createMultiGraphWithWeightedEdges () {multiGraph = novi Multigraph (DefaultWeightedEdge.class); multiGraph.addVertex ("v1"); multiGraph.addVertex ("v2"); DefaultWeightedEdge edge1 = multiGraph.addEdge ("v1", "v2"); multiGraph.setEdgeWeight (rub1, 5); DefaultWeightedEdge edge2 = multiGraph.addEdge ("v1", "v2"); multiGraph.setEdgeWeight (rub2, 3); }

Uz to, možemo imati nepromjenjive (samo za čitanje) i slušljive (omogućuje vanjskim slušateljima da prate izmjene) grafikone kao i podgrafe. Također, uvijek možemo stvoriti sve sastave ovih grafova.

Dodatne detalje o API-ju možete pronaći ovdje.

4. API algoritmi

Sad, kad imamo pune objekte grafa fledgea, pogledajmo neke uobičajene probleme i njihova rješenja.

4.1. Iteracija grafikona

Grafikom možemo prelaziti pomoću različitih iteratora kao što su BreadthFirstIterator, DepthFirstIterator, ClosestFirstIterator, RandomWalkIterator prema zahtjevu.

Jednostavno trebamo stvoriti instancu odgovarajućih iteratora prosljeđivanjem objekata grafa:

DepthFirstIterator deepFirstIterator = novi DepthFirstIterator (directorGraph); BreadthFirstIterator widththFirstIterator = novi BreadthFirstIterator (directorGraph);

Jednom kada dobijemo objekte iteratora, iteraciju možemo izvesti pomoću hasNext () i Sljedeći() metode.

4.2. Pronalaženje najkraćeg puta

Pruža implementacije različitih algoritama kao što su Dijkstra, Bellman-Ford, Astar i FloydWarshall u org.jgrapht.alg.shortestpath paket.

Pronađimo najkraći put koristeći Dijkstrin algoritam:

@Test public void whenGetDijkstraShortestPath_thenGetNotNullPath () {DijkstraShortestPath dijkstraShortestPath = new DijkstraShortestPath (directorGraph); Navesti najkraći put = dijkstraShortestPath .getPath ("v1", "v4"). GetVertexList (); assertNotNull (shortestPath); }

Slično tome, da biste dobili najkraći put koristeći Bellman-Fordov algoritam:

@Test public void whenGetBellmanFordShortestPath_thenGetNotNullPath () {BellmanFordShortestPath bellmanFordShortestPath = new BellmanFordShortestPath (directorGraph); Navesti najkraći put = bellmanFordShortestPath .getPath ("v1", "v4") .getVertexList (); assertNotNull (shortestPath); }

4.3. Pronalaženje čvrsto povezanih podgrafa

Prije nego što krenemo u implementaciju, pogledajmo ukratko što znače jako povezani podgrafi. Za podgraf se kaže da je čvrsto povezan samo ako postoji put između svakog para njegovih vrhova.

U našem primjeru, {v1, v2, v3, v4} možemo smatrati jako povezanim podgrafom ako možemo prijeći bilo koji vrh bez obzira na to koji je trenutni vrh.

Za usmjereni graf prikazan na gornjoj slici možemo navesti četiri takva podgrafa:

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

Implementacija za navođenje svih jako povezanih podgrafa:

@Test javna praznina kadaGetStronglyConnectedSubgraphs_thenPathExists () {StrongConnectivityAlgorithm scAlg = novi KosarajuStrongConnectivityInspector (directorGraph); Popis močnoConnectedSubgraphs = scAlg.stronglyConnectedSubgraphs (); Popis močnoConnectedVertices = novi popis nizova (močnoConnectedSubgraphs.get (3) .vertexSet ()); Niz randomVertex1 = strongConnectedVertices.get (0); Niz randomVertex2 = strongConnectedVertices.get (3); AllDirectedPaths allDirectedPaths = novi AllDirectedPaths (directorGraph); Popis possiblePathList = allDirectedPaths.getAllPaths (randomVertex1, randomVertex2, false, močnoConnectedVertices.size ()); assertTrue (possiblePathList.size ()> 0); }

4.4. Eulerov krug

Eulerov krug u grafu G je sklop koji uključuje sve vrhove i bridove G. Graf koji ga ima je Eulerov graf.

Pogledajmo grafikon:

javna praznina createGraphWithEulerianCircuit () {SimpleWeightedGraph simpleGraph = novi 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);} ); }

Sada možemo testirati sadrži li graf Eulerov krug pomoću API-ja:

@Test javna praznina givenGraph_whenCheckEluerianCycle_thenGetResult () {HierholzerEulerianCycle eulerianCycle = novi HierholzerEulerianCycle (); assertTrue (eulerianCycle.isEulerian (simpleGraph)); } @Test javna praznina kadaGetEulerianCycle_thenGetGraphPath () {HierholzerEulerianCycle eulerianCycle = novi HierholzerEulerianCycle (); GraphPath put = eulerianCycle.getEulerianCycle (simpleGraph); assertTrue (path.getEdgeList () .containsAll (simpleGraph.edgeSet ())); }

4.5. Hamiltonov krug

A GraphPath koji posjeti svaki vrh točno jednom poznat je kao Hamiltonov put.

Hamiltonov ciklus (ili Hamiltonov krug) Hamiltonov je put takav da postoji rub (u grafikonu) od zadnjeg vrha do prvog vrha puta.

Možemo pronaći optimalni Hamiltonov ciklus za cjeloviti graf sa HamiltonianCycle.getApproximateOptimalForCompleteGraph () metoda.

Ova metoda vratit će približnu minimalnu turu trgovačkog putnika (Hamiltonov ciklus). Optimalno rješenje je NP-kompletno, tako da je ovo pristojna aproksimacija koja traje u polinomnom vremenu:

javna praznina whenGetHamiltonianCyclePath_thenGetVerticeSequence () {Popis verticeList = HamiltonianCycle .getApproximateOptimalForCompleteGraph (completeGraph); assertEquals (verticeList.size (), completeGraph.vertexSet (). size ()); }

4.6. Detektor ciklusa

Također možemo provjeriti postoje li ciklusi na grafikonu. Trenutno, Detektor ciklusa podržava samo usmjerene grafove:

@Test public void whenCheckCycles_thenDetectCycles () {CycleDetector cycleDetector = novi CycleDetector (directorGraph); assertTrue (cycleDetector.detectCycles ()); Postavite cycleVertices = cycleDetector.findCycles (); assertTrue (cycleVertices.size ()> 0); }

5. Vizualizacija grafikona

JGraphT nam omogućuje generiranje vizualizacija grafikona i njihovo spremanje kao slike, prvo dodamo ovisnost o proširenju jgrapht-ext iz Maven Central:

 org.jgrapht jgrapht-ext 1.0.1 

Dalje, kreirajmo jednostavan usmjereni graf s 3 vrha i 3 ruba:

@Prije javne praznine createGraph () {Datoteka imgFile = nova datoteka ("src / test / resources / graph.png"); imgFile.createNewFile (); DefaultDirectedGraph g = novi DefaultDirectedGraph (DefaultEdge.class); Niz x1 = "x1"; Niz x2 = "x2"; Niz x3 = "x3"; g.addVertex (x1); g.addVertex (x2); g.addVertex (x3); g.addEdge (x1, x2); g.addEdge (x2, x3); g.addEdge (x3, x1); }

Sada možemo vizualizirati ovaj graf:

@Test javna praznina givenAdaptedGraph_whenWriteBufferedImage_thenFileShouldExist () baca IOException {JGraphXAdapter graphAdapter = novi JGraphXAdapter (g); mxIGraphLayout layout = novi mxCircleLayout (graphAdapter); layout.execute (graphAdapter.getDefaultParent ()); BufferedImage image = mxCellRenderer.createBufferedImage (graphAdapter, null, 2, Color.WHITE, true, null); Datoteka imgFile = nova datoteka ("src / test / resources / graph.png"); ImageIO.write (slika, "PNG", imgFile); assertTrue (imgFile.exists ()); }

Ovdje smo stvorili JGraphXAdapter koji prima naš graf kao argument konstruktora i primijenili smo a mxCircleLayout tome. Ovo vizualizaciju postavlja na kružni način.

Nadalje, koristimo a mxCellRenderer stvoriti a Slika u baferu a zatim napišite vizualizaciju u png datoteku.

Konačnu sliku možemo vidjeti u pregledniku ili u našem omiljenom renderu:

Više detalja možemo pronaći u službenoj dokumentaciji.

6. Zaključak

JGraphT pruža gotovo sve vrste grafova i razne algoritme grafova. Opisali smo kako koristiti nekoliko popularnih API-ja. Međutim, knjižnicu uvijek možete istražiti na službenoj stranici.

Implementacija svih ovih primjera i isječaka koda može se naći na Githubu.