Lý thuyết đồ thị trong Ruby

Đối với mỗi developers không ít lần chúng ta từng nghe đến lý thuyết về đồ thị, bài viết dưới đây sẽ giới thiệu cơ bản về cách sử dụng trong Ruby.

Có lẽ bạn đã từng nghe nói đến cây nhị phân

Điều này có nghĩa là một cây nhị phân chỉ là một phiên bản đặc biệt của một graph, từ đó bạn sẽ có thể thấy được ý tưởng về việc mở rộng đồ thị như thế nào.

Hãy bắt đầu bằng một cái nhìn tổng quát về các nguyên lý cơ bản của đồ thị, sau đó sẽ thấy ứng dụng thực tế và làm sao để thực thi nó trong Ruby.

Các nguyên lý cơ bản của đồ thị

Một đồ thị bao gồm 2 yếu tố

• Nodes (hay còn gọi là đỉnh)
• Edges (cạnh, nối các đỉnh với nhau)

Một node sẽ biểu thị một phần tử trong biểu đồ, ví dụ với một biểu đồ mô tả bản đồ thì các node là một thành phố hoặc tên một con phố. Trong khi các cạnh là đại diện cho sự kết nối giữa các nodes.

Khi bạn nhìn vào một cuốn sách khoa học máy tính hoặc về toán học thì bạn sẽ thấy một đồ thị sẽ được định nghĩa theo công thức này: G(V, E), trong đó G có nghĩa là graph, V là vertices (nodes, đỉnh) và E là edges (cạnh)

Graph có thể được định hướng hoặc không được định hướng, nó có nghĩa là bạn có thể đi theo một hướng hướng (như đường một chiều) hoặc có thể đi theo hai hướng (như đường 2 chiều).

Loại phổ biến nhất của đồ thị là Directed Acyclic Graph (DAG)(biểu đồ đường vòng được định hướng). Acyclic có nghĩa là không có vòng lặp, không có cách nào để quay trở lại

Sử dụng đồ thị

Chúng ta đã thấy được tổng quan về đồ thị ở trên kia, bây giờ sẽ xem một số cách sử dụng phổ biến cho đồ thị

Sử dụng graph bạn có thể làm những việc như:

• Tìm đường dẫn ngắn nhất (hoặc dài nhất) giữa hai vị trí
• Kiểm tra xem 2 điều gì đó có liên quan đến nhau hay không
• Phân tích sự phụ thuộc
• Hay là tìm ra con đường ngắn nhất đến đích

Cách thực thi và sử dụng đồ thị

Bạn có thể tự viết cách hiện thị graph cho chính bạn, nhưng trong bài này chúng ta sẽ sử dụng một gem có sẵn để thực thi chúng. Đó chính là gem RGL

Để tạo một biểu đồ cơ bản với RGl chúng ta làm như sau:

require 'rgl/adjacency'
 
graph = RGL::DirectedAdjacencyGraph.new
 
graph.add_edge 1,2
graph.add_edge 3,4
graph.add_edge 1,4
graph.add_edge 4,3

require 'rgl/dot'
dg.write_to_graphic_file('jpg')

Code trên sẽ xây dựng một graph như sau

Hoặc bạn có thể lấy graph theo dạng dot và copy kết quả vào site có thực thi dot language như GraphvizOnline và xem kết quả

require 'rgl/dot'
 
graph.print_dotted_on

Bây giờ chúng ta đã có một đồ thị, và chúng ta sẽ bắt đầu tìm hiểu nó Chúng ta có hai thuật toán cơ bản để search trong đồ thị của bạn

• Breadth-First Search (BFS) - tìm kiếm theo chiều ngang
• Depth-First Search (DFS) - tìm kiếm theo chiều sâu

Trong thuật toán BFS bạn sẽ nhận được các nodes gần nhất và trong DFS bạn đi càng sâu càng tốt trong mỗi node. Thuật toán này có thể được thực thi bằng cách sử dụng stack

Và nếu sử dụng gem GRL thì nó đã thực hiện hết điều này cho bạn

require 'rgl/traversal'
 
graph.bfs_iterator.to_a
# [1, 2, 4, 3]
 
graph.dfs_iterator.to_a
# [1, 4, 3, 2]

Nhìn vào kết quả và bản đồ có được trên kia, bạn sẽ hình dung ra được những gì nó đã làm.

Các đồ thị có trọng số

Chúng ta có thể thêm các thông tin vào trong graph dưới dạng các trọng số để làm cho nó hữu ích hơn Các trọng số được định nghĩa cho các edges(cạnh) là các đường dẫn giữa 2 nodes. Các trọng số này là đại diện cho chi phí để đi từ điểm này đến điểm khác.

Ví dụ, chúng ta có bản đồ của một quốc gia ở dạng đồ thị và chúng tôi muốn đi đến một điểm trong thời gian ngắn nhất có thể, thì trọng số ở đây sẽ thể hiện khoảng cách giữa 2 thành phố.

Dưới đây là một ví dụ về đồ thị có trọng số

graph = RGL::DirectedAdjacencyGraph.new
graph.add_vertices "Los Angeles", "New York", "Chicago", "Houston", "Seattle"
 
edge_weights =
{
  ["New York", "Los Angeles"] => 2445,
  ["Los Angeles", "Chicago"] => 2015,
  ["Los Angeles", "Houston"] => 1547,
  ["Chicago", "Houston"] => 939,
  ["Seattle", "Los Angeles"] => 1548
}
 
edge_weights.each { |(city1, city2), w| graph.add_edge(city1, city2) }

Tìm đường đi ngắn nhất

Thuật toán phổ biến để tìm đường dẫn ngắn nhất bên trong một đồ thị là thuật toán Dijkstra’s Shortest Path

Với một đồ thị có trọng số, chúng ta có thể dụng thuật toán Dijkstra để giải quyết câu hỏi này.

Sử dụng RGL gem ta sẽ dễ dàng có kết quả cho câu hỏi, con đường nhanh nhất để đi từ điểm A đến B là gì. Ví dụ là đường đi ngắn nhất từ New York tới Houston là gì.

p graph.dijkstra_shortest_path(edge_weights, "New York", "Houston")
# ["New York", "Los Angeles", "Houston"]

Dự vào các thông tin có trong đồ thị ta sẽ có được đường đi ngắn nhất như trên.

Tổng kết

Ở trên đã giới thiệu tổng quát cho bạn về cấu trúc dữ liệu đồ thị và sử dụng nó như thế nào với RGL gem. Bạn cũng đã học được về các thuật toán phổ biến để làm việc với đồ thị như là BFS, DFS, hay Dijkstra’s. Qua đó có thể vận dụng giải quyết các vấn đề về khoa học máy tính trong ứng dụng của bạn.