Làm cách nào để hạn chế các đường dẫn nhất định trong biểu đồ NetworkX?

Question

Tôi đang cố gắng tính toán đường đi ngắn nhất giữa 2 điểm bằng cách sử dụng thuật toán Dijkstra và A Star (trong biểu đồ NetworkX được chỉ dẫn).

Tại thời điểm này nó hoạt động tốt và tôi có thể nhìn thấy con đường tính toán nhưng tôi muốn tìm một cách để hạn chế nhất định đường.

Ví dụ nút nếu chúng tôi đã sau:

nút = [1,2,3,4]

Với những cạnh:

cạnh = ((1,2), (2 , 3), (3,4))

có cách nào chặn/hạn chế 1 -> 2 -> 3 nhưng vẫn đợi 2 -> 3 & 1 -> 2.

Điều này có nghĩa rằng:

• thể du lịch từ 1 để 2

• thể du lịch từ 2 để 3

• không thể đi 1-3 .. trực tiếp hoặc gián tiếp (tức là hạn chế 1-> 2-> 3 đường dẫn).

Điều này có thể đạt được trong NetworkX .. nếu không có thư viện biểu đồ khác bằng Python cho phép điều này không?

Cảm ơn.

Answer 1

Câu hỏi thú vị, tôi chưa bao giờ nghe nói về vấn đề này, có lẽ vì tôi không có nhiều kiến ​​thức về chủ đề này, cũng như không có nhiều kinh nghiệm với NetworkX. Tuy nhiên, tôi có một ý tưởng cho một thuật toán. Đây có thể là cách ngây thơ nhất để làm điều này và tôi rất vui khi nghe một thuật toán thông minh hơn.

Ý tưởng là bạn có thể sử dụng các quy tắc hạn chế để biến đổi đồ thị thành đồ thị mới trong đó tất cả các cạnh đều hợp lệ, sử dụng thuật toán sau.

Hạn chế của con đường (1,2,3) có thể được chia làm hai quy tắc:

• Nếu bạn đến hơn (1,2) sau đó loại bỏ (2,3)
• Nếu bạn bỏ trên (2,3) sau đó xóa (1,2)

Để đặt điều này vào biểu đồ, bạn có thể chèn bản sao của nút 2 cho mỗi trường hợp. Tôi sẽ gọi các nút mới 1_2 và 2_3 sau khi cạnh hợp lệ trong trường hợp tương ứng. Đối với cả hai nút, bạn sao chép tất cả các cạnh vào và ra trừ đi cạnh bị giới hạn.

Ví dụ:

Nodes = [1,2,3,4] 
Edges = [(1,2),(2,3),(4,2)] 

Các đường dẫn hợp lệ thì chỉ được 4> 2-> 3 không 1-> 2-> 3. Vì vậy, chúng tôi mở rộng biểu đồ:

Nodes = [1,1_2,2_3,3,4] # insert the two states of 2 
Edges = [ # first case: no (1_2,3) because of the restriction 
      (1,1_2), (4, 1_2) 
      # 2nd case, no (1,2_3) 
      (2_3,3), (4,2_3)] 

Đường dẫn hợp lệ duy nhất trong biểu đồ này là 4-> 2_3-> 3. Điều này chỉ đơn giản là bản đồ đến 4 -> 2-> 3 trong đồ thị ban đầu.

Tôi hy vọng câu trả lời này ít nhất có thể giúp bạn nếu bạn không tìm thấy giải pháp hiện có nào. Các quy tắc hạn chế dài hơn sẽ làm nổ tung biểu đồ với số lượng nút nhà nước tăng lên theo cấp số nhân, do đó thuật toán này quá đơn giản hoặc khó khăn ;-)

Answer 2

Bạn có thể đặt dữ liệu nút {color = ['blue' ]} cho nút 1, nút 2 có {color = ['red', 'blue']} và node3 có {color = ['red']}. Sau đó sử dụng thuật toán networkx.alms. astar_path() thiết lập dựa trên kinh nghiệm

• phương pháp được thiết lập để một hàm trả về một might_as_well_be_infinity khi nó gặp một nút mà không cùng màu bạn đang tìm kiếm
• weight = less_than_infinity.