Einführung in JGraphT

1. Übersicht

Wenn wir graphbasierte Algorithmen implementieren, müssen wir meistens auch einige Dienstprogrammfunktionen implementieren.

JGraphT ist eine Open-Source-Java-Klassenbibliothek, die uns nicht nur verschiedene Arten von Diagrammen bietet, sondern auch viele nützliche Algorithmen zur Lösung der am häufigsten auftretenden Diagrammprobleme.

In diesem Artikel erfahren Sie, wie Sie verschiedene Diagrammtypen erstellen und wie bequem es ist, die bereitgestellten Dienstprogramme zu verwenden.

2. Maven-Abhängigkeit

Beginnen wir mit dem Hinzufügen der Abhängigkeit zu unserem Maven-Projekt:

 org.jgrapht jgrapht-core 1.0.1 

Die neueste Version finden Sie im Maven Central.

3. Diagramme erstellen

JGraphT unterstützt verschiedene Arten von Diagrammen.

3.1. Einfache Grafiken

Lassen Sie uns zunächst ein einfaches Diagramm mit einem Scheitelpunkt vom Typ String erstellen :

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

3.2. Gerichtete / ungerichtete Diagramme

Es ermöglicht uns auch, gerichtete / ungerichtete Diagramme zu erstellen.

In unserem Beispiel erstellen wir ein gerichtetes Diagramm und verwenden es, um andere Dienstprogrammfunktionen und -algorithmen zu demonstrieren:

DirectedGraph directedGraph = new DefaultDirectedGraph(DefaultEdge.class); directedGraph.addVertex("v1"); directedGraph.addVertex("v2"); directedGraph.addVertex("v3"); directedGraph.addEdge("v1", "v2"); // Add remaining vertices and edges

3.3. Vollständige Grafiken

In ähnlicher Weise können wir auch ein vollständiges Diagramm erstellen:

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

3.4. Multi-Graphen

Neben einfachen Diagrammen bietet uns die API auch Multigraphen (Diagramme mit mehreren Pfaden zwischen zwei Scheitelpunkten).

Außerdem können wir in jedem Diagramm gewichtete / ungewichtete oder benutzerdefinierte Kanten haben.

Erstellen wir einen Multigraph mit gewichteten Kanten:

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); }

Darüber hinaus können wir nicht modifizierbare (schreibgeschützte) und hörbare (ermöglicht externen Listenern, Änderungen zu verfolgen) sowie Untergraphen haben. Außerdem können wir immer alle Kompositionen dieser Diagramme erstellen.

Weitere API-Details finden Sie hier.

4. API-Algorithmen

Nachdem wir nun vollständige Fledge-Graph-Objekte haben, schauen wir uns einige häufig auftretende Probleme und deren Lösungen an.

4.1. Graph Iteration

Wir können das Diagramm mit verschiedenen Iteratoren wie BreadthFirstIterator , DepthFirstIterator , ClosestFirstIterator und RandomWalkIterator gemäß den Anforderungen durchlaufen .

Wir müssen lediglich eine Instanz der jeweiligen Iteratoren erstellen, indem wir Diagrammobjekte übergeben:

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

Sobald wir die Iteratorobjekte erhalten haben, können wir die Iteration mit den Methoden hasNext () und next () durchführen .

4.2. Den kürzesten Weg finden

Es bietet Implementierungen verschiedener Algorithmen wie Dijkstra, Bellman-Ford, Astar und FloydWarshall im Paket org.jgrapht.alg.shortestpath .

Finden wir den kürzesten Weg mit dem Dijkstra-Algorithmus:

@Test public void whenGetDijkstraShortestPath_thenGetNotNullPath() { DijkstraShortestPath dijkstraShortestPath = new DijkstraShortestPath(directedGraph); List shortestPath = dijkstraShortestPath .getPath("v1","v4").getVertexList(); assertNotNull(shortestPath); }

Um den kürzesten Weg mit dem Bellman-Ford-Algorithmus zu ermitteln:

@Test public void whenGetBellmanFordShortestPath_thenGetNotNullPath() { BellmanFordShortestPath bellmanFordShortestPath = new BellmanFordShortestPath(directedGraph); List shortestPath = bellmanFordShortestPath .getPath("v1", "v4") .getVertexList(); assertNotNull(shortestPath); }

4.3. Suche nach stark verbundenen Untergraphen

Bevor wir mit der Implementierung beginnen, schauen wir uns kurz an, was stark verbundene Untergraphen bedeuten. Ein Untergraph wird nur dann als stark verbunden bezeichnet, wenn zwischen jedem Paar seiner Eckpunkte ein Pfad besteht.

In unserem Beispiel kann {v1, v2, v3, v4} als stark verbundener Teilgraph betrachtet werden, wenn wir unabhängig von dem aktuellen Scheitelpunkt zu einem beliebigen Scheitelpunkt wechseln können.

Wir können vier solcher Untergraphen für den im obigen Bild gezeigten gerichteten Graphen auflisten:

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

Implementierung zur Auflistung aller stark verbundenen Untergraphen:

@Test public void whenGetStronglyConnectedSubgraphs_thenPathExists() { StrongConnectivityAlgorithm scAlg = new KosarajuStrongConnectivityInspector(directedGraph); List
    
      stronglyConnectedSubgraphs = scAlg.stronglyConnectedSubgraphs(); List stronglyConnectedVertices = new ArrayList(stronglyConnectedSubgraphs.get(3) .vertexSet()); String randomVertex1 = stronglyConnectedVertices.get(0); String randomVertex2 = stronglyConnectedVertices.get(3); AllDirectedPaths allDirectedPaths = new AllDirectedPaths(directedGraph); List
     
       possiblePathList = allDirectedPaths.getAllPaths( randomVertex1, randomVertex2, false, stronglyConnectedVertices.size()); assertTrue(possiblePathList.size() > 0); }
     
    

4.4. Eulersche Schaltung

A Eulerian Circuit in a graph G is a circuit that includes all vertices and edges of G. A graph which has it is a Eulerian Graph.

Let's have a look at the graph:

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); }); }

Now, we can test whether a graph contains Eulerian Circuit using the API:

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

4.5. Hamiltonian Circuit

A GraphPath that visits each vertex exactly once is known as Hamiltonian Path.

A Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian Path such that there is an edge (in the graph) from the last vertex to the first vertex of the path.

We can find optimal Hamiltonian Cycle for complete graph with HamiltonianCycle.getApproximateOptimalForCompleteGraph() method.

This method will return an approximate minimal traveling salesman tour (Hamiltonian cycle). The optimal solution is NP-complete, so this is a decent approximation that runs in polynomial time:

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

4.6. Cycle Detector

We can also check if there are any cycles in the graph. Currently, CycleDetector only supports directed graphs:

@Test public void whenCheckCycles_thenDetectCycles() { CycleDetector cycleDetector = new CycleDetector(directedGraph); assertTrue(cycleDetector.detectCycles()); Set cycleVertices = cycleDetector.findCycles(); assertTrue(cycleVertices.size() > 0); }

5. Graph Visualization

JGraphT allows us to generate visualizations of graphs and save them as images, first let's add the jgrapht-ext extension dependency from Maven Central:

 org.jgrapht jgrapht-ext 1.0.1 

Next, let's create a simple directed graph with 3 vertices and 3 edges:

@Before public void createGraph() { File imgFile = new File("src/test/resources/graph.png"); imgFile.createNewFile(); DefaultDirectedGraph g = new 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 can now visualize this graph:

@Test public void givenAdaptedGraph_whenWriteBufferedImage_thenFileShouldExist() throws IOException { JGraphXAdapter graphAdapter = new JGraphXAdapter(g); mxIGraphLayout layout = new mxCircleLayout(graphAdapter); layout.execute(graphAdapter.getDefaultParent()); BufferedImage image = mxCellRenderer.createBufferedImage(graphAdapter, null, 2, Color.WHITE, true, null); File imgFile = new File("src/test/resources/graph.png"); ImageIO.write(image, "PNG", imgFile); assertTrue(imgFile.exists()); }

Hier haben wir einen JGraphXAdapter erstellt, der unser Diagramm als Konstruktorargument empfängt, und wir haben ein mxCircleLayout darauf angewendet . Dadurch wird die Visualisierung kreisförmig dargestellt.

Darüber hinaus verwenden wir eine mxCellRenderer ein erstellen BufferedImage und dann die Visualisierung zu einer PNG - Datei schreiben.

Wir können das endgültige Bild in einem Browser oder unserem Lieblingsrenderer sehen:

Weitere Details finden Sie in der offiziellen Dokumentation.

6. Fazit

JGraphT bietet nahezu alle Arten von Diagrammen und eine Vielzahl von Diagrammalgorithmen. Wir haben erläutert, wie Sie einige beliebte APIs verwenden. Sie können die Bibliothek jedoch jederzeit auf der offiziellen Seite erkunden.

Die Implementierung all dieser Beispiele und Codefragmente finden Sie auf Github.