Build-Diagramm angegebenen Koordinaten von benachbarten Knoten

Question

Die Art und Weise dies interpretieren kann, ist als solche:

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

... und der Rest sind nur mehr Koordinaten von benachbarten Knoten. Ich versuche herauszufinden, wie ich das als Diagramm speichern kann, damit ich prüfen kann, ob ein Pfad legal ist. Zum Beispiel ist vielleicht nodeA-nodeB-nodeC legal, aber nodeA-nodeC-nodeD nicht.

Also, meine letzte Frage ist: Was ist der beste Weg, um die Graph-Klasse zu programmieren, und bevölkern sie durch Einlesen dieser Daten?

Answer 1

Sie können Dateien in Gruppen von Zeilen aufteilen. Jede Gruppe beschreibt einen Knoten. Und dann alle Gruppen analysieren.

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

Ich denke, es gibt keine Notwendigkeit, Knoten irgendwie zu speichern, um herauszufinden, ob der Pfad legal ist: Sie können die Rechtmäßigkeit des nächsten Knotens überprüfen, wenn Sie sie lesen. Der nächste Knoten ist nur dann zulässig, wenn seine Koordinaten um nicht mehr als 1 abweichen.

Answer 3

Sie möchten vielleicht JGraphT

Sie nur eine Instanz des SimpleGraph schaffen könnten mit berücksichtigen und es mit Knoten und Kanten füllen:

// 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 (...); 

Schließlich können Sie DijkstraShortestPath verwenden zu finden ob ein Pfad existiert oder nicht: