Introduksjon til JGraphT

1. Oversikt

Når vi implementerer grafbaserte algoritmer, trenger vi også å implementere noen verktøyfunksjoner.

JGraphT er et åpen kildekode Java-klassebibliotek som ikke bare gir oss forskjellige typer grafer, men også mange nyttige algoritmer for å løse grafproblemer som ofte oppstod.

I denne artikkelen ser vi hvordan du lager forskjellige typer grafer og hvor praktisk det er å bruke de medfølgende verktøyene.

2. Maven avhengighet

La oss begynne med å legge til avhengigheten til vårt Maven-prosjekt:

 org.jgrapht jgrapht-core 1.0.1 

Den siste versjonen finner du på Maven Central.

3. Lage grafer

JGraphT støtter forskjellige typer grafer.

3.1. Enkle grafer

For det første, la oss lage en enkel graf med et toppunkt av typen String:

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

3.2. Regisserte / ikke-dirigerte grafer

Det lar oss også lage dirigerte / ikke-rettet grafer.

I vårt eksempel lager vi en rettet graf og bruker den til å demonstrere andre nyttefunksjoner og algoritmer:

DirectedGraph directedGraph = ny DefaultDirectedGraph (DefaultEdge.class); directedGraph.addVertex ("v1"); directedGraph.addVertex ("v2"); directedGraph.addVertex ("v3"); directedGraph.addEdge ("v1", "v2"); // Legg til gjenværende hjørner og kanter

3.3. Komplette grafer

På samme måte kan vi også generere en komplett graf:

public void createCompleteGraph () {completeGraph = new SimpleWeightedGraph (DefaultEdge.class); CompleteGraphGenerator completeGenerator = ny CompleteGraphGenerator (størrelse); VertexFactory vFactory = ny VertexFactory () {private int id = 0; public String createVertex () {return "v" + id ++; }}; completeGenerator.generateGraph (completeGraph, vFactory, null); }

3.4. Multi-grafer

Annet enn enkle grafer, gir API oss også multigrafier (grafer med flere baner mellom to hjørner).

Dessuten kan vi ha vektede / uveide eller brukerdefinerte kanter i hvilken som helst graf.

La oss lage et multigrafi med vektede kanter:

public void createMultiGraphWithWeightedEdges () {multiGraph = new Multigraph (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); }

I tillegg til dette kan vi ha umodifiserbare (skrivebeskyttet) og lytbare (tillater eksterne lyttere å spore modifikasjoner) grafer så vel som underbilder. Vi kan også alltid lage alle komposisjoner av disse grafene.

Ytterligere API-detaljer finner du her.

4. API-algoritmer

Nå som vi har fullverdige grafobjekter, la oss se på noen vanlige problemer og deres løsninger.

4.1. Grafitasjon

Vi kan krysse grafen ved hjelp av forskjellige iteratorer som BreadthFirstIterator, DepthFirstIterator, Nærmeste FirstIterator, RandomWalkIterator i henhold til kravet.

Vi trenger bare å lage en forekomst av respektive iteratorer ved å sende grafobjekter:

DepthFirstIterator depthFirstIterator = ny DepthFirstIterator (directedGraph); BreadthFirstIterator breadthFirstIterator = ny BreadthFirstIterator (directedGraph);

Når vi har fått iteratorobjektene, kan vi utføre iterasjonen ved hjelp av hasNext () og neste () metoder.

4.2. Finne den korteste veien

Den gir implementeringer av forskjellige algoritmer som Dijkstra, Bellman-Ford, Astar og FloydWarshall i org.jgrapht.alg.shortestpath pakke.

La oss finne den korteste veien ved hjelp av Dijkstras algoritme:

@Test offentlig ugyldig nårGetDijkstraShortestPath_thenGetNotNullPath () {DijkstraShortestPath dijkstraShortestPath = ny DijkstraShortestPath (directedGraph); Liste shortestPath = dijkstraShortestPath .getPath ("v1", "v4"). GetVertexList (); assertNotNull (shortestPath); }

På samme måte, for å få den korteste veien ved hjelp av Bellman-Ford-algoritmen:

@Test offentlig ugyldig nårGetBellmanFordShortestPath_thenGetNotNullPath () {BellmanFordShortestPath bellmanFordShortestPath = ny BellmanFordShortestPath (directedGraph); Liste shortestPath = bellmanFordShortestPath .getPath ("v1", "v4") .getVertexList (); assertNotNull (shortestPath); }

4.3. Finne sterkt koblede underbilder

Før vi går inn i implementeringen, la oss kort se på hva sterkt sammenkoblede underbilder betyr. En undergraf sies å være sterkt koblet bare hvis det er en sti mellom hvert par av toppunktene.

I vårt eksempel kan {v1, v2, v3, v4} betraktes som et sterkt koblet subgraf hvis vi kan krysse til et hvilket som helst toppunkt uavhengig av hva dagens toppunkt er.

Vi kan liste opp fire slike underbilder for den dirigerte grafen vist i bildet ovenfor:

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

Implementering for å liste ut alle sterkt sammenkoblede underbilder:

@Test offentlig ugyldig nårGetStronglyConnectedSubgraphs_thenPathExists () {StrongConnectivityAlgorithm scAlg = ny KosarajuStrongConnectivityInspector (directedGraph); Liste strongConnectedSubgraphs = scAlg.stronglyConnectedSubgraphs (); Liste sterktConnectedVertices = ny ArrayList (sterkConnectedSubgraphs.get (3) .vertexSet ()); Streng randomVertex1 = sterkConnectedVertices.get (0); Streng randomVertex2 = sterkConnectedVertices.get (3); AllDirectedPaths allDirectedPaths = nye AllDirectedPaths (directedGraph); Liste possiblePathList = allDirectedPaths.getAllPaths (randomVertex1, randomVertex2, false, strongConnectedVertices.size ()); assertTrue (possiblePathList.size ()> 0); }

4.4. Eulerian Circuit

En Eulerian Circuit i en graf G er en krets som inkluderer alle hjørner og kanter av G. En graf som har den er en Euleriansk graf.

La oss ta en titt på grafen:

offentlig ugyldig createGraphWithEulerianCircuit () {SimpleWeightedGraph simpleGraph = ny 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);} ); }

Nå kan vi teste om en graf inneholder Eulerian Circuit ved hjelp av API:

@Test offentlig ugyldig givenGraph_whenCheckEluerianCycle_thenGetResult () {HierholzerEulerianCycle eulerianCycle = ny HierholzerEulerianCycle (); assertTrue (eulerianCycle.isEulerian (simpleGraph)); } @Test offentlig ugyldig nårGetEulerianCycle_thenGetGraphPath () {HierholzerEulerianCycle eulerianCycle = ny HierholzerEulerianCycle (); GraphPath-sti = eulerianCycle.getEulerianCycle (simpleGraph); assertTrue (path.getEdgeList () .containsAll (simpleGraph.edgeSet ())); }

4.5. Hamiltonian Circuit

EN GraphPath som besøker hvert toppunkt nøyaktig en gang, er kjent som Hamiltonian Path.

En Hamilton-syklus (eller Hamilton-krets) er en Hamilton-sti slik at det er en kant (i grafen) fra siste toppunkt til første toppunkt på stien.

Vi kan finne optimal Hamiltonian Cycle for fullstendig graf med HamiltonianCycle.getApproximateOptimalForCompleteGraph () metode.

Denne metoden vil returnere en omtrentlig minimal omreisende selger-tur (Hamilton-syklus). Den optimale løsningen er NP-komplett, så dette er en anstendig tilnærming som går i polynomisk tid:

offentlig ugyldig nårGetHamiltonianCyclePath_thenGetVerticeSequence () {List verticeList = HamiltonianCycle .getApproximateOptimalForCompleteGraph (completeGraph); assertEquals (verticeList.size (), completeGraph.vertexSet (). størrelse ()); }

4.6. Syklusdetektor

Vi kan også sjekke om det er noen sykluser i grafen. For tiden, CycleDetector støtter bare rettet grafer:

@Test offentlig ugyldig nårCheckCycles_thenDetectCycles () {CycleDetector cycleDetector = ny CycleDetector (directedGraph); assertTrue (cycleDetector.detectCycles ()); Sett cycleVertices = cycleDetector.findCycles (); assertTrue (cycleVertices.size ()> 0); }

5. Grafvisualisering

JGraphT lar oss generere visualiseringer av grafer og lagre dem som bilder, la oss først legge til avhengigheten av utvidelsen jgrapht-ext fra Maven Central:

 org.jgrapht jgrapht-ext 1.0.1 

Deretter la oss lage en enkel rettet graf med 3 hjørner og 3 kanter:

@Før offentlig ugyldig createGraph () {File imgFile = ny fil ("src / test / resources / graph.png"); imgFile.createNewFile (); DefaultDirectedGraph g = ny DefaultDirectedGraph (DefaultEdge.class); Streng x1 = "x1"; Streng x2 = "x2"; Streng x3 = "x3"; g.addVertex (x1); g.addVertex (x2); g.addVertex (x3); g.addEdge (x1, x2); g.addEdge (x2, x3); g.addEdge (x3, x1); }

Vi kan nå visualisere denne grafen:

@Test offentlig ugyldighet gittAdaptedGraph_whenWriteBufferedImage_thenFileShouldExist () kaster IOException {JGraphXAdapter graphAdapter = ny JGraphXAdapter (g); mxIGraphLayout layout = new mxCircleLayout (graphAdapter); layout.execute (graphAdapter.getDefaultParent ()); BufferedImage image = mxCellRenderer.createBufferedImage (graphAdapter, null, 2, Color.WHITE, true, null); Fil imgFile = ny fil ("src / test / resources / graph.png"); ImageIO.write (bilde, "PNG", imgFile); assertTrue (imgFile.exists ()); }

Her har vi laget en JGraphXAdapter som mottar grafen vår som et konstruktørargument, og vi har brukt en mxCircleLayout til det. Dette legger visualiseringen ut på en sirkulær måte.

Videre bruker vi a mxCellRenderer å lage en BufferedImage og skriv deretter visualiseringen til en png-fil.

Vi kan se det endelige bildet i en nettleser eller vår favorittrender:

Vi finner mer informasjon i den offisielle dokumentasjonen.

6. Konklusjon

JGraphT gir nesten alle typer grafer og forskjellige grafalgoritmer. Vi dekket hvordan du bruker få populære APIer. Du kan imidlertid alltid utforske biblioteket på den offisielle siden.

Implementeringen av alle disse eksemplene og kodebiter finner du på Github.


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