-1

ここにコードがあります。これは私のダイクストラ実装からの抜粋です。ここでは、4つの頂点がインスタンス化されており、各頂点には指定されたエッジと頂点（ノード）からの距離があります。このコードは、データがメインクラスに直接入力される場合、簡単で有益です。

Vertex v0 = new Vertex("Redvile");
Vertex v1 = new Vertex("Blueville");
Vertex v2 = new Vertex("Greenville");
Vertex v3 = new Vertex("Orangeville");
Vertex v4 = new Vertex("Purpleville");

v0.adjacencies = new Edge[]{ new Edge(v1, 5),
                             new Edge(v2, 10),
                                 new Edge(v3, 8) };
v1.adjacencies = new Edge[]{ new Edge(v0, 5),
                             new Edge(v2, 3),
                             new Edge(v4, 7) };
v2.adjacencies = new Edge[]{ new Edge(v0, 10),
                                 new Edge(v1, 3) };
v3.adjacencies = new Edge[]{ new Edge(v0, 8),
                             new Edge(v4, 2) };
v4.adjacencies = new Edge[]{ new Edge(v1, 7),
                                 new Edge(v3, 2) };

しかし、私のデータはファイルからのものです。ファイルを読み取り、各頂点のエッジ（隣接）とともに頂点のインスタンスを作成する必要があります。この関数の実装に問題があります。つまり、上記のコードを、データがファイルからのものであるものに変換するコードが必要です。

これが私のサンプルデータです：

a0 -    a1,1.6
a1 -    a0,1.6      * a2,0.85   * a3,0.5
a2 -    a1,0.85     * a34,1.2   * a39,0.65
a3 -    a1,0.5      * a4,0.2    * a5,0.1
a4 -    a3,0.2      * a5,0.2
a5 -    a4,0.1      * a6,1      * a36,0.65
a6 -    a5,1        * a7,1.5    * a14,0.45
a7 -    a6,1.5      * a8,0.18   * a11,1.2
a8 -    a7,0.18     * a9,1
a9 -    a8,1
a10 -   a13,1.9

a0-a10は頂点であり、a1,1.6はその他、（頂点、距離）形式で頂点に接続された隣接またはエッジを表します。

これまでのところ、このファイルを読み取って、各行をArrayListに配置することができます。私の今の問題は、基本的に、各頂点をインスタンス化し、隣接関係を追加する方法です。

これが私がファイルを読む方法です：

private void readFile(String fileName) {

    try{
        FileReader file = new FileReader(fileName);
        Scanner sc = new Scanner(file);

        int i = 0;
        while (sc.hasNextLine()) {
          input.add(sc.nextLine());
          i++;
        }

        setNodes();
        System.out.println();
        file.close();
    } catch(Exception e){
        System.out.println(e);
    }
}

入力は、1行あたりのファイルのすべてのコンテンツを含むarrayListです。一方、ノードにはすべての頂点のリストがあります。

public void setNodes() {

    System.out.println();

    for(int i=0; i<input.size(); i++) {
        line = this.input.get(i);
        nodes.add(line.substring(0,line.indexOf("-")).trim());
    }
}

また、

PS私もデータ型の問題です。私のarrayListは文字列であり、頂点はタイプVertexであり、これは私のコードで定義されたクラスです。

この説明が不十分な場合は、お気軽にコメントしてください。ありがとう、乾杯！

4

2 に答える 2

2

これは簡単なはずです

a0 -    a1,1.6
a1 -    a0,1.6      * a2,0.85   * a3,0.5

コードではなくプロセスをお見せします

Create vertex_list list 
For each line read
  split on '-' left side is your current_vertex, right side is your 'adjacency list'
   check if your vertex is present in vertex_list if not create it and add it
   adj list =  a0,1.6      * a2,0.85   * a3,0.5
   split your adj list   on '*' 
   for each entry ex 'a0,1.6'
      split on ','  now you know the edge_vertex=split[0] = a0 and weight = split[1] = 1.6
      check if you already have edge_vertex in your vertex list if not add it
      create and add edge(edge_vertex, weight)  to current vertex
    end
 end

プロセスの最後に、 vertex_list からすべての頂点を表示できるはずです

頂点に名前を付ける方法はいくつかありますが、設定ファイルで頂点に名前を付けるのが簡単な方法です。これには、リストに対して 2 つのパスを実行する必要があります。1 つ目は名前を付けて各頂点を生成し、2 つ目は上記の疑似コードと同じですが、最初のパスで作成されているため、新しい頂点を作成する必要はありません。単純に追加します。 adj へのエッジ頂点。リスト。

a0,Name A -    a1,1.6
a1,Name B -    a0,1.6      * a2,0.85   * a3,0.5
a2,Name C -    a1,0.85     * a34,1.2   * a39,0.65
a3,Name D -    a1,0.5      * a4,0.2    * a5,0.1
于 2013-03-14T17:39:17.433 に答える
1

私の実装と@gregから提供された情報に基づいて、この質問に対する回答を公開しています。彼に感謝します！

private void setVertices() {

    String[] listEdges;

    for(int i=0; i<nodes.size(); i++) {

        //if vertex does not exist, create it
        if(vertexList.containsKey(nodes.get(i))) {
            vertexList.put(nodes.get(i), new Vertex(nodes.get(i)));
        }

        line = adjLine.get(i);

        //separate adj edges to *
        if(line.contains("*")) {
            listEdges = line.split("[*]");
        } else {
            listEdges = new String[1];
            listEdges[0] = line;
        }

        //add edges to specified vertex
        for(int j=0; j < listEdges.length; j++ ) {
            String[] word = listEdges[j].split(",");
            edges.add(new Edge(vertexList.get(word[0]),Double.parseDouble(word[1])));
        }

        map.put(nodes.get(i), edges);
        edges.clear();
    }
}

基本的に、これを行うために ArrayList、Map、および HashMap を使用しました。はい！

于 2013-03-19T05:11:22.853 に答える