Tất cả các đường dẫn có thể từ nút này đến nút khác trong cây được chỉ định (igraph)

Question

Tôi sử dụng python binding đến igraph để thể hiện cây được chỉ định. Tôi muốn tìm tất cả các đường dẫn có thể có từ một nút trong biểu đồ đó đến biểu đồ khác. Thật không may, tôi không thể tìm thấy một chức năng sẵn sàng để sử dụng trong igraph thực hiện nhiệm vụ này?

EDIT

Các mối quan tâm về số lượng vô hạn của con đường

đồ thị Tôi đang nói về thực sự là một đồ thị acyclic đạo (DAG) với một gốc duy nhất. Nó đại diện cho một tầng thác một chiều của các sự kiện mà, trên các cấp độ khác nhau của thác, có thể phân chia hoặc kết hợp với nhau. Như tôi đã nói, đây là đồ thị một chiều. Nó cũng được cung cấp rằng đồ thị không chứa bất kỳ chu kỳ nào. Do hai lý do này, danh sách vô hạn các đường dẫn, là không thể.

Tôi đang cố gắng làm gì?

Mục tiêu của tôi là tìm tất cả các đường dẫn có thể dẫn từ đầu biểu đồ (gốc) đến nút đã cho.

Answer 1

Bạn đang tìm tất cả các đường dẫn giữa một nút và nút khác trong biểu đồ tuần hoàn theo hướng (DAG).

Cây luôn là DAG, nhưng DAG không phải lúc nào cũng là cây. Sự khác biệt là cành cây không được phép tham gia, chỉ phân chia, trong khi nhánh của DAG có thể chảy cùng nhau, miễn là không có chu trình nào được giới thiệu.

Giải pháp của bạn có thể được tìm thấy là find_all_paths() trong "Python Patterns - Implementing Graphs." Điều này đòi hỏi một chút thích ứng để sử dụng với igraph. Tôi không có igraph cài đặt, nhưng sử dụng mocks, điều này dường như làm việc:

def adjlist_find_paths(a, n, m, path=[]): 
    "Find paths from node index n to m using adjacency list a." 
    path = path + [n] 
    if n == m: 
    return [path] 
    paths = [] 
    for child in a[n]: 
    if child not in path: 
     child_paths = adjlist_find_paths(a, child, m, path) 
     for child_path in child_paths: 
     paths.append(child_path) 
    return paths 

def paths_from_to(graph, source, dest): 
    "Find paths in graph from vertex source to vertex dest." 
    a = graph.get_adjlist() 
    n = source.index 
    m = dest.index 
    return adjlist_find_paths(a, n, m) 

Đó là chưa rõ ràng từ các tài liệu liệu adjlist là một danh sách liệt kê các chỉ số đỉnh hoặc một danh sách danh sách các đỉnh đối tượng tự . Tôi giả định rằng các danh sách chứa các chỉ mục để đơn giản hóa việc sử dụng danh sách điều khiển. Kết quả là, các đường dẫn trả về là về các chỉ số đỉnh. Bạn sẽ phải ánh xạ những đối tượng này trở lại các đối tượng đỉnh nếu bạn cần những thứ đó, hoặc điều chỉnh mã để nối thêm đỉnh thay vì chỉ mục của nó.