Graphiques en Java

1. Vue d'ensemble

Dans ce didacticiel, nous allons comprendre les concepts de base d'un graphique en tant que structure de données .

Nous explorerons également son implémentation en Java ainsi que diverses opérations possibles sur un graphe. Nous discuterons également des bibliothèques Java proposant des implémentations de graphes.

2. Structure des données du graphique

Un graphique est une structure de données permettant de stocker des données connectées comme un réseau de personnes sur une plateforme de médias sociaux.

Un graphe se compose de sommets et d'arêtes. Un sommet représente l'entité (par exemple, les personnes) et un bord représente la relation entre les entités (par exemple, les amitiés d'une personne).

Définissons un graphique simple pour mieux comprendre cela:

Ici, nous avons défini un graphe simple avec cinq sommets et six arêtes. Les cercles sont des sommets représentant des personnes et les lignes reliant deux sommets sont des arêtes représentant des amis sur un portail en ligne.

Il existe quelques variantes de ce graphique simple en fonction des propriétés des arêtes. Passons-les brièvement en revue dans les sections suivantes.

Cependant, nous nous concentrerons uniquement sur le graphique simple présenté ici pour les exemples Java de ce didacticiel.

2.1. Graphique dirigé

Le graphique que nous avons défini jusqu'à présent a des arêtes sans aucune direction. Si ces arêtes comportent une direction , le graphe résultant est appelé graphe orienté.

Un exemple de ceci peut être de représenter qui envoie la demande d'amitié dans une amitié sur le portail en ligne:

Ici, nous pouvons voir que les arêtes ont une direction fixe. Les bords peuvent également être bidirectionnels.

2.2. Graphique pondéré

Encore une fois, notre graphique simple a des arêtes non biaisées ou non pondérées. Si à la place ces arêtes ont un poids relatif , ce graphique est connu sous le nom de graphique pondéré.

Un exemple d'application pratique de ceci peut être la représentation de l'âge relatif d'une amitié sur le portail en ligne:

Ici, nous pouvons voir que les arêtes ont des poids qui leur sont associés. Cela donne une signification relative à ces bords.

3. Représentations graphiques

Un graphique peut être représenté sous différentes formes comme une matrice de contiguïté et une liste de contiguïté. Chacun a ses avantages et ses inconvénients dans une configuration différente.

Nous présenterons ces représentations graphiques dans cette section.

3.1. Matrice d'adjacence

Une matrice de contiguïté est une matrice carrée de dimensions équivalentes au nombre de sommets du graphe.

Les éléments de la matrice ont généralement les valeurs «0» ou «1». Une valeur de «1» indique la contiguïté entre les sommets de la ligne et de la colonne et une valeur de «0» dans le cas contraire.

Voyons à quoi ressemble la matrice de contiguïté pour notre graphique simple de la section précédente:

Cette représentation est relativement plus facile à implémenter et efficace à interroger également. Cependant, c'est moins efficace par rapport à l'espace occupé .

3.2. Liste de proximité

Une liste de contiguïté n'est rien d'autre qu'un tableau de listes . La taille du tableau équivaut au nombre de sommets du graphe.

La liste à un index spécifique du tableau représente les sommets adjacents du sommet représenté par cet index de tableau.

Voyons à quoi ressemble la liste de contiguïté pour notre graphique simple de la section précédente:

Cette représentation est relativement difficile à créer et moins efficace à interroger . Cependant, il offre une meilleure efficacité de l'espace .

Nous utiliserons la liste de contiguïté pour représenter le graphique dans ce tutoriel.

4. Graphiques en Java

Java n'a pas d'implémentation par défaut de la structure de données du graphe.

Cependant, nous pouvons implémenter le graphe à l'aide des collections Java.

Commençons par définir un sommet:

class Vertex { String label; Vertex(String label) { this.label = label; } // equals and hashCode }

La définition ci-dessus du sommet ne comporte qu'une étiquette, mais cela peut représenter n'importe quelle entité possible comme Person ou City.

Notez également que nous devons remplacer les méthodes equals () et hashCode () car elles sont nécessaires pour travailler avec les collections Java.

Comme nous l'avons vu précédemment, un graphe n'est rien d'autre qu'une collection de sommets et d'arêtes qui peuvent être représentés comme une matrice de contiguïté ou une liste de contiguïté.

Voyons comment nous pouvons définir cela en utilisant une liste de contiguïté ici:

class Graph { private Map
    
      adjVertices; // standard constructor, getters, setters }
    

Comme nous pouvons le voir ici, la classe Graph utilise Map from Java Collections pour définir la liste de contiguïté.

Il existe plusieurs opérations possibles sur une structure de données de graphique, telles que la création, la mise à jour ou la recherche dans le graphique .

Nous allons passer en revue certaines des opérations les plus courantes et voir comment nous pouvons les implémenter en Java.

5. Opérations de mutation de graphe

Pour commencer, nous allons définir quelques méthodes pour muter la structure des données du graphe.

Définissons des méthodes pour ajouter et supprimer des sommets:

void addVertex(String label) { adjVertices.putIfAbsent(new Vertex(label), new ArrayList()); } void removeVertex(String label) { Vertex v = new Vertex(label); adjVertices.values().stream().forEach(e -> e.remove(v)); adjVertices.remove(new Vertex(label)); }

Ces méthodes ajoutent et suppriment simplement des éléments de l' ensemble de sommets .

Maintenant, définissons également une méthode pour ajouter une arête:

void addEdge(String label1, String label2) { Vertex v1 = new Vertex(label1); Vertex v2 = new Vertex(label2); adjVertices.get(v1).add(v2); adjVertices.get(v2).add(v1); }

Cette méthode crée une nouvelle arête et met à jour la carte des sommets adjacents .

De la même manière, nous définirons la méthode removeEdge () :

void removeEdge(String label1, String label2) { Vertex v1 = new Vertex(label1); Vertex v2 = new Vertex(label2); List eV1 = adjVertices.get(v1); List eV2 = adjVertices.get(v2); if (eV1 != null) eV1.remove(v2); if (eV2 != null) eV2.remove(v1); }

Ensuite, voyons comment nous pouvons créer le graphique simple que nous avons dessiné plus tôt en utilisant les méthodes que nous avons définies jusqu'à présent:

Graph createGraph() { Graph graph = new Graph(); graph.addVertex("Bob"); graph.addVertex("Alice"); graph.addVertex("Mark"); graph.addVertex("Rob"); graph.addVertex("Maria"); graph.addEdge("Bob", "Alice"); graph.addEdge("Bob", "Rob"); graph.addEdge("Alice", "Mark"); graph.addEdge("Rob", "Mark"); graph.addEdge("Alice", "Maria"); graph.addEdge("Rob", "Maria"); return graph; }

Nous allons enfin définir une méthode pour obtenir les sommets adjacents d'un sommet particulier:

List getAdjVertices(String label) { return adjVertices.get(new Vertex(label)); }

6. Traverser un graphique

Now that we have graph data structure and functions to create and update it defined, we can define some additional functions for traversing the graph. We need to traverse a graph to perform any meaningful action, like search within the graph.

There are two possible ways to traverse a graph, depth-first traversal and breadth-first traversal.

6.1. Depth-First Traversal

A depth-first traversal starts at an arbitrary root vertex and explores vertices as deeper as possible along each branch before exploring vertices at the same level.

Let's define a method to perform the depth-first traversal:

Set depthFirstTraversal(Graph graph, String root) { Set visited = new LinkedHashSet(); Stack stack = new Stack(); stack.push(root); while (!stack.isEmpty()) { String vertex = stack.pop(); if (!visited.contains(vertex)) { visited.add(vertex); for (Vertex v : graph.getAdjVertices(vertex)) { stack.push(v.label); } } } return visited; }

Here, we're using a Stack to store the vertices that need to be traversed.

Let's run this on the graph we created in the previous subsection:

assertEquals("[Bob, Rob, Maria, Alice, Mark]", depthFirstTraversal(graph, "Bob").toString());

Please note that we're using vertex “Bob” as our root for traversal here, but this can be any other vertex.

6.2. Breadth-First Traversal

Comparatively, a breadth-first traversal starts at an arbitrary root vertex and explores all neighboring vertices at the same level before going deeper in the graph.

Now let's define a method to perform the breadth-first traversal:

Set breadthFirstTraversal(Graph graph, String root) { Set visited = new LinkedHashSet(); Queue queue = new LinkedList(); queue.add(root); visited.add(root); while (!queue.isEmpty()) { String vertex = queue.poll(); for (Vertex v : graph.getAdjVertices(vertex)) { if (!visited.contains(v.label)) { visited.add(v.label); queue.add(v.label); } } } return visited; }

Note that a breadth-first traversal makes use of Queue to store the vertices which need to be traversed.

Let's again run this traversal on the same graph:

assertEquals( "[Bob, Alice, Rob, Mark, Maria]", breadthFirstTraversal(graph, "Bob").toString());

Again, the root vertex which is “Bob” here can as well be any other vertex.

7. Java Libraries for Graphs

It's not necessary to always implement the graph from scratch in Java. There are several open source and mature libraries available which offers graph implementations.

In the next few subsections, we'll go through some of these libraries.

7.1. JGraphT

JGraphT is one of the most popular libraries in Java for the graph data structure. It allows the creation of a simple graph, directed graph, weighted graph, amongst others.

Additionally, it offers many possible algorithms on the graph data structure. One of our previous tutorials covers JGraphT in much more detail.

7.2. Google Guava

Google Guava is a set of Java libraries that offer a range of functions including graph data structure and its algorithms.

It supports creating simple Graph, ValueGraph, and Network. These can be defined as Mutable or Immutable.

7.3. Apache Commons

Apache Commons is an Apache project that offers reusable Java components. This includes Commons Graph which offers a toolkit to create and manage graph data structure. This also provides common graph algorithms to operate on the data structure.

7.4. Sourceforge JUNG

Java Universal Network/Graph (JUNG) is a Java framework that provides extensible language for modeling, analysis, and visualization of any data that can be represented as a graph.

JUNG supports a number of algorithms which includes routines like clustering, decomposition, and optimization.

Ces bibliothèques fournissent un certain nombre d'implémentations basées sur la structure de données du graphe. Il existe également des frameworks plus puissants basés sur des graphiques , tels que Apache Giraph, actuellement utilisé sur Facebook pour analyser le graphique formé par leurs utilisateurs, et Apache TinkerPop, couramment utilisé en plus des bases de données de graphiques.

8. Conclusion

Dans cet article, nous avons abordé le graphe en tant que structure de données avec ses représentations. Nous avons défini un graphe très simple en Java à l'aide de collections Java et également défini des traversées communes pour le graphe.

Nous avons également parlé brièvement de diverses bibliothèques disponibles en Java en dehors de la plate-forme Java qui fournit des implémentations de graphes.

Comme toujours, le code des exemples est disponible à l'adresse over sur GitHub.