Алгоритмы поиска маршрута на графике

Question

Постановка задачи

Я пытаюсь реализовать DFS, BFS и UCS (поиск единой стоимости), чтобы найти маршруты между разными железнодорожными станциями с помощью этого файла CSV . Если вы откроете файл данных с помощью любого текстового редактора, вы увидите содержимое файла как:

      "Harrow & Wealdstone", "Kenton", "Bakerloo", 3, "5", "0"
"Kenton", "South Kenton", "Bakerloo", 2, "4", "0"
· · ·
"Bank/Monument", "Waterloo", "Waterloo & City", 4, "1", "0"

Каждая строка в CSV-файле представляет собой «шаг» Tube и имеет следующий формат:

      [StartingStation], [EndingStation], [TubeLine], [AverageTimeTaken], [MainZone], [SecondaryZone]

куда:

• StartingStation: начальная станция
• EndingStation: конечная станция с прямым подключением
• TubeLine: линия метро, ​​соединяющая названные станции
• AverageTimeTaken: среднее время в минутах между указанными станциями.
• MainZone: основная зона станций
• SecondaryZone: дополнительная зона станций, которая равна «0», если станция находится только в одной зоне.

Я реализовал алгоритмы поиска, но у меня возникли проблемы с преобразованием данных CSV в подходящий граф (с использованием NetworkX) в качестве входных данных для алгоритмов.

Я хочу напечатать информацию, относящуюся к поиску, например станции, стоимость, количество развернутых узлов и т. Д. В настоящее время, когда я вызываю блок кода визуализации графика, я получаю пустой результат? Как представить состояние и как построить новое состояние из каждой станции, доступной из станции в текущем состоянии, но еще не посещенной на текущем пути? Спасибо.

Реализации

Визуализация графика

      import pandas as pd
import networkx as nx
import matplotlib.pyplot  as plt

tube_data = pd.read_csv('tubedata.csv')
Graphtype = nx.Graph()
tube_data = nx.read_edgelist(tube_data, delimiter=',')

      def show_weighted_graph(networkx_graph, node_size, font_size, fig_size):
  plt.figure(num=None, figsize=fig_size, dpi=80)
  plt.axis('off')
  nodes_position = nx.spring_layout(networkx_graph) 
  edges_weights  = nx.get_edge_attributes(networkx_graph,'weight')

  nx.draw_networkx_nodes(networkx_graph, nodes_position, node_size=node_size,  
                         node_color = ["orange"]*networkx_graph.number_of_nodes())

  nx.draw_networkx_edges(networkx_graph, nodes_position, 
                         edgelist=list(networkx_graph.edges), width=2)

  nx.draw_networkx_edge_labels(networkx_graph, nodes_position, 
                               edge_labels = edges_weights)

  nx.draw_networkx_labels(networkx_graph, nodes_position, font_size=font_size, 
                          font_family='sans-serif')
  plt.axis('off')
  plt.show()

DFS

      def dfs(graph, origin, destination, already_visited = [], count=1, reverse=False):
  if origin == destination:
    return [origin],count+1
  
  next_already_visited = already_visited.copy()
  next_already_visited.append(origin)
  
  neighbours = reversed(list(graph.neighbors(origin))) if reverse else graph.neighbors(origin)
  for next_node in neighbours: 
    if next_node not in already_visited:
      result, count= dfs(graph, next_node, destination, next_already_visited, count, reverse)
      if result != []:
        path = [origin] + result
        return path,count+1

  return [],count+1

BFS

      def bfs(graph, origin, destination, counter = 0, reverse=False):
  next_already_visited = [origin]
  total_paths = [[origin]] 

  while len(total_paths)!= 0: 
    new_total_paths = []
    for path in total_paths:
      last_element_in_path = path[-1]
      nodes_found = list(reversed(list(graph.neighbors(last_element_in_path)))) if reverse else list(graph.neighbors(last_element_in_path))
      if destination in nodes_found:
        return path + [destination], counter+1

      for node in nodes_found:
        if node not in next_already_visited:
          counter += 1
          next_already_visited.append(node)
          new_total_paths = new_total_paths + [path + [node]]
    
    total_paths = new_total_paths

  return [],-1

UCS

      from queue import PriorityQueue

def h(node): # Calculates the admissible heuristic of a node, format is [X,Y]
    node = node.replace('[','')
    node = node.replace(']','')
    x, y = node.split(',', maxsplit=2)
    x = float(x)
    y = float(y)
    return abs(x-9) + abs(y-9)

def Astar(graph, origin, goal):
    admissible_heuristics = {} 
    h = heuristic(origin)
    admissible_heuristics[origin] = h
    visited_nodes = {}
    visited_nodes[origin] = (h, [origin]) 

    paths_to_explore = PriorityQueue()
    paths_to_explore.put((h, [origin], 0)) 
    while not paths_to_explore.empty(): 
        _, path, total_cost = paths_to_explore.get()
        current_node = path[-1]
        neighbors = graph.neighbors(current_node) 
        
        for neighbor in neighbors:
            edge_data = graph.get_edge_data(path[-1], neighbor)
            if "weight" in edge_data:
                cost_to_neighbor = edge_data["weight"] 
            else:
                cost_to_neighbor = 1 

            if neighbor in admissible_heuristics:
                h = admissible_heuristics[neighbor]
            else:
                h = heuristic(neighbor)
                admissible_heuristics[neighbor] = h

            new_cost = total_cost + cost_to_neighbor
            new_cost_plus_h = new_cost + h
            if (neighbor not in visited_nodes) or (visited_nodes[neighbor][0]>new_cost_plus_h): 
                next_node = (new_cost_plus_h, path+[neighbor], new_cost)
                visited_nodes[neighbor] = next_node 
                paths_to_explore.put(next_node) 

    return visited_nodes[goal]