StackOverflowError durante l'esecuzione di Depth First Search (grafico non orientato)

Question

Ho un metodo ricorsivo di visita DFS che a volte genera un errore StackOverflowError. Dato che la dimensione del grafico è ampia (circa 20000 vertici), le chiamate ricorsive sono molte e quindi ho provato a eseguire -Xss10M e tutto funziona. Vorrei solo capire perché aggiungendo all'inizio del metodo un System.out.println, anche senza -Xss10M, il metodo non lancia alcun StackOverflowError. Come è possibile?

Questo è il metodo visita DFS:

private int dfsVisit(Vertex<T> v, int time){ 
    // System.out.println("Hello"); 
    Vertex<T> n; 
    time++; 
    v.d = 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++; 
    v.f = time; 

    return time; 
} 

Questo è il codice completo

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(); 
     } 

    } 
    /* 
    P.S. 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++; 
     v.d = 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++; 
     v.f = 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); 
     } 

    } 



} 

ecco la classe di test

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(); 
    } 
} 

N.B. prova a commentare g.dijkstra (START) e g.printPath (END); tutto sembra funzionare.

Ecco il link per il set di dati

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

Answer 1

alcune raccomandazioni generali:
Il codice mescola attributi di vertici, che sono legati a una singola esecuzione di dfs e tale che sono attributi diretti dei vertici . Pessimo brutto stile. È molto probabile che questo rompa un algoritmo più complesso, che possa produrre un comportamento inaspettato e richieda la cancellazione degli stati dopo ogni esecuzione, per garantire la stabilità del codice. Mantenere invece gli stati correlati a una singola esecuzione di un algoritmo visibile solo per quella funzione. Per esempio. memorizzare gli stati all'interno di un Map, utilizzare il modello decoratore per creare una struttura dati che fornisce attributi aggiuntivi e che ha il metodo locale scope, ecc. Ad esempio: esecuzione del codice due volte sullo stesso grafico (stesso Object) con lo stesso l'input senza cancellare tutti gli stati porterà a un risultato errato (1).

In aggiunta: la creazione di una versione iterativa di DFS non è esattamente difficile, quindi dovresti provarla, soprattutto perché il tuo grafico sembra abbastanza grande.

Per quanto riguarda il motivo per cui il codice funziona (o non fa) il modo in cui funziona:
Questo è difficile da dire, dal momento che dipende da un sacco di fattori. Non hai fornito il codice completo, quindi non posso rieseguire test o verificare che tutto si comporti come dovrebbe. Le risposte più probabili:

Vertex utilizza il codice hash predefinito fornito da Object. Ciò porta all'ordinamento casuale delle voci nella mappa dei vicini, quindi l'ordine in cui determinati percorsi sono attraversati è casuale in ogni corsa e molto probabilmente diverso. Quindi stai attraversando il grafico usando percorsi casuali, che molto probabilmente (specialmente a causa delle dimensioni del tuo grafico) differiscono per ogni corsa. Il motivo non è il System.out.println, ma il semplice fatto che il tuo codice genera una struttura diversa (da un POV di ordinamento, non matematico), ogni volta che viene eseguito più la coincidente, che per qualche motivo piuttosto strano ogni build del grafico , che non raggiunge la necessaria profondità di ricorsione per StackOverflow e il codice compilato con System.out.println è apparso insieme.

Il compilatore Java o JIT modifica il comportamento del codice in modo strano. I moderni compilatori hanno la tendenza a produrre codice piuttosto strano nei loro tentativi di ottimizzare tutto ciò che riescono a ottenere.