4 Replies Latest reply: May 24, 2007 2:01 PM by 807606 RSS

    Iterators in recursive functions

    807606
      I've been having some trouble in a function that apparently should work perfectly fine. The program is about dealing with graphs, detecting and showing the Euler path and circuit of a given graph

      The following function is a depth first search , for each vertex it searches in depth the adjacent vertexes and checks each edge connecting each pair of vertexes. An iterator is used for each vertex, allowing to cover the list of adjacencies, that are on linked-list
      /* edge[ ] is an array of edges, and the boolean visited defines if that edge already belongs to the circuit or not
         circuit[ ] is an array where the edges of the path are saved
      */
      public boolean Euler(int n, int pos, int numSteps) {
             
              int ind;
              //this section verifies the last step of the Euler circuit
              if (pos==numSteps-2 && typeEuler==EULER_CIRCUIT) { 
                     
                  ind = findEdge(circuito[pos], circuit[pos+2]);
                  if(ind != NOT_FOUND) {
                      circuit[pos+1]=edge[ind].name();
                      return true;
                      
                  } else {
                      edge[ind].set_visited(false);
                      return false;
                  }
              }
              
              else {
                  /* The error is here: when the recursive call returns false (which means that no unvisited edge was found) the iterator doesn't increase, not pointing to the next adjacent vertex to continue building the Euler Path. This happens to all the pending calls, ending the DFS*/
      
                  it = verts[n].vertAdj().iterator(); 
                  pos+=2;
                  while (it.hasNext()) {
                      
                      tempS =(String)it.next();
                      
                      ind=findEdge(verts[n].name(), tempS);
                      
                      if( (ind != NOT_FOUND) && (!tempS.equals(circuit[0]))) {
                          edge[ind].set_visited(true);
                      
                          circuit[pos] = tempS;
                          circuit[pos-1] = edge[ind].nome();
                          n = searchVert(circuito[pos]);                    
                          if(pos==numSteps)  // Ends Euler Path
                              return true;                    
                          if(Euler(n,pos,numSteps))
                              return true;                    
                          else
                              edge[ind].set_visited(false);
                      }
                  }
                  return false;
              }
          }
        • 1. Re: Iterators in recursive functions
          800382
          I'm not entirely understanding what you are doing, but my gut feeling is that you don't realize that this:

          it = verts[n].vertAdj().iterator();

          is creating a new iterator, which starts over from the first index/item in the list/set, and you probably are expecting to reuse the iterator.

          But I could be wrong.
          • 2. Re: Iterators in recursive functions
            807606
            The problem could be there if the pending recursive call had been made outside the while cycle.

            As the recursive call to Euler is made within the cycle, when it returns false the iterator should point to the next adjacent vertex
            • 3. Re: Iterators in recursive functions
              800382
              Where is "it" (the iterator) declared? You realize that the way it looks in the post is that "it" is declared outside the method. That means that ever recursive call to your method is resetting the "it" field to a new iterator. That means by the time it's returned, it's no longer the same iterator your method started with in the first call.
              • 4. Re: Iterators in recursive functions
                807606
                Problem solved!Thanks a lot, you were right. The iterator was declared outside the method, thus changing whenever a recursive call was made. Declaring a new iterator for every call solved the problem