CODEWITHSUNDEEP
javagraph
varatis
varatis

Reputation: 14740

Build graph given coordinates of adjacent nodes

The way you can interpret this is as such:

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

...and the rest are just more coordinates of adjacent nodes. I'm trying to figure out how to store this as a graph so I can check if a path is legal. For example, maybe nodeA-nodeB-nodeC is legal, but nodeA-nodeC-nodeD is not.

So, my final question is: what is the best way to code the Graph class, and populate it by reading in this data?

Upvotes: 1

Views: 2737

Answers (3)

ArjunShankar
ArjunShankar

Reputation: 23680

You might want to consider using JGraphT

You could just create an instance of the SimpleGraph and populate it with nodes and edges:

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

Finally, you can use DijkstraShortestPath to find whether or not a path exists:

Upvotes: 0

Mikita Belahlazau
Mikita Belahlazau

Reputation: 15434

You can split file to groups of lines. Each group describes node. And then parse all groups. 

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);
    }
}

Upvotes: 1

Alexey Berezkin
Alexey Berezkin

Reputation: 1543

I think there is no need to store nodes somehow to find out whether the path is legal: you can check the legalty of the next node when reading them. The next node is legal if and only if it's coordinates differ to previous ones by no more than 1.

Upvotes: 0

Related Questions