code: def christofides(G, weight="weight", tree=None):
      """Approximate a solution of the traveling salesman problem
  
      Compute a 3/2-approximation of the traveling salesman problem
      in a complete undirected graph using Christofides [1]_ algorithm.
  
      Parameters
      ----------
      G : Graph
          `G` should be a complete weighted undirected graph.
          The distance between all pairs of nodes should be included.
  
      weight : string, optional (default="weight")
          Edge data key corresponding to the edge weight.
          If any edge does not have this attribute the weight is set to 1.
  
      tree : NetworkX graph or None (default: None)
          A minimum spanning tree of G. Or, if None, the minimum spanning
          tree is computed using :func:`networkx.minimum_spanning_tree`
  
      Returns
      -------
      list
          List of nodes in `G` along a cycle with a 3/2-approximation of
          the minimal Hamiltonian cycle.
  
      References
      ----------
      .. [1] Christofides, Nicos. "Worst-case analysis of a new heuristic for
         the travelling salesman problem." No. RR-388. Carnegie-Mellon Univ
         Pittsburgh Pa Management Sciences Research Group, 1976.
      """
      # Remove selfloops if necessary
      loop_nodes = nx.nodes_with_selfloops(G)
      try:
          node = next(loop_nodes)
      except StopIteration:
          pass
      else:
          G = G.copy()
          G.remove_edge(node, node)
          G.remove_edges_from((n, n) for n in loop_nodes)
      # Check that G is a complete graph
      N = len(G) - 1
      # This check ignores selfloops which is what we want here.
      if any(len(nbrdict) != N for n, nbrdict in G.adj.items()):
          raise nx.NetworkXError("G must be a complete graph.")
  
      if tree is None:
          tree = nx.minimum_spanning_tree(G, weight=weight)
      L = G.copy()
      L.remove_nodes_from(
          [v for v, degree in tree.degree if not (degree % 2)]
      )
      MG = nx.MultiGraph()
      MG.add_edges_from(tree.edges)
      edges = nx.min_weight_matching(L, weight=weight)
      MG.add_edges_from(edges)
      return _shortcutting(nx.eulerian_circuit(MG))
  
file_path: networkx/networkx/algorithms/approximation/traveling_salesman.py
imports: import math
  import networkx
  from networkx.algorithms.tree.mst import random_spanning_tree
  from networkx.utils import not_implemented_for, pairwise, py_random_state
label_desc: Use image node_id 3 for calling a global function with example usage: christofides(G, weight, tree) and returns: _shortcutting