text: let chai = require( 'chai' );
  chai.use( require( 'chai-spies' ) );
  const {
    expect,
    spy
  } = chai;
  
  const {
    Graph
  } = require( '../problems/graph' );
  
  
  describe( 'Graph Implementation', () => {
    describe( '#constructor()', () => {
      it( 'should initialize an `adjList` to an empty object', () => {
        let graph = new Graph();
        expect( graph ).to.have.property( 'adjList' );
        expect( graph.adjList ).to.eql( {} );
      } );
    } );
  
    describe( '#addVertex(vertex)', () => {
      context( 'when the vertex is not in the graph', () => {
        it( 'should initialize a value of a new vertex as an empty array', () => {
          let graph = new Graph();
          graph.addVertex( 'c' )
          expect( graph.adjList ).to.eql( {
            'c': []
          } );
        } );
      } );
  
      context( 'when the vertex is already in the graph', () => {
        it( 'should not add the vertex', () => {
          let graph = new Graph();
          graph.addVertex( 'c' )
          graph.addVertex( 'a' )
          graph.adjList[ 'c' ] = [ 'a' ]
          graph.adjList[ 'a' ] = [ 'c' ]
          graph.addVertex( 'c' ) // second entry
          expect( graph.adjList ).to.eql( {
            'c': [ 'a' ],
            'a': [ 'c' ]
          } );
        } );
      } );
  
  
    } );
  
    describe( '#addEdges(edge1, edge2)', () => {
      context( 'when the graph does not include the edges', () => {
        it( 'should add the edges into the graph first', () => {
          let graph = new Graph();
          graph.addEdges( 'f', 'a' )
          expect( graph.adjList ).to.eql( {
            'f': [ 'a' ],
            'a': [ 'f' ]
          } );
          graph.addEdges( 'f', 'b' )
          expect( graph.adjList ).to.eql( {
            'f': [ 'a', 'b' ],
            'a': [ 'f' ],
            'b': [ 'f' ]
          } );
        } );
      } );
      context( 'when the graph includes the edges', () => {
        beforeEach( () => {
          graph = new Graph();
          graph.addVertex( 'f' )
          graph.addVertex( 'a' )
          graph.addVertex( 'b' )
        } )
        it( 'should add the edges as neighbors', () => {
          let graph = new Graph();
          graph.addEdges( 'f', 'a' )
          expect( graph.adjList ).to.eql( {
            'f': [ 'a' ],
            'a': [ 'f' ]
          } );
          graph.addEdges( 'f', 'b' )
          expect( graph.adjList ).to.eql( {
            'f': [ 'a', 'b' ],
            'a': [ 'f' ],
            'b': [ 'f' ]
          } );
        } );
      } );
  
    } );
  
    describe( '#buildGraph(edgeList)', () => {
      context( 'takes an edge list as an argument and builds a graph', () => {
        it( 'should call `#addvertex` and `#addEdge`', () => {
          const edges = [
            [ 'a', 'b' ],
            [ 'a', 'c' ],
            [ 'a', 'd' ],
            [ 'd', 'g' ],
            [ 'b', 'c' ],
            [ 'b', 'e' ],
            [ 'c', 'f' ],
            [ 'c', 'g' ],
            [ 'f', 'g' ]
          ]
  
          let graph = new Graph();
  
          const graph1 = {
            a: [ 'b', 'c', 'd' ],
            b: [ 'a', 'c', 'e' ],
            c: [ 'a', 'b', 'f', 'g' ],
            d: [ 'a', 'g' ],
            g: [ 'd', 'c', 'f' ],
            e: [ 'b' ],
            f: [ 'c', 'g' ]
          }
  
          expect( graph.buildGraph( edges ) ).to.eql( graph1 );
        } );
      } );
    } );
  
    describe( '#breadthFirstTraversal(startingVertex)', () => {
      let graph;
      const edges = [
        [ 'a', 'b' ],
        [ 'a', 'c' ],
        [ 'a', 'd' ],
        [ 'd', 'g' ],
        [ 'b', 'c' ],
        [ 'b', 'e' ],
        [ 'c', 'f' ],
        [ 'c', 'g' ],
        [ 'f', 'g' ],
        [ 'h' ]
      ]
      beforeEach( () => {
        graph = new Graph();
        for ( let edge of edges ) {
          if ( edge.length === 1 ) {
            graph.addVertex( edge[ 0 ] )
          } else {
            graph.addEdges( edge[ 0 ], edge[ 1 ] )
          }
        }
      } )
      it( 'should not be recursive', () => {
        spy.on( graph, 'breadthFirstTraversal' )
        graph.breadthFirstTraversal( 'a' );
        expect( graph.breadthFirstTraversal ).to.have.been.called.once;
      } );
  
      it( 'should return an array of vertices visited in a bfs order', () => {
        expect( graph.breadthFirstTraversal( 'a' ) ).to.have.ordered.members( [ 'a', 'b', 'c', 'd', 'e', 'f', 'g' ] );
      } );
    } );
  
    describe( '#depthFirstTraversalIterative(startingVertex)', () => {
      let graph;
      const edges = [
        [ 'a', 'b' ],
        [ 'a', 'c' ],
        [ 'a', 'd' ],
        [ 'd', 'g' ],
        [ 'b', 'c' ],
        [ 'b', 'e' ],
        [ 'c', 'f' ],
        [ 'c', 'g' ],
        [ 'f', 'g' ],
        [ 'h' ]
      ]
      beforeEach( () => {
        graph = new Graph();
        for ( let edge of edges ) {
          if ( edge.length === 1 ) {
            graph.addVertex( edge[ 0 ] )
          } else {
            graph.addEdges( edge[ 0 ], edge[ 1 ] )
          }
        }
      } )
      it( 'should not be recursive', () => {
        spy.on( graph, 'depthFirstTraversalIterative' )
        graph.depthFirstTraversalIterative( 'a' );
        expect( graph.depthFirstTraversalIterative ).to.have.been.called.once;
      } );
  
      it( 'should return an array of vertices visited in a dfs order', () => {
        expect( graph.depthFirstTraversalIterative( 'a' ) ).to.have.ordered.members( [ 'a', 'd', 'g', 'f', 'c', 'b', 'e' ] );
      } );
    } );
  
    describe( '#DepthFirstTraversalRecursive(startingVertex)', () => {
      let graph;
      const edges = [
        [ 'a', 'b' ],
        [ 'a', 'c' ],
        [ 'a', 'd' ],
        [ 'd', 'g' ],
        [ 'b', 'c' ],
        [ 'b', 'e' ],
        [ 'c', 'f' ],
        [ 'c', 'g' ],
        [ 'f', 'g' ],
        [ 'h' ]
      ]
      beforeEach( () => {
        graph = new Graph();
        for ( let edge of edges ) {
          if ( edge.length === 1 ) {
            graph.addVertex( edge[ 0 ] )
          } else {
            graph.addEdges( edge[ 0 ], edge[ 1 ] )
          }
        }
      } )
      it( 'should be recursive', () => {
        spy.on( graph, 'depthFirstTraversalRecursive' )
        graph.depthFirstTraversalRecursive( 'a' );
        expect( graph.depthFirstTraversalRecursive ).to.have.been.called.above( 1 );
      } );
  
      it( 'should return an array of vertices visited in a dfs order', () => {
        expect( graph.depthFirstTraversalRecursive( 'a' ) ).to.have.ordered.members( [ 'a', 'b', 'c', 'f', 'g', 'd', 'e' ] );
      } );
    } );
  } );
  