I write a simple code about dfs in a data file with 720 thousand vertex pair and find stack overflow. I am not quite sure whether it is caused by large data set or problems of my code. Any ideas is appreciated. Code part is showed below:
private void dfs(Graph G, int v) {
dfsMarked[v] = true;
for (Edge e : G.adj(v)) {
int w = e.other(v);
if (!dfsMarked[w]) {
dfsEdgeTo[w] = v;
dfs(G, w);
}
}
}
720 thousand vertex pairs with a pass spanning a few hundred thousand of them will easily overflow stack on most systems.
You needs to switch to an implementation of DFS that uses your own stack allocated independently of Java stack:
Stack<Integer> stack = new Stack<Integer>();
stack.push(start);
while (!stack.empty()) {
int v = stack.pop();
dfsMarked[v] = true;
for (Edge e : G.adj(v)) {
int w = e.other(v);
if (!dfsMarked[w]) {
dfsEdgeTo[w] = v;
stack.push(w);
}
}
}
Note: The above assumes that adjacency lists are unordered. If you need to preserve the specific ordering to match the recursive version, change the nested loop to enumerate adjacency lists in reverse.
