StackOverflow error: How can I avoid it or turn this DFS into an iterative one?

I'm using Depth First Search for maze generation.

The adjacency matrix of M*N vertices is traversed in a random order using DFS, I'm only interested in generating a random route.

The thing works fine with a reduced number of vertices, but I'm getting a StackOverflow Exception when using it with

 Graph theGraph = new Graph(1000,1000);

Questions: a)How can I change this recursive calls to iterative ones using a stack?

b)Is there a way to assign more memory to the method call stack?

class IJ {

        int i;
        int j;

        IJ (int i,int j){
            i = this.i;
            j= this.j;

        }

}


class Graph {

    in开发者_运维技巧t M;
    int N;

    int adjacencyMatrix[][];

    ArrayList <IJ> orderOfVisits;

    Graph(int M,int N){

        this.M=M;
        this.N=N;
        adjacencyMatrix=new int[M][N];

        for (int i=0; i<M; i++)
            for (int j=0;j<N;j++){
                    adjacencyMatrix[i][j]=-1; //mark all vertices as not visited
            }

        orderOfVisits = new ArrayList<IJ>();

    }

 void DFS(int i, int j){ // i,j identifies the vertex

     boolean northValid= false;
     boolean southValid= false;
     boolean eastValid = false;
     boolean westValid = false;


     int iNorth, jNorth;
     int iSouth, jSouth;
     int iEast, jEast;
     int iWest, jWest;

     iNorth=i-1;
     if (!(iNorth<0)) northValid=true;

     iSouth=i+1;
     if(!((iSouth)>=M)) southValid=true;

     jEast=j+1;
     if(!((jEast)>=N)) eastValid=true;

     jWest= j-1;
     if (!(jWest<0)) westValid=true;


    if (adjacencyMatrix[i][j]==-1){ //if the vertex is unvisited

        adjacencyMatrix[i][j]=0; //mark the vertex as visited
        IJ ij = new IJ(i,j);
        orderOfVisits.add(ij); //add the vertex to the visit list
        System.out.println("Visit i,j: " + i +" " +j);



        Double lottery = Math.random();

       for (int rows=i; rows<M; rows++)
           for (int cols=j; cols<N; cols++){


        if (lottery>0.75D){
            if(northValid)
            {
                DFS(iNorth,j);
            }

            if(southValid){
                DFS(iSouth,j);
            }

            if(eastValid){
                DFS(i, jEast);
            }

            if(westValid){
                DFS(i,jWest);
            }


        }

       else if (lottery<0.25D)
       {

            if(westValid){
                DFS(i,jWest);
            }

             if(eastValid){
                DFS(i, jEast);
            }

             if(southValid){
                DFS(iSouth,j);
            }

            if(northValid)
            {
                DFS(iNorth,j);
            }

       }

       else if ((lottery>=0.25D)&&(lottery<0.5D))
       {

             if(southValid){
                DFS(iSouth,j);
            }

             if(eastValid){
                DFS(i, jEast);
            }

            if(westValid){
                DFS(i,jWest);
            }

            if(northValid){
                DFS(iNorth,j);
            }

       }

        else if ((lottery>=0.5D)&&(lottery<=0.75D))
       {

            if(eastValid){
                DFS(i, jEast);
            }

            if(westValid){
                DFS(i,jWest);
            }

            if(southValid){
                DFS(iSouth,j);
            }

            if(northValid){
                DFS(iNorth,j);
            }

       }

    }

 } //end nested for

} //end DFS

//
}


public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here



    Graph theGraph = new Graph(1000,1000);
    theGraph.DFS(0,0);



    }

}

Some pseudo code:

Stack<IJ> nodesToVisit;

nodesToVisit.Push(new IJ(0, 1));
nodesToVisit.Push(new IJ(1, 0));

while (nodesToVisit.Count > 0)
{
    var ij = nodesToVisit.Pop();
    if (visited ij) 
       continue;
    .... mark ij visited
    ... check north/south/east/west validity
    List<IJ> directions = new List<IJ>();
    if (canGoNorth)
        directions.Add(new IJ(iNorth, j));
    if (canGoSouth)
        directions.Add(new IJ(iSouth, j));
    if (canGoEast)
        directions.Add(new IJ(i, jEast));
    if (canGoWest)
        directions.Add(new IJ(i, jWest));
    ... randomize list
    foreach (direction in directions)
       nodesToVisit.Push(direction);
}

Basically:

• Push all possible directions on the stack in random order
• Pick the top item
• Go there
• Repeat until the stack is empty (nor more nodes to be visited)

I don't think increasing your stack limit is a good solution to your problem.

With respect to (b), at least with a Sun/Oracle JVM, you can increase the stack size with the -Xss command line option to the JVM.

You would have to convert the recursive implementation to an iterative one. Often (and I think here, too) a recursive algorithm is a lot easier to understand than an iterative one doing the same things.

In principle, you need to replace the Java method calling stack with an explicit data structure (a stack or such) containing the necessary information.

In your case it would be the current node, and a list of the remaining neighbor nodes to be visited, in the order they should be visited.

class DFSNode {
   DFSNode parent;
   int x, y;
   Queue<Direction> neighborsToVisit;
   DFSNode(DFSNode p, int x, int y) {
      this.parent = p; this.x = x; this.y = y;
      this.neighborsToVisit = new ArrayDeque(3);
   }
}

enum Direction {

   // TODO: check the numbers
   NORTH(0,1), SOUTH(0,-1), EAST(1,0), WEST(-1,0);

   Direction(int dX, dY) {
      deltaX = dX; deltaY = dY;
   }

   private int deltaX, deltaY;

   int nextX(int x) { return x + deltaX; }
   int nextY(int y) { return y + deltaY; }
}

void visitNode(DFSNode node) {
    // TODO: check which adjacent directions are valid,
    // randomize the order of these adjacent directions,
    // fill them in the queue.
}

void visitGraph(int x, int y) {
   DFSNode currentNode = new DFSNode(null,x,y);
   visitNode(currentNode);
   while(currentNode != null) {
      Direction dir = currentNode.neighboursToVisit.poll();
      if(dir == null) {
         // all neighbours of this node already visited
         // ==> trackback to parent (and end if this is root node)
         currentNode = currentNode.parent;
         continue;
      }
      currentNode = new DFSNode(currentNode, dir.nextX(currentNode.x), dir.nextY(currentNode.y));
      visitNode(currentNode);
   }
}

The visitNode would contain the main logic, i.e. what is now in your DFS method. Instead of recursing it would fill the queue with some of the four directions (at most 3, I think), in a order determined by the random() result.

I hope you'll find this helpfull.

You can either increase Stack size with -Xss option or rewrite the code. You can get some ideas here.

http://www.vvlasov.com/2013/07/post-order-iterative-dfs-traversal.html

Code:

public void dfsPostOrderIterative(AdjGraph graph, AdjGraph.Node vertex, Callback callback) { Stack toVisit = new Stack(); toVisit.push(new Level(Collections.singletonList(vertex)));

while (!toVisit.isEmpty()) {
    Level level = toVisit.peek();

    if (level.index >= level.nodes.size()) {
        toVisit.pop();
        continue;
    }

    AdjGraph.Node node = level.nodes.get(level.index);

    if (!node.isVisited()) {
        if (node.isChildrenExplored()) {
            node.markVisited();
            callback.nodeVisited(graph, node);
            level.index++;
        } else {
            List<AdjGraph.Node> edges = graph.edges(node);
            List<AdjGraph.Node> outgoing = Lists.newArrayList(Collections2.filter(edges, new Predicate<AdjGraph.Node>() {
                @Override
                public boolean apply(AdjGraph.Node input) {
                    return !input.isChildrenExplored();
                }
            }));

            if (outgoing.size() > 0)
                toVisit.add(new Level(outgoing));
            node.markChildrenExplored();
        }
    } else {
        level.index++;
    }
}

}