Tại sao cấu trúc dữ liệu C++ cho biểu đồ ẩn chỉ số nguyên liền kề?

Question

Cấu trúc dữ liệu cho các đồ thị có hướng và không bị giới hạn có tầm quan trọng cơ bản. Các triển khai nổi tiếng và được sử dụng rộng rãi như Boost Graph Library và Lemon được thiết kế sao cho các chỉ số nguyên tiếp giáp của các nút và cạnh không được tiếp xúc với người dùng thông qua giao diện.

Thay vào đó, người dùng xác định các nút và cạnh bằng các đối tượng đại diện (nhỏ). Một ưu điểm là các đối tượng này được cập nhật tự động khi các chỉ mục của các nút và các cạnh thay đổi do việc loại bỏ các cạnh hoặc các nút khỏi biểu đồ.

Theo ý kiến ​​của tôi (!), Lợi thế này bị đánh giá quá cao. Người dùng thường sẽ lưu trữ các đối tượng đại diện của các nút và/hoặc các cạnh trong một vùng chứa, ví dụ: std::vector. Bây giờ, nếu các nút hoặc các cạnh được loại bỏ khỏi đồ thị và các đối tượng đại diện của chúng trở nên không hợp lệ, người dùng cần bỏ qua hoặc sắp xếp lại vectơ để giữ các chỉ số nguyên hợp nhau, nghĩa là, thực hiện chính xác sổ kế toán mà thiết kế được cho là làm cho không cần thiết.

Do đó, câu hỏi của tôi là: Lựa chọn thiết kế (ẩn các chỉ số nguyên liền kề của các nút và cạnh từ người dùng) có lợi thế khác không?

Answer 1

Tôi không thể nói cho biểu đồ Lemon, nhưng đối với biểu đồ tăng tôi nghĩ mục tiêu chính là chung chung. Vì vậy, trừu tượng đi truy cập đỉnh (cạnh) giúp đạt được mục tiêu đó.

Điều này được nêu trong tài liệu làm tăng biểu đồ dựa trên Luận văn Thạc sĩ của Dietmar Kühl về thuật toán đồ thị chung. (Xem câu trả lời của tôi cho Do property maps remain necessary for BGL?). Vì vậy, mục tiêu chính đằng sau thư viện là để được chung chung và mở rộng. Việc lựa chọn truy cập đóng gói là một phần của việc tóm tắt các thuật toán từ biểu diễn biểu đồ. Đối với tôi, chỉ số nguyên liên tục là chi tiết triển khai.

Tăng cường không đưa ra bất kỳ giả định nào về cách bạn sẽ sử dụng biểu đồ hoặc mức độ giao dịch hiệu suất nào quan trọng đối với bạn. Nó cho phép bạn chọn (hoặc triển khai) vùng chứa phù hợp nhất với nhu cầu của bạn.

Nếu bạn muốn ngắt đóng gói này, bạn được tự do làm như vậy. Thực tế, việc sử dụng đồ thị tăng cường phổ biến nhất của tôi bao gồm các thùng chứa vecS và vector trong số struct s. Tôi thường làm việc với các đồ thị có kích thước cố định. Tôi có thể dễ dàng sử dụng một số map của vertex_descriptor s (hoặc edge_descriptor s) cho các đối tượng để đạt được cùng một mục tiêu.

Vì vậy, tóm lại, tôi sẽ nói rằng đây không phải là một sự lựa chọn thiết kế, mà là hậu quả của việc đạt được mục tiêu rộng hơn là chung chung. Vì vậy, việc ẩn quyền truy cập có lợi ích chung chung hơn.

Answer 2

_{(Tôi đang ở nhà trong thế giới Java, nhưng hy vọng rằng nó là OK để đưa ra một câu trả lời mà không được tập trung vào các thư viện đặc biệt trong câu hỏi)}

Có một số lợi thế có thể xảy ra như một trừu tượng. Một trong những điều quan trọng nhất đã được đề cập trong câu hỏi: Sự nhất quán khi thực hiện sửa đổi trong biểu đồ khó thực hiện hơn khi chỉ số phải được duy trì.

Lý do tại sao này có thể là những lời dối trá cứng trong cơ quan đại diện có thể đồ thị khác nhau: Nó có thể dễ dàng để duy trì các chỉ số phù hợp nếu các đại diện nội bộ duy nhất (và luôn luôn) bao gồm các danh sách truy cập ngẫu nhiên của Vertex và Edge đối tượng.Nhưng đối với các đại diện khác, việc xác định một chỉ mục có thể khó khăn.

Điều này liên quan trực tiếp đến lợi thế chính thứ hai: Một là miễn phí sử dụng các triển khai khác nhau của giao diện đồ thị. Phần "Graph Data Structures" trong tài liệu hướng dẫn tăng cường liệt kê một số cấu trúc dữ liệu đã được BGL cung cấp (và mọi người có thể thêm việc triển khai của riêng mình). Thời gian chạy cho các hoạt động nhất định được đưa ra trong ký hiệu Big-O, và một khi có thể thấy rằng chúng thay đổi rất lớn giữa các cấu trúc dữ liệu khác nhau.

Vì vậy, người ta có thể dễ dàng tưởng tượng rằng các triển khai khác nhau phù hợp hơn cho các tác vụ nhất định. Ví dụ, hãy xem xét một thuật toán thường xuyên phải kiểm tra xem một đỉnh cụ thể có được chứa trong biểu đồ hay không. Đối với bộ nhớ đỉnh được lập chỉ mục (có nghĩa là, list), điều này sẽ yêu cầu O (n) cho mỗi thử nghiệm. Với bộ nhớ dựa trên set dựa trên các đỉnh, điều này có thể được thực hiện trong O (1) - nhưng đơn giản là không có "chỉ số" hợp lý trong trường hợp này.

Bên cạnh đó, như đã đề cập trong phần tổng quan Graph Concepts:

Trong thực tế, giao diện BGL cần thậm chí không được thực hiện bằng cách sử dụng cấu trúc dữ liệu, như đối với một số vấn đề đó là dễ dàng hơn và hiệu quả hơn để xác định một đồ thị ngầm dựa trên một số chức năng.

Vì vậy gợi ý rằng có một "truy cập được lập chỉ mục" ngay cả khi đồ thị thậm chí không tồn tại trong bộ nhớ có thể cản trở việc thực hiện hoàn toàn chức năng như vậy.