// Path: src/test/java/io/github/marioluan/datastructures/factory/DigraphGraphFactory.java
// public final class DigraphGraphFactory {
//     private DigraphGraphFactory() {
//     }
// 
//     /**
//      * Builds a graph with the same vertices and edges from lecture slides. <br>
//      * <strong>https://algs4.cs.princeton.edu/lectures/42DirectedGraphs.pdf</strong>
//      */
//     public static Digraph build() {
//         Digraph graph = new Digraph(13);
// 
//         graph.addEdge(0, 1);
//         graph.addEdge(0, 5);
// 
//         graph.addEdge(2, 0);
//         graph.addEdge(2, 3);
// 
//         graph.addEdge(3, 2);
//         graph.addEdge(3, 5);
// 
//         graph.addEdge(4, 2);
//         graph.addEdge(4, 3);
// 
//         graph.addEdge(5, 4);
// 
//         graph.addEdge(6, 0);
//         graph.addEdge(6, 9);
//         graph.addEdge(6, 4);
//         graph.addEdge(6, 8);
// 
//         graph.addEdge(7, 6);
//         graph.addEdge(7, 9);
// 
//         graph.addEdge(8, 6);
// 
//         graph.addEdge(9, 10);
//         graph.addEdge(9, 11);
// 
//         graph.addEdge(10, 12);
// 
//         graph.addEdge(11, 12);
//         graph.addEdge(11, 4);
// 
//         graph.addEdge(12, 9);
// 
//         return graph;
//     }
// }
// 
// Path: src/test/java/io/github/marioluan/datastructures/factory/UndirectedGraphFactory.java
// public final class UndirectedGraphFactory {
//     /**
//      * Builds a graph with the same vertices and edges from lecture slides. <br>
//      * <strong>https://www.coursera.org/learn/algorithms-part2/lecture/mW9aG/depth-first-search</strong>
//      */
//     public static Undirected build() {
//         Undirected graph = new Undirected(13);
// 
//         graph.addEdge(0, 1);
//         graph.addEdge(0, 2);
//         graph.addEdge(0, 5);
//         graph.addEdge(0, 6);
//         graph.addEdge(6, 4);
//         graph.addEdge(4, 3);
//         graph.addEdge(4, 5);
//         graph.addEdge(3, 5);
// 
//         graph.addEdge(7, 8);
// 
//         graph.addEdge(9, 10);
//         graph.addEdge(9, 11);
//         graph.addEdge(9, 12);
//         graph.addEdge(11, 12);
// 
//         return graph;
//     }
// }
// 
// Path: src/main/java/io/github/marioluan/datastructures/graph/Graph.java
// public interface Graph {
// 
//     /**
//      * Adds an edge v-w.
//      *
//      * @param v vertex v
//      * @param w vertex w
//      */
//     void addEdge(int v, int w);
// 
//     /**
//      * Returns the vertices adjacent to v.
//      *
//      * @param v vertex v
//      * @return vertices adjacent to v
//      */
//     Iterable<Integer> adj(int v);
// 
//     /**
//      * Returns the number of vertices.
//      *
//      * @return number of vertices
//      */
//     int V();
// 
//     /**
//      * Returns the number of edges.
//      *
//      * @return number of edges
//      */
//     int E();
// 
//     /**
//      * Returns its reverse order.
//      *
//      * @return its reverse order
//      */
//     Graph reverse();
// 
//     /**
//      * Returns its string representation.
//      *
//      * @return string representation
//      */
//     String toString();
// }
// 
// Path: src/main/java/io/github/marioluan/datastructures/graph/Undirected.java
// public class Undirected implements Graph {
//     private final int V;
//     private int E;
//     private Bag<Integer>[] adj;
// 
//     /**
//      * Creates an empty {@link Digraph}.<br>
//      * time complexity: O(V)
//      *
//      * @param V number of vertices
//      */
//     public Undirected(int V) {
//         this.V = V;
//         adj = (Bag<Integer>[]) new Bag[V];
//         IntStream.range(0, V).forEach(v -> adj[v] = new Bag<>());
//         E = 0;
//     }
// 
//     // time complexity: O(1)
//     @Override
//     public void addEdge(int v, int w) {
//         adj[v].add(w);
//         adj[w].add(v);
//         E++;
//     }
// 
//     // time complexity: degree(v)
//     @Override
//     public Iterable<Integer> adj(int v) {
//         return adj[v];
//     }
// 
//     // time complexity: O(1)
//     @Override
//     public int V() {
//         return V;
//     }
// 
//     // time complexity: O(1)
//     @Override
//     public int E() {
//         return E;
//     }
// 
//     @Override
//     public Graph reverse() {
//         return this;
//     }
// 
//     // TODO: implement me!
//     @Override
//     public String toString() {
//         return null;
//     }
// }


import com.greghaskins.spectrum.Spectrum;
import io.github.marioluan.datastructures.factory.DigraphGraphFactory;
import io.github.marioluan.datastructures.factory.UndirectedGraphFactory;
import io.github.marioluan.datastructures.graph.Graph;
import io.github.marioluan.datastructures.graph.Undirected;
import org.hamcrest.CoreMatchers;
import org.hamcrest.core.IsInstanceOf;
import org.junit.Assert;
import org.junit.runner.RunWith;
import static com.greghaskins.spectrum.Spectrum.*;
package io.github.marioluan.datastructures.graph.search;



@RunWith(Spectrum.class)
public class DepthFirstSearchTest {
// Path: src/test/java/io/github/marioluan/datastructures/factory/DigraphGraphFactory.java
// public final class DigraphGraphFactory {
//     private DigraphGraphFactory() {
//     }
// 
//     /**
//      * Builds a graph with the same vertices and edges from lecture slides. <br>
//      * <strong>https://algs4.cs.princeton.edu/lectures/42DirectedGraphs.pdf</strong>
//      */
//     public static Digraph build() {
//         Digraph graph = new Digraph(13);
// 
//         graph.addEdge(0, 1);
//         graph.addEdge(0, 5);
// 
//         graph.addEdge(2, 0);
//         graph.addEdge(2, 3);
// 
//         graph.addEdge(3, 2);
//         graph.addEdge(3, 5);
// 
//         graph.addEdge(4, 2);
//         graph.addEdge(4, 3);
// 
//         graph.addEdge(5, 4);
// 
//         graph.addEdge(6, 0);
//         graph.addEdge(6, 9);
//         graph.addEdge(6, 4);
//         graph.addEdge(6, 8);
// 
//         graph.addEdge(7, 6);
//         graph.addEdge(7, 9);
// 
//         graph.addEdge(8, 6);
// 
//         graph.addEdge(9, 10);
//         graph.addEdge(9, 11);
// 
//         graph.addEdge(10, 12);
// 
//         graph.addEdge(11, 12);
//         graph.addEdge(11, 4);
// 
//         graph.addEdge(12, 9);
// 
//         return graph;
//     }
// }
// 
// Path: src/test/java/io/github/marioluan/datastructures/factory/UndirectedGraphFactory.java
// public final class UndirectedGraphFactory {
//     /**
//      * Builds a graph with the same vertices and edges from lecture slides. <br>
//      * <strong>https://www.coursera.org/learn/algorithms-part2/lecture/mW9aG/depth-first-search</strong>
//      */
//     public static Undirected build() {
//         Undirected graph = new Undirected(13);
// 
//         graph.addEdge(0, 1);
//         graph.addEdge(0, 2);
//         graph.addEdge(0, 5);
//         graph.addEdge(0, 6);
//         graph.addEdge(6, 4);
//         graph.addEdge(4, 3);
//         graph.addEdge(4, 5);
//         graph.addEdge(3, 5);
// 
//         graph.addEdge(7, 8);
// 
//         graph.addEdge(9, 10);
//         graph.addEdge(9, 11);
//         graph.addEdge(9, 12);
//         graph.addEdge(11, 12);
// 
//         return graph;
//     }
// }
// 
// Path: src/main/java/io/github/marioluan/datastructures/graph/Graph.java
// public interface Graph {
// 
//     /**
//      * Adds an edge v-w.
//      *
//      * @param v vertex v
//      * @param w vertex w
//      */
//     void addEdge(int v, int w);
// 
//     /**
//      * Returns the vertices adjacent to v.
//      *
//      * @param v vertex v
//      * @return vertices adjacent to v
//      */
//     Iterable<Integer> adj(int v);
// 
//     /**
//      * Returns the number of vertices.
//      *
//      * @return number of vertices
//      */
//     int V();
// 
//     /**
//      * Returns the number of edges.
//      *
//      * @return number of edges
//      */
//     int E();
// 
//     /**
//      * Returns its reverse order.
//      *
//      * @return its reverse order
//      */
//     Graph reverse();
// 
//     /**
//      * Returns its string representation.
//      *
//      * @return string representation
//      */
//     String toString();
// }
// 
// Path: src/main/java/io/github/marioluan/datastructures/graph/Undirected.java
// public class Undirected implements Graph {
//     private final int V;
//     private int E;
//     private Bag<Integer>[] adj;
// 
//     /**
//      * Creates an empty {@link Digraph}.<br>
//      * time complexity: O(V)
//      *
//      * @param V number of vertices
//      */
//     public Undirected(int V) {
//         this.V = V;
//         adj = (Bag<Integer>[]) new Bag[V];
//         IntStream.range(0, V).forEach(v -> adj[v] = new Bag<>());
//         E = 0;
//     }
// 
//     // time complexity: O(1)
//     @Override
//     public void addEdge(int v, int w) {
//         adj[v].add(w);
//         adj[w].add(v);
//         E++;
//     }
// 
//     // time complexity: degree(v)
//     @Override
//     public Iterable<Integer> adj(int v) {
//         return adj[v];
//     }
// 
//     // time complexity: O(1)
//     @Override
//     public int V() {
//         return V;
//     }
// 
//     // time complexity: O(1)
//     @Override
//     public int E() {
//         return E;
//     }
// 
//     @Override
//     public Graph reverse() {
//         return this;
//     }
// 
//     // TODO: implement me!
//     @Override
//     public String toString() {
//         return null;
//     }
// }


// Path: src/test/java/io/github/marioluan/datastructures/graph/search/DepthFirstSearchTest.java
import com.greghaskins.spectrum.Spectrum;
import io.github.marioluan.datastructures.factory.DigraphGraphFactory;
import io.github.marioluan.datastructures.factory.UndirectedGraphFactory;
import io.github.marioluan.datastructures.graph.Graph;
import io.github.marioluan.datastructures.graph.Undirected;
import org.hamcrest.CoreMatchers;
import org.hamcrest.core.IsInstanceOf;
import org.junit.Assert;
import org.junit.runner.RunWith;
import static com.greghaskins.spectrum.Spectrum.*;

package io.github.marioluan.datastructures.graph.search;



@RunWith(Spectrum.class)
public class DepthFirstSearchTest {
    private Graph graph;