StackOverflowError during Depth First Search run (undirected graph)

Question

I have a recursive DFS visit method that sometimes raises a StackOverflowError. Since the size of the graph is large (about 20,000 vertices), there are many recursive calls, so I tried to work with -Xss10M, and everything works. I just wanted to understand why when adding the System.out.println method at the beginning, even without -Xss10M, the method does not throw any StackOverflowError. How is this possible?

This is the method of visiting DFS:

private int dfsVisit(Vertex<T> v, int time){ // System.out.println("Hello"); Vertex<T> n; time++; vd = time; v.color = Vertex.Color.GRAY; for (Map.Entry<Vertex<T>, Float> a : v.neighbours.entrySet()){ n = a.getKey(); if(n.color == Vertex.Color.WHITE){ n.previous = v; time = dfsVisit(n, time); } } v.color = Vertex.Color.BLACK; time++; vf = time; return time; } 

This is the complete code.

 import java.io.*; import java.util.*; class Graph<T> { private final Map<T, Vertex<T>> graph; public static class Edge<T>{ public final T v1, v2; public final float dist; public Edge(T v1, T v2, float dist) { this.v1 = v1; this.v2 = v2; this.dist = dist; } } public static class Vertex<T> implements Comparable<Vertex>{ // SPOSTARE VAR IST NEL COSTRUTTORE public enum Color {WHITE, GRAY, BLACK, UNKNOWN}; public final T name; public float dist; public Vertex<T> previous; public final Map<Vertex<T>, Float> neighbours; public Color color; public int d, f; public Vertex(T name) { this.name = name; dist = Float.MAX_VALUE; previous = null; neighbours = new HashMap<Vertex<T>, Float>(); // adjacency list color = Color.UNKNOWN; d = 0; f = 0; } private void printPath() { if (this == this.previous) { System.out.print(this.name); } else if (this.previous == null) { System.out.print(this.name + " unreached"); } else { this.previous.printPath(); System.out.print(" -> " + this.name + "(" + this.dist + ")"); } } public int compareTo(Vertex other){ if(this.dist == other.dist) return 0; else if(this.dist > other.dist) return 1; else return -1; } } // Builds a graph from an array of edges public Graph(ArrayList<Graph.Edge> edges) { graph = new HashMap<>(edges.size()); // add vertices for (Edge<T> e : edges) { if (!graph.containsKey(e.v1)) graph.put(e.v1, new Vertex<>(e.v1)); if (!graph.containsKey(e.v2)) graph.put(e.v2, new Vertex<>(e.v2)); } // create adjacency list for (Edge<T> e : edges) { graph.get(e.v1).neighbours.put(graph.get(e.v2), e.dist); graph.get(e.v2).neighbours.put(graph.get(e.v1), e.dist); } } public void dijkstra(T startName) { if (!graph.containsKey(startName)) { System.err.println("Graph doesn't contain start vertex " + startName); return; } final Vertex<T> source = graph.get(startName); NavigableSet<Vertex<T>> q = new TreeSet<>(); // priority queue // set-up vertices for (Vertex<T> v : graph.values()) { v.previous = v == source ? source : null; v.dist = v == source ? 0 : Float.MAX_VALUE; q.add(v); } dijkstra(q); } private void dijkstra(final NavigableSet<Vertex<T>> q) { Vertex<T> u, v; while (!q.isEmpty()) { u = q.pollFirst(); if (u.dist == Float.MAX_VALUE) break; //??????????? for (Map.Entry<Vertex<T>, Float> a : u.neighbours.entrySet()) { v = a.getKey(); final float alternateDist = u.dist + a.getValue(); if (alternateDist < v.dist) { q.remove(v); v.dist = alternateDist; v.previous = u; q.add(v); } } } } public void printPath(T endName) { if (!graph.containsKey(endName)) { System.err.println("Graph doesn't contain end vertex " + "\"" + endName + "\"" ); return; } graph.get(endName).printPath(); System.out.println(); } public void printAllPaths() { for (Vertex<T> v : graph.values()) { v.printPath(); System.out.println(); } } public Vertex<T> getVertex(T key){ if(graph.containsKey(key)) return graph.get(key); return null; } public void printAdjacencyList(){ System.out.println("Adjacency list:"); for(Vertex<T> v : graph.values()){ System.out.print(v.name + ":\t"); for (Map.Entry<Vertex<T>, Float> a : v.neighbours.entrySet()){ System.out.print(a.getKey().name + "(" + a.getValue() + ") | "); } System.out.println(); } } /* PS I know that if only used to calculate the connected components of the graph, dfs visit could be written differently but I preferred to write it in a more general way, so that it can be reused if necessary. */ private int dfsVisit(Vertex<T> v, int time){ // System.out.println("ciao"); Vertex<T> n; time++; vd = time; v.color = Vertex.Color.GRAY; for (Map.Entry<Vertex<T>, Float> a : v.neighbours.entrySet()){ n = a.getKey(); if(n.color == Vertex.Color.WHITE){ n.previous = v; time = dfsVisit(n, time); } } v.color = Vertex.Color.BLACK; time++; vf = time; return time; } /* Print the size of the connected components of the graph */ public void connectedComponents(){ for(Vertex<T> v : graph.values()){ v.color = Vertex.Color.WHITE; v.previous = null; } for(Vertex<T> v : graph.values()){ if(v.color == Vertex.Color.WHITE) System.out.println(dfsVisit(v, 0)/2); } } } 

here is the test class

 import java.io.*; import java.util.*; public class Dijkstra { private static ArrayList<Graph.Edge> a = new ArrayList<Graph.Edge>(); private static final String START = "torino"; private static final String END = "catania"; public static void main(String[] args) { String fileName = "italian_dist_graph.txt"; try{ Scanner inputStream = new Scanner(new File(fileName)); String record; while(inputStream.hasNextLine()){ record = inputStream.nextLine(); String[] array = record.split(","); String from = array[0]; String to = array[1]; float dist = Float.parseFloat(array[2]); a.add(new Graph.Edge(from, to, dist)); } inputStream.close(); } catch(FileNotFoundException e){ System.out.println("Impossibile trovare il file "+fileName); } Graph<String> g = new Graph<String>(a); g.dijkstra(START); g.printPath(END); //System.out.printf("%f\n", g.getVertex(END).dist/1000.0f); g.connectedComponents(); } } 

NB try to comment on g.dijkstra (START) and g.printPath (END); everything works.

Here is a link to the dataset

 https://drive.google.com/open?id=0B7XZY8cd0L_fZVl1aERlRmhQN0k 

Answer 1

Some general recommendations:
Your code mixes the vertex attributes associated with one dfs run and those that are direct vertex attributes. Bad bad style . This is likely to violate a more complex algorithm, may lead to unexpected behavior and require clearing states after each run to ensure code stability. Instead, save the states associated with one run of the algorithm, only visible for this function. For instance. save states inside the Map , use the decorator template to create a data structure that provides additional attributes and has a local method area, etc. As an example: running your code twice on the same chart (the same Object ) with the same input without clearing all states will lead to an incorrect result (1).

Also: creating an iterative version of DFS is not very difficult, so you should try, especially because your graph looks pretty big.

As for why your code works (or not), how it does it:
This is hard to say, since it depends on many factors. You did not provide the complete code, so I cannot repeat any tests or make sure that everything behaves as it should. Most likely answers:

Vertex uses the default hash code provided by Object . This leads to a random ordering of entries on the map of neighbors, so the order of passage of certain paths is random in each run and, most likely, different. Thus, you are viewing a graph using random paths that are very likely (especially due to the size of your graph) to differ for each run. The reason is not System.out.println , but the fact that your code generates a different structure (from POV ordering, not mathematically), every time it works, plus the coincidence that for some rather strange reason, every assembly schedule which does not reach the required recursion depth for StackOverflow, and code compiled using System.out.println appeared together.

The Java compiler, or JIT, modifies code behavior in a weird way. Modern compilers tend to create rather strange code in their attempts to optimize everything that they can hold.