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 Collections.
Както обсъждахме по-рано, графика не е нищо друго освен колекция от върхове и ребра, които могат да бъдат представени като матрица на съседство или списък на съседство.
Нека да видим как можем да дефинираме това, като използваме списък за съседство тук:
class Graph { private Map
adjVertices; // standard constructor, getters, setters }
Както виждаме тук, класът Graph използва Map от Java Collections, за да дефинира списъка на съседство.
Възможни са няколко операции върху структурата на данните на графика, като създаване, актуализиране или търсене в графиката .
Ще преминем през някои от най-често срещаните операции и ще видим как можем да ги приложим в 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.