A_Star_1.py
def astar_path_Kasia(G, source, target, scenario, coordDict): # weight=GlobalScore and add later LocalScore
    """Returns a list of nodes in a shortest path between source and target
    using the A* ("A-star") algorithm.
    
    Heurestic function changed to include the dictionairy with the coordinates
    
    Weights used in the function include distant and local scores of the edges
    
    """
    def heuristic_Kasia(theNode, theTarget, coordDict):
        nodeX = coordDict[theNode][0]
        nodeY = coordDict[theNode][1]
        targetX = coordDict[theTarget][0]
        targetY = coordDict[theTarget][1]
        distanceToTarget = math.sqrt(math.pow((targetX-nodeX),2)+math.pow((targetY-nodeY),2))
        return distanceToTarget

    if source not in G or target not in G:
        msg = 'Either source {} or target {} is not in G'
        raise nx.NodeNotFound(msg.format(source, target))

    push = heappush
    pop = heappop
    
    # Prepare data for calculating the weights
    distanceToTarget = heuristic_Kasia(source, target, coordDict)
    print('Max heuristic value (eucidlian distance to destination from the starting node): ', distanceToTarget)
    print('Max Total Score of the edge: 1')
    # Assign scenario
    # 1: TS = 0.5 Local Score + 0.5 Distant Score'
    # 2: TS = (DS = 0.8 and LS = 0.8. Linear change of DS and LS towards the destination till DS = 0.2 and LS = 0.8))
    if scenario == 1:
        weightDS = 0.5
        weightLS = 0.5
    elif scenario == 2:
        weightDS = w1
        weightLS = (1-w1)
        
    # Heurestic values are ~1000 times higher than edge scores.
    # Apply the factor to scale the weights (0-1) to match heurestic (0-~1000 m)
    heuristicCostRatio = 1000
    
    # The queue stores priority, node, cost to reach, and parent.
    # Uses Python heapq to keep in priority order.
    # Add a counter to the queue to prevent the underlying heap from
    # attempting to compare the nodes themselves. The hash breaks ties in the
    # priority and is guaranteed unique for all nodes in the graph.
    c = count()
    queue = [(0, next(c), source, 0, None)]

    # Maps enqueued nodes to distance of discovered paths and the
    # computed heuristics to target. We avoid computing the heuristics
    # more than once and inserting the node into the queue too many times.
    enqueued = {}
    # Maps explored nodes to parent closest to the source.
    explored = {}

    while queue:
        # Pop the smallest item from queue.
        _, __, curnode, dist, parent = pop(queue)
                
        if curnode == target:
            path = [curnode]
            node = parent
            while node is not None:
                path.append(node)
                node = explored[node]
            path.reverse()
            return path

        if curnode in explored:
            continue

        explored[curnode] = parent

        for neighbor, w in G[curnode].items():
            
            if neighbor in explored:
                continue
                        
            # If the weight are linear, calculate the weights, depending on their eucidlian distance to the destination
            if scenario==2:
                weightDS = (2*w1-1)/distanceToTarget * heuristic_Kasia(neighbor, target, coordDict) + (1-w1)
                weightLS = (-1)*(2*w1-1)/distanceToTarget * heuristic_Kasia(neighbor, target, coordDict) + w1
                        
            # Calculate the cost of the link.Cost of the link includes the scaling of factors, scaling of heurestic and the weighted scores of landmarks (1-landmarkScore, to be included as cost)
            ncost = dist + TotalScoreToHeuresticScaleFactor * heuristicCostRatio * (weightDS * (1-w.get('DS', 1)) + weightLS * (1-w.get('LS', 1))) ## dist = sum of weights
            if neighbor in enqueued:
                qcost, h = enqueued[neighbor]
                # if qcost <= ncost, a less costly pathl from the
                # neighbor to the source was already determined.
                # Therefore, we won't attempt to push this neighbor
                # to the queue
                if qcost <= ncost:
                    continue
            else:
                h = heuristic_Kasia(neighbor, target, coordDict)
               
            enqueued[neighbor] = ncost, h
            push(queue, (ncost + h, next(c), neighbor, ncost, curnode))
            
    raise nx.NetworkXNoPath("Node %s not reachable from %s" % (target, source))
Returns a list of nodes in a shortest path between source and target
    using the A* ("A-star") algorithm.
    
    Heurestic function changed to include the dictionairy with the coordinates
    
    Weights used in the function include distant and local scores of the edges
    
    
Returns a list of nodes in a shortest path between source and target
using the A* ("A-star") algorithm.

Heurestic function changed to include the dictionairy with the coordinates

Weights used in the function include distant and local scores of the edges
Returns a list of nodes in a shortest path between source and target using the A * ( " A - star " ) algorithm . Heurestic function changed to include the dictionairy with the coordinates Weights used in the function include distant and local scores of the edges
def astar_path_Kasia(G, source, target, scenario, coordDict): 
    def heuristic_Kasia(theNode, theTarget, coordDict):
        nodeX = coordDict[theNode][0]
        nodeY = coordDict[theNode][1]
        targetX = coordDict[theTarget][0]
        targetY = coordDict[theTarget][1]
        distanceToTarget = math.sqrt(math.pow((targetX-nodeX),2)+math.pow((targetY-nodeY),2))
        return distanceToTarget
    if source not in G or target not in G:
        msg = 'Either source {} or target {} is not in G'
        raise nx.NodeNotFound(msg.format(source, target))
    push = heappush
    pop = heappop
    distanceToTarget = heuristic_Kasia(source, target, coordDict)
    print('Max heuristic value (eucidlian distance to destination from the starting node): ', distanceToTarget)
    print('Max Total Score of the edge: 1')
    if scenario == 1:
        weightDS = 0.5
        weightLS = 0.5
    elif scenario == 2:
        weightDS = w1
        weightLS = (1-w1)
    heuristicCostRatio = 1000
    c = count()
    queue = [(0, next(c), source, 0, None)]
    enqueued = {}
    explored = {}
    while queue:
        _, __, curnode, dist, parent = pop(queue)
        if curnode == target:
            path = [curnode]
            node = parent
            while node is not None:
                path.append(node)
                node = explored[node]
            path.reverse()
            return path
        if curnode in explored:
            continue
        explored[curnode] = parent
        for neighbor, w in G[curnode].items():
            if neighbor in explored:
                continue
            if scenario==2:
                weightDS = (2*w1-1)/distanceToTarget * heuristic_Kasia(neighbor, target, coordDict) + (1-w1)
                weightLS = (-1)*(2*w1-1)/distanceToTarget * heuristic_Kasia(neighbor, target, coordDict) + w1
            ncost = dist + TotalScoreToHeuresticScaleFactor * heuristicCostRatio * (weightDS * (1-w.get('DS', 1)) + weightLS * (1-w.get('LS', 1))) 
            if neighbor in enqueued:
                qcost, h = enqueued[neighbor]
                if qcost <= ncost:
                    continue
            else:
                h = heuristic_Kasia(neighbor, target, coordDict)
            enqueued[neighbor] = ncost, h
            push(queue, (ncost + h, next(c), neighbor, ncost, curnode))
    raise nx.NetworkXNoPath("Node %s not reachable from %s" % (target, source))
def astar_path_Kasia ( G , source , target , scenario , coordDict ) : def heuristic_Kasia ( theNode , theTarget , coordDict ) : nodeX = coordDict [ theNode ] [ 0 ] nodeY = coordDict [ theNode ] [ 1 ] targetX = coordDict [ theTarget ] [ 0 ] targetY = coordDict [ theTarget ] [ 1 ] distanceToTarget = math . sqrt ( math . pow ( ( targetX - nodeX ) , 2 ) + math . pow ( ( targetY - nodeY ) , 2 ) ) return distanceToTarget if source not in G or target not in G : msg = 'Either source {} or target {} is not in G' raise nx . NodeNotFound ( msg . format ( source , target ) ) push = heappush pop = heappop distanceToTarget = heuristic_Kasia ( source , target , coordDict ) print ( 'Max heuristic value (eucidlian distance to destination from the starting node): ' , distanceToTarget ) print ( 'Max Total Score of the edge: 1' ) if scenario == 1 : weightDS = 0.5 weightLS = 0.5 elif scenario == 2 : weightDS = w1 weightLS = ( 1 - w1 ) heuristicCostRatio = 1000 c = count ( ) queue = [ ( 0 , next ( c ) , source , 0 , None ) ] enqueued = { } explored = { } while queue : _ , __ , curnode , dist , parent = pop ( queue ) if curnode == target : path = [ curnode ] node = parent while node is not None : path . append ( node ) node = explored [ node ] path . reverse ( ) return path if curnode in explored : continue explored [ curnode ] = parent for neighbor , w in G [ curnode ] . items ( ) : if neighbor in explored : continue if scenario == 2 : weightDS = ( 2 * w1 - 1 ) / distanceToTarget * heuristic_Kasia ( neighbor , target , coordDict ) + ( 1 - w1 ) weightLS = ( - 1 ) * ( 2 * w1 - 1 ) / distanceToTarget * heuristic_Kasia ( neighbor , target , coordDict ) + w1 ncost = dist + TotalScoreToHeuresticScaleFactor * heuristicCostRatio * ( weightDS * ( 1 - w . get ( 'DS' , 1 ) ) + weightLS * ( 1 - w . get ( 'LS' , 1 ) ) ) if neighbor in enqueued : qcost , h = enqueued [ neighbor ] if qcost <= ncost : continue else : h = heuristic_Kasia ( neighbor , target , coordDict ) enqueued [ neighbor ] = ncost , h push ( queue , ( ncost + h , next ( c ) , neighbor , ncost , curnode ) ) raise nx . NetworkXNoPath ( "Node %s not reachable from %s" % ( target , source ) )
Returns a list of nodes in a shortest path between source and target
using the A* ("A-star") algorithm.
Returns a list of nodes in a shortest path between source and target using the A * ( " A - star " ) algorithm .
# weight=GlobalScore and add later LocalScore """Returns a list of nodes in a shortest path between source and target
    using the A* ("A-star") algorithm.
    
    Heurestic function changed to include the dictionairy with the coordinates
    
    Weights used in the function include distant and local scores of the edges
    
    """ # Prepare data for calculating the weights # Assign scenario # 1: TS = 0.5 Local Score + 0.5 Distant Score' # 2: TS = (DS = 0.8 and LS = 0.8. Linear change of DS and LS towards the destination till DS = 0.2 and LS = 0.8)) # Heurestic values are ~1000 times higher than edge scores. # Apply the factor to scale the weights (0-1) to match heurestic (0-~1000 m) # The queue stores priority, node, cost to reach, and parent. # Uses Python heapq to keep in priority order. # Add a counter to the queue to prevent the underlying heap from # attempting to compare the nodes themselves. The hash breaks ties in the # priority and is guaranteed unique for all nodes in the graph. # Maps enqueued nodes to distance of discovered paths and the # computed heuristics to target. We avoid computing the heuristics # more than once and inserting the node into the queue too many times. # Maps explored nodes to parent closest to the source. # Pop the smallest item from queue. # If the weight are linear, calculate the weights, depending on their eucidlian distance to the destination # Calculate the cost of the link.Cost of the link includes the scaling of factors, scaling of heurestic and the weighted scores of landmarks (1-landmarkScore, to be included as cost) ## dist = sum of weights # if qcost <= ncost, a less costly pathl from the # neighbor to the source was already determined. # Therefore, we won't attempt to push this neighbor # to the queue
G
source
target
scenario
coordDict