streamalism.org

1. Overzicht

Meestal, wanneer we op grafieken gebaseerde algoritmen implementeren, moeten we ook enkele hulpprogramma-functies implementeren.

JGraphT is een open-source Java-klassenbibliotheek die ons niet alleen verschillende soorten grafieken biedt, maar ook veel nuttige algoritmen voor het oplossen van de meest voorkomende grafiekproblemen.

In dit artikel zullen we zien hoe u verschillende soorten grafieken kunt maken en hoe gemakkelijk het is om de meegeleverde hulpprogramma's te gebruiken.

2. Maven Afhankelijkheid

Laten we beginnen met het toevoegen van de afhankelijkheid aan ons Maven-project:

 org.jgrapht jgrapht-core 1.0.1 

De nieuwste versie is te vinden op de Maven Central.

3. Grafieken maken

JGraphT ondersteunt verschillende soorten grafieken.

3.1. Eenvoudige grafieken

Laten we om te beginnen een eenvoudige grafiek maken met een hoekpunt van het type Draad:

Grafiek g = nieuwe SimpleGraph (DefaultEdge.class); g.addVertex ("v1"); g.addVertex ("v2"); g.addEdge (v1, v2);

3.2. Gerichte / niet-gerichte grafieken

Het stelt ons ook in staat om gerichte / ongerichte grafieken te maken.

In ons voorbeeld maken we een gerichte grafiek en gebruiken we deze om andere hulpprogramma-functies en algoritmen te demonstreren:

DirectedGraph directionGraph = nieuwe DefaultDirectedGraph (DefaultEdge.class); directionGraph.addVertex ("v1"); directionGraph.addVertex ("v2"); directionGraph.addVertex ("v3"); gerichtGraph.addEdge ("v1", "v2"); // Voeg resterende hoekpunten en randen toe

3.3. Volledige grafieken

Evenzo kunnen we ook een volledige grafiek genereren:

public void createCompleteGraph () {completeGraph = nieuwe SimpleWeightedGraph (DefaultEdge.class); CompleteGraphGenerator completeGenerator = nieuwe CompleteGraphGenerator (grootte); VertexFactory vFactory = nieuwe VertexFactory () {privé int id = 0; public String createVertex () {return "v" + id ++; }}; completeGenerator.generateGraph (completeGraph, vFactory, null); }

3.4. Multi-grafieken

Naast eenvoudige grafieken biedt API ons ook multigraphs (grafieken met meerdere paden tussen twee hoekpunten).

Bovendien kunnen we gewogen / ongewogen of door de gebruiker gedefinieerde randen in elke grafiek hebben.

Laten we een multigraph maken met verzwaarde randen:

openbare ongeldige createMultiGraphWithWeightedEdges () {multiGraph = nieuwe 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); }

Daarnaast kunnen we niet-wijzigbare (alleen-lezen) en luisterbare (externe luisteraars kunnen wijzigingen volgen) grafieken en subgraphs hebben. We kunnen ook altijd alle composities van deze grafieken maken.

Verdere API-details zijn hier te vinden.

4. API-algoritmen

Nu we volledige grafiekobjecten hebben, gaan we eens kijken naar enkele veelvoorkomende problemen en hun oplossingen.

4.1. Grafiekherhaling

We kunnen de grafiek doorlopen met verschillende iteratoren, zoals Breedte EersteIterator, DiepteFirstIterator, DichtstbijzijndeFirstIterator, RandomWalkIterator vanaf het vereiste.

We hoeven alleen maar een instantie van respectieve iteratoren te maken door grafiekobjecten door te geven:

DepthFirstIterator depthFirstIterator = nieuwe DepthFirstIterator (directGraph); BreadthFirstIterator breedteFirstIterator = nieuwe BreadthFirstIterator (directGraph);

Zodra we de iterator-objecten hebben, kunnen we de iteratie uitvoeren met hasNext () en De volgende() methoden.

4.2. Het kortste pad vinden

Het biedt implementaties van verschillende algoritmen zoals Dijkstra, Bellman-Ford, Astar en FloydWarshall in de org.jgrapht.alg.shortestpath pakket.

Laten we het kortste pad vinden met het algoritme van Dijkstra:

@Test openbare leegte whenGetDijkstraShortestPath_thenGetNotNullPath () {DijkstraShortestPath dijkstraShortestPath = nieuwe DijkstraShortestPath (directGraph); Lijst shortestPath = dijkstraShortestPath .getPath ("v1", "v4"). GetVertexList (); assertNotNull (shortestPath); }

Evenzo, om het kortste pad te krijgen met behulp van het Bellman-Ford-algoritme:

@Test openbare leegte whenGetBellmanFordShortestPath_thenGetNotNullPath () {BellmanFordShortestPath bellmanFordShortestPath = nieuwe BellmanFordShortestPath (directGraph); Lijst shortestPath = bellmanFordShortestPath .getPath ("v1", "v4") .getVertexList (); assertNotNull (shortestPath); }

4.3. Sterk verbonden subgraphs vinden

Laten we, voordat we met de implementatie beginnen, kort kijken naar wat sterk verbonden subgraphs betekenen. Er wordt gezegd dat een subgraaf alleen sterk verbonden is als er een pad is tussen elk paar hoekpunten.

In ons voorbeeld kan {v1, v2, v3, v4} worden beschouwd als een sterk verbonden subgraaf als we naar een hoekpunt kunnen gaan, ongeacht wat het huidige hoekpunt is.

We kunnen vier van dergelijke subgraphs noemen voor de gerichte grafiek die in de bovenstaande afbeelding wordt weergegeven:

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

Implementatie om alle sterk verbonden subgraphs op te sommen:

@Test openbare leegte whenGetStronglyConnectedSubgraphs_thenPathExists () {StrongConnectivityAlgorithm scAlg = nieuwe KosarajuStrongConnectivityInspector (directGraph); Lijst sterkConnectedSubgraphs = scAlg.stronglyConnectedSubgraphs (); Lijst sterkConnectedVertices = nieuwe ArrayList (strongConnectedSubgraphs.get (3) .vertexSet ()); String randomVertex1 = strongConnectedVertices.get (0); String randomVertex2 = strongConnectedVertices.get (3); AllDirectedPaths allDirectedPaths = nieuwe AllDirectedPaths (directGraph); Lijst mogelijkPathList = allDirectedPaths.getAllPaths (randomVertex1, randomVertex2, false, strongConnectedVertices.size ()); assertTrue (mogelijkPathList.size ()> 0); }

4.4. Euleriaans circuit

Een Euleriaans circuit in een grafiek G is een circuit dat alle hoekpunten en randen van G. Een grafiek die het heeft, is een Euleriaanse grafiek.

Laten we de grafiek eens bekijken:

public void createGraphWithEulerianCircuit () {SimpleWeightedGraph simpleGraph = nieuwe 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 kunnen we testen of een grafiek het Eulerian Circuit bevat met behulp van de API:

@Test openbare leegte gegevenGraph_whenCheckEluerianCycle_thenGetResult () {HierholzerEulerianCycle eulerianCycle = nieuwe HierholzerEulerianCycle (); assertTrue (eulerianCycle.isEulerian (simpleGraph)); } @Test openbare leegte whenGetEulerianCycle_thenGetGraphPath () {HierholzerEulerianCycle eulerianCycle = nieuwe HierholzerEulerianCycle (); GraphPath path = eulerianCycle.getEulerianCycle (simpleGraph); assertTrue (path.getEdgeList () .containsAll (simpleGraph.edgeSet ())); }

4.5. Hamiltonian Circuit

EEN GraphPath dat elk hoekpunt precies één keer bezoekt, staat bekend als Hamiltonian Path.

Een Hamiltoniaanse cyclus (of Hamiltoniaans circuit) is een Hamiltoniaans pad zodat er een rand (in de grafiek) is van het laatste hoekpunt naar het eerste hoekpunt van het pad.

We kunnen de optimale Hamiltoniaanse cyclus vinden voor een volledige grafiek met HamiltonianCycle.getApproximateOptimalForCompleteGraph () methode.

Deze methode levert een geschatte minimale rondreizende verkoper op (Hamiltoniaanse cyclus). De optimale oplossing is NP-compleet, dus dit is een behoorlijke benadering die loopt in polynoomtijd:

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

4.6. Cyclus Detector

We kunnen ook controleren of er cycli in de grafiek staan. Momenteel, CycleDetector ondersteunt alleen gerichte grafieken:

@Test openbare leegte whenCheckCycles_thenDetectCycles () {CycleDetector cycleDetector = nieuwe CycleDetector (directGraph); assertTrue (cycleDetector.detectCycles ()); Stel cycleVertices = cycleDetector.findCycles (); assertTrue (cycleVertices.size ()> 0); }

5. Grafiek visualisatie

Met JGraphT kunnen we visualisaties van grafieken genereren en deze als afbeeldingen opslaan, laten we eerst de jgrapht-ext extensie-afhankelijkheid van Maven Central toevoegen:

 org.jgrapht jgrapht-ext 1.0.1 

Laten we vervolgens een eenvoudige gerichte grafiek maken met 3 hoekpunten en 3 randen:

@Before public void createGraph () {Bestand imgFile = nieuw bestand ("src / test / resources / graph.png"); imgFile.createNewFile (); DefaultDirectedGraph g = nieuwe DefaultDirectedGraph (DefaultEdge.class); String x1 = "x1"; String x2 = "x2"; String x3 = "x3"; g.addVertex (x1); g.addVertex (x2); g.addVertex (x3); g.addEdge (x1, x2); g.addEdge (x2, x3); g.addEdge (x3, x1); }

We kunnen deze grafiek nu visualiseren:

@Test openbare leegte gegevenAdaptedGraph_whenWriteBufferedImage_thenFileShouldExist () gooit IOException {JGraphXAdapter graphAdapter = nieuwe JGraphXAdapter (g); mxIGraphLayout layout = nieuwe mxCircleLayout (graphAdapter); layout.execute (graphAdapter.getDefaultParent ()); BufferedImage-afbeelding = mxCellRenderer.createBufferedImage (graphAdapter, null, 2, Color.WHITE, true, null); Bestand imgFile = nieuw bestand ("src / test / resources / graph.png"); ImageIO.write (afbeelding, "PNG", imgFile); assertTrue (imgFile.exists ()); }

Hier hebben we een JGraphXAdapter die onze grafiek ontvangt als een constructorargument en we hebben een mxCircleLayout eraan. Dit legt de visualisatie op een circulaire manier uit.

Verder gebruiken we een mxCellRenderer om een BufferedImage en schrijf de visualisatie vervolgens naar een png-bestand.

We kunnen de uiteindelijke afbeelding in een browser of onze favoriete renderer zien:

We kunnen meer details vinden in de officiële documentatie.

6. Conclusie

JGraphT biedt bijna alle soorten grafieken en verschillende grafiekalgoritmen. We hebben besproken hoe u enkele populaire API's kunt gebruiken. U kunt de bibliotheek echter altijd verkennen op de officiële pagina.

De implementatie van al deze voorbeelden en codefragmenten is te vinden op Github.