Grafice în Java

1. Prezentare generală

În acest tutorial, vom înțelege conceptele de bază ale unui grafic ca structură de date .

De asemenea, vom explora implementarea acestuia în Java, împreună cu diverse operațiuni posibile pe un grafic. De asemenea, vom discuta despre bibliotecile Java care oferă implementări de grafice.

2. Structura datelor grafice

Un grafic este o structură de date pentru stocarea datelor conectate, cum ar fi o rețea de oameni pe o platformă de socializare.

Un grafic este format din vârfuri și muchii. Un vârf reprezintă entitatea (de exemplu, oameni) și o margine reprezintă relația dintre entități (de exemplu, prietenia unei persoane).

Să definim un grafic simplu pentru a înțelege mai bine acest lucru:

Aici, am definit un grafic simplu cu cinci vârfuri și șase margini. Cercurile sunt vârfuri care reprezintă oameni, iar liniile care leagă două vârfuri sunt margini reprezentând prieteni pe un portal online.

Există câteva variații ale acestui grafic simplu, în funcție de proprietățile marginilor. Să le parcurgem pe scurt în secțiunile următoare.

Cu toate acestea, ne vom concentra doar pe graficul simplu prezentat aici pentru exemplele Java din acest tutorial.

2.1. Grafic regizat

Graficul pe care l-am definit până acum are margini fără nicio direcție. Dacă aceste margini prezintă o direcție în ele , graficul rezultat este cunoscut sub numele de grafic direcționat.

Un exemplu în acest sens poate fi reprezentarea celor care trimit cererea de prietenie într-o prietenie pe portalul online:

Aici, putem vedea că marginile au o direcție fixă. Marginile pot fi și bidirecționale.

2.2. Grafic ponderat

Din nou, graficul nostru simplu are muchii care sunt imparțiale sau neponderate. Dacă în schimb aceste muchii au greutate relativă , acest grafic este cunoscut sub numele de grafic ponderat.

Un exemplu de aplicare practică a acestui lucru poate fi reprezentarea cât de vechi este o prietenie pe portalul online:

Aici, putem vedea că marginile au greutăți asociate cu ele. Aceasta oferă o semnificație relativă acestor margini.

3. Reprezentări grafice

Un grafic poate fi reprezentat în diferite forme, cum ar fi matricea de adiacență și lista de adiacențe. Fiecare are avantajele și dezavantajele sale într-un set diferit.

Vom introduce aceste reprezentări grafice în această secțiune.

3.1. Matricea adiacenței

O matrice de adiacență este o matrice pătrată cu dimensiuni echivalente cu numărul de vârfuri din grafic.

Elementele matricei au de obicei valori '0' sau '1'. O valoare „1” indică adiacența între vârfurile din rând și coloană și o valoare „0” în caz contrar.

Să vedem cum arată matricea de adiacență pentru graficul nostru simplu din secțiunea anterioară:

Această reprezentare este destul de ușor de implementat și de interogat eficient. Cu toate acestea, este mai puțin eficient în ceea ce privește spațiul ocupat .

3.2. Lista adiacenței

O listă de adiacență nu este altceva decât o serie de liste . Dimensiunea matricei este echivalentă cu numărul de vârfuri din grafic.

Lista la un indice specific al tabloului reprezintă vârfurile adiacente ale vârfului reprezentat de acel index al matricei.

Să vedem cum arată lista de adiacențe pentru graficul nostru simplu din secțiunea anterioară:

Această reprezentare este relativ dificil de creat și mai puțin eficientă pentru interogare . Cu toate acestea, oferă o eficiență spațială mai bună .

Vom folosi lista de adiacențe pentru a reprezenta graficul din acest tutorial.

4. Grafice în Java

Java nu are o implementare implicită a structurii datelor grafice.

Cu toate acestea, putem implementa graficul folosind Java Collections.

Să începem prin definirea unui vârf:

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

Definiția de mai sus a vertexului conține doar o etichetă, dar aceasta poate reprezenta orice entitate posibilă, cum ar fi Persoana sau Orașul.

De asemenea, rețineți că trebuie să înlocuim metodele equals () și hashCode () deoarece acestea sunt necesare pentru a lucra cu Java Collections.

După cum am discutat mai devreme, un grafic nu este altceva decât o colecție de vârfuri și muchii care pot fi reprezentate fie ca o matrice de adiacență, fie ca o listă de adiacențe.

Să vedem cum putem defini acest lucru folosind o listă de adiacențe aici:

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

După cum putem vedea aici, clasa Graph utilizează Harta din colecțiile Java pentru a defini lista de adiacențe.

Există mai multe operații posibile pe o structură de date a graficului, cum ar fi crearea, actualizarea sau căutarea prin grafic .

Vom parcurge unele dintre cele mai frecvente operațiuni și vom vedea cum le putem implementa în 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.

Aceste biblioteci oferă o serie de implementări bazate pe structura datelor grafice. Există, de asemenea, cadre mai puternice bazate pe grafice , cum ar fi Apache Giraph, utilizat în prezent la Facebook pentru a analiza graficul format de utilizatorii lor și Apache TinkerPop, utilizat în mod obișnuit în baza de date a graficului.

8. Concluzie

În acest articol, am discutat graficul ca o structură de date împreună cu reprezentările sale. Am definit un grafic foarte simplu în Java folosind colecțiile Java și am definit, de asemenea, traversări comune pentru grafic.

De asemenea, am vorbit pe scurt despre diferite biblioteci disponibile în Java în afara platformei Java care oferă implementări grafice.

Ca întotdeauna, codul pentru exemple este disponibil pe GitHub.