1+ 'use strict' ;
2+
3+ var sampleGraph = [ [ 1 , 1 , 1 , 0 , 0 , 0 ] ,
4+ [ 0 , 1 , 1 , 1 , 0 , 0 ] ,
5+ [ 1 , 0 , 1 , 1 , 1 , 0 ] ,
6+ [ 0 , 1 , 0 , 1 , 1 , 0 ] ,
7+ [ 0 , 1 , 0 , 1 , 1 , 0 ] ,
8+ [ 0 , 1 , 0 , 1 , 1 , 0 ] ,
9+ [ 0 , 0 , 1 , 1 , 1 , 1 ] ,
10+ [ 0 , 0 , 0 , 0 , 1 , 1 ] ] ;
11+
12+ var dfs = require ( '../../../src/graphs/searching/dfs' ) . depthFirstSearch ;
13+
14+ describe ( 'dfs' , function ( ) {
15+
16+ it ( 'should work with incorrect input' , function ( ) {
17+ expect ( function ( ) {
18+ dfs ( null , [ 1 , 1 ] , [ 1 , 1 ] ) ;
19+ } ) . toThrow ( ) ;
20+ expect ( function ( ) {
21+ dfs ( sampleGraph , [ - 1 , - 1 ] , [ 0 , 0 ] ) ;
22+ } ) . toThrow ( ) ;
23+ expect ( function ( ) {
24+ dfs ( sampleGraph , [ 0 , - 1 ] , [ - 1 , 0 ] ) ;
25+ } ) . toThrow ( ) ;
26+ expect ( function ( ) {
27+ dfs ( sampleGraph , [ 0 , 0 ] , [ - 1 , 0 ] ) ;
28+ } ) . toThrow ( ) ;
29+ expect ( function ( ) {
30+ dfs ( sampleGraph , [ 0 , 1000 ] , [ - 1 , 0 ] ) ;
31+ } ) . toThrow ( ) ;
32+ expect ( function ( ) {
33+ dfs ( sampleGraph , [ 100000 , 1000 ] , [ - 1 , 0 ] ) ;
34+ } ) . toThrow ( ) ;
35+ expect ( function ( ) {
36+ dfs ( sampleGraph , [ 0 , 0 ] , [ 100 , 100 ] ) ;
37+ } ) . toThrow ( ) ;
38+ expect ( function ( ) {
39+ dfs ( sampleGraph , [ 0 , 0 ] , [ 5 , 5 ] ) ;
40+ } ) . not . toThrow ( ) ;
41+ } ) ;
42+
43+ it ( 'should work with 1x1 matrix' , function ( ) {
44+ var graph = [ [ 1 ] ] ;
45+ expect ( dfs ( graph , [ 0 , 0 ] , [ 0 , 0 ] ) ) . toBeTruthy ( ) ;
46+ graph = [ [ 0 ] ] ;
47+ expect ( dfs ( graph , [ 0 , 0 ] , [ 0 , 0 ] ) ) . toBeFalsy ( ) ;
48+ } ) ;
49+
50+ it ( 'should work in the general case' , function ( ) {
51+ expect ( dfs ( sampleGraph , [ 0 , 0 ] , [ 1 , 1 ] ) ) . toBeTruthy ( ) ;
52+ expect ( dfs ( sampleGraph , [ 0 , 0 ] , [ 6 , 5 ] ) ) . toBeTruthy ( ) ;
53+ expect ( dfs ( sampleGraph , [ 0 , 0 ] , [ 0 , 5 ] ) ) . toBeFalsy ( ) ;
54+ expect ( dfs ( sampleGraph , [ 1 , 1 ] , [ 6 , 5 ] ) ) . toBeTruthy ( ) ;
55+ expect ( dfs ( sampleGraph , [ 1 , 1 ] , [ 0 , 5 ] ) ) . toBeFalsy ( ) ;
56+ } ) ;
57+
58+ } ) ;