java - 从简单的图形格式文本文件创建对象。 java 。迪杰斯特拉算法

Question

我想从简单的图形格式 txt 文件创建对象、顶点和边。这里的一位程序员建议我使用简单的图形格式来存储 dijkstra 算法的数据。

问题是目前所有信息，例如权重、链接，都在源代码中。我想要一个单独的文本文件并将其读入程序中。

我考虑过使用扫描仪扫描文本文件的代码。但我不太确定如何从同一文件创建不同的对象。我可以帮忙吗？

文件是

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

dijkstra算法代码为

下载自:http://en.literateprograms.org/Special:Downloadcode/Dijkstra%27s_algorithm_%28Java%29 */

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

}
}

扫描文件的代码是

 import java.util.Scanner;
 import java.io.File;
 import java.io.FileNotFoundException;

 public class DataScanner1 {

 //private int total = 0;
 //private int distance = 0; 
 private String vector; 
 private String stations;
 private double [] Edge = new double []; 

 /*public int getTotal(){
    return total;
  }
  */

  /*
  public void getMenuInput(){
    KeyboardInput in = new KeyboardInput;
    System.out.println("Enter the destination? ");
    String val = in.readString();
    return val;
  }
  */


 public void readFile(String fileName) {
   try {
     Scanner scanner =
       new Scanner(new File(fileName));
     scanner.useDelimiter
       (System.getProperty("line.separator")); 
     while (scanner.hasNext()) {
       parseLine(scanner.next()); 
    }
       scanner.close();
   } catch (FileNotFoundException e) {
     e.printStackTrace();
   }
 }



  public void parseLine(String line) {
   Scanner lineScanner = new Scanner(line);
   lineScanner.useDelimiter("\\s*,\\s*");
   vector = lineScanner.next();
   stations = lineScanner.next();
   System.out.println("The current station is " + vector + " and the destination to the next station is " + stations + ".");
   //total += distance;
   //System.out.println("The total distance is " + total);
  }

 public static void main(String[] args) {
  /* if (args.length != 1) {
     System.err.println("usage: java TextScanner2"
       + "file location");
     System.exit(0);
   }
   */
   DataScanner1 scanner = new DataScanner1();
   scanner.readFile(args[0]);
   //int total =+ distance;
   //System.out.println("");
   //System.out.println("The total distance is " + scanner.getTotal());
 }
 }

Answer 1

你已经很接近了。

要读取每一行，请使用 String.split(" ") 。这将为文件行中的每个参数提供一个字符串数组。

对于解析文件，HashMap 是你的 friend 。源文件使用“v0”等名称，因此首先创建 HashMap<String, Vertex>它将“v0”(或您正在查看的任何键)存储在键中，并使用城市名称作为值初始化一个新的 Vertex 对象。

在第二个数据 block (邻接)的循环中，您希望通过类似 new Edge(verticies.get(parsedLine[1]), parsedLine[2])) 来创建一条边。 ，然后通过 verticies.get(parsedLine[0]).getAdjacencies().add(..) 将其添加到正确的顶点，用您刚刚创建的 Edge 替换我示例中的“..”。

请注意，他们的代码将 Vertex.adjaccies 定义为 Edge[]，我的示例需要将其设为在字段中初始化的 ArrayList。