ビルドグラフ与えられた座標

Question

方法は、次のような次のとおりです。

 
nodeName 
nodeName's x-coord, nodeName's y-coord 
x-coord of an adjacent node, y-coord of that adjacent node 

...と、残りの隣接ノードのちょうどより多く座標です。私はどのようにグラフとして格納する方法を把握しようとしているので、パスが合法であるかどうかを確認することができます。たとえば、nodeA-nodeB-nodeCは有効ですが、nodeA-nodeC-nodeDは有効ではありません。

私の最終的な質問は、Graphクラスをコーディングし、このデータを読み込むことでデータを取り込む最良の方法は何ですか？

Answer 1

ファイルを行のグループに分割することができます。各グループはノードを記述する。そして、すべてのグループを解析します。

あなたはちょうど SimpleGraphのインスタンスを作成し、ノードとエッジを移入でき JGraphT

を使用して検討する必要があります

Map<Node, List<Node>> neighbors; 
Map<String, Node> nodeByCoords; 

// Get node by it's coordinates. Create new node, if it doesn't exist. 
Node getNode(String coords) { 
    String[] crds = coords.split(" "); 
    int x = Integer.parseInt(crds[0]); 
    int y = Integer.parseInt(crds[1]); 
    String key = x + " " + y; 
    if (!nodeByCoords.containsKey(key)) { 
     Node node = new Node(); 
     node.setX(x); 
     node.setY(y); 
     nodeByCoords.put(key, node); 
     neighbords.put(node, new ArrayList<Node>()); 
    } 
    return nodeByCoords.get(key); 
} 

// Create node (if not exists) and add neighbors. 
void List<String> readNode(List<String> description) { 
    Node node = getNode(description.get(1)); 
    node.setName(description.get(0)); 

    for (int i = 2; i < description.size(); i++) { 
     Node neighbor = getNode(description.get(i)); 
     neighbors.get(node).add(neighbor); 
    } 
} 

// Splits lines to groups. Each group describes particular node. 
List<List<String>> splitLinesByGroups (String filename) { 
    BufferedReader reader = new BufferedReader(new FileReader(filename)); 
    List<List<String>> groups = new ArrayList<List<String>>(); 
    List<String> group = new ArrayList<String>(); 
    while (reader.ready()) { 
     String line = reader.readLine(); 
     if (Character.isLetter(line.charAt())) { 
      groups.add(group); 
      group = new ArrayList<String>(); 
     } 
     group.add(line); 
    } 
    groups.add(group); 
    return groups; 
} 

// Read file, split it to groups and read nodes from groups. 
void readGraph(String filename) { 
    List<List<String>> groups = splitLineByGroups(filename); 
    for (List<String> group: groups) { 
     readNode(group); 
    } 
} 

Answer 2

パスが正しいかどうかを調べるために、何らかの方法でノードを保存する必要はないと思います。次のノードの読み方をチェックすることができます。次のノードは、座標が以前のものと1だけ異なる場合にのみ有効です。

Answer 3

：

// Define your node, override 'equals' and 'hashCode' 
public class Node { 

    public int x, y; 

    Node (int _x, int _y) { 
    x = _x; 
    y = _y; 
    } 

    @Override public boolean equals (Object other) { 
    if ((other.x == x) 
     && (other.y == y)) 
     return true; 

    return false; 
    } 

    /* Override hashCode also */ 
} 

// Later on, you just add edges and vertices to your graph 
SimpleGraph<Node,Edge> sg; 
sg.addEdge (...); 
sg.addVertex (...); 

最後に、あなたは見つけることDijkstraShortestPathを使用することができますパスが存在するかどうか：