Grafik di Jawa

1. Ikhtisar

Dalam tutorial ini, kita akan memahami konsep dasar grafik sebagai struktur data .

Kami juga akan mengeksplorasi implementasinya di Java bersama dengan berbagai operasi yang mungkin dilakukan pada grafik. Kami juga akan membahas pustaka Java yang menawarkan implementasi grafik.

2. Grafik Struktur Data

Grafik adalah struktur data untuk menyimpan data yang terhubung seperti jaringan orang di platform media sosial.

Grafik terdiri dari simpul dan tepi. Sebuah simpul mewakili entitas (misalnya, orang) dan tepi mewakili hubungan antar entitas (misalnya, persahabatan seseorang).

Mari tentukan Grafik sederhana untuk memahami ini lebih baik:

Di sini, kami telah mendefinisikan grafik sederhana dengan lima simpul dan enam sisi. Lingkaran adalah simpul yang mewakili orang dan garis yang menghubungkan dua simpul adalah tepi yang mewakili teman di portal online.

Ada beberapa variasi dari grafik sederhana ini tergantung pada properti tepinya. Mari kita bahas secara singkat di bagian selanjutnya.

Namun, kami hanya akan fokus pada grafik sederhana yang disajikan di sini untuk contoh Java dalam tutorial ini.

2.1. Grafik Berarah

Grafik yang kita definisikan sejauh ini memiliki tepi tanpa arah apa pun. Jika tepi ini memiliki arah di dalamnya , grafik yang dihasilkan dikenal sebagai grafik berarah.

Contohnya dapat mewakili siapa yang mengirimkan permintaan pertemanan dalam pertemanan di portal online:

Di sini, kita dapat melihat bahwa tepinya memiliki arah yang tetap. Tepinya juga bisa dua arah.

2.2. Grafik Tertimbang

Sekali lagi, grafik sederhana kami memiliki tepi yang tidak bias atau tidak berbobot. Jika sebaliknya tepi - tepi ini memiliki bobot relatif , grafik ini dikenal sebagai grafik berbobot.

Contoh penerapan praktis dari ini dapat mewakili seberapa lama persahabatan di portal online:

Di sini, kita dapat melihat bahwa tepi memiliki bobot yang terkait dengannya. Ini memberikan arti relatif ke tepi-tepi ini.

3. Representasi Grafik

Grafik dapat direpresentasikan dalam berbagai bentuk seperti matriks kedekatan dan daftar kedekatan. Masing-masing memiliki pro dan kontra dalam pengaturan yang berbeda.

Kami akan memperkenalkan representasi grafik ini di bagian ini.

3.1. Matriks Adjacency

Matriks ketetanggaan adalah matriks bujur sangkar dengan dimensi yang setara dengan jumlah simpul pada grafik.

Elemen matriks biasanya memiliki nilai '0' atau '1'. Nilai '1' menunjukkan kedekatan antara simpul di baris dan kolom dan nilai '0' jika tidak.

Mari kita lihat bagaimana matriks ketetanggaan terlihat untuk grafik sederhana kita dari bagian sebelumnya:

Representasi ini cukup mudah diterapkan dan efisien untuk melakukan kueri juga. Namun, ini kurang efisien sehubungan dengan ruang yang ditempati .

3.2. Daftar Adjacency

Daftar kedekatan tidak lain adalah serangkaian daftar . Ukuran larik sama dengan jumlah simpul pada grafik.

Daftar pada indeks tertentu dari larik mewakili simpul yang berdekatan dari simpul yang diwakili oleh indeks larik tersebut.

Mari kita lihat seperti apa daftar kedekatan untuk grafik sederhana kita dari bagian sebelumnya:

Representasi ini relatif sulit dibuat dan kurang efisien untuk membuat kueri . Namun, ini menawarkan efisiensi ruang yang lebih baik .

Kami akan menggunakan daftar kedekatan untuk mewakili grafik dalam tutorial ini.

4. Grafik di Jawa

Java tidak memiliki implementasi default dari struktur data grafik.

Namun, kami dapat menerapkan grafik menggunakan Koleksi Java.

Mari kita mulai dengan mendefinisikan sebuah simpul:

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

Definisi simpul di atas hanya menampilkan label tetapi ini dapat mewakili entitas apa pun yang mungkin seperti Orang atau Kota.

Juga, perhatikan bahwa kita harus mengganti metode equals () dan hashCode () karena ini diperlukan untuk bekerja dengan Java Collections.

Seperti yang telah kita bahas sebelumnya, grafik tidak lain adalah kumpulan simpul dan tepi yang dapat direpresentasikan sebagai matriks ketetanggaan atau daftar ketetanggaan.

Mari kita lihat bagaimana kita dapat mendefinisikan ini menggunakan daftar kedekatan di sini:

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

Seperti yang bisa kita lihat di sini, Graph kelas menggunakan Map from Java Collections untuk menentukan daftar kedekatan.

Ada beberapa operasi yang mungkin dilakukan pada struktur data grafik, seperti membuat, memperbarui, atau menelusuri melalui grafik .

Kami akan membahas beberapa operasi yang lebih umum dan melihat bagaimana kami dapat menerapkannya di 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.

Library ini menyediakan sejumlah implementasi berdasarkan struktur data grafik. Ada juga kerangka kerja yang lebih kuat berdasarkan grafik , seperti Apache Giraph, yang saat ini digunakan di Facebook untuk menganalisis grafik yang dibentuk oleh penggunanya, dan Apache TinkerPop, yang biasa digunakan di atas database grafik.

8. Kesimpulan

Pada artikel ini, kita membahas grafik sebagai struktur data beserta representasinya. Kami mendefinisikan grafik yang sangat sederhana di Java menggunakan Koleksi Java dan juga mendefinisikan traversal umum untuk grafik tersebut.

Kami juga berbicara secara singkat tentang berbagai pustaka yang tersedia di Java di luar platform Java yang menyediakan implementasi grafik.

Seperti biasa, kode untuk contoh tersedia di GitHub.