class_docstr: Edmonds algorithm [1]_ for finding optimal branchings and spanning
  arborescences.
  
  This algorithm can find both minimum and maximum spanning arborescences and
  branchings.
  
  Notes
  -----
  While this algorithm can find a minimum branching, since it isn't required
  to be spanning, the minimum branching is always from the set of negative
  weight edges which is most likely the empty set for most graphs.
  
  References
  ----------
  .. [1] J. Edmonds, Optimum Branchings, Journal of Research of the National
         Bureau of Standards, 1967, Vol. 71B, p.233-240,
         https://archive.org/details/jresv71Bn4p233
docstr: Returns a branching from G.
  
  Parameters
  ----------
  attr : str
      The edge attribute used to in determining optimality.
  default : float
      The value of the edge attribute used if an edge does not have
      the attribute `attr`.
  kind : {'min', 'max'}
      The type of optimum to search for, either 'min' or 'max'.
  style : {'branching', 'arborescence'}
      If 'branching', then an optimal branching is found. If `style` is
      'arborescence', then a branching is found, such that if the
      branching is also an arborescence, then the branching is an
      optimal spanning arborescences. A given graph G need not have
      an optimal spanning arborescence.
  preserve_attrs : bool
      If True, preserve the other edge attributes of the original
      graph (that are not the one passed to `attr`)
  partition : str
      The edge attribute holding edge partition data. Used in the
      spanning arborescence iterator.
  seed : integer, random_state, or None (default)
      Indicator of random number generation state.
      See :ref:`Randomness<randomness>`.
  
  Returns
  -------
  H : (multi)digraph
      The branching.
code: def find_optimum(
      self,
      attr="weight",
      default=1,
      kind="max",
      style="branching",
      preserve_attrs=False,
      partition=None,
      seed=None,
  ):
      """
      Returns a branching from G.
  
      Parameters
      ----------
      attr : str
          The edge attribute used to in determining optimality.
      default : float
          The value of the edge attribute used if an edge does not have
          the attribute `attr`.
      kind : {'min', 'max'}
          The type of optimum to search for, either 'min' or 'max'.
      style : {'branching', 'arborescence'}
          If 'branching', then an optimal branching is found. If `style` is
          'arborescence', then a branching is found, such that if the
          branching is also an arborescence, then the branching is an
          optimal spanning arborescences. A given graph G need not have
          an optimal spanning arborescence.
      preserve_attrs : bool
          If True, preserve the other edge attributes of the original
          graph (that are not the one passed to `attr`)
      partition : str
          The edge attribute holding edge partition data. Used in the
          spanning arborescence iterator.
      seed : integer, random_state, or None (default)
          Indicator of random number generation state.
          See :ref:`Randomness<randomness>`.
  
      Returns
      -------
      H : (multi)digraph
          The branching.
  
      """
      self._init(
          attr, default, kind, style, preserve_attrs, seed, partition
      )
      uf = self.uf
  
      # This enormous while loop could use some refactoring...
  
      G, B = self.G, self.B
      D = set()
      nodes = iter(list(G.nodes()))
      attr = self._attr
      G_pred = G.pred
  
      def desired_edge(v):
          """
          Find the edge directed toward v with maximal weight.
  
          If an edge partition exists in this graph, return the included edge
          if it exists and no not return any excluded edges. There can only
          be one included edge for each vertex otherwise the edge partition is
          empty.
          """
          edge = None
          weight = -INF
          for u, _, key, data in G.in_edges(v, data=True, keys=True):
              # Skip excluded edges
              if data.get(partition) == nx.EdgePartition.EXCLUDED:
                  continue
              new_weight = data[attr]
              # Return the included edge
              if data.get(partition) == nx.EdgePartition.INCLUDED:
                  weight = new_weight
                  edge = (u, v, key, new_weight, data)
                  return edge, weight
              # Find the best open edge
              if new_weight > weight:
                  weight = new_weight
                  edge = (u, v, key, new_weight, data)
  
          return edge, weight
  
      while True:
          # (I1): Choose a node v in G^i not in D^i.
          try:
              v = next(nodes)
          except StopIteration:
              # If there are no more new nodes to consider, then we *should*
              # meet the break condition (b) from the paper:
              #   (b) every node of G^i is in D^i and E^i is a branching
              # Construction guarantees that it's a branching.
              assert len(G) == len(B)
              if len(B):
                  assert is_branching(B)
  
              if self.store:
                  self.graphs.append(G.copy())
                  self.branchings.append(B.copy())
  
                  # Add these to keep the lengths equal. Element i is the
                  # circuit at level i that was merged to form branching i+1.
                  # There is no circuit for the last level.
                  self.circuits.append([])
                  self.minedge_circuit.append(None)
              break
          else:
              if v in D:
                  # print("v in D", v)
                  continue
  
          # Put v into bucket D^i.
          # print(f"Adding node {v}")
          D.add(v)
          B.add_node(v)
          # End (I1)
  
          # Start cycle detection
          edge, weight = desired_edge(v)
          # print(f"Max edge is {edge!r}")
          if edge is None:
              # If there is no edge, continue with a new node at (I1).
              continue
          else:
              # Determine if adding the edge to E^i would mean its no longer
              # a branching. Presently, v has indegree 0 in B---it is a root.
              u = edge[0]
  
              if uf[u] == uf[v]:
                  # Then adding the edge will create a circuit. Then B
                  # contains a unique path P from v to u. So condition (a)
                  # from the paper does hold. We need to store the circuit
                  # for future reference.
                  Q_nodes, Q_edges = get_path(B, v, u)
                  Q_edges.append(edge[2])  # Edge key
              else:
                  # Then B with the edge is still a branching and condition
                  # (a) from the paper does not hold.
                  Q_nodes, Q_edges = None, None
              # End cycle detection
  
              # THIS WILL PROBABLY BE REMOVED? MAYBE A NEW ARG FOR THIS FEATURE?
              # Conditions for adding the edge.
              # If weight < 0, then it cannot help in finding a maximum branching.
              # This is the root of the problem with minimum branching.
              if self.style == "branching" and weight <= 0:
                  acceptable = False
              else:
                  acceptable = True
  
              # print(f"Edge is acceptable: {acceptable}")
              if acceptable:
                  dd = {attr: weight}
                  if edge[4].get(partition) is not None:
                      dd[partition] = edge[4].get(partition)
                  B.add_edge(u, v, edge[2], **dd)
                  G[u][v][edge[2]][self.candidate_attr] = True
                  uf.union(u, v)
                  if Q_edges is not None:
                      # print("Edge introduced a simple cycle:")
                      # print(Q_nodes, Q_edges)
  
                      # Move to method
                      # Previous meaning of u and v is no longer important.
  
                      # Apply (I2).
                      # Get the edge in the cycle with the minimum weight.
                      # Also, save the incoming weights for each node.
                      minweight = INF
                      minedge = None
                      Q_incoming_weight = {}
                      for edge_key in Q_edges:
                          u, v, data = B.edge_index[edge_key]
                          # We cannot remove an included edges, even if it is
                          # the minimum edge in the circuit
                          w = data[attr]
                          Q_incoming_weight[v] = w
                          if (
                              data.get(partition)
                              == nx.EdgePartition.INCLUDED
                          ):
                              continue
                          if w < minweight:
                              minweight = w
                              minedge = edge_key
  
                      self.circuits.append(Q_edges)
                      self.minedge_circuit.append(minedge)
  
                      if self.store:
                          self.graphs.append(G.copy())
                      # Always need the branching with circuits.
                      self.branchings.append(B.copy())
  
                      # Now we mutate it.
                      new_node = self.template.format(self.level)
  
                      # print(minweight, minedge, Q_incoming_weight)
  
                      G.add_node(new_node)
                      new_edges = []
                      for u, v, key, data in G.edges(
                          data=True, keys=True
                      ):
                          if u in Q_incoming_weight:
                              if v in Q_incoming_weight:
                                  # Circuit edge, do nothing for now.
                                  # Eventually delete it.
                                  continue
                              else:
                                  # Outgoing edge. Make it from new node
                                  dd = data.copy()
                                  new_edges.append(
                                      (new_node, v, key, dd)
                                  )
                          else:
                              if v in Q_incoming_weight:
                                  # Incoming edge. Change its weight
                                  w = data[attr]
                                  w += minweight - Q_incoming_weight[v]
                                  dd = data.copy()
                                  dd[attr] = w
                                  new_edges.append(
                                      (u, new_node, key, dd)
                                  )
                              else:
                                  # Outside edge. No modification necessary.
                                  continue
  
                      G.remove_nodes_from(Q_nodes)
                      B.remove_nodes_from(Q_nodes)
                      D.difference_update(set(Q_nodes))
  
                      for u, v, key, data in new_edges:
                          G.add_edge(u, v, key, **data)
                          if self.candidate_attr in data:
                              del data[self.candidate_attr]
                              B.add_edge(u, v, key, **data)
                              uf.union(u, v)
  
                      nodes = iter(list(G.nodes()))
                      self.level += 1
                  # END STEP (I2)?
  
      # (I3) Branch construction.
      # print(self.level)
      H = self.G_original.__class__()
  
      def is_root(G, u, edgekeys):
          """
          Returns True if `u` is a root node in G.
  
          Node `u` will be a root node if its in-degree, restricted to the
          specified edges, is equal to 0.
  
          """
          if u not in G:
              # print(G.nodes(), u)
              raise Exception(f"{u!r} not in G")
          for v in G.pred[u]:
              for edgekey in G.pred[u][v]:
                  if edgekey in edgekeys:
                      return False, edgekey
          else:
              return True, None
  
      # Start with the branching edges in the last level.
      edges = set(self.branchings[self.level].edge_index)
      while self.level > 0:
          self.level -= 1
  
          # The current level is i, and we start counting from 0.
  
          # We need the node at level i+1 that results from merging a circuit
          # at level i. randomname_0 is the first merged node and this
          # happens at level 1. That is, randomname_0 is a node at level 1
          # that results from merging a circuit at level 0.
          merged_node = self.template.format(self.level)
  
          # The circuit at level i that was merged as a node the graph
          # at level i+1.
          circuit = self.circuits[self.level]
          # print
          # print(merged_node, self.level, circuit)
          # print("before", edges)
          # Note, we ask if it is a root in the full graph, not the branching.
          # The branching alone doesn't have all the edges.
          isroot, edgekey = is_root(
              self.graphs[self.level + 1], merged_node, edges
          )
          edges.update(circuit)
          if isroot:
              minedge = self.minedge_circuit[self.level]
              if minedge is None:
                  raise Exception
  
              # Remove the edge in the cycle with minimum weight.
              edges.remove(minedge)
          else:
              # We have identified an edge at next higher level that
              # transitions into the merged node at the level. That edge
              # transitions to some corresponding node at the current level.
              # We want to remove an edge from the cycle that transitions
              # into the corresponding node.
              # print("edgekey is: ", edgekey)
              # print("circuit is: ", circuit)
              # The branching at level i
              G = self.graphs[self.level]
              # print(G.edge_index)
              target = G.edge_index[edgekey][1]
              for edgekey in circuit:
                  u, v, data = G.edge_index[edgekey]
                  if v == target:
                      break
              else:
                  raise Exception(
                      "Couldn't find edge incoming to merged node."
                  )
  
              edges.remove(edgekey)
  
      self.edges = edges
  
      H.add_nodes_from(self.G_original)
      for edgekey in edges:
          u, v, d = self.graphs[0].edge_index[edgekey]
          dd = {self.attr: self.trans(d[self.attr])}
  
          # Optionally, preserve the other edge attributes of the original
          # graph
          if preserve_attrs:
              for key, value in d.items():
                  if key not in [self.attr, self.candidate_attr]:
                      dd[key] = value
  
          # TODO: make this preserve the key.
          H.add_edge(u, v, **dd)
  
      return H
  
imports: import string
  from dataclasses import dataclass, field
  from enum import Enum
  from operator import itemgetter
  from queue import PriorityQueue
  import networkx
  from networkx.utils import py_random_state
  from .recognition import is_arborescence, is_branching
label_desc: Use image node_id 3 for calling the Edmonds obj's underlying member method code with example usage: obj.find_optimum(attr, default, kind, style, preserve_attrs, partition, seed) and returns: H, edge,  weight, True,  None, edge,  weight, False,  edgekey