Project_1.py

from collections import deque
# paper conclusion: min distance -> BFS; min time->BNART

INTERSECTION_DELAY = 2


class graph:

    def __init__(self):
        self.graph ={ }

    # s: source node; d:destiniation node; w: weight
    def add_edge(self, s, d, w):
        if s not in self.graph:
            self.graph[s] = { }
        if d not in self.graph:
            self.graph[d] = { }

        self.graph[s][d] = w
        self.graph[d][s] = w

    # n: node, if a node has more than 2 edges, it's a intersection
    def intersection(self, n):
        if len(self.graph[n]) > 2:
            return True
        else:
            return False
        
    # find the weight between node s and d    
    def find_weight(self, s, d):
        if s in self.graph and d in self.graph:
            cost = self.graph[s][d]
            if(self.intersection(s)):
                cost += INTERSECTION_DELAY
     #           print("\nintersection: ", s)
            
            return cost
        else:
            return 0

    #s: source node/ root; d: destination
    def BFS(self, s, d):
        if s not in self.graph or d not in self.graph:
            return None

        visited = set()
        frontier = deque([(s, 0)])  # Tuple: (node, cumulative weight)
        result = { }
        target = False

        while (frontier != None):
            n, w = frontier.popleft()
            visited.add(n)
            

            if n == d:
                target = True
                break

            for neighbor, weight in self.graph[n].items():
                if neighbor not in visited:
                    w += weight
                    frontier.append((neighbor, w))
                    visited.add(neighbor)
                    result[neighbor] = (n, w)

        if target == False:
            return None
        
        path = [d]
        while (path[-1] != s):
            path.append(result[path[-1]][0])
        path.reverse()

        return path

    # return the total wight of the selected path
    def get_weight(self, p):
        weight = 0
        for i in range(len(p) - 1):
            w = self.find_weight(p[i], p[i+1])
            weight += w
        return weight

    # retruen true if two cars share a same peroid of path
    def same_path(self, p1, p2):
        for i in range (len(p1) -1):
            if p1[i] in p2 and p1[i+1] in p2:
                index1 = p2.index(p1[i])
                index2 = p2.index(p1[i+1])
                if index1 + 1 == index2:
                    return True
        return False









# test 1
g1 = graph()
g1.add_edge("1", "2", 1)
g1.add_edge("2", "3", 1)
g1.add_edge("2", "4", 1)
g1.add_edge("2", "5", 1)
g1.add_edge("3", "6", 1)
g1.add_edge("4", "6", 1)

shortest1_1 = graph.BFS(g1, "1", "6")
if shortest1_1:
    print("The shortest is:", shortest1_1)
else:
    print("No shortest path")
cost1_1 = graph.get_weight(g1, shortest1_1)
print("The minimun weight is: ", cost1_1)


shortest1_2 = graph.BFS(g1, "2", "6")
if shortest1_2:
    print("The shortest is:", shortest1_2)
else:
    print("No shortest path")
cost1_2 = graph.get_weight(g1, shortest1_2)
print("The minimun weight is: ", cost1_2)

print("\nWill these two path colides?")
if(graph.same_path(g1, shortest1_1, shortest1_2)):
    print("Yes, but I have no idea how to solve now\n")
else:
    print("No\n")

# test 2
g2 = graph()
g2.add_edge("A", "B", 1)
g2.add_edge("A", "C", 1)
g2.add_edge("B", "D", 1)
g2.add_edge("C", "D", 1)
        
shortest2 = graph.BFS(g2, "A", "D")
if shortest2:
    print("The shortest is:", shortest2)
else:
    print("No shortest path")

cost2 = graph.get_weight(g2, shortest2)
print("The minimun weight is: ", cost2)