Ошибка типа между двумя экземплярами вершин (узлов) в алгоритме SPF Дейкстры - PullRequest
Новая
       29

Ошибка типа между двумя экземплярами вершин (узлов) в алгоритме SPF Дейкстры

1 голос
/ 15 апреля 2019

В настоящее время я работаю над решением проблемы оптимизации расписания движения поездов в рамках обучения. В этой задаче необходимо максимизировать функцию полезности, которая увеличивает количество посещаемых (критических) станций, уменьшает количество используемых поездов и общее количество минут, в течение которых они ходят.

Проблема состоит из станций (узлов) и соединений (ребер). Данные по обоим из них сначала загружаются из двух файлов CSV. Затем создаются экземпляры классов для каждой станции (с указанием названия и того, является ли оно критическим) и для каждого соединения (с указанием станций в соединении и времени, которое требуется для перехода друг к другу). Эти станции и соединения хранятся в словарях.

В качестве первого шага мои одногруппники и я решили, что сначала мы хотели реализовать версию алгоритма поиска пути Дейкстры, чтобы найти самый быстрый маршрут между двумя станциями. BogoToBogo имеет очень подробное руководство о том, как реализовать версию алгоритма Дейкстры. Мы решили сначала попытаться реализовать их код, чтобы увидеть, каковы будут результаты. Однако ошибка TypeError продолжает появляться:

TypeError: '<' не поддерживается между экземплярами 'Vertex' и 'Vertex' </p>

Если у кого-то есть идея, что является причиной этой ошибки, любая помощь будет очень признательна! 

#Makes the shortest path from v.previous
def shortest(v, path):
    if v.previous:
        path.append(v.previous.get_id())
        shortest(v.previous, path)
    return

def dijkstra(aGraph, start, target):
    print('Dijkstras shortest path')
    # Set the distance for the start node to zero
    start.set_distance(0)

# Put tuple pair into the priority queue
unvisited_queue = [(v.get_distance(),v) for v in aGraph]
heapq.heapify(unvisited_queue)

while len(unvisited_queue):
    # Pops a vertex with the smallest distance
    uv = heapq.heappop(unvisited_queue)
    current = uv[1]
    current.set_visited()

    #for next in v.adjacent:
    for next in current.adjacent:
        # if visited, skip
        if next.visited:
            continue
        new_dist = current.get_distance() + current.get_weight(next)

        if new_dist < next.get_distance():
            next.set_distance(new_dist)
            next.set_previous(current)
            print('updated : current = ' + current.get_id() + ' next = ' + next.get_id() + ' new_dist = ' + next.get_distance())

        else:
            print('not updated : current = ' + current.get_id() + ' next = ' + next.get_id() + ' new_dist = ' + next.get_distance())

    # Rebuild heap
    # 1. Pop every item
    while len(unvisited_queue):
        heapq.heappop(unvisited_queue)
    # 2. Put all vertices not visited into the queue
    unvisited_queue = [(v.get_distance(),v) for v in aGraph if not v.visited]
    heapq.heapify(unvisited_queue)

if __name__ == "__main__":

# Calling the CSV loading functions in mainActivity
# These functions will also instantiate station and connections objects
load_stations(INPUT_STATIONS)
load_connections(INPUT_CONNECTIONS)

g = Graph()

for index in stations:
    g.add_vertex(stations[index].name)

for counter in connections:
    g.add_edge(connections[counter].stat1, connections[counter].stat2, int(connections[counter].time))

for v in g:
    for w in v.get_connections():
        vid = v.get_id()
        wid = w.get_id()
        print( vid, wid, v.get_weight(w))

dijkstra(g, g.get_vertex('Alkmaar'), g.get_vertex('Zaandam'))

target = g.get_vertex('Zaandam')
path = [target.get_id()]
shortest(target, path)
print('The shortest path :' + (path[::-1]))

В этом случае вызывается функция dijkstra с учетом параметров g (который является экземпляром класса Graph), Alkmaar и Zaandam. 

# Represents a grid of nodes/stations composed of nodes and edges
class Graph:
    def __init__(self):
        self.vert_dict = {}
        self.num_vertices = 0

    def __iter__(self):
        return iter(self.vert_dict.values())

    def add_vertex(self, node):
        self.num_vertices = self.num_vertices + 1
        new_vertex = Vertex(node)
        self.vert_dict[node] = new_vertex
        return new_vertex

    def get_vertex(self, n):
        if n in self.vert_dict:
            return self.vert_dict[n]
        else:
            return None

    def add_edge(self, frm, to, cost = 0):
        if frm not in self.vert_dict:
            self.add_vertex(frm)
        if to not in self.vert_dict:
            self.add_vertex(to)

        self.vert_dict[frm].add_neighbor(self.vert_dict[to], cost)
        self.vert_dict[to].add_neighbor(self.vert_dict[frm], cost)

    def get_vertices(self):
        return self.vert_dict.keys()

    def set_previous(self, current):
        self.previous = current

    def get_previous(self, current):
        return self.previous

Класс Граф. 

# Represents a node (station)
class Vertex:

    def __init__(self, node):
        self.id = node
        self.adjacent = {}
        # Set distance to infinity for all nodes
        self.distance = sys.maxsize
        # Mark all nodes unvisited
        self.visited = False
        # Predecessor
        self.previous = None

    def add_neighbor(self, neighbor, weight=0):
        self.adjacent[neighbor] = weight

    def get_connections(self):
        return self.adjacent.keys()

    def get_id(self):
        return self.id

    def get_weight(self, neighbor):
        return self.adjacent[neighbor]

    def set_distance(self, dist):
        self.distance = dist

    def get_distance(self):
        return self.distance

    def set_previous(self, prev):
        self.previous = prev

    def set_visited(self):
        self.visited = True

    def __str__(self):
        return str(self.id) + ' adjacent: ' + str([x.id for x in self.adjacent])

Класс Vertex. Спасибо за ваше время!

1 Ответ

0 голосов
/ 15 апреля 2019

Я думаю, что это может помочь, но при публикации в stackoverflow просто отправляйте как можно меньше и полную информацию 

# Put tuple pair into the priority queue
unvisited_queue = [(v.get_distance(),v) for v in aGraph]
heapq.heapify(unvisited_queue)

Если вы посмотрите на этот код, он преобразует список в кучу, которая требует < Сравнение того, что вы даете ему, определите метод __gt__() в классе вершин, функция определит, что вы получите сначала, поэтому напишите это, как считаете нужным, и я думаю, что ошибка исчезнет,: -)

...