streamalism.org

1. Oversigt

Det meste af tiden, når vi implementerer grafbaserede algoritmer, er vi også nødt til at implementere nogle hjælpefunktioner.

JGraphT er et open source Java-klassebibliotek, som ikke kun giver os forskellige typer grafer, men også mange nyttige algoritmer til løsning af hyppigst opståede grafproblemer.

I denne artikel vil vi se, hvordan man opretter forskellige typer grafer, og hvor praktisk det er at bruge de medfølgende hjælpeprogrammer.

2. Maven-afhængighed

Lad os starte med at tilføje afhængigheden af ​​vores Maven-projekt:

 org.jgrapht jgrapht-core 1.0.1 

Den nyeste version kan findes på Maven Central.

3. Oprettelse af grafer

JGraphT understøtter forskellige typer grafer.

3.1. Enkle grafer

For det første skal vi oprette en simpel graf med et toppunkt af typen Snor:

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

3.2. Direkte / ikke-dirigerede grafer

Det giver os også mulighed for at oprette rettet / ikke-rettet grafer.

I vores eksempel opretter vi en rettet graf og bruger den til at demonstrere andre hjælpefunktioner og algoritmer:

DirectedGraph directedGraph = ny DefaultDirectedGraph (DefaultEdge.class); directedGraph.addVertex ("v1"); directedGraph.addVertex ("v2"); directedGraph.addVertex ("v3"); directedGraph.addEdge ("v1", "v2"); // Tilføj resterende hjørner og kanter

3.3. Komplette grafer

På samme måde kan vi også generere en komplet graf:

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

3.4. Multi-grafer

Bortset fra simple grafer giver API os også multigrafier (grafer med flere stier mellem to hjørner).

Desuden kan vi have vægtede / ikke-vægtede eller brugerdefinerede kanter i enhver graf.

Lad os oprette et multigrafi med vægtede kanter:

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

Ud over dette kan vi have umodificerbare (skrivebeskyttede) og lytbare (tillader eksterne lyttere at spore ændringer) grafer såvel som underbilleder. Vi kan også altid oprette alle kompositioner af disse grafer.

Yderligere API-detaljer kan findes her.

4. API-algoritmer

Nu, hvor vi har fuldgyldige grafobjekter, skal vi se på nogle almindelige problemer og deres løsninger.

4.1. Grafitation

Vi kan krydse grafen ved hjælp af forskellige iteratorer som f.eks BreadthFirstIterator, DepthFirstIterator, TættestFirstIterator, RandomWalkIterator i henhold til kravet.

Vi er simpelthen nødt til at oprette en forekomst af respektive iteratorer ved at sende grafobjekter:

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

Når vi først har iteratorobjekterne, kan vi udføre iterationen ved hjælp af hasNext () og Næste() metoder.

4.2. Find den korteste vej

Det giver implementeringer af forskellige algoritmer som Dijkstra, Bellman-Ford, Astar og FloydWarshall i org.jgrapht.alg.shortestpath pakke.

Lad os finde den korteste vej ved hjælp af Dijkstras algoritme:

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

Tilsvarende for at få den korteste vej ved hjælp af Bellman-Ford-algoritmen:

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

4.3. Find stærkt forbundne underbilleder

Før vi går ind i implementeringen, skal vi kort se på, hvad stærkt forbundne underbilleder betyder. En undergraf siges kun at være stærkt forbundet, hvis der er en sti mellem hvert par af dets hjørner.

I vores eksempel kan {v1, v2, v3, v4} betragtes som et stærkt forbundet subgraf, hvis vi kan krydse et hvilket som helst toppunkt uanset hvad det aktuelle toppunkt er.

Vi kan liste fire sådanne underbilleder til den dirigerede graf vist i ovenstående billede:

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

Implementering til liste over alle stærkt forbundne underbilleder:

@Test offentlig ugyldig nårGetStronglyConnectedSubgraphs_thenPathExists () {StrongConnectivityAlgorithm scAlg = ny KosarajuStrongConnectivityInspector (directedGraph); Liste staarkConnectedSubgraphs = scAlg.stronglyConnectedSubgraphs (); Liste stærktConnectedVertices = ny ArrayList (starkConnectedSubgraphs.get (3) .vertexSet ()); Streng randomVertex1 = starktConnectedVertices.get (0); Streng randomVertex2 = starktConnectedVertices.get (3); AllDirectedPaths allDirectedPaths = nye AllDirectedPaths (directedGraph); Liste possiblePathList = allDirectedPaths.getAllPaths (randomVertex1, randomVertex2, false, starktConnectedVertices.size ()); assertTrue (possiblePathList.size ()> 0); }

4.4. Eulerian Circuit

Et Euleriansk kredsløb i en graf G er et kredsløb, der inkluderer alle hjørner og kanter på G. En graf, der har det, er en Euleriansk graf.

Lad os se på grafen:

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

Nu kan vi teste, om en graf indeholder Eulerian Circuit ved hjælp af API:

@Test offentlig ugyldighed 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 der besøger hvert toppunkt nøjagtigt en gang er kendt som Hamiltonian Path.

En Hamilton-cyklus (eller Hamilton-kredsløb) er en Hamilton-sti, således at der er en kant (fra grafen) fra det sidste toppunkt til den første toppunkt på stien.

Vi kan finde den optimale Hamilton-cyklus til komplet graf med HamiltonianCycle.getApproximateOptimalForCompleteGraph () metode.

Denne metode returnerer en omtrentlig minimal rejsetællertur (Hamilton-cyklus). Den optimale løsning er NP-komplet, så dette er en anstændig tilnærmelse, der løber i polynomisk tid:

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

4.6. Cyklusdetektor

Vi kan også kontrollere, om der er cyklusser i grafen. I øjeblikket, CycleDetector understøtter kun rettet grafer:

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

5. Grafvisualisering

JGraphT giver os mulighed for at generere visualiseringer af grafer og gemme dem som billeder, lad os først tilføje afhængigheden jgrapht-ext-udvidelse fra Maven Central:

 org.jgrapht jgrapht-ext 1.0.1 

Lad os derefter oprette en simpel rettet graf med 3 hjørner og 3 kanter:

@Før offentligt ugyldigt 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 nu visualisere denne graf:

@Test offentlig ugyldighed givenAdaptedGraph_whenWriteBufferedImage_thenFileShouldExist () kaster IOException {JGraphXAdapter graphAdapter = ny JGraphXAdapter (g); mxIGraphLayout layout = ny 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 (billede, "PNG", imgFile); assertTrue (imgFile.exists ()); }

Her har vi oprettet en JGraphXAdapter som modtager vores graf som et konstruktørargument, og vi har anvendt en mxCircleLayout til det. Dette lægger visualiseringen ud på en cirkulær måde.

Desuden bruger vi en mxCellRenderer at oprette en BufferedImage og skriv derefter visualiseringen til en png-fil.

Vi kan se det endelige billede i en browser eller vores yndlingsrender:

Vi kan finde flere detaljer i den officielle dokumentation.

6. Konklusion

JGraphT giver næsten alle typer grafer og forskellige grafalgoritmer. Vi dækkede, hvordan man bruger få populære API'er. Du kan dog altid udforske biblioteket på den officielle side.

Implementeringen af ​​alle disse eksempler og kodestykker kan findes på Github.