Dijkstraのアルゴリズムシミュレーション

Question

私は、マルチキャストルーティングの動作をシミュレートするDijkstraの最短パスアルゴリズムの実装に取り​​組んでいますが、私のシミュレーションクラスでエラーが発生しています。

シミュレーションクラス

public class simulation 
{ 
    private List<Vertex> nodes; 
    private List<Edge> edges; 
    public void testExcute() 
    { 
     nodes = new ArrayList<Vertex>(); 
     edges = new ArrayList<Edge>(); 
     for (int i = 0; i < 11; i++) 
     { 
      Vertex location = new Vertex("Node_" + i, "Node_" + i); 
      nodes.add(location); 
     } 
    } 
    addLink("Edge_0", 0, 1, ((int)Math.random()*101)); 
    addLink("Edge_1", 0, 2, ((int)Math.random()*101)); 
    addLink("Edge_2", 0, 4, ((int)Math.random()*101)); 
    addLink("Edge_3", 2, 6, ((int)Math.random()*101)); 
    addLink("Edge_4", 2, 7, ((int)Math.random()*101)); 
    addLink("Edge_5", 3, 7, ((int)Math.random()*101)); 
    addLink("Edge_6", 5, 8, ((int)Math.random()*101)); 
    addLink("Edge_7", 8, 9, ((int)Math.random()*101)); 
    addLink("Edge_8", 7, 9, ((int)Math.random()*101)); 
    addLink("Edge_9", 4, 9, ((int)Math.random()*101)); 
    addLink("Edge_10", 9,10,((int)Math.random()*101)); 
    addLink("Edge_11", 1,10,((int)Math.random()*101)); 

    // Lets check from location Loc_1 to Loc_10 
    Graph graph = new Graph(nodes, edges); 
    DijkstraAlgorithm dijkstra = new DijkstraAlgorithm(graph); 
    dijkstra.execute(nodes.get(0)); 
    LinkedList<Vertex> path = dijkstra.getPath(nodes.get(10)); 

    for (Vertex vertex : path) 
    { 
     System.out.println(vertex); 
    } 
    public void addLink(String laneId, int outcomingPortLabel, int incomingPortLabel,int cost) 
    { 
    Edge link = new Edge(laneId,nodes.get(outcomingPortLabel), nodes.get(incomingPortLabel), cost); 
    edges.add(link); 
    } 
} 

エッジクラス

package multicastroutingproject; 
public class Edge 
{ 
    private final String id; 
    private final Vertex source; 
    private final Vertex destination; 
    private final int weight; 

    public Edge(String id, Vertex source, Vertex destination, int weight) 
    { 
     this.id = id; 
     this.source = source; 
     this.destination = destination; 
     this.weight = weight; 
    } 

    public String getId() 
    { 
     return id; 
    } 
    public Vertex getDestination() 
    { 
     return destination; 
    } 
    public Vertex getSource() 
    { 
     return source; 
    } 
    public int getWeight() 
    { 
     return weight; 
    } 
    @Override 
    public String toString() 
    { 
    return source + " " + destination; 
    } 
} 

グラフクラス

package multicastroutingproject; 
import java.util.List; 
public class Graph 
{ 
    private final List<Vertex> vertexes; 
    private final List<Edge> edges; 
    public Graph(List<Vertex> vertexes, List<Edge> edges) 
    { 
     this.vertexes = vertexes; 
     this.edges = edges; 
    } 
    public List<Vertex> getVertexes() 
    { 
     return vertexes; 
    } 
    public List<Edge> getEdges() 
    { 
     return edges; 
    } 
} 

頂点クラス

package multicastroutingproject; 
public class Vertex 
{ 
    final private String id; 
    final private String name; 
    public Vertex(String id, String name) 
    { 
     this.id = id; 
     this.name = name; 
    } 
    public String getId() 
    { 
     return id; 
    } 

    public String getName() 
    { 
     return name; 
    } 

    @Override 
    public int hashCode() 
    { 
     final int prime = 31; 
     int result = 1; 
     result = prime * result + ((id == null) ? 0 : id.hashCode()); 
     return result; 
    } 

    @Override 
    public boolean equals(Object obj) 
    { 
     if (this == obj) 
      return true; 
     if (obj == null) 
      return false; 
     if (getClass() != obj.getClass()) 
      return false; 
     Vertex other = (Vertex) obj; 
     if (id == null) { 
      if (other.id != null) 
       return false; 
     } 
     else if (!id.equals(other.id)) 
      return false; 
    return true; 
    } 

    @Override 
    public String toString() 
    { 
     return name; 
    } 
} 

、最終的にはダイクストラのクラス

package multicastroutingproject; 
import java.util.*; 
public class DijkstraAlgorithm 
{ 
    private final List<Vertex> nodes; 
    private final List<Edge> edges; 
    private Set<Vertex> settledNodes; 
    private Set<Vertex> unSettledNodes; 
    private Map<Vertex, Vertex> predecessors; 
    private Map<Vertex, Integer> distance; 
    public DijkstraAlgorithm(Graph graph) 
    { 
    // create a copy of the array so that we can operate on this array 
    this.nodes = new ArrayList<>(graph.getVertexes()); 
    this.edges = new ArrayList<>(graph.getEdges()); 
    } 
    public void execute(Vertex source) 
    { 
    settledNodes = new HashSet<Vertex>(); 
    unSettledNodes = new HashSet<Vertex>(); 
    distance = new HashMap<Vertex, Integer>(); 
    predecessors = new HashMap<Vertex, Vertex>(); 
    distance.put(source, 0); 
    unSettledNodes.add(source); 
    while (unSettledNodes.size() > 0) 
    { 
     Vertex node = getMinimum(unSettledNodes); 
     settledNodes.add(node); 
     unSettledNodes.remove(node); 
     findMinimalDistances(node); 
    } 
    } 
    private void findMinimalDistances(Vertex node) 
    { 
    List<Vertex> adjacentNodes = getNeighbors(node); 
    for (Vertex target : adjacentNodes) 
    { 
     if (getShortestDistance(target) > getShortestDistance(node) 
      + getDistance(node, target)) 
     { 
     distance.put(target, getShortestDistance(node) 
      + getDistance(node, target)); 
     predecessors.put(target, node); 
     unSettledNodes.add(target); 
     } 
    } 
    } 
    private int getDistance(Vertex node, Vertex target) 
    { 
    for (Edge edge : edges) 
    { 
     if (edge.getSource().equals(node) 
      && edge.getDestination().equals(target)) 
     { 
     return edge.getWeight(); 
     } 
    } 
    throw new RuntimeException("Should not happen"); 
    } 
    private List<Vertex> getNeighbors(Vertex node) 
    { 
    List<Vertex> neighbors = new ArrayList<Vertex>(); 
    for (Edge edge : edges) 
    { 
     if (edge.getSource().equals(node) 
      && !isSettled(edge.getDestination())) 
     { 
     neighbors.add(edge.getDestination()); 
     } 
    } 
    return neighbors; 
    } 
    private Vertex getMinimum(Set<Vertex> vertexes) 
    { 
    Vertex minimum = null; 
    for (Vertex vertex : vertexes) 
    { 
     if (minimum == null) 
     { 
     minimum = vertex; 
     } 
     else 
     { 
     if (getShortestDistance(vertex) < getShortestDistance(minimum)) 
     { 
      minimum = vertex; 
     } 
     } 
    } 
    return minimum; 
    } 
    private boolean isSettled(Vertex vertex) 
    { 
    return settledNodes.contains(vertex); 
    } 
    private int getShortestDistance(Vertex destination) 
    { 
    Integer d = distance.get(destination); 
    if (d == null) 
    { 
    return Integer.MAX_VALUE; 
    } 
    else 
    { 
     return d; 
    } 
} 
public LinkedList<Vertex> getPath(Vertex target) 
{ 
    LinkedList<Vertex> path = new LinkedList<Vertex>(); 
    Vertex step = target; 
    // check if a path exists 
    if (predecessors.get(step) == null) 
    { 
    return null; 
    } 
    path.add(step); 
    while (predecessors.get(step) != null) 
    { 
    step = predecessors.get(step); 
    path.add(step); 
    } 
    // Put it into the correct order 
    Collections.reverse(path); 
    return path; 
    } 
} 

私がしようとすると

addLink("Edge_9", 4, 9, ((int)Math.random()*101));

それは私に次の警告/エラー与える：「無効なメソッドの宣言を、戻り値の型を行方不明」、そしてそれは私が名前を変更することを示唆していますシミュレーションへのaddLinkは意味がありません。

私はライン上

DijkstraAlgorithm dijkstra = new DijkstraAlgorithm(graph); 
dijkstra.execute(nodes.get(0)); 

を得ている他の警告/エラー、私ははっきりとoboveライン上のオブジェクトをインスタンス化するが、それは、パッケージダイクストラが存在しないことを言います。

そして最後に、

LinkedList<Vertex> path = dijkstra.getPath(nodes.get(10)); 

for (Vertex vertex : path) 
{ 
    System.out.println(vertex); 
} 

それは「タイプの不正なスタート」と言うと、それは私が私のパッケージに「パス」クラスを作成することを示唆しているが、私はパスをインスタンス化して、再びそれは意味がありません。この時間各ループの右上に表示されます。

長い投稿には申し訳ありませんが、なぜこれらのエラーが発生しているのか分かりません。 ？

Answer 1

いくつかの問題がありますが、最も目立つのは、addLink()への呼び出しが、メソッドではなく、クラス本体の中間にあることです。コンパイラはそこでメソッドの宣言を期待しており、それらの呼び出しをどうすればよいか分かりません。 main()が見つからないようです。いくつかのJava構文を見直す必要があります。