Lần theo kiểu dữ liệu đã biến mất

Tìm kiểu dữ liệu bị thiếu

• Đồ thị là một tập hợp các nút, được kết nối bằng các mũi tên (cạnh).
• Nút và cạnh có thể chứa dữ liệu.
• Trong kỹ thuật phần mềm, đồ thị xuất hiện dưới nhiều dạng như phụ thuộc gói, liên kết Internet, không gian trạng thái của phần mềm, cơ sở dữ liệu quan hệ, danh sách liên kết, cây nhị phân, bảng băm, v.v.
• Trong logic nghiệp vụ, đồ thị cũng được dùng cho tham chiếu trích dẫn, mạng lưới giao thông, mạng xã hội, v.v.
• Nếu làm phát triển phần mềm đủ lâu, rất có thể bạn sẽ gặp đồ thị ở khắp mọi nơi.

Suy nghĩ về việc dùng đồ thị

• Đồ thị rất hữu ích, nhưng việc sử dụng đồ thị trong mã thực tế lại khá nặng nề.
• Trong phần lớn các ngôn ngữ chủ đạo, đồ thị không được hỗ trợ như một kiểu dựng sẵn; ngay cả trong thư viện chuẩn cũng hiếm thấy, và số thư viện bên thứ ba đủ vững chắc cũng không nhiều.
• Trong nhiều trường hợp, bạn phải tự cài đặt đồ thị.
• Có một khoảng cách giữa tần suất mà kỹ sư phần mềm có thể dùng đồ thị và mức độ hỗ trợ dành cho nó trong hệ sinh thái lập trình.

Vì sao không có kiểu đồ thị

Có quá nhiều lựa chọn về thiết kế

• Có rất nhiều loại đồ thị khác nhau: đồ thị có hướng và vô hướng, đồ thị đơn và đa đồ thị, siêu đồ thị, ubergraph, v.v.
• Với từng loại, còn phải quyết định có gán ID cho nút và cạnh hay không, sẽ lưu kiểu dữ liệu nào, v.v.
• Một thư viện đồ thị hoàn hảo hỗ trợ mọi khả năng sẽ tốn rất nhiều thời gian để xây dựng.
• Hiệu năng của các thuật toán đồ thị rất quan trọng, và các trường hợp đặc thù cũng rất quan trọng.
• Các thuật toán đồ thị rất khó cài đặt cho đúng.

Có quá nhiều lựa chọn về cách triển khai

• Ngay cả khi chỉ giả sử hỗ trợ một đồ thị có hướng đơn giản, vẫn có nhiều cách để biểu diễn đồ thị ở bên trong.
• Có nhiều cách lưu trữ như danh sách cạnh, danh sách kề, ma trận kề, tập hợp các struct, v.v.
• Những phép toán đồ thị khác nhau sẽ có đặc tính hiệu năng khác nhau tùy theo cách biểu diễn.
• Tùy vào độ thưa hay độ dày của đồ thị mà cách biểu diễn nội bộ tối ưu sẽ khác nhau.
• Việc triển khai dữ liệu của nút, dữ liệu của cạnh, cũng như nhiều kiểu nút và cạnh khác nhau còn làm mọi thứ phức tạp hơn.

Hiệu năng quá quan trọng

• Nhiều thuật toán đồ thị là bài toán NP-đầy đủ hoặc còn khó hơn.
• Đồ thị có thể trở thành những bài toán cực lớn, và hiệu năng có thể khác biệt rất nhiều tùy theo cách biểu diễn và chi tiết cài đặt thuật toán.
• Cần có nhiều quyền kiểm soát đối với biểu diễn dữ liệu và thuật toán.

Quan điểm thống nhất

• Sự đa dạng của loại đồ thị, cách biểu diễn, thuật toán, độ nhạy với hiệu năng, và chi phí chạy các thuật toán đắt đỏ trên đồ thị lớn là những lý do khiến hỗ trợ cho đồ thị không phổ biến rộng rãi.
• Điều này giải thích vì sao các ngôn ngữ không hỗ trợ đồ thị trong thư viện chuẩn.
• Điều này cũng giải thích vì sao lập trình viên thường tránh các thư viện đồ thị bên thứ ba.
• Vì dùng đồ thị là việc khó, nên trừ những trường hợp cực đoan, người ta không muốn phải suy nghĩ theo hướng đồ thị.

Ý kiến của GN⁺

• Bài viết này mang lại góc nhìn về lý do vì sao đồ thị chưa trở thành một kiểu dữ liệu cơ bản trong ngôn ngữ lập trình và thư viện.
• Lý thuyết đồ thị là một lĩnh vực quan trọng của khoa học máy tính và được ứng dụng trong nhiều mảng như thuật toán, phân tích mạng, cơ sở dữ liệu, v.v.
• Để sử dụng đồ thị hiệu quả, tối ưu hiệu năng và lựa chọn cấu trúc dữ liệu phù hợp là rất quan trọng.
• Một số thư viện bên thứ ba như NetworkX, Boost Graph Library, Graph-tool có thể được dùng để giải quyết nhiều bài toán đồ thị khác nhau.
• Khi dùng đồ thị, điều quan trọng là chọn loại đồ thị và thuật toán phù hợp với đặc tính của bài toán, vì điều này ảnh hưởng trực tiếp đến hiệu năng của hệ thống.

[GN⁺]

Ý kiến trên Hacker News

• Graphviz có thư viện đồ thị riêng của mình, và thư viện này không được dùng trong các dự án khác. Thư viện đó có cả ưu và nhược điểm.

  • Dựa trên trải nghiệm này, họ đã gặp phải chính phiên bản "hội chứng hệ thống thứ hai" của mình.
  • Họ đi đến kết luận rằng thư viện đồ thị phải có tính mô-đun, an toàn kiểu và hiệu quả. Đây có thể là một biến thể của câu "tốt, nhanh, rẻ - hãy chọn hai".
  • Tính mô-đun có nghĩa là họ muốn viết một bộ các thư viện thuật toán đồ thị được phát triển và biên dịch độc lập.
  • An toàn kiểu có nghĩa là họ muốn phát hiện lỗi lập trình khi biên dịch hoặc chậm nhất là khi liên kết. Họ không muốn lỗi thời gian chạy.
  • Hiệu quả có nghĩa là việc truy cập các thuộc tính của đồ thị phải rẻ như truy cập một trường trong struct C.
  • Có thể tranh cãi liệu những mục tiêu này có đáng giá hay không, nhưng đó là điều họ muốn. Vì những người tạo ra C++ nổi tiếng đang ở trong phòng thí nghiệm của họ, họ kỳ vọng có thể nhận được sự giúp đỡ và quyết định cho C++ thêm một cơ hội nữa.
  • Gordon Woodhull, một cựu thực tập sinh, là một lập trình viên xuất sắc, đã triển khai loại thư viện đồ thị này bằng template C++. Nó đã được phát hành qua sourceforge tại https://www.dynagraph.org/.
  • Vì không chắc người khác có thể hiểu được cách mã hoạt động, họ đã thực hiện review code với những nhà phát minh C++ nổi tiếng. Họ nhận ra rằng có thể mình đã bước qua bờ vực của sự phức tạp.
  • Đây không phải lỗi của Gordon, và anh ấy tiếp tục cắm cúi làm việc, thậm chí còn thành công với bố cục đồ thị động trong Microsoft OLE. Nhìn lại, đây có thể là Project Xanadu của riêng họ.
  • Trong lúc họ mải mê với việc này, rất nhiều thứ khác đã xuất hiện như Gephi (Java) và NetworkX cùng NetworKit (Python).
  • John Ellson là một kỹ sư phần mềm rất tài năng, người đã viết một phần của Graphviz, và đã hồi sinh nỗ lực cốt lõi.

• Nếu bạn lập trình trên .NET, tôi khuyên nên thử Arborescence, một thư viện đồ thị nhỏ và không quá nhiều tính năng.

  • Tôi tin rằng thư viện này mang lại sự tách biệt tốt giữa trừu tượng, thuật toán và cấu trúc dữ liệu.
  • Người dùng có thể dùng edge với ID riêng, hoặc dùng đồ thị ngầm được mở rộng tại chỗ.
  • Có thể dùng cả interface adjacency (các hàng xóm theo hướng ra ngoài) và incidence (các edge đi ra + đỉnh đích).
  • Thư viện không ép buộc kiểu edge, nhưng cung cấp cấu trúc cặp tail-head cơ bản như một tiện ích.

• Đồ thị không phải là cấu trúc dữ liệu hay kiểu dữ liệu, mà là một phép trừu tượng.

  • Về cơ bản, những gì cần để định nghĩa một đồ thị chỉ là tập đỉnh và hàm lân cận.
  • Mọi thứ khác đều là các ràng buộc theo từng trường hợp.
  • Nếu xét hypergraph, thì đồ thị chỉ đơn giản là một trường hợp đặc biệt.
  • Nếu suy nghĩ từ góc nhìn cơ sở dữ liệu, đồ thị là một bài toán tối ưu hóa truy vấn và lập chỉ mục.

• Tôi đã nhận được rất nhiều câu hỏi về lý do không có kiểu dữ liệu đồ thị được tích hợp sẵn trong ngôn ngữ lập trình.

  • Giờ tôi rất vui vì có thể chỉ họ đến những phân tích sâu hơn như bài viết này.

• Trở ngại trung tâm là như sau:

  • Với các bài toán đồ thị đơn giản và nhỏ, việc tự viết adjacency list bằng vector của vector là đủ dễ.
  • Với các bài toán đồ thị phức tạp và khổng lồ, không có cách nào đạt hiệu năng ngoài việc tùy biến cách triển khai đồ thị cho đúng với bài toán.
  • Không rõ kiểu hỗ trợ nào từ ngôn ngữ sẽ thực sự hữu ích.

• Bài viết này phần lớn trả lời câu hỏi vì sao thuật toán đồ thị không được hỗ trợ tốt hơn trong ngôn ngữ lập trình.

  • Nếu nhìn rộng hơn vào hỗ trợ cho đồ thị nói chung, ta sẽ thấy những câu hỏi lớn hơn như vì sao OGM không phổ biến bằng ORM, hay vì sao JSON được dùng rộng rãi hơn RDF.
  • Cuối cùng, vì các lý do lịch sử và sự phức tạp của đồ thị, nó không mở rộng tốt trong cộng đồng nhà phát triển.

• Các công cụ vẽ đồ thị cũng rất đáng thất vọng.

  • Với đồ thị có hơn 500 node, đầu ra trở nên khó hiểu hoặc quá rối rắm.
  • Chúng thiếu khả năng tự động tổ chức đồ thị thành cấu trúc phân cấp và cung cấp giao diện tốt để duyệt khám phá.

• Bài viết này thực sự rất hay.

  • Về quan sát cốt lõi rằng "có quá nhiều lựa chọn triển khai", thực ra không hẳn vậy.
  • Trên thực tế, thư viện có thể triển khai mọi biểu diễn đồ thị phù hợp.
  • Có thể tùy biến thuật toán theo biểu diễn và chuyển đổi từ biểu diễn này sang biểu diễn khác.

• Electric Clojure dùng chính Clojure (s-expression) làm cú pháp để biên soạn đồ thị.

  • Một DSL biên soạn đồ thị phải biểu đạt phạm vi, luồng điều khiển và phép trừu tượng, và về bản chất điều này cũng giống như một ngôn ngữ lập trình.

• Có một kiểu dữ liệu hữu ích khác giống như bảng, chẳng hạn bảng trong cơ sở dữ liệu.

  • Sẽ có tiến bộ trong ngôn ngữ lập trình nếu để compiler chọn cách triển khai cấu trúc dữ liệu.
  • Dùng các cấu trúc trừu tượng như sequence, map, set, table, graph... rồi để compiler chọn cách triển khai cụ thể dựa trên profile của chương trình.