<jupyter_start><jupyter_text>A*Let us now modify the graph to accept the 2D co-ordinates of the node. We will use Euclidean distance as the heuristic<jupyter_code>node_coords = [(0, 0),(2,2),(1,2),(1,0),(3,3),(3,2), (4,2)]
# Function to calculate euclidean distance
# (x1, y1), (x2, y2) given
def euclidean(node1, node2):
    x1, y1 = node1
    x2, y2 = node2
    return np.sqrt((x1-x2)**2+(y1-y2)**2)

class Graph(object):
  def __init__(self, nodes, edges, coords, weight=1.0, heuristic=euclidean):
    self.nodes = nodes
    self.adjacency = -np.ones([nodes, nodes])
    self.shortest_path_set = [False] * nodes
    self.heuristic = heuristic
    self.coords = coords
    self.weight = weight # weight of heuristic
    #populate the adjacency matrix from edges
    # edges = (node1, node2, edge_cost)
    
	

  # Input: 1-D distance array to source, destination (x, y)
  # output: next node to be selected
  # remember criteria is source_cost + weight * heuristic_destination
  # node should not be in shortest_path_set
  def min_astar_distance(self, dist, dest_coords):
     heuristic_cost = np.array([self.heuristic(n, dest_coords) for n in self.coords])
     src_cost = np.array(dist)
     costs = src_cost + self.weight*heuristic_cost + 1000 *np.array(self.shortest_path_set)
     return np.argmin(costs)

  def astar(self, src, dest):
    #initialize distance array
    dist = [1000] * self.nodes
    dist[src] = 0
    #get the destination (x,y)
    dest_coords = self.coords[dest]
    for _ in range(self.nodes):	
      
      i = self.min_astar_distance(dist, dest_coords)
      # Store min distance vertex in shortest path tree
      self.shortest_path_set[i] = True
      
      # Update dist value of the neighbors of selected node 
      # Two conditions to check for each neighbor 
      # (a) not in shortest path tree (b) cost is now lowered
      # first get neighbor list from adjacency matrix
      
      all_nodes = self.adjacency[i,:]

      # loop over neighbor list to check for other 2 conditions
      # if satisfied, change dist[j]
      
      for j, edge_cost in enumerate(all_nodes):
        if edge_cost > 0 and not self.shortest_path_set[j]: # valid neighbor
            if dist[i] + edge_cost < dist[j]:
                dist[j] = dist[i] + edge_cost

    # find heuristic cost from all nodes to destination
    # use list comprehension
    heuristic_cost = [self.heuristic(n, dest_coords) for n in self.coords]
        
    return dist, heuristic_cost
nodes = 7
# (node_A, node_B, edge_cost)
edges = [(0, 1, 8), (0, 2, 5), (0, 3, 2), (1, 4, 2), (2, 5, 3), \
		     (3, 5, 8), (4, 5, 7), (5, 4, 7), (5, 6, 1), (6, 5, 4) ]
node_coords = [(0, 0),(2,2),(1,2),(1,0),(3,3),(3,2),(4,2)]
g = Graph(nodes, edges, node_coords)
cost, heuristic = g.astar(0, 6)
for node, (dist, heur) in enumerate(zip(cost, heuristic)):
    print(f"Node {node} is at distance {dist}")
    print(f"Node {node} heuristic is  {heur}")<jupyter_output>Node 0 is at distance 0
Node 0 heuristic is  4.47213595499958
Node 1 is at distance 1000
Node 1 heuristic is  2.0
Node 2 is at distance 1000
Node 2 heuristic is  3.0
Node 3 is at distance 1000
Node 3 heuristic is  3.605551275463989
Node 4 is at distance 1000
Node 4 heuristic is  1.4142135623730951
Node 5 is at distance 1000
Node 5 heuristic is  1.0
Node 6 is at distance 1000
Node 6 heuristic is  0.0
{'fraction_non_alphanumeric': 0.11449016100178891, 'fraction_numerical': 0.0569469290399523, 'mean_word_length': 3.252217997465146, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '98038', 'license': 'MIT', 'n_tokens_mistral': 1332, 'n_tokens_neox': 1149, 'n_words': 395, 'path': 'week2/edm19b012/Q2 - Q/Attempt1_filesubmission_search_based_planning.ipynb', 'repo_name': 'naveenmoto/lablet102', 'size': '3354'}