Grafici in Java

1. Panoramica

In questo tutorial, comprenderemo i concetti di base di un grafico come struttura dati .

Esploreremo anche la sua implementazione in Java insieme a varie operazioni possibili su un grafico. Discuteremo anche delle librerie Java che offrono implementazioni grafiche.

2. Struttura dei dati del grafico

Un grafico è una struttura dati per memorizzare dati connessi come una rete di persone su una piattaforma di social media.

Un grafo è costituito da vertici e bordi. Un vertice rappresenta l'entità (ad esempio, le persone) e un bordo rappresenta la relazione tra le entità (ad esempio, le amicizie di una persona).

Definiamo un semplice grafico per capirlo meglio:

Qui, abbiamo definito un semplice grafo con cinque vertici e sei bordi. I cerchi sono vertici che rappresentano le persone e le linee che collegano due vertici sono bordi che rappresentano gli amici su un portale online.

Ci sono alcune variazioni di questo semplice grafico a seconda delle proprietà dei bordi. Esaminiamoli brevemente nelle prossime sezioni.

Tuttavia, ci concentreremo solo sul semplice grafico presentato qui per gli esempi Java in questo tutorial.

2.1. Grafico diretto

Il grafico che abbiamo definito finora ha bordi senza alcuna direzione. Se questi bordi presentano una direzione in essi , il grafico risultante è noto come grafico diretto.

Un esempio di questo può essere rappresentare chi invia la richiesta di amicizia in un'amicizia sul portale online:

Qui possiamo vedere che i bordi hanno una direzione fissa. Anche i bordi possono essere bidirezionali.

2.2. Grafico ponderato

Ancora una volta, il nostro grafico semplice ha bordi che sono imparziali o non ponderati. Se invece questi bordi hanno un peso relativo , questo grafico è noto come grafico ponderato.

Un esempio di un'applicazione pratica di questo può essere rappresentare quanto sia relativamente vecchia un'amicizia sul portale online:

Qui, possiamo vedere che ai bordi sono associati dei pesi. Ciò fornisce un significato relativo a questi bordi.

3. Rappresentazioni grafiche

Un grafico può essere rappresentato in diverse forme come matrice di adiacenza e lista di adiacenza. Ognuno ha i suoi pro e contro in una diversa configurazione.

In questa sezione introdurremo queste rappresentazioni grafiche.

3.1. Matrice di adiacenza

Una matrice di adiacenza è una matrice quadrata con dimensioni equivalenti al numero di vertici nel grafo.

Gli elementi della matrice hanno in genere valori "0" o "1". Un valore "1" indica l'adiacenza tra i vertici nella riga e nella colonna e un valore "0" in caso contrario.

Vediamo come appare la matrice di adiacenza per il nostro semplice grafico della sezione precedente:

Questa rappresentazione è abbastanza più facile da implementare ed efficiente anche da interrogare . Tuttavia, è meno efficiente rispetto allo spazio occupato .

3.2. Elenco di adiacenza

Un elenco di adiacenza non è altro che un array di elenchi . La dimensione della matrice è equivalente al numero di vertici nel grafico.

The list at a specific index of the array represents the adjacent vertices of the vertex represented by that array index.

Let's see what the adjacency list looks like for our simple graph from the previous section:

This representation is comparatively difficult to create and less efficient to query. However, it offers better space efficiency.

We'll use the adjacency list to represent the graph in this tutorial.

4. Graphs in Java

Java doesn't have a default implementation of the graph data structure.

However, we can implement the graph using Java Collections.

Let's begin by defining a vertex:

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

The above definition of vertex just features a label but this can represent any possible entity like Person or City.

Also, note that we have to override the equals() and hashCode() methods as these are necessary to work with Java Collections.

As we discussed earlier, a graph is nothing but a collection of vertices and edges which can be represented as either an adjacency matrix or an adjacency list.

Let's see how we can define this using an adjacency list here:

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

As we can see here, the class Graph is using Map from Java Collections to define the adjacency list.

There are several operations possible on a graph data structure, such as creating, updating or searching through the graph.

We'll go through some of the more common operations and see how we can implement them in Java.

5. Graph Mutation Operations

To start with, we'll define some methods to mutate the graph data structure.

Let's define methods to add and remove vertices:

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

These methods simply add and remove elements from the vertices Set.

Now, let's also define a method to add an edge:

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

This method creates a new Edge and updates the adjacent vertices Map.

In a similar way, we'll define the removeEdge() method:

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

Next, let's see how we can create the simple graph we have drawn earlier using the methods we've defined so far:

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

We'll finally define a method to get the adjacent vertices of a particular vertex:

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

6. Traversing a Graph

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.

Queste librerie forniscono una serie di implementazioni basate sulla struttura dei dati del grafico. Esistono anche framework più potenti basati su grafici , come Apache Giraph, attualmente utilizzato su Facebook per analizzare il grafico formato dai propri utenti, e Apache TinkerPop, comunemente usato sopra i database di grafici.

8. Conclusione

In questo articolo, abbiamo discusso il grafico come una struttura di dati insieme alle sue rappresentazioni. Abbiamo definito un grafico molto semplice in Java utilizzando Java Collections e definito anche attraversamenti comuni per il grafico.

Abbiamo anche parlato brevemente di varie librerie disponibili in Java al di fuori della piattaforma Java che fornisce implementazioni grafiche.

Come sempre, il codice per gli esempi è disponibile su GitHub.