search.py

city_data = {
    'Arad': [('Zerind', 75), ('Sibiu', 140), ('Timisoara', 118)],'Zerind': [('Arad', 75), ('Oradea', 71)],'Sibiu': [('Arad', 140), ('Oradea', 151), ('Fagaras', 99), ('Rimnicu', 80)], 'Timisoara': [('Arad', 118), ('Lugoj', 111)],
    'Bucharest': [('Fagaras', 211), ('Pitesti', 101), ('Giurgiu', 90), ('Urziceni', 85)],'Urziceni': [('Bucharest', 85), 
    ('Hirsova', 98), ('Vaslui', 142)], 'Craiova': [('Drobeta', 120), ('Rimnicu', 146), ('Pitesti', 138)],
    'Drobeta': [('Mehadia', 75), ('Craiova', 120)],'Eforie': [('Hirsova', 86)],'Fagaras': [('Sibiu', 99), ('Bucharest', 211)],
    'Giurgiu': [('Bucharest', 90)],'Hirsova': [('Urziceni', 98), ('Eforie', 86)],'Iasi': [('Vaslui', 92), ('Neamt', 87)],
    'Lugoj': [('Timisoara', 111), ('Mehadia', 70)],'Mehadia': [('Lugoj', 70), ('Drobeta', 75)],'Neamt': [('Iasi', 87)],
    'Oradea': [('Zerind', 71), ('Sibiu', 151)],'Pitesti': [('Rimnicu', 97), ('Bucharest', 101), ('Craiova', 138)],
    'Rimnicu': [('Sibiu', 80), ('Pitesti', 97), ('Craiova', 146)],'Sibiu': [('Rimnicu', 80), ('Fagaras', 99), ('Arad', 140), ('Oradea', 151)],
    'Timisoara': [('Lugoj', 111), ('Arad', 118)],'Urziceni': [('Vaslui', 142), ('Bucharest', 85), ('Hirsova', 98)],
    'Vaslui': [('Iasi', 92), ('Urziceni', 142)],'Zerind': [('Oradea', 71), ('Arad', 75)],}

city_coordinates = {
    'Arad': (91, 492),
    'Bucharest': (400, 327),
    'Craiova': (253, 288),
    'Drobeta': (165, 299),
    'Eforie': (562, 293),
    'Fagaras': (305, 449),
    'Giurgiu': (375, 270),
    'Hirsova': (534, 350),
    'Iasi': (473, 506),
    'Lugoj': (165, 379),
    'Mehadia': (168, 339),
    'Neamt': (406, 537),
    'Oradea': (131, 571),
    'Pitesti': (320, 368),
    'Rimnicu': (233, 410),
    'Sibiu': (207, 457),
    'Timisoara': (94, 410),
    'Urziceni': (456, 350),
    'Vaslui': (509, 444),
    'Zerind': (108, 531),}

fromCity = "Oradea"
toCity = "Eforie"

def getDest(ctName : str) -> list:
    return city_data[ctName]

visited = set()

def hikari(city):
    # print(city)
    pass

def bfs(fromCity : str, toCity : str) -> list:
    queue = []
    queue.append(([fromCity], 0))
    result = []
    while len(queue) > 0:
        gotoCities = city_data[queue[0][0][-1]].copy()
        for city in gotoCities:
            if city[0] not in queue[0][0]:
                queue.append((queue[0][0] + [city[0]], city[1] + queue[0][1]))
                # visited.add(city[0])
        # print(queue[0][0])
        if(queue[0][0][-1] == toCity):
            result.append((queue[0][0], queue[0][1]))
        queue.pop(0)
    return result

def dfs(fromCity : str, toCity : str) -> list:
    stack = []
    stack.append(([fromCity], 0))
    result = []
    while len(stack) > 0:
        hikari(stack[-1])
        gotoCities = city_data[stack[-1][0][-1]].copy()
        tail = stack.pop()
        if(tail[0][-1] == toCity):
            result.append((tail[0], tail[1]))
        for city in gotoCities:
            if city[0] not in tail[0]:
                #visit node
                stack.append([tail[0] + [city[0]], city[1] + tail[1]])
    return result


def estm(fromCity : str, toCity : str):
    pass

def astar(fromCity : str, toCity : str, estimator : callable) -> list:
    visited = set()
    priority = []
    priority.append((fromCity, 0))
    track = {}
    while(len(priority) > 0):
        hikari(priority[0])
        priority.sort(key = lambda item: item[1] + estimator(item[0], toCity))
        # print(priority)
        bestMatch = priority.pop(0)
        bestMatchCity = bestMatch[0]
        bestMatchCost = bestMatch[1]
        if(bestMatchCity not in visited):
            visited.add(bestMatchCity)
            for city in city_data[bestMatchCity]:
                if(city[0] not in visited):
                    priority.append((city[0], bestMatchCost + city[1]))
                    if(city[0] not in track):
                        track[city[0]] = (bestMatchCity, bestMatchCost + city[1])
                    elif(track[city[0]][1] > bestMatchCost + city[1]):
                        track[city[0]] = (bestMatchCity, bestMatchCost + city[1])
    result = []
    result.append(toCity)
    go = []
    while(result[-1] != fromCity):
        result.append(track[result[-1]][0])
        snapShot = result.copy()
        snapShot.reverse()
    result.reverse()
    return [[tuple(result), track[toCity][1]]]

def dijkstra():
    return astar(fromCity, toCity, noEstimate)

result = bfs(fromCity, toCity)
print(len(result))
print(result)
# print(result)
result = dfs(fromCity, toCity)
# for _ in result:
#     print(_)
def euclidianDistance(city1, city2):
    a = city_coordinates[city1][0] - city_coordinates[city2][0]
    b = city_coordinates[city1][1] - city_coordinates[city2][1]
    return (a ** 2 + b ** 2)**0.5
def noEstimate(city1, city2):
    return 0
print("--")
# result = astar(fromCity, toCity, euclidianDistance)
# print(result)
result = dijkstra()

print(result)