code: def graph_edit_distance(
      G1,
      G2,
      node_match=None,
      edge_match=None,
      node_subst_cost=None,
      node_del_cost=None,
      node_ins_cost=None,
      edge_subst_cost=None,
      edge_del_cost=None,
      edge_ins_cost=None,
      roots=None,
      upper_bound=None,
      timeout=None,
  ):
      """Returns GED (graph edit distance) between graphs G1 and G2.
  
      Graph edit distance is a graph similarity measure analogous to
      Levenshtein distance for strings.  It is defined as minimum cost
      of edit path (sequence of node and edge edit operations)
      transforming graph G1 to graph isomorphic to G2.
  
      Parameters
      ----------
      G1, G2: graphs
          The two graphs G1 and G2 must be of the same type.
  
      node_match : callable
          A function that returns True if node n1 in G1 and n2 in G2
          should be considered equal during matching.
  
          The function will be called like
  
             node_match(G1.nodes[n1], G2.nodes[n2]).
  
          That is, the function will receive the node attribute
          dictionaries for n1 and n2 as inputs.
  
          Ignored if node_subst_cost is specified.  If neither
          node_match nor node_subst_cost are specified then node
          attributes are not considered.
  
      edge_match : callable
          A function that returns True if the edge attribute dictionaries
          for the pair of nodes (u1, v1) in G1 and (u2, v2) in G2 should
          be considered equal during matching.
  
          The function will be called like
  
             edge_match(G1[u1][v1], G2[u2][v2]).
  
          That is, the function will receive the edge attribute
          dictionaries of the edges under consideration.
  
          Ignored if edge_subst_cost is specified.  If neither
          edge_match nor edge_subst_cost are specified then edge
          attributes are not considered.
  
      node_subst_cost, node_del_cost, node_ins_cost : callable
          Functions that return the costs of node substitution, node
          deletion, and node insertion, respectively.
  
          The functions will be called like
  
             node_subst_cost(G1.nodes[n1], G2.nodes[n2]),
             node_del_cost(G1.nodes[n1]),
             node_ins_cost(G2.nodes[n2]).
  
          That is, the functions will receive the node attribute
          dictionaries as inputs.  The functions are expected to return
          positive numeric values.
  
          Function node_subst_cost overrides node_match if specified.
          If neither node_match nor node_subst_cost are specified then
          default node substitution cost of 0 is used (node attributes
          are not considered during matching).
  
          If node_del_cost is not specified then default node deletion
          cost of 1 is used.  If node_ins_cost is not specified then
          default node insertion cost of 1 is used.
  
      edge_subst_cost, edge_del_cost, edge_ins_cost : callable
          Functions that return the costs of edge substitution, edge
          deletion, and edge insertion, respectively.
  
          The functions will be called like
  
             edge_subst_cost(G1[u1][v1], G2[u2][v2]),
             edge_del_cost(G1[u1][v1]),
             edge_ins_cost(G2[u2][v2]).
  
          That is, the functions will receive the edge attribute
          dictionaries as inputs.  The functions are expected to return
          positive numeric values.
  
          Function edge_subst_cost overrides edge_match if specified.
          If neither edge_match nor edge_subst_cost are specified then
          default edge substitution cost of 0 is used (edge attributes
          are not considered during matching).
  
          If edge_del_cost is not specified then default edge deletion
          cost of 1 is used.  If edge_ins_cost is not specified then
          default edge insertion cost of 1 is used.
  
      roots : 2-tuple
          Tuple where first element is a node in G1 and the second
          is a node in G2.
          These nodes are forced to be matched in the comparison to
          allow comparison between rooted graphs.
  
      upper_bound : numeric
          Maximum edit distance to consider.  Return None if no edit
          distance under or equal to upper_bound exists.
  
      timeout : numeric
          Maximum number of seconds to execute.
          After timeout is met, the current best GED is returned.
  
      Examples
      --------
      >>> G1 = nx.cycle_graph(6)
      >>> G2 = nx.wheel_graph(7)
      >>> nx.graph_edit_distance(G1, G2)
      7.0
  
      >>> G1 = nx.star_graph(5)
      >>> G2 = nx.star_graph(5)
      >>> nx.graph_edit_distance(G1, G2, roots=(0, 0))
      0.0
      >>> nx.graph_edit_distance(G1, G2, roots=(1, 0))
      8.0
  
      See Also
      --------
      optimal_edit_paths, optimize_graph_edit_distance,
  
      is_isomorphic: test for graph edit distance of 0
  
      References
      ----------
      .. [1] Zeina Abu-Aisheh, Romain Raveaux, Jean-Yves Ramel, Patrick
         Martineau. An Exact Graph Edit Distance Algorithm for Solving
         Pattern Recognition Problems. 4th International Conference on
         Pattern Recognition Applications and Methods 2015, Jan 2015,
         Lisbon, Portugal. 2015,
         <10.5220/0005209202710278>. <hal-01168816>
         https://hal.archives-ouvertes.fr/hal-01168816
  
      """
      bestcost = None
      for _, _, cost in optimize_edit_paths(
          G1,
          G2,
          node_match,
          edge_match,
          node_subst_cost,
          node_del_cost,
          node_ins_cost,
          edge_subst_cost,
          edge_del_cost,
          edge_ins_cost,
          upper_bound,
          True,
          roots,
          timeout,
      ):
          # assert bestcost is None or cost < bestcost
          bestcost = cost
      return bestcost
  
file_path: networkx/networkx/algorithms/similarity.py
imports: import math
  import time
  import warnings
  from dataclasses import dataclass
  from itertools import product
  import networkx
label_desc: Use image node_id 2 for calling a global function with example usage: graph_edit_distance(G1, G2, node_match, edge_match, node_subst_cost, node_del_cost, node_ins_cost, edge_subst_cost, edge_del_cost, edge_ins_cost, roots, upper_bound, timeout) and returns: bestcost