a* algorithm problem with one single edge

Question

i'm having trouble with my python implementation of a* algorithm, but only with one edge. When I run the code searching for path with the two broken nodes the code tries to compare single nodes to insert it in my priority queue, but i have defined another class, here's the code to help me explain to you

 def a_search(self, start, goal):
    if start not in self.connections or goal not in self.connections:
        raise Exception("Non sono stati forniti nodi validi.")
    frontier = PriorityQueue()
    frontier.put(PrioritizedItem(0, start))
    visited_path = {}
    estimated_cost = dict()
    visited_path[start] = None
    estimated_cost[start] = 0
    while not frontier.empty():
        current = frontier.get()
        current = current.get_node()
        if current == goal:
            break
        next_node: Node
        for next_node in self.connection(current):
            new_cost = estimated_cost[current] + self.pathweight(current, next_node)
            if next_node not in estimated_cost or new_cost < estimated_cost[next_node]:
                estimated_cost[next_node] = new_cost
                priority = new_cost + self.euristic(next_node, goal)
                frontier.put(PrioritizedItem(priority, next_node))
                visited_path[next_node] = current
    return frontier

Here's the class PrioritizedItem

@dataclass(order=True)
class PrioritizedItem:
priority: float
item: object = field()

def get_node(self):
    return self.item

def __cmp__(self, other):
    if self.priority < other.priority:
        return -1
    elif self.priority > other.priority:
        return 1
    else:
        return 0

Answer 1

__cmp__ doesn't do anything in Python 3. It got replaced with rich comparisons ages ago - separate methods for each comparison operator, which can return arbitrary objects.

You're telling dataclass to generate comparison methods for you with order=True. If you don't want a field to be considered in comparisons, you can specify compare=False for that field... but then PrioritizedItem instances with the same priority and different items will be considered equal, which can have weird side effects.

Instead of changing comparison logic, the usual trick for handling this kind of thing is to just add an incrementing counter field to your elements and use that for tiebreaking, like (priority, counter_value, item) instead of (priority, item). If you want to stick with a dataclass, you can add a field called counter or something between priority and item.

---

As an aside, if that PriorityQueue is the class from the queue module, you should use heapq instead. queue.PriorityQueue is specifically designed for use as a prioritized inter-thread message-passing system, and it has design decisions and overhead that don't make sense for single-threaded usage. For example, it blocks on get instead of raising an exception when there's nothing to get.