code: def asadpour_atsp(G, weight="weight", seed=None, source=None):
      """
      Returns an approximate solution to the traveling salesman problem.
  
      This approximate solution is one of the best known approximations for the
      asymmetric traveling salesman problem developed by Asadpour et al,
      [1]_. The algorithm first solves the Held-Karp relaxation to find a lower
      bound for the weight of the cycle. Next, it constructs an exponential
      distribution of undirected spanning trees where the probability of an
      edge being in the tree corresponds to the weight of that edge using a
      maximum entropy rounding scheme. Next we sample that distribution
      $2 \\lceil \\ln n \\rceil$ times and save the minimum sampled tree once the
      direction of the arcs is added back to the edges. Finally, we augment
      then short circuit that graph to find the approximate tour for the
      salesman.
  
      Parameters
      ----------
      G : nx.DiGraph
          The graph should be a complete weighted directed graph. The
          distance between all paris of nodes should be included and the triangle
          inequality should hold. That is, the direct edge between any two nodes
          should be the path of least cost.
  
      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.
  
      seed : integer, random_state, or None (default)
          Indicator of random number generation state.
          See :ref:`Randomness<randomness>`.
  
      source : node label (default=`None`)
          If given, return the cycle starting and ending at the given node.
  
      Returns
      -------
      cycle : list of nodes
          Returns the cycle (list of nodes) that a salesman can follow to minimize
          the total weight of the trip.
  
      Raises
      ------
      NetworkXError
          If `G` is not complete or has less than two nodes, the algorithm raises
          an exception.
  
      NetworkXError
          If `source` is not `None` and is not a node in `G`, the algorithm raises
          an exception.
  
      NetworkXNotImplemented
          If `G` is an undirected graph.
  
      References
      ----------
      .. [1] A. Asadpour, M. X. Goemans, A. Madry, S. O. Gharan, and A. Saberi,
         An o(log n/log log n)-approximation algorithm for the asymmetric
         traveling salesman problem, Operations research, 65 (2017),
         pp. 1043–1061
  
      Examples
      --------
      >>> import networkx as nx
      >>> import networkx.algorithms.approximation as approx
      >>> G = nx.complete_graph(3, create_using=nx.DiGraph)
      >>> nx.set_edge_attributes(G, {(0, 1): 2, (1, 2): 2, (2, 0): 2, (0, 2): 1, (2, 1): 1, (1, 0): 1}, "weight")
      >>> tour = approx.asadpour_atsp(G,source=0)
      >>> tour
      [0, 2, 1, 0]
      """
      from math import ceil, exp
      from math import log as ln
  
      # Check that G is a complete graph
      N = len(G) - 1
      if N < 2:
          raise nx.NetworkXError("G must have at least two nodes")
      # This check ignores selfloops which is what we want here.
      if any(
          len(nbrdict) - (n in nbrdict) != N
          for n, nbrdict in G.adj.items()
      ):
          raise nx.NetworkXError("G is not a complete DiGraph")
      # Check that the source vertex, if given, is in the graph
      if source is not None and source not in G.nodes:
          raise nx.NetworkXError("Given source node not in G.")
  
      opt_hk, z_star = held_karp_ascent(G, weight)
  
      # Test to see if the ascent method found an integer solution or a fractional
      # solution. If it is integral then z_star is a nx.Graph, otherwise it is
      # a dict
      if not isinstance(z_star, dict):
          # Here we are using the shortcutting method to go from the list of edges
          # returned from eulerian_circuit to a list of nodes
          return _shortcutting(
              nx.eulerian_circuit(z_star, source=source)
          )
  
      # Create the undirected support of z_star
      z_support = nx.MultiGraph()
      for u, v in z_star:
          if (u, v) not in z_support.edges:
              edge_weight = min(G[u][v][weight], G[v][u][weight])
              z_support.add_edge(u, v, **{weight: edge_weight})
  
      # Create the exponential distribution of spanning trees
      gamma = spanning_tree_distribution(z_support, z_star)
  
      # Write the lambda values to the edges of z_support
      z_support = nx.Graph(z_support)
      lambda_dict = {
          (u, v): exp(gamma[(u, v)]) for u, v in z_support.edges()
      }
      nx.set_edge_attributes(z_support, lambda_dict, "weight")
      del gamma, lambda_dict
  
      # Sample 2 * ceil( ln(n) ) spanning trees and record the minimum one
      minimum_sampled_tree = None
      minimum_sampled_tree_weight = math.inf
      for _ in range(2 * ceil(ln(G.number_of_nodes()))):
          sampled_tree = random_spanning_tree(
              z_support, "weight", seed=seed
          )
          sampled_tree_weight = sampled_tree.size(weight)
          if sampled_tree_weight < minimum_sampled_tree_weight:
              minimum_sampled_tree = sampled_tree.copy()
              minimum_sampled_tree_weight = sampled_tree_weight
  
      # Orient the edges in that tree to keep the cost of the tree the same.
      t_star = nx.MultiDiGraph()
      for u, v, d in minimum_sampled_tree.edges(data=weight):
          if d == G[u][v][weight]:
              t_star.add_edge(u, v, **{weight: d})
          else:
              t_star.add_edge(v, u, **{weight: d})
  
      # Find the node demands needed to neutralize the flow of t_star in G
      node_demands = {
          n: t_star.out_degree(n) - t_star.in_degree(n) for n in t_star
      }
      nx.set_node_attributes(G, node_demands, "demand")
  
      # Find the min_cost_flow
      flow_dict = nx.min_cost_flow(G, "demand")
  
      # Build the flow into t_star
      for source, values in flow_dict.items():
          for target in values:
              if (source, target) not in t_star.edges and values[
                  target
              ] > 0:
                  # IF values[target] > 0 we have to add that many edges
                  for _ in range(values[target]):
                      t_star.add_edge(source, target)
  
      # Return the shortcut eulerian circuit
      circuit = nx.eulerian_circuit(t_star, source=source)
      return _shortcutting(circuit)
  
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 6 for calling a global function with example usage: asadpour_atsp(G, weight, seed, source) and returns: _shortcutting, _shortcutting