CODEWITHSUNDEEP
javarecursionmethodsdirected-graph
Masteprh33r
Masteprh33r

Reputation: 105

Why is this causing a stack overflow error? Directed graph

I am trying to make a method that traverses a directed graph and all the vertexes are either grey or black, if it goes to black it marks a root as black and so signifies that it doesn't produce a tree. This one keeps giving me a stack overflow error. I would like it to even if it encounters a black one still continue the depth search just so that it doesn't miss any after that.

void colorRoots(Vertex root, Vertex v) {

    if (v.getColor() == DiGraph.BLACK) {
        root.setColor(DiGraph.BLACK);
    }

    for (Vertex g : v.neighbors()) {
        if (g.getColor() == DiGraph.GREY || g.getColor() == DiGraph.BLACK) {
            colorRoots(root, g); 
        }
    }
}

This is the method i use to traverse every root once and coloring. So i call this first before calling the above with roots.

void dfs(Vertex v) {

    if(v.getColor()==DiGraph.GREY) {
        v.setColor(DiGraph.BLACK);
    }else {
        v.setColor(DiGraph.GRAY);
    }


    for (Vertex g : v.neighbors()) {
        if(g.getColor()==DiGraph.WHITE || g.getColor()==DiGraph.GREY) {
        dfs(g); 
        }
    }   
    }

Could the issue be in the dsf method?

The whole plan i had in my head was traversing the graph once from all potential roots, then doing it again and marking all roots that can't produce a tree as black.

Upvotes: 0

Views: 84

Answers (3)

Masteprh33r
Masteprh33r

Reputation: 105

by changing DSF to 

void dfs(Vertex v) {

        v.setColor(DiGraph.GREY);

    for (Vertex g : v.neighbors()) {
        if(g.getColor()==DiGraph.WHITE) {
        dfs(g); 
        }
    }   
    v.setColor(DiGraph.BLACK);
    }

Seemed to solve the issue.

Upvotes: 0

Lai
Lai

Reputation: 482

The recursive call at dfs(g) loop does not seem to have a logical end. Every processed Vertex object calls neighbors() and each neighbor Vertex calls neighbors and each neighbor called calls neighbors ...and on and on.

Upvotes: 0

Samuel Bouffard
Samuel Bouffard

Reputation: 26

Check how you spelled "GRAY" vs "GREY" in dfs, might be the problem.

Upvotes: 1

Related Questions