import com.google.common.collect.ImmutableList;
import com.google.errorprone.annotations.CanIgnoreReturnValue;

/**
 * Standard implementation of {@link MutableNetwork} that supports both directed and undirected
 * graphs. Instances of this class should be constructed with {@link NetworkBuilder}.
 *
 * <p>Time complexities for mutation methods are all O(1) except for {@code removeNode(N node)},

   * starting and ending with the same node.
   *
   * <p>This method will detect any non-empty cycle, including self-loops (a cycle of length 1).
   */
  public static boolean hasCycle(Network<?, ?> network) {
    // In a directed graph, parallel edges cannot introduce a cycle in an acyclic graph.
    // However, in an undirected graph, any parallel edge induces a cycle in the graph.
    if (!network.isDirected()
        && network.allowsParallelEdges()

 *
 * <ul>
 *   <li>Test cases related to whether the graph is directed or undirected.
 *   <li>Test cases related to the specific implementation of the {@link Graph} interface.
 * </ul>
 *
 * TODO(user): Make this class generic (using <N, E>) for all node and edge types.
 * TODO(user): Differentiate between directed and undirected edge strings.
 */
@NullUnmarked
public abstract class AbstractGraphTest {

import java.util.Collections;
import java.util.Optional;
import java.util.Set;
import org.jspecify.annotations.NullUnmarked;
import org.junit.After;
import org.junit.Test;

/**
 * Abstract base class for testing directed {@link Network} implementations defined in this package.
 */
@NullUnmarked
public abstract class AbstractStandardDirectedNetworkTest extends AbstractNetworkTest {

  @After
  public void validateSourceAndTarget() {

import static org.junit.Assert.assertThrows;

import java.util.Set;
import org.jspecify.annotations.NullUnmarked;
import org.junit.Test;

/**
 * Abstract base class for testing directed {@link Graph} implementations defined in this package.
 */
@NullUnmarked
public abstract class AbstractStandardDirectedGraphTest extends AbstractGraphTest {

  @Override
  @Test

        // repeat the request (even non-idempotent ones.)
        if (!chain.retryOnConnectionFailure) {
          // The application layer has directed us not to retry the request.
          return null
        }

        val requestBody = userResponse.request.body
        if (requestBody != null && requestBody.isOneShot()) {
          return null
        }

        ImmutableNetwork.copyOf(NetworkBuilder.directed().<String, String>build());
    Network<String, String> network2 = ImmutableNetwork.copyOf(network1);

    assertThat(network2).isSameInstanceAs(network1);
  }

  @Test
  public void edgesConnecting_directed() {
    MutableNetwork<String, String> mutableNetwork =
        NetworkBuilder.directed().allowsSelfLoops(true).build();

    Graph<String> graph1 = ImmutableGraph.copyOf(GraphBuilder.directed().<String>build());
    Graph<String> graph2 = ImmutableGraph.copyOf(graph1);

    assertThat(graph2).isSameInstanceAs(graph1);
  }

  @Test
  public void immutableGraphBuilder_appliesGraphBuilderConfig() {
    ImmutableGraph<String> emptyGraph =
        GraphBuilder.directed()
            .allowsSelfLoops(true)

 * Thread1: acquire(LockA) --X acquire(LockB)
 * Thread2: acquire(LockB) --X acquire(LockC)
 * ...
 * ThreadN: acquire(LockN) --X acquire(LockA)
 * </pre>
 *
 * <p>The implementation detects cycles by constructing a directed graph in which each lock
 * represents a node and each edge represents an acquisition ordering between two locks.
 *
 * <ul>
 *   <li>Each lock adds (and removes) itself to/from a ThreadLocal Set of acquired locks when the

  private static final ImmutableNetwork<String, String> IMMUTABLE_NETWORK_B =
      NetworkBuilder.directed().<String, String>immutable().addNode("B").build();

  public PackageSanityTests() {
    MutableNetwork<String, String> mutableNetworkA = NetworkBuilder.directed().build();
    mutableNetworkA.addNode("a");
    MutableNetwork<String, String> mutableNetworkB = NetworkBuilder.directed().build();