Introduction à JGraphT

1. Vue d'ensemble

La plupart du temps, lorsque nous implémentons des algorithmes basés sur des graphes, nous devons également implémenter certaines fonctions utilitaires.

JGraphT est une bibliothèque de classes Java open source qui nous fournit non seulement divers types de graphiques, mais également de nombreux algorithmes utiles pour résoudre les problèmes de graphes les plus fréquemment rencontrés.

Dans cet article, nous verrons comment créer différents types de graphiques et à quel point il est pratique d'utiliser les utilitaires fournis.

2. Dépendance de Maven

Commençons par ajouter la dépendance à notre projet Maven:

 org.jgrapht jgrapht-core 1.0.1 

La dernière version est disponible sur le Maven Central.

3. Création de graphiques

JGraphT prend en charge différents types de graphiques.

3.1. Graphiques simples

Pour commencer, créons un graphique simple avec un sommet de type String :

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

3.2. Graphiques dirigés / non dirigés

Cela nous permet également de créer des graphiques dirigés / non dirigés.

Dans notre exemple, nous allons créer un graphe orienté et l'utiliser pour démontrer d'autres fonctions et algorithmes utilitaires:

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. Graphiques complets

De même, nous pouvons également générer un graphique complet:

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-graphes

Outre les graphes simples, l'API nous fournit également des multigraphes (graphes avec plusieurs chemins entre deux sommets).

En outre, nous pouvons avoir des arêtes pondérées / non pondérées ou définies par l'utilisateur dans n'importe quel graphique.

Créons un multigraphe avec des arêtes pondérées:

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

En plus de cela, nous pouvons avoir des graphiques non modifiables (lecture seule) et écoutables (permet aux écouteurs externes de suivre les modifications) ainsi que des sous-graphiques. De plus, nous pouvons toujours créer toutes les compositions de ces graphiques.

Vous trouverez plus de détails sur l'API ici.

4. Algorithmes API

Maintenant que nous avons des objets graphiques complets, examinons quelques problèmes courants et leurs solutions.

4.1. Itération de graphe

Nous pouvons parcourir le graphique en utilisant divers itérateurs tels que BreadthFirstIterator , DepthFirstIterator , ClosestFirstIterator , RandomWalkIterator selon les besoins.

Nous devons simplement créer une instance d'itérateurs respectifs en passant des objets graphiques:

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

Une fois que nous obtenons les objets itérateur, nous pouvons effectuer l'itération en utilisant les méthodes hasNext () et next () .

4.2. Trouver le chemin le plus court

Il fournit des implémentations de divers algorithmes tels que Dijkstra, Bellman-Ford, Astar et FloydWarshall dans le package org.jgrapht.alg.shortestpath .

Trouvons le chemin le plus court en utilisant l'algorithme de Dijkstra:

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

De même, pour obtenir le chemin le plus court à l'aide de l'algorithme Bellman-Ford:

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

4.3. Recherche de sous-graphes fortement connectés

Avant d'entrer dans l'implémentation, examinons brièvement ce que signifient les sous-graphes fortement connectés. Un sous-graphe est dit fortement connecté uniquement s'il existe un chemin entre chaque paire de ses sommets.

Dans notre exemple, {v1, v2, v3, v4} peut être considéré comme un sous-graphe fortement connecté si nous pouvons traverser vers n'importe quel sommet quel que soit le sommet actuel.

Nous pouvons lister quatre de ces sous-graphiques pour le graphe orienté montré dans l'image ci-dessus:

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

Implémentation pour lister tous les sous-graphes fortement connectés:

@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. Circuit eulérien

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

Ici, nous avons créé un JGraphXAdapter qui reçoit notre graphe en tant qu'argument du constructeur et nous lui avons appliqué un mxCircleLayout . Cela présente la visualisation de manière circulaire.

De plus, nous utilisons un mxCellRenderer pour créer un BufferedImage , puis écrire la visualisation dans un fichier png.

Nous pouvons voir l'image finale dans un navigateur ou notre moteur de rendu préféré:

Nous pouvons trouver plus de détails dans la documentation officielle.

6. Conclusion

JGraphT fournit presque tous les types de graphiques et une variété d'algorithmes de graphes. Nous avons expliqué comment utiliser quelques API populaires. Cependant, vous pouvez toujours explorer la bibliothèque sur la page officielle.

L'implémentation de tous ces exemples et extraits de code peut être trouvée sur Github.