Графики на Java

1. Обзор

В этом руководстве мы поймем основные концепции графа как структуры данных .

Мы также рассмотрим его реализацию на Java вместе с различными операциями, возможными на графике. Мы также обсудим библиотеки Java, предлагающие реализации графов.

2. Структура данных графика

Граф - это структура данных для хранения связанных данных, таких как сеть людей в социальной сети.

Граф состоит из вершин и ребер. Вершина представляет объект (например, людей), а край представляет отношения между объектами (например, дружбу человека).

Давайте определим простой график, чтобы лучше понять это:

Здесь мы определили простой граф с пятью вершинами и шестью ребрами. Круги - это вершины, представляющие людей, а линии, соединяющие две вершины, - ребра, представляющие друзей на онлайн-портале.

Есть несколько вариантов этого простого графа в зависимости от свойств ребер. Давайте кратко рассмотрим их в следующих разделах.

Однако мы сосредоточимся только на простом графике, представленном здесь для примеров Java в этом руководстве.

2.1. Направленный график

У графа, который мы до сих пор определили, есть ребра без направления. Если эти ребра имеют направление , результирующий граф называется ориентированным графом.

Примером этого может быть тот, кто отправил запрос дружбы на онлайн-портале:

Здесь мы видим, что ребра имеют фиксированное направление. Края также могут быть двунаправленными.

2.2. Взвешенный график

Опять же, у нашего простого графа есть несмещенные или невзвешенные ребра. Если вместо этого эти ребра несут относительный вес , этот граф известен как взвешенный граф.

Примером практического применения этого может быть представление о том, сколько лет дружбе на онлайн-портале:

Здесь мы видим, что с ребрами связаны веса. Это придает относительное значение этим краям.

3. Графические представления

Граф может быть представлен в различных формах, таких как матрица смежности и список смежности. У каждого из них есть свои плюсы и минусы в разных настройках.

Мы представим эти графические представления в этом разделе.

3.1. Матрица смежности

Матрица смежности - это квадратная матрица с размерами, эквивалентными количеству вершин в графе.

Элементы матрицы обычно имеют значения «0» или «1». Значение «1» указывает на смежность между вершинами в строке и столбце, а значение «0» в противном случае.

Давайте посмотрим, как выглядит матрица смежности для нашего простого графа из предыдущего раздела:

Это представление довольно просто реализовать, и оно также эффективно для запросов . Однако он менее эффективен в отношении занимаемого места .

3.2. Список смежности

Список смежности - это не что иное, как массив списков . Размер массива эквивалентен количеству вершин в графе.

Список с определенным индексом массива представляет смежные вершины вершины, представленной этим индексом массива.

Давайте посмотрим, как выглядит список смежности для нашего простого графика из предыдущего раздела:

Это представление сравнительно сложно создать и менее эффективно для запроса . Однако он предлагает лучшую экономию пространства .

Мы будем использовать список смежности для представления графика в этом руководстве.

4. Графики на Java

В Java нет стандартной реализации структуры данных графа.

Однако мы можем реализовать граф с помощью Java Collections.

Начнем с определения вершины:

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

Вышеупомянутое определение вершины просто имеет метку, но она может представлять любую возможную сущность, такую ​​как Человек или Город.

Также обратите внимание, что мы должны переопределить методы equals () и hashCode (), поскольку они необходимы для работы с коллекциями Java.

Как мы обсуждали ранее, граф - это не что иное, как набор вершин и ребер, которые могут быть представлены либо как матрица смежности, либо как список смежности.

Давайте посмотрим, как мы можем определить это, используя список смежности здесь:

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

Как мы видим здесь, класс Graph использует карту из коллекций Java для определения списка смежности.

Есть несколько операций, которые возможны со структурой данных графа, такие как создание, обновление или поиск по графу .

Мы рассмотрим некоторые из наиболее распространенных операций и посмотрим, как мы можем реализовать их на 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.

Эти библиотеки предоставляют ряд реализаций на основе структуры данных графа. Существуют также более мощные фреймворки, основанные на графах , такие как Apache Giraph, который в настоящее время используется в Facebook для анализа графа, сформированного их пользователями, и Apache TinkerPop, обычно используемый поверх графовых баз данных.

8. Заключение

В этой статье мы обсудили граф как структуру данных вместе с ее представлениями. Мы определили очень простой граф в Java, используя Java Collections, а также определили общие обходы для графа.

Мы также кратко поговорили о различных библиотеках, доступных в Java за пределами платформы Java, которые предоставляют реализации графов.

Как всегда, код примеров доступен на GitHub.