code: def __init__(
      self,
      G1,
      G2,
      parent_matched_cost,
      parent_matched_nodes,
      parent_matched_edges,
      node_G1,
      node_G2,
      parent_unprocessed_nodes_G1,
      parent_unprocessed_nodes_G2,
      parent_unprocessed_edges_G1,
      parent_unprocessed_edges_G2,
      cost_matrix_nodes,
      cost_matrix_edges,
  ):
      self.matched_cost = parent_matched_cost
      self.future_approximate_cost = 0.0
      self.matched_nodes = deepcopy(parent_matched_nodes)
      self.matched_nodes[0].append(node_G1)
      self.matched_nodes[1].append(node_G2)
      self.matched_edges = deepcopy(parent_matched_edges)
      self.unprocessed_nodes_G1 = [
          _ for _ in parent_unprocessed_nodes_G1 if _ != node_G1
      ]
      self.unprocessed_nodes_G2 = [
          _ for _ in parent_unprocessed_nodes_G2 if _ != node_G2
      ]
  
      # Add the cost of matching nodes at this tree-node to the matched cost
      if (
          node_G1 is not None and node_G2 is not None
      ):  # Substitute node_G1 with node_G2
          self.matched_cost += cost_matrix_nodes[node_G1, node_G2]
      elif node_G1 is not None:  # Delete node_G1
          self.matched_cost += cost_matrix_nodes[
              node_G1, node_G1 + G2.num_nodes()
          ]
      elif node_G2 is not None:  # Insert node_G2
          self.matched_cost += cost_matrix_nodes[
              node_G2 + G1.num_nodes(), node_G2
          ]
  
      # Add the cost of matching edges at this tree-node to the matched cost
      incident_edges_G1 = []
      if (
          node_G1 is not None
      ):  # Find the edges with one end-point as node_G1 and other in matched nodes or node_G1
          (
              incident_edges_G1,
              index_G1,
              direction_G1,
          ) = get_edges_to_match(G1, node_G1, parent_matched_nodes[0])
  
      incident_edges_G2 = np.array([])
      if (
          node_G2 is not None
      ):  # Find the edges with one end-point as node_G2 and other in matched nodes or node_G2
          (
              incident_edges_G2,
              index_G2,
              direction_G2,
          ) = get_edges_to_match(G2, node_G2, parent_matched_nodes[1])
  
      if (
          len(incident_edges_G1) > 0 and len(incident_edges_G2) > 0
      ):  # Consider substituting
          matched_edges_cost_matrix = subset_cost_matrix(
              cost_matrix_edges,
              incident_edges_G1,
              incident_edges_G2,
              G1.num_edges(),
              G2.num_edges(),
          )
          max_sum = matched_edges_cost_matrix.sum()
          # take care of impossible assignments by assigning maximum cost
          for i in range(len(incident_edges_G1)):
              for j in range(len(incident_edges_G2)):
                  # both edges need to have same direction and the other end nodes are matched
                  if (
                      direction_G1[i] == direction_G2[j]
                      and index_G1[i] == index_G2[j]
                  ):
                      continue
                  else:
                      matched_edges_cost_matrix[i, j] = max_sum
          # Match the edges as per the LAP solution
          row_ind, col_ind, _ = lapjv(matched_edges_cost_matrix)
          lap_cost = 0.00
          for i in range(len(row_ind)):
              lap_cost += matched_edges_cost_matrix[i, row_ind[i]]
  
          # Update matched edges
          for i in range(len(row_ind)):
              if i < len(incident_edges_G1):
                  self.matched_edges[0].append(incident_edges_G1[i])
                  if row_ind[i] < len(incident_edges_G2):
                      self.matched_edges[1].append(
                          incident_edges_G2[row_ind[i]]
                      )
                  else:
                      self.matched_edges[1].append(None)
              elif row_ind[i] < len(incident_edges_G2):
                  self.matched_edges[0].append(None)
                  self.matched_edges[1].append(
                      incident_edges_G2[row_ind[i]]
                  )
          self.matched_cost += lap_cost
  
      elif len(incident_edges_G1) > 0:  # only deletion possible
          edge_deletion_cost = 0.0
          for edge in incident_edges_G1:
              edge_deletion_cost += cost_matrix_edges[
                  edge, G2.num_edges() + edge
              ]
          # Update matched edges
          for edge in incident_edges_G1:
              self.matched_edges[0].append(edge)
              self.matched_edges[1].append(None)
  
              # Update matched edges
  
          self.matched_cost += edge_deletion_cost
  
      elif len(incident_edges_G2) > 0:  # only insertion possible
          edge_insertion_cost = 0.0
          for edge in incident_edges_G2:
              edge_insertion_cost += cost_matrix_edges[
                  G1.num_edges() + edge, edge
              ]
          # Update matched edges
          for edge in incident_edges_G2:
              self.matched_edges[0].append(None)
              self.matched_edges[1].append(edge)
  
          self.matched_cost += edge_insertion_cost
  
      # Add the cost of matching of unprocessed nodes to the future approximate cost
      if (
          len(self.unprocessed_nodes_G1) > 0
          and len(self.unprocessed_nodes_G2) > 0
      ):  # Consider substituting
          unmatched_nodes_cost_matrix = subset_cost_matrix(
              cost_matrix_nodes,
              self.unprocessed_nodes_G1,
              self.unprocessed_nodes_G2,
              G1.num_nodes(),
              G2.num_nodes(),
          )
          # Match the edges as per the LAP solution
          row_ind, col_ind, _ = lapjv(unmatched_nodes_cost_matrix)
          lap_cost = 0.00
          for i in range(len(row_ind)):
              lap_cost += unmatched_nodes_cost_matrix[i, row_ind[i]]
  
          self.future_approximate_cost += lap_cost
  
      elif len(self.unprocessed_nodes_G1) > 0:  # only deletion possible
          node_deletion_cost = 0.0
          for node in self.unprocessed_nodes_G1:
              node_deletion_cost += cost_matrix_nodes[
                  node, G2.num_nodes() + node
              ]
  
          self.future_approximate_cost += node_deletion_cost
  
      elif (
          len(self.unprocessed_nodes_G2) > 0
      ):  # only insertion possible
          node_insertion_cost = 0.0
          for node in self.unprocessed_nodes_G2:
              node_insertion_cost += cost_matrix_nodes[
                  G1.num_nodes() + node, node
              ]
  
          self.future_approximate_cost += node_insertion_cost
  
      # Add the cost of LAP matching of unprocessed edges to the future approximate cost
      self.unprocessed_edges_G1 = [
          _
          for _ in parent_unprocessed_edges_G1
          if _ not in incident_edges_G1
      ]
      self.unprocessed_edges_G2 = [
          _
          for _ in parent_unprocessed_edges_G2
          if _ not in incident_edges_G2
      ]
      if (
          len(self.unprocessed_edges_G1) > 0
          and len(self.unprocessed_edges_G2) > 0
      ):  # Consider substituting
          unmatched_edges_cost_matrix = subset_cost_matrix(
              cost_matrix_edges,
              self.unprocessed_edges_G1,
              self.unprocessed_edges_G2,
              G1.num_edges(),
              G2.num_edges(),
          )
          # Match the edges as per the LAP solution
          row_ind, col_ind, _ = lapjv(unmatched_edges_cost_matrix)
          lap_cost = 0.00
          for i in range(len(row_ind)):
              lap_cost += unmatched_edges_cost_matrix[i, row_ind[i]]
  
          self.future_approximate_cost += lap_cost
  
      elif len(self.unprocessed_edges_G1) > 0:  # only deletion possible
          edge_deletion_cost = 0.0
          for edge in self.unprocessed_edges_G1:
              edge_deletion_cost += cost_matrix_edges[
                  edge, G2.num_edges() + edge
              ]
  
          self.future_approximate_cost += edge_deletion_cost
  
      elif (
          len(self.unprocessed_edges_G2) > 0
      ):  # only insertion possible
          edge_insertion_cost = 0.0
          for edge in self.unprocessed_edges_G2:
              edge_insertion_cost += cost_matrix_edges[
                  G1.num_edges() + edge, edge
              ]
  
          self.future_approximate_cost += edge_insertion_cost
  
file_path: dgl/examples/pytorch/graph_matching/ged.py
imports: from copy import deepcopy
  from heapq import heapify, heappop, heappush, nsmallest
  import dgl
  import numpy
  from lapjv import lapjv
label_desc: Use image node_id 1 to create a new search_tree_node object  with example: obj = search_tree_node(G1, G2, parent_matched_cost, parent_matched_nodes, parent_matched_edges, node_G1, node_G2, parent_unprocessed_nodes_G1, parent_unprocessed_nodes_G2, parent_unprocessed_edges_G1, parent_unprocessed_edges_G2, cost_matrix_nodes, cost_matrix_edges)