กราฟใน Java

1. ภาพรวม

ในการกวดวิชานี้เราจะเข้าใจแนวคิดพื้นฐานของกราฟเป็นโครงสร้างข้อมูล

นอกจากนี้เราจะสำรวจการใช้งานใน Java พร้อมกับการดำเนินการต่างๆที่เป็นไปได้บนกราฟ เราจะพูดถึงไลบรารี Java ที่นำเสนอการใช้งานกราฟ

2. โครงสร้างข้อมูลกราฟ

กราฟเป็นโครงสร้างข้อมูลสำหรับจัดเก็บข้อมูลที่เชื่อมต่อกันเช่นเครือข่ายของผู้คนบนแพลตฟอร์มโซเชียลมีเดีย

กราฟประกอบด้วยจุดยอดและขอบ จุดยอดหมายถึงเอนทิตี (ตัวอย่างเช่นคน) และขอบหมายถึงความสัมพันธ์ระหว่างเอนทิตี (ตัวอย่างเช่นมิตรภาพของบุคคล)

มากำหนดกราฟง่ายๆเพื่อทำความเข้าใจสิ่งนี้ให้ดีขึ้น:

ที่นี่เราได้กำหนดกราฟง่ายๆโดยมีจุดยอดห้าจุดและหกขอบ วงกลมคือจุดยอดที่แสดงถึงบุคคลและเส้นที่เชื่อมต่อจุดยอดสองจุดคือขอบที่แสดงถึงเพื่อนบนพอร์ทัลออนไลน์

กราฟอย่างง่ายนี้มีรูปแบบต่าง ๆ ขึ้นอยู่กับคุณสมบัติของขอบ เรามาดูกันสั้น ๆ ในหัวข้อถัดไป

อย่างไรก็ตามเราจะเน้นเฉพาะกราฟง่ายๆที่นำเสนอที่นี่สำหรับตัวอย่าง Java ในบทช่วยสอนนี้

2.1. กราฟกำกับ

กราฟที่เรากำหนดไว้จนถึงตอนนี้มีขอบที่ไม่มีทิศทางใด ๆ หากขอบเหล่านี้มีทิศทางอยู่ในนั้นกราฟที่ได้จะเรียกว่ากราฟกำกับ

ตัวอย่างนี้สามารถแสดงให้เห็นว่าใครเป็นผู้ส่งคำขอเป็นเพื่อนด้วยมิตรภาพบนพอร์ทัลออนไลน์:

ที่นี่เราจะเห็นว่าขอบมีทิศทางคงที่ ขอบสามารถเป็นแบบสองทิศทางได้เช่นกัน

2.2. กราฟถ่วงน้ำหนัก

อีกครั้งกราฟง่ายๆของเรามีขอบที่ไม่เอนเอียงหรือไม่ถ่วงน้ำหนัก หากขอบเหล่านี้มีน้ำหนักสัมพัทธ์แทนกราฟนี้เรียกว่ากราฟถ่วงน้ำหนัก

ตัวอย่างของการประยุกต์ใช้ในทางปฏิบัตินี้สามารถแสดงให้เห็นถึงความเก่าแก่ของมิตรภาพบนพอร์ทัลออนไลน์:

ที่นี่เราจะเห็นว่าขอบมีน้ำหนักสัมพันธ์กัน สิ่งนี้ให้ความหมายสัมพัทธ์กับขอบเหล่านี้

3. การแสดงกราฟ

กราฟสามารถแสดงในรูปแบบต่างๆเช่นเมทริกซ์ adjacency และรายการ adjacency แต่ละคนมีข้อดีข้อเสียในการตั้งค่าที่แตกต่างกัน

เราจะแนะนำการแสดงกราฟเหล่านี้ในส่วนนี้

3.1. เมทริกซ์ Adjacency

เมทริกซ์ adjacency คือเมทริกซ์สี่เหลี่ยมที่มีขนาดเทียบเท่ากับจำนวนจุดยอดในกราฟ

โดยทั่วไปองค์ประกอบของเมทริกซ์จะมีค่าเป็น "0" หรือ "1" ค่า '1' หมายถึงความใกล้ชิดระหว่างจุดยอดในแถวและคอลัมน์และค่า '0' มิฉะนั้น

มาดูกันว่าเมทริกซ์ adjacency มีลักษณะอย่างไรสำหรับกราฟอย่างง่ายของเราจากส่วนก่อนหน้า:

การเป็นตัวแทนนี้ค่อนข้างง่ายต่อการนำไปใช้และมีประสิทธิภาพในการสืบค้นเช่นกัน แต่ก็มีประสิทธิภาพน้อยลงเกี่ยวกับการครอบครองพื้นที่

3.2. รายการ Adjacency

รายการถ้อยคำคืออะไร แต่อาร์เรย์ของรายการ ขนาดของอาร์เรย์เทียบเท่ากับจำนวนจุดยอดในกราฟ

รายการที่ดัชนีเฉพาะของอาร์เรย์แสดงถึงจุดยอดที่อยู่ติดกันของจุดยอดที่แสดงโดยดัชนีอาร์เรย์นั้น

มาดูกันว่ารายการ adjacency จะเป็นอย่างไรสำหรับกราฟง่ายๆของเราจากส่วนก่อนหน้า:

การแสดงนี้เป็นเปรียบเทียบยากที่จะสร้างและมีประสิทธิภาพน้อยลงในแบบสอบถาม แต่ก็มีประสิทธิภาพในพื้นที่ดีขึ้น

เราจะใช้รายการ adjacency เพื่อแสดงกราฟในบทช่วยสอนนี้

4. กราฟใน Java

Java ไม่มีการใช้งานโครงสร้างข้อมูลกราฟโดยปริยาย

อย่างไรก็ตามเราสามารถใช้กราฟโดยใช้ Java Collections

เริ่มต้นด้วยการกำหนดจุดยอด:

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

คำจำกัดความข้างต้นของจุดยอดเป็นเพียงป้ายกำกับ แต่สามารถแสดงถึงเอนทิตีที่เป็นไปได้เช่นบุคคลหรือเมือง

นอกจากนี้โปรดทราบว่าเราต้องแทนที่เมธอดequals ()และhashCode ()เนื่องจากสิ่งเหล่านี้จำเป็นในการทำงานกับ Java Collections

ดังที่เราได้กล่าวไปก่อนหน้านี้กราฟไม่ได้เป็นเพียงแค่การรวบรวมจุดยอดและขอบซึ่งสามารถแสดงเป็นเมทริกซ์การปรับตัวหรือรายการการปรับ

มาดูกันว่าเราจะกำหนดสิ่งนี้โดยใช้ adjacency list ได้อย่างไร:

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

ดังที่เราเห็นที่นี่คลาสGraphกำลังใช้Mapจาก Java Collections เพื่อกำหนดรายการ adjacency

มีการดำเนินการเป็นไปได้ในหลายโครงสร้างข้อมูลกราฟเช่นสร้างอัปเดตหรือการค้นหาผ่านกราฟ

เราจะพูดถึงการดำเนินการทั่วไปและดูว่าเราจะนำไปใช้ใน 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