Ввод файла для алгоритма Дейкстры

Question

У меня проблемы с выяснением, как читать входной файл с помощью Java. Файл имеет следующий формат:

u1 v1 w1
u2 v2 w2
...
um vm wm
-1
source

Каждый 3-кортеж обозначает ребро, которое определяется его исходной вершиной, конечной вершиной и весом (пример: нью-йоркский бостон 30). Описание графа заканчивается «флагом», целым числом -1. Строка следует за этим флагом; эта строка является именем исходной вершины для алгоритма кратчайшего пути Дейкстры. То есть вы должны определить и распечатать кратчайший путь от этой исходной вершины ко всем остальным вершинам графа. Вот моя текущая работа.

import java.io.File;
import java.io.FileNotFoundException;
import java.util.PriorityQueue;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

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 ArrayList<Vertex> getShortestPathTo(Vertex target) {
        ArrayList<Vertex> path = new ArrayList<Vertex>();
        for (Vertex vertex = target; vertex != null; vertex = vertex.previous)
            path.add(vertex);

        Collections.reverse(path);
        return path;
    }

    public String[] readFile(String fileName) throws FileNotFoundException {
        Scanner input = new Scanner(new File(fileName));
        String line = "";
        while (input.hasNext()) {
            line = line.concat(input.nextLine());
        }
        String[] graph = line.split("");
        return graph;

    }

    public static void main(String[] args) throws FileNotFoundException {

        final String TEST = "/TestInput.txt";
        Scanner input = new Scanner(new File(TEST));
        String line = "";
        while (input.hasNext()) {
            line = line.concat(input.nextLine());
        }
        String[] graph = line.split(" ");

        for (int i = 0; i < graph.length; i++) {
            System.out.println(graph[i]);
        }

        Vertex[] verts = new Vertex[graph.length];
        Edge[] edges = new Edge[graph.length];
        Vertex v1 = new Vertex("");
        Vertex v2 = new Vertex("");
        Vertex source = new Vertex("");
        int count = 0;

        outerloop: for (int i = 0; i < (graph.length); i++) {

            if (graph[i].equals("-1")) {
                // do algorithm initialization here w/ source
            }
            if (i == 0) {
                verts[i] = new Vertex(graph[i]);
                count++;
            } else {
                innerloop: for (int j = count; j >= 0; j--) {
                    if (i / 3 == 0) {

                        if (graph[i].equals(verts[j].toString())) {
                            break innerloop;
                        } else if (j == 0) {
                            verts[count] = new Vertex(graph[i]);
                            v1 = verts[count];
                            count++;
                        }
                    }

                    if (i / 3 == 1) {

                        if (graph[i].equals(verts[j])) {
                            break innerloop;
                        } else if (j == 0) {
                            verts[count] = new Vertex(graph[i]);
                            v2 = verts[count];
                            count++;
                        }
                    }
                    if (i / 3 == 2) {

                    }
                }
            }

        }

        for (int i = 0; i < verts.length; i++) {
            System.out.println(verts[i]);
        }
    }
}

Так что моя единственная проблема - как перейти из заданного формата файла .txt в график. Любые предложения приветствуются.

Answer 1

Используйте Сканер для анализа данных файла. Для каждого кортежа, если исходная вершина не была создана, создайте ее, в противном случае найдите ее в существующем графе - создайте функцию поиска. Сделайте то же самое для целевой вершины. Затем создайте ребро с весом, равным третьему токену в кортеже, и добавьте целевую вершину к ребру. Наконец, добавьте ребро в список смежности исходной вершины.

Для ранее упомянутой функции поиска вы можете реализовать что-то, что может искать в каждой вершине графа, начиная с любой вершины. Рекурсия будет необходима.

public static Vertex search(Vertex src, String name);

Более простое решение - сохранить список всех вершин, которые вы создаете при построении графа, и искать по нему.

public static Vertex search(List<Vertex> vertices, String name);

Когда вы закончили построение графа и у вас есть имя вершины, с которой начнется алгоритм Дейкстры, вы можете использовать функцию поиска, чтобы получить ссылку на вершину.

Dijkstra.computePath(search(vertices, startVertexName));

И это все. Вот пример того, как анализировать данные вашего файла:

List<Vertex> vertices = new ArrayList<Vertex>();
String src = 
    "Pittsburgh Philadelphia 323 "+
    "Pittsburgh Ohio 125 "+
    "Ohio Philadelphia 400 "+
    "-1 Ohio";
            //new Scanner(new File(fileName));
Scanner scnr = new Scanner(src); 
String src, target;
int weight;
while(scnr.hasNext())
{
    src = scnr.next();
    if(src.equals("-1"))
        break;
    else {
        target = scnr.next();
        weight = scnr.nextInt();
    }
    //call search(), implement logic in addToGraph()
    addVertexToGraph(src, target, weight, vertices);    
}   
String startVertexName = scnr.next();
scnr.close();

Обратите внимание, что Scanner.next возвращает следующий токен, разделенный пробелом (разделитель по умолчанию), поэтому данные вашего файла должны быть отформатированы таким образом.

Answer 2

{import Stack.Dijkstra; { import java.io.File;{import java.io.FileNotFoundException; { import java.util.Scanner;

{public class App { { public static void main (String [] args) throws {FileNotFoundException { { Vertex v1 = new Vertex ("A");{Vertex v2 = new Vertex("B"); { Vertex v3 = новая вершина ("C");

    {`v1.addNeighbour(new Edge(1, v1, v2));
    {`v1.addNeighbour(new Edge(10, v1, v2));
    {`v2.addNeighbour(new Edge(1, v2, v3));

    {`Dijkstra dijkstra = new Dijkstra();
    {`dijkstra.computePath(v1);

    {`System.out.println(dijkstra.getShortestPathTo(v3));
    {`final String test = "X:\\neon3\\eclipse\\TestInput.txt";
    {`Scanner input = new Scanner(new File(test));
    {`String line = "";
    {`while (input.hasNext()) {
        {`line = line.concat(input.nextLine());
    }
    {`String[] graph = line.split(" ");

    {`for (int i = 0; i < graph.length; i++) {
        {`System.out.println(graph[i]);
    }
}

} `}

Answer 3

Вот снимок:

/**
 * Read the file using provided filename, construct vertices etc.
 * 
 * @param fileName name of the file to read.
 * @return true if everything is OK
 * @throws FileNotFoundException if file is not found or not readable
 */
public boolean readFile(final String fileName) throws FileNotFoundException {
    final Scanner input = new Scanner(new File(fileName));
    boolean result = false;

    while (input.hasNext()) {
        final String line = line = input.nextLine();
        if ("-1".equals(line)) {
            // end of data
            if (input.hasNext()) {
                final String nameOfTheSource = input.next();
                // TODO: do something with nameOfTheSource
                result = true;
            } else {
                // bad input format: there should be something after -1
            }
        } else {
            final String Scanner vert = new Scanner(line);

            try {
                final String sourceName = vert.next();
                final String targetName = vert.next();
                final int weight = vert.nextInt(); // assuming int for weight
                // TODO: create Vertices and Edge here
            } catch (final NoSuchElementException ex) {
                // bad input format for "line"!
            }
        }
    }

    return result;
}

Не проверено.