// -> ReadVariableOp1 and AssignVariableOp0 -> AssignVariableOp1 edges will be
// respected by XlaLaunchOp though because all reads happen before all writes
// with that limited clustering..
//
//
// NB!  The result computed by this analysis assumes that we don't auto-cluster
// back-edges (i.e. the edges from NextIteration to Merge).
//

// declaration "type T int", we construct edges T<-A and T<-B with
// weight 1; and because of instantiation "f[T, map[A]B]" we construct
// edges A<-T with weight 0, and B<-A and B<-B with weight 1.
//
// Finally, we look for any positive-weight cycles. Zero-weight cycles
// are allowed because static instantiation will reach a fixed point.

type monoGraph struct {
	vertices []monoVertex
	edges    []monoEdge

// declaration "type T int", we construct edges T<-A and T<-B with
// weight 1; and because of instantiation "f[T, map[A]B]" we construct
// edges A<-T with weight 0, and B<-A and B<-B with weight 1.
//
// Finally, we look for any positive-weight cycles. Zero-weight cycles
// are allowed because static instantiation will reach a fixed point.

type monoGraph struct {
	vertices []monoVertex
	edges    []monoEdge

    const Graph* g, const string& outside_compilation_attr_name);

// Preprocesses edges within the same XLA cluster. It will perform the following
// operations in order:
//
// 0.  Remove edges from source node to outside compilation nodes, and edges
//     from outside compilation nodes to sink node.
// 1a. For edges between different outside compilation clusters, remove the edge

// of edges. An edge connects two nodes. Both nodes and edges must be
// comparable. This is an undirected simple graph.
type _Graph[_Node _NodeC[_Edge], _Edge _EdgeC[_Node]] struct {
	nodes []_Node
}

// _NodeC is the constraints on a node in a graph, given the _Edge type.
type _NodeC[_Edge any] interface {
	comparable
	Edges() []_Edge
}

import java.util.Map.Entry;
import javax.annotation.CheckForNull;

/**
 * A class to represent the set of edges connecting an (implicit) origin node to a target node.
 *
 * <p>The {@link #outEdgeToNode} map allows this class to work on networks with parallel edges. See
 * {@link EdgesConnecting} for a class that is more efficient but forbids parallel edges.
 *
 * @author James Sexton
 * @param <E> Edge parameter type
 */

 * user-defined properties.
 *
 * <p>A {@code Network} built by this class has the following default properties:
 *
 * <ul>
 *   <li>does not allow parallel edges
 *   <li>does not allow self-loops
 *   <li>orders {@link Network#nodes()} and {@link Network#edges()} in the order in which the
 *       elements were added (insertion order)
 * </ul>
 *

@ElementTypesAreNonnullByDefault
abstract class AbstractBaseGraph<N> implements BaseGraph<N> {

  /**
   * Returns the number of edges in this graph; used to calculate the size of {@link Graph#edges()}.
   * This implementation requires O(|N|) time. Classes extending this one may manually keep track of
   * the number of edges as the graph is updated, and override this method for better performance.
   */
  protected long edgeCount() {

    return new AbstractGraph<N>() {
      @Override
      public Set<N> nodes() {
        return AbstractValueGraph.this.nodes();
      }

      @Override
      public Set<EndpointPair<N>> edges() {
        return AbstractValueGraph.this.edges();
      }

      @Override
      public boolean isDirected() {
        return AbstractValueGraph.this.isDirected();
      }

      @Override
      public boolean allowsSelfLoops() {

@ElementTypesAreNonnullByDefault
abstract class AbstractBaseGraph<N> implements BaseGraph<N> {

  /**
   * Returns the number of edges in this graph; used to calculate the size of {@link Graph#edges()}.
   * This implementation requires O(|N|) time. Classes extending this one may manually keep track of
   * the number of edges as the graph is updated, and override this method for better performance.
   */
  protected long edgeCount() {