Dijkstra et FileInput. Java

Question

J'ai ce code java algorithme Dijkstra ci-dessous. J'ai téléchargé le code. Je veux apporter des modifications à ce programme et stocker les données dans le fichier et le lire plutôt que de le mettre dans le code source. Quels seraient les meilleurs moyens de le faire?

import java.util.PriorityQueue; 
import java.util.List; 
import java.util.ArrayList; 
import java.util.Collections; 


class Vertex implements Comparable<Vertex> 
{ 
public final String name; 
public Edge[] adjacencies; 
public double minDistance = Double.POSITIVE_INFINITY; 
public Vertex previous; 

public Vertex(String argName) { 
    name = argName; 
} 

public String toString() { 
    return name; 
} 


public int compareTo(Vertex other) 
{ 
    return Double.compare(minDistance, other.minDistance); 
} 

} 


class Edge 
{ 
public final Vertex target; 
public final double weight; 

public Edge(Vertex argTarget, double argWeight) { 

    target = argTarget; 
    weight = argWeight; 
} 
} 


public class Dijkstra 
{ 
public static void computePaths(Vertex source) 
{ 
    source.minDistance = 0.; 
    PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>(); 
    vertexQueue.add(source); 

while (!vertexQueue.isEmpty()) { 
    Vertex u = vertexQueue.poll(); 

     // Visit each edge exiting u 
     for (Edge e : u.adjacencies) 
     { 
      Vertex v = e.target; 
      double weight = e.weight; 
      double distanceThroughU = u.minDistance + weight; 
    if (distanceThroughU < v.minDistance) { 
     vertexQueue.remove(v); 

     v.minDistance = distanceThroughU ; 
     v.previous = u; 
     vertexQueue.add(v); 

    } 

     } 
    } 
} 


public static List<Vertex> getShortestPathTo(Vertex target) 
{ 
    List<Vertex> path = new ArrayList<Vertex>(); 
    for (Vertex vertex = target; vertex != null; vertex = vertex.previous) 
     path.add(vertex); 
     Collections.reverse(path); 
     return path; 
} 

public static void main(String[] args) 
{ 
Vertex v0 = new Vertex("Nottinghill_Gate"); 
Vertex v1 = new Vertex("High_Street_kensignton"); 
Vertex v2 = new Vertex("Glouchester_Road"); 
Vertex v3 = new Vertex("South_Kensignton"); 
Vertex v4 = new Vertex("Sloane_Square"); 
Vertex v5 = new Vertex("Victoria"); 
Vertex v6 = new Vertex("Westminster"); 
v0.adjacencies = new Edge[]{new Edge(v1, 79.83), new Edge(v6, 97.24)}; 
v1.adjacencies = new Edge[]{new Edge(v2, 39.42), new Edge(v0, 79.83)}; 
v2.adjacencies = new Edge[]{new Edge(v3, 38.65), new Edge(v1, 39.42)}; 
v3.adjacencies = new Edge[]{new Edge(v4, 102.53), new Edge(v2, 38.65)}; 
v4.adjacencies = new Edge[]{new Edge(v5, 133.04), new Edge(v3, 102.53)}; 
v5.adjacencies = new Edge[]{new Edge(v6, 81.77), new Edge(v4, 133.04)}; 
v6.adjacencies = new Edge[]{new Edge(v0, 97.24), new Edge(v5, 81.77)}; 
Vertex[] vertices = { v0, v1, v2, v3, v4, v5, v6 }; 


    computePaths(v0); 
    for (Vertex v : vertices) 
{ 
    System.out.println("Distance to " + v + ": " + v.minDistance); 
    List<Vertex> path = getShortestPathTo(v); 
    System.out.println("Path: " + path); 
} 

} 
} 

Le code est basé sur http://en.literateprograms.org/Special:Downloadcode/Dijkstra%27s_algorithm_%28Java%29 [dernière consultation le 6 Janvier 2011]

Answer 1

Je vous recommande décrire votre graphique Trivial Graph Format.

C'est ce qu'il va ressembler à:

v0 Harrisburg 
v1 Baltimore 
v2 Washington 
v3 Philadelphia 
v4 Binghamton 
v5 Allentown 
v6 New York 
# 
v0 v1 79.83 
v0 v5 81.15 
v1 v0 79.75 
v1 v2 39.42 
v1 v3 103.00 
v2 v1 38.65 
v3 v1 102.53 
v3 v5 61.44 
v3 v6 96.79 
v4 v5 133.04 
v5 v0 81.77 
v5 v3 62.05 
v5 v4 134.47 
v5 v6 91.63 
v6 v3 97.24 
v6 v5 87.94 

Vous pouvez ensuite analyser ce fichier et créer le Vertex et les objets Edge.

Voici le code complet:

class Vertex implements Comparable<Vertex> { 
    public final String name; 
    public List<Edge> adjacencies; 
    public double minDistance = Double.POSITIVE_INFINITY; 
    public Vertex previous; 

    public Vertex(String argName) { 
     name = argName; 
     adjacencies = new ArrayList<Edge>(); 
    } 

    public void addEdge(Edge e) { 
     adjacencies.add(e); 
    } 

    public String toString() { 
     return name; 
    } 

    public int compareTo(Vertex other) { 
     return Double.compare(minDistance, other.minDistance); 
    } 

} 

class Edge { 
    public final Vertex target; 
    public final double weight; 

    public Edge(Vertex argTarget, double argWeight) { 
     target = argTarget; 
     weight = argWeight; 
    } 
} 


public class Dijkstra { 

    public static void computePaths(Vertex source) { 
     source.minDistance = 0.; 
     PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>(); 
     vertexQueue.add(source); 

     while (!vertexQueue.isEmpty()) { 
      Vertex u = vertexQueue.poll(); 

      // Visit each edge exiting u 

      for (Edge e : u.adjacencies) { 
       Vertex v = e.target; 
       double weight = e.weight; 
       double distanceThroughU = u.minDistance + weight; 
       if (distanceThroughU < v.minDistance) { 
        vertexQueue.remove(v); 
        v.minDistance = distanceThroughU; 
        v.previous = u; 
        vertexQueue.add(v); 
       } 

      } 
     } 
    } 

    public static List<Vertex> getShortestPathTo(Vertex target) { 
     List<Vertex> path = new ArrayList<Vertex>(); 
     for (Vertex vertex = target; vertex != null; vertex = vertex.previous) 
      path.add(vertex); 

     Collections.reverse(path); 
     return path; 
    } 

    public static void main(String args[]) { 

     Map<String, Vertex> vertexMap = new HashMap<String, Vertex>(); 
     BufferedReader in = null; 
     try { 
      in = new BufferedReader(new FileReader("graph.txt")); 
      String line; 
      boolean inVertex = true; 

      while ((line = in.readLine()) != null) { 
       if (line.charAt(0) == '#') { 
        inVertex = false; 
        continue; 
       } 
       if (inVertex) { 
        //store the vertices 
        int indexOfSpace = line.indexOf(' '); 
        String vertexId = line.substring(0, indexOfSpace); 
        String vertexName = line.substring(indexOfSpace + 1); 
        Vertex v = new Vertex(vertexName); 
        vertexMap.put(vertexId, v); 
       } else { 
        //store the edges 
        String[] parts = line.split(" "); 
        String vFrom = parts[0]; 
        String vTo = parts[1]; 
        double weight = Double.parseDouble(parts[2]); 
        Vertex v = vertexMap.get(vFrom); 
        if (v != null) { 
         v.addEdge(new Edge(vertexMap.get(vTo), weight)); 
        } 
       } 
      } 
     } catch (IOException e) { 
      e.printStackTrace(); 
      return; 
     } 
     finally{ 
      if(in!= null) 
       try { 
        in.close(); 
       } catch (IOException ignore) { 
       } 
     } 

     //get a list of all the vertices 
     Collection<Vertex> vertices = vertexMap.values(); 
     Vertex source = vertices.iterator().next(); 
     System.out.println("Computing paths from " + source); 
     computePaths(source); 
     for (Vertex v : vertices) { 
      System.out.println("Distance to " + v + ": " + v.minDistance); 
      List<Vertex> path = getShortestPathTo(v); 
      System.out.println("Path: " + path); 
     } 
    } 
} 

Answer 2

Fondamentalement, vous pouvez stocker les données dans le fichier texte d'une manière méthodique, comme laisser un espace entre toutes les autres données. Par la suite, vous pouvez utiliser Java File Reader et lire le contenu de ce fichier dans un tableau. Une fois dans le tableau, vous pouvez passer l'index du tableau dans les endroits respectifs où les données doivent être ajoutées dans votre code. Par exemple, il ressemblerait à cela, (ici le tableau de type String comme il est utilisé pour stocker les données du fichier texte. Par conséquent, vous pouvez utiliser ses index pour ajouter les données à votre code.

FileInputStream fileinputstream = new FileInputStream("FileName.txt"); 
DataInputStream datainputstream = new DataInputStream(fileinputstream); 
BufferedReader bufferedreader1 = new BufferedReader(new InputStreamReader(datainputstream));          
do{ 
    String s1; 
    if((s1 = bufferedreader1.readLine()) == null){ 
     break; 
    } 
     String as[] = s1.split(" "); 
} while(true); 
    datainputstream.close(); 
}