1. Información general
En este tutorial, entenderemos los conceptos básicos de un gráfico como estructura de datos .
También exploraremos su implementación en Java junto con varias operaciones posibles en un gráfico. También discutiremos las bibliotecas de Java que ofrecen implementaciones de gráficos.
2. Estructura de datos del gráfico
Un gráfico es una estructura de datos para almacenar datos conectados como una red de personas en una plataforma de redes sociales.
Un gráfico consta de vértices y aristas. Un vértice representa la entidad (por ejemplo, personas) y un borde representa la relación entre entidades (por ejemplo, las amistades de una persona).
Definamos un gráfico simple para entender esto mejor:
Aquí, hemos definido un gráfico simple con cinco vértices y seis aristas. Los círculos son vértices que representan personas y las líneas que conectan dos vértices son bordes que representan amigos en un portal en línea.
Hay algunas variaciones de este gráfico simple dependiendo de las propiedades de los bordes. Repasemos brevemente en las siguientes secciones.
Sin embargo, solo nos centraremos en el gráfico simple que se presenta aquí para los ejemplos de Java en este tutorial.
2.1. Gráfico dirigido
El gráfico que hemos definido hasta ahora tiene bordes sin dirección. Si estos bordes presentan una dirección en ellos , el gráfico resultante se conoce como gráfico dirigido.
Un ejemplo de esto puede ser representar quién envía la solicitud de amistad en una amistad en el portal en línea:
Aquí, podemos ver que los bordes tienen una dirección fija. Los bordes también pueden ser bidireccionales.
2.2. Gráfico ponderado
Nuevamente, nuestro gráfico simple tiene bordes que son insesgados o no ponderados. Si, en cambio, estos bordes tienen un peso relativo , este gráfico se conoce como gráfico ponderado.
Un ejemplo de una aplicación práctica de esto puede ser representar qué tan relativamente antigua es una amistad en el portal en línea:
Aquí, podemos ver que los bordes tienen pesos asociados a ellos. Esto proporciona un significado relativo a estos bordes.
3. Representaciones gráficas
Un gráfico se puede representar en diferentes formas como matriz de adyacencia y lista de adyacencia. Cada uno tiene sus pros y sus contras en una configuración diferente.
Introduciremos estas representaciones gráficas en esta sección.
3.1. Matriz de adyacencia
Una matriz de adyacencia es una matriz cuadrada con dimensiones equivalentes al número de vértices del gráfico.
Los elementos de la matriz suelen tener valores '0' o '1'. Un valor de '1' indica adyacencia entre los vértices en la fila y columna y un valor de '0' en caso contrario.
Veamos cómo se ve la matriz de adyacencia para nuestro gráfico simple de la sección anterior:
Esta representación es bastante más fácil de implementar y eficiente de consultar . Sin embargo, es menos eficiente con respecto al espacio ocupado .
3.2. Lista de adyacencia
Una lista de adyacencia no es más que una matriz de listas . El tamaño de la matriz es equivalente al número de vértices del gráfico.
La lista en un índice específico de la matriz representa los vértices adyacentes del vértice representado por ese índice de matriz.
Veamos cómo se ve la lista de adyacencia para nuestro gráfico simple de la sección anterior:
Esta representación es comparativamente difícil de crear y menos eficiente de consultar . Sin embargo, ofrece una mejor eficiencia de espacio .
Usaremos la lista de adyacencia para representar el gráfico en este tutorial.
4. Gráficos en Java
Java no tiene una implementación predeterminada de la estructura de datos del gráfico.
Sin embargo, podemos implementar el gráfico utilizando colecciones de Java.
Comencemos por definir un vértice:
class Vertex { String label; Vertex(String label) { this.label = label; } // equals and hashCode }La definición anterior de vértice solo presenta una etiqueta, pero esto puede representar cualquier entidad posible como Persona o Ciudad.
Además, tenga en cuenta que tenemos que anular los métodos equals () y hashCode () ya que son necesarios para trabajar con las colecciones de Java.
Como comentamos anteriormente, un gráfico no es más que una colección de vértices y aristas que se pueden representar como una matriz de adyacencia o una lista de adyacencia.
Veamos cómo podemos definir esto usando una lista de adyacencia aquí:
class Graph { private Map
adjVertices; // standard constructor, getters, setters }
Como podemos ver aquí, la clase Graph está usando Map from Java Collections para definir la lista de adyacencia.
Hay varias operaciones posibles en la estructura de datos de un gráfico, como crear, actualizar o buscar en el gráfico .
Repasaremos algunas de las operaciones más comunes y veremos cómo podemos implementarlas en 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.
Estas bibliotecas proporcionan una serie de implementaciones basadas en la estructura de datos del gráfico. También hay marcos más potentes basados en gráficos , como Apache Giraph, que se utiliza actualmente en Facebook para analizar el gráfico formado por sus usuarios, y Apache TinkerPop, que se utiliza comúnmente en la parte superior de las bases de datos de gráficos.
8. Conclusión
En este artículo, discutimos el gráfico como una estructura de datos junto con sus representaciones. Definimos un gráfico muy simple en Java usando colecciones de Java y también definimos recorridos comunes para el gráfico.
También hablamos brevemente sobre varias bibliotecas disponibles en Java fuera de la plataforma Java que proporciona implementaciones de gráficos.
Como siempre, el código de los ejemplos está disponible en GitHub.