networkx: tìm đường dẫn dài nhất tuyệt đối trong digraph

Question

Tôi muốn networkx tìm đường đi dài nhất tuyệt đối trong biểu đồ tuần hoàn theo chỉ dẫn của tôi.

Tôi biết về Bellman-Ford, vì vậy tôi đã phủ nhận độ dài biểu đồ của mình. Vấn đề: bellx_ford() của networkx yêu cầu nút nguồn. Tôi muốn tìm đường dẫn dài nhất tuyệt đối (hoặc đường đi ngắn nhất sau khi phủ định), chứ không phải đường dẫn dài nhất từ một nút nhất định.

Tất nhiên, tôi có thể chạy bellman_ford() trên mỗi nút trong biểu đồ và sắp xếp, nhưng có phương pháp hiệu quả hơn không?

Từ những gì tôi đã đọc (ví dụ: http://en.wikipedia.org/wiki/Longest_path_problem) Tôi nhận ra có thực sự có thể không phải là một phương pháp hiệu quả hơn, nhưng đã tự hỏi nếu ai có bất kỳ ý tưởng (và/hoặc đã chứng minh P = NP (cười)).

CHỈNH SỬA: tất cả độ dài cạnh trong biểu đồ của tôi là +1 (hoặc -1 sau phủ định), do đó, một phương thức chỉ truy cập vào hầu hết các nút cũng sẽ hoạt động. Nói chung, nó sẽ không thể truy cập tất cả các nút của khóa học.

EDIT: OK, tôi vừa nhận ra rằng tôi có thể thêm một nút bổ sung chỉ đơn giản là kết nối với mọi nút khác trong biểu đồ và sau đó chạy bellman_ford từ nút đó. Bất cứ một đề nghị nào khác?

Answer 1

Có một thuật toán tuyến tính thời gian nêu tại http://en.wikipedia.org/wiki/Longest_path_problem

Đây là một (thử nghiệm rất nhẹ) thực hiện

EDIT, đây rõ ràng là sai, xem dưới đây. 1 cho tương lai thử nghiệm hơn nhẹ trước khi gửi bài

import networkx as nx 

def longest_path(G): 
    dist = {} # stores [node, distance] pair 
    for node in nx.topological_sort(G): 
     pairs = [[dist[v][0]+1,v] for v in G.pred[node]] # incoming pairs 
     if pairs: 
      dist[node] = max(pairs) 
     else: 
      dist[node] = (0, node) 
    node, max_dist = max(dist.items()) 
    path = [node] 
    while node in dist: 
     node, length = dist[node] 
     path.append(node) 
    return list(reversed(path)) 

if __name__=='__main__': 
    G = nx.DiGraph() 
    G.add_path([1,2,3,4]) 
    print longest_path(G) 

EDIT: Sửa phiên bản (sử dụng có nguy cơ của riêng bạn và xin vui lòng thông báo lỗi)

def longest_path(G): 
    dist = {} # stores [node, distance] pair 
    for node in nx.topological_sort(G): 
     # pairs of dist,node for all incoming edges 
     pairs = [(dist[v][0]+1,v) for v in G.pred[node]] 
     if pairs: 
      dist[node] = max(pairs) 
     else: 
      dist[node] = (0, node) 
    node,(length,_) = max(dist.items(), key=lambda x:x[1]) 
    path = [] 
    while length > 0: 
     path.append(node) 
     length,node = dist[node] 
    return list(reversed(path)) 

if __name__=='__main__': 
    G = nx.DiGraph() 
    G.add_path([1,2,3,4]) 
    G.add_path([1,20,30,31,32,4]) 
# G.add_path([20,2,200,31]) 
    print longest_path(G) 

Answer 2

câu trả lời sửa đổi Aric là một trong những tốt và tôi thấy nó đã được chấp nhận bởi thư viện networkx link

Tuy nhiên, tôi đã tìm thấy một lỗ hổng nhỏ trong phương pháp này.

if pairs: 
    dist[node] = max(pairs) 
else: 
    dist[node] = (0, node) 

vì cặp là danh sách các bộ (int, nodetype). Khi so sánh tuple, python so sánh phần tử đầu tiên và nếu chúng giống nhau, sẽ xử lý để so sánh phần tử thứ hai, đó là nodetype. Tuy nhiên, trong trường hợp của tôi, nodetype là một phương thức so sánh lớp tùy chỉnh mà không được định nghĩa. do đó Python ném ra một lỗi như 'Lỗi Loại: loại unorderable: xxx()> xxx()'

Đối với một cải thiện có thể, tôi nói dòng

dist[node] = max(pairs) 

có thể được thay thế bằng

dist[node] = max(pairs,key=lambda x:x[0]) 

Xin lỗi về định dạng vì đây là lần đầu tiên tôi đăng bài. Tôi ước tôi có thể đăng câu trả lời của Aric dưới dạng bình luận nhưng trang web cấm tôi làm như vậy nói rằng tôi không có đủ danh tiếng (tốt ...)