Построить график, данные координаты соседних узлов

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

Вы можете разделить файл на группы строк. Каждая группа описывает узел. А затем разобрать все группы.

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

Вы могли бы рассмотреть возможность использования JGraphT

Вы можете просто создать экземпляр SimpleGraph и заполнить его узлов и ребер:

// 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 найти существует или нет путь: