public int dfs ( int root , boolean isRootT1 , boolean [ ] marked1 , boolean [ ] marked2 , BipVisitor < T1 , T2 > visitor ) { IntStack sNode = new IntStack ( ) ; ByteStack sIsT1 = new ByteStack ( ) ; // TODO: This should be a boolean stack. sNode . push ( root ) ; sIsT1 . push ( ( byte ) ( isRootT1 ? 1 : 0 ) ) ; // The number of times we check if any node is marked. // For acyclic graphs this should be two times the number of nodes. int numMarkedChecks = 0 ; while ( sNode . size ( ) != 0 ) { int node = sNode . pop ( ) ; boolean isT1 = ( sIsT1 . pop ( ) == 1 ) ; if ( isT1 ) { // Visit node only if not marked. int t1 = node ; if ( ! marked1 [ t1 ] ) { marked1 [ t1 ] = true ; if ( visitor != null ) { visitor . visit ( t1 , true , this ) ; } for ( int nb = numNbsT1 ( t1 ) - 1 ; nb >= 0 ; nb -- ) { int t2 = childT1 ( t1 , nb ) ; if ( ! marked2 [ t2 ] ) { sNode . push ( t2 ) ; sIsT1 . push ( ( byte ) 0 ) ; } numMarkedChecks ++ ; } } numMarkedChecks ++ ; } else { // Visit node only if not marked. int t2 = node ; if ( ! marked2 [ t2 ] ) { marked2 [ t2 ] = true ; if ( visitor != null ) { visitor . visit ( t2 , false , this ) ; } for ( int nb = numNbsT2 ( t2 ) - 1 ; nb >= 0 ; nb -- ) { int t1 = childT2 ( t2 , nb ) ; if ( ! marked1 [ t1 ] ) { sNode . push ( t1 ) ; sIsT1 . push ( ( byte ) 1 ) ; } numMarkedChecks ++ ; } } numMarkedChecks ++ ; } } return numMarkedChecks ; }
Runs a depth - first - search starting at the root node .