Ví dụ về phân loại topo trên các DAG lớn

Question

Tôi đang tìm các ứng dụng thực tế trong đó phân loại topo được thực hiện trên biểu đồ lớn kích cỡ.

Một số trường nơi tôi có thể tìm thấy các trường hợp như tin sinh học, độ phân giải phụ thuộc, cơ sở dữ liệu, thiết kế phần cứng, kho dữ liệu ... nhưng tôi hy vọng một số bạn có thể gặp hoặc nghe bất kỳ thuật toán/dự án/ứng dụng cụ thể nào/datasets yêu cầu topsort.

Ngay cả khi dữ liệu/dự án có thể không truy cập công khai bất kỳ gợi ý nào (và ước tính theo thứ tự độ lớn của kích thước biểu đồ tiềm năng) có thể hữu ích.

Answer 1

Dưới đây là một số ví dụ tôi đã nhìn thấy cho đến nay cho tôpô Sorting:

• Trong khi lịch biểu đồ nhiệm vụ trong một hệ thống phân phối, nó thường là cần thiết để sắp xếp các nhiệm vụ topology và sau đó giao cho tài nguyên. Tôi biết các biểu đồ nhiệm vụ có chứa hơn 100.000 các nhiệm vụ cần được sắp xếp theo thứ tự cấu trúc liên kết. Xem this trong ngữ cảnh này.

• Ngày xửa ngày xưa tôi đang làm việc trên Hệ thống quản lý tài liệu. Mỗi tài liệu trên hệ thống này có một số hạn chế ưu tiên đối với một bộ tài liệu khác , ví dụ: loại nội dung hoặc tham chiếu trường. Sau đó, hệ thống sẽ có thể tạo thứ tự các tài liệu với thứ tự tôpô được bảo tồn. Như tôi có thể nhớ, đã có khoảng 5.000.000 tài liệu có sẵn cách đây hai năm !!!

• Trong lĩnh vực mạng xã hội, có truy vấn nổi tiếng để biết khoảng cách tình bạn lớn nhất trong mạng là . Vấn đề này cần phải đi qua biểu đồ bằng cách tiếp cận BFS, bằng với chi phí của một phân loại topo . Xem xét các thành viên của Facebook và tìm câu trả lời của bạn .

Nếu bạn cần thêm ví dụ thực tế, đừng ngần ngại hỏi tôi. Tôi đã làm việc trong rất nhiều dự án làm việc trên các đồ thị lớn.

P.S. đối với các tập dữ liệu DAG lớn, bạn có thể xem trang Stanford Large Network Dataset Collection và Graphics@ Illinois.

Answer 2

Tôi không chắc chắn nếu điều này phù hợp với những gì bạn đang tìm kiếm nhưng bạn có biết Bio4j dự án?

Không phải tất cả nội dung được lưu trữ trong DB dựa trên đồ thị đều thích hợp cho việc phân loại topo (có tồn tại các chu trình trực tiếp trong một phần quan trọng của biểu đồ), tuy nhiên có các biểu đồ con như Bản thể học và Phân loại. giác quan.

Answer 3

TopoR là bộ định tuyến PCB topo thương mại hoạt động đầu tiên bằng cách định tuyến PCB dưới dạng vấn đề tô pô và sau đó dịch cấu trúc liên kết thành không gian vật lý. Chúng hỗ trợ lên đến 32 lớp điện, vì vậy nó phải có khả năng của hàng ngàn kết nối (nói 10^4).

Tôi nghi ngờ mạch tích hợp có thể sử dụng các phương pháp tương tự.

Answer 4

company where I work quản lý cơ sở dữ liệu độc quyền về lỗ hổng và bản vá phần mềm. Các bản vá thường được phát hành bởi một nhà cung cấp phần mềm (như Microsoft, Adobe, v.v.) trong các khoảng thời gian đều đặn, và các bản vá lỗi "mới và cải tiến" "supercede" cũ hơn, theo nghĩa là nếu bạn áp dụng bản vá mới hơn cho máy chủ thì cũ bản vá không còn cần thiết nữa.

Điều này làm tăng DAG trong đó mỗi bản vá phần mềm là một nút có vòng cung trỏ đến một nút cho mỗi bản vá "superceding". Hiện có gần 10K nút trong biểu đồ và các bản vá mới được thêm vào mỗi tuần.

Phân loại topo rất hữu ích trong ngữ cảnh này để xác minh rằng biểu đồ không chứa chu trình - nếu chúng xuất hiện thì có nghĩa là có lỗi khi thêm bản ghi DB mới hoặc tham chiếu được sao chép dữ liệu bị hỏng giữa các phiên bản DB.