Django tìm đường đi giữa hai đỉnh trong một đồ thị

Question

Đây chủ yếu là một câu hỏi hợp lý, nhưng ngữ cảnh được thực hiện ở Django.

Trong Cơ sở dữ liệu của chúng tôi, chúng tôi có Vertex và Dòng Lớp học, những tạo thành một (thần kinh) mạng, nhưng nó là không có thứ tự và tôi không thể thay đổi nó, đó là một Legacy Cơ sở dữ liệu

class Vertex(models.Model) 
    code = models.AutoField(primary_key=True) 
    lines = models.ManyToManyField('Line', through='Vertex_Line') 

class Line(models.Model) 
    code = models.AutoField(primary_key=True) 

class Vertex_Line(models.Model) 
    line = models.ForeignKey(Line, on_delete=models.CASCADE) 
    vertex = models.ForeignKey(Vertex, on_delete=models.CASCADE) 

Bây giờ, trong việc áp dụng , người dùng sẽ có thể chọn trực quan hAI các đỉnh (các vòng tròn màu xanh lá cây dưới đây)

các javascript sau đó sẽ gửi các vn hai vertex này để Django, và nó có để tìm các lớp học Dòng đáp ứng một tuyến đường giữa chúng, trong trường hợp này, 4 dòng màu đỏ sau đây: Logic

kinh doanh:

• Một Vertex có thể có 1-4 dòng liên quan đến nó
• A Line có thể có 1-2 vertex liên quan đến nó
• sẽ chỉ có một con đường có thể giữa hai vertex

Những gì tôi có cho đến nay:

• Tôi hiểu rằng câu trả lời có thể bao gồm đệ quy
• Đường dẫn phải được tìm thấy bằng cách cố gắng mỗi đường đi từ một Vertex đến khi người kia được tìm thấy, nó không thể được trực tiếp tìm thấy
• Kể từ khi có bốn và ba chiều nút giao thông, tất cả các tuyến đường đang được thử phải được lưu trong suốt đệ quy (không chắc chắn về điều này một)

tôi biết logic cơ bản được lặp qua tất cả các dòng của mỗi Đỉnh, và sau đó lấy Vertex khác của những dòng này, và tiếp tục đi theo đệ quy, nhưng tôi thực sự không biết bắt đầu từ đâu trên cái này.

Đây là như xa như tôi có thể nhận được, nhưng nó có lẽ không giúp (views.py):

def findRoute(request): 
    data = json.loads(request.body.decode("utf-8")) 
    v1 = Vertex.objects.get(pk=data.get('v1_pk')) 
    v2 = Vertex.objects.get(pk=data.get('v2_pk')) 
    lines = v1.lines.all() 
    routes = [] 
    for line in lines: 
     starting_line = line 
     #Trying a new route 
     this_route_index = len(routes) 
     routes[this_route_index] = [starting_line.pk] 
     other_vertex = line.vertex__set.all().exclude(pk=v1.pk) 
     #There are cases with dead-ends 
     if other_vertex.length > 0: 
     #Mind block... 

Answer 1

Như bạn đã chỉ, đây không phải là một câu hỏi liên quan Django/Python, nhưng một logic/vấn đề thuật toán.

Để tìm đường đi giữa hai đỉnh chóp trong một đồ thị, bạn có thể sử dụng rất nhiều thuật toán: Dijkstra, A*, DFS, BFS, Floyd–Warshall vv .. Bạn có thể chọn tùy thuộc vào những gì bạn cần: ngắn/path tối thiểu, tất cả các đường dẫn ..

Làm cách nào để triển khai điều này ở Django? Tôi đề nghị không áp dụng các thuật toán trên các mô hình chính nó, vì điều này có thể tốn kém (về thời gian, truy vấn db, vv ...) đặc biệt cho các đồ thị lớn; thay vào đó, tôi muốn ánh xạ biểu đồ trong cấu trúc dữ liệu trong bộ nhớ và thực thi thuật toán trên nó.

Bạn có thể xem qua số này Networkx, một thuật toán (cấu trúc dữ liệu + thuật toán) hoàn chỉnh và thư viện tài liệu tốt; python-graph, cung cấp cấu trúc dữ liệu phù hợp và toàn bộ các thuật toán quan trọng (bao gồm một số thuật toán nêu trên). Các tùy chọn khác tại Python Graph Library