private void parseRec ( BitSet traversed , BitSet extension , BitSet forbidden ) { BitSet newTraversed = null ; BitSet newExtension = null ; BitSet newForbidden = null ; BitSet potentialNode = null ; // Test whether the timeout is reached. Stop searching. if ( this . timeout > - 1 && ( System . currentTimeMillis ( ) - this . start ) > this . timeout ) { stop = true ; } // if there is no more extension possible we // have reached a potential new solution if ( extension . isEmpty ( ) ) { solution ( traversed ) ; } // carry on with each possible extension else { // calculates the set of nodes that may still // be reached at this stage (not forbidden) potentialNode = ( ( BitSet ) graphBitSet . clone ( ) ) ; potentialNode . andNot ( forbidden ) ; potentialNode . or ( traversed ) ; // checks if we must continue the search // according to the potential node set if ( mustContinue ( potentialNode ) ) { // carry on research and update iteration count nbIteration ++ ; // for each node in the set of possible extension (neighbors of // the current partial solution, include the node to the solution // and parse recursively the RGraph with the new context. for ( int x = extension . nextSetBit ( 0 ) ; x >= 0 && ! stop ; x = extension . nextSetBit ( x + 1 ) ) { // evaluates the new set of forbidden nodes // by including the nodes not compatible with the // newly accepted node. newForbidden = ( BitSet ) forbidden . clone ( ) ; newForbidden . or ( ( ( RNode ) graph . get ( x ) ) . forbidden ) ; // if it is the first time we are here then // traversed is empty and we initialize the set of // possible extensions to the extension of the first // accepted node in the solution. if ( traversed . isEmpty ( ) ) { newExtension = ( BitSet ) ( ( ( RNode ) graph . get ( x ) ) . extension . clone ( ) ) ; } // else we simply update the set of solution by // including the neighbors of the newly accepted node else { newExtension = ( BitSet ) extension . clone ( ) ; newExtension . or ( ( ( RNode ) graph . get ( x ) ) . extension ) ; } // extension my not contain forbidden nodes newExtension . andNot ( newForbidden ) ; // create the new set of traversed node // (update current partial solution) // and add x to the set of forbidden node // (a node may only appear once in a solution) newTraversed = ( BitSet ) traversed . clone ( ) ; newTraversed . set ( x ) ; forbidden . set ( x ) ; // parse recursively the RGraph parseRec ( newTraversed , newExtension , newForbidden ) ; } } } }
Parsing of the RGraph . This is the recursive method to perform a query . The method will recursively parse the RGraph thru connected nodes and visiting the RGraph using allowed adjacency relationship .