Создание графа лабиринта из текстового файла: Java

Question

Мне нужно сделать график из текстового файла, содержащего несколько «лабиринтов», представленных в виде списков смежности.Список выглядит следующим образом:

A,G
A,B,F
B,A,C,G
C,B,D,G
D,C,E
E,D,F,G
F,A,E
G,B,C,E

D,F
A,B,G
B,A,C,E,G
C,B,D,E,G
D,C
E,B,C,G
F,G
G,A,B,C,E,F

F,A
A,B,G
B,A,G
C,D,G
D,C,G
E,F,G
F,E,G
G,A,B,C,D,E,F

Первая строка каждого «лабиринта» содержит начальный узел лабиринта (первая буква) и конечный узел лабиринта (вторая буква).

Я проанализировал текстовый файл в ArrayList всех строк (включая пустые строки), затем в ArrayList ArrayLists из строк (список отдельных лабиринтов).Я сделал это, разделив весь текст на пустые строки.Теперь моя проблема в том, что я не могу понять, как использовать класс своего узла для построения графа из этих «лабиринтов».Вот мой класс узла:

package algo2;

import java.util.ArrayList;


public class Node<T>{

    private T value; //this Node<T>'s value
    public ArrayList<Node<T>> connections;
    public boolean isStart;
    public boolean isEnd;
    public boolean visited;

    public Node(T value){
        this.value = value;
        connections = new ArrayList<Node<T>>();
    }

    //returns the value of this Node<T>
    public T getValue(){
        return value;
    }

    //returns true if the node is connected to any other nodes
    public boolean isConnected(){
        if(connections == null){
            return false;
        }
        return true;
    }

    //returns a list of nodes connected to this node
    public ArrayList<Node<T>> getConnections(){
        return connections;
    }

    //sets the node's value
    public void setValue(T value){
        this.value = value;
    }

    //adds a connection from this node to the passed node
    public void connect(Node<T> node){
        connections.add(node);
    }

    public String toString(){
        return value+"";
    }
}

Может кто-нибудь указать мне правильное направление, пожалуйста?

Answer 1

Давайте сконцентрируемся на настройке 1 лабиринта, и затем мы можем повторить процесс для всех них.Я попытался написать алгоритм, дружественный к синтаксису Java.

Итак, вот наша переменная ArrayList для первого лабиринта, насколько я понимаю ...

List<String> preNodes, which contains:
{"A,G", "A,B,F", "B,A,C,G", "C,B,D,G", "D,C,E", "E,D,F,G", "F,A,E", "G,B,C,E"};

Поскольку первыйСтрока имеет особое значение, давайте отделим ее от остальных.(т.е. установите его как отдельную переменную String и удалите его из ArrayList).

String startAndEnd, which contains: "A,G";
List<String> preNodes, which contains: 
{"A,B,F", "B,A,C,G", "C,B,D,G", "D,C,E", "E,D,F,G", "F,A,E", "G,B,C,E"};

Теперь давайте сначала соберем все нужные нам узлы, а затем сможем связать их.

//Define container for nodes
HashMap<String, Node> nodes = new HashMap<String, Node>();
//Create a node for each letter
for(String s : preNodes) {
    String nodeName = s.charAt(0) + "";
    nodes.put(nodeName, new Node());
}
//Link them up appropriately
for(String s : preNodes) {
    String[] splitS = s.split(","); //1 letter in each array cell.
    Node current = nodes.get(splitS[0]); //Get the node we're going to link up.
    for(int i=1; i<splitS.length; i++) {
        current.connect(nodes.get(splitS[i]));
    }
}
//Finally, set the start and end Node.
String[] splitStartAndEnd = startAndEnd.split(",");
nodes.get(splitStartAndEnd[0]).isStart = true;
nodes.get(splitStartAndEnd[1]).isEnd = true;

Это должно сделать это, я думаю;теперь "узлы" содержат весь лабиринт, все связаны.Я поймал ошибку в вашем коде: ваша функция isConnected () должна возвращать false, если connections.isEmpty (), а не если он нулевой.Он никогда не должен быть нулевым, потому что вы инициализируете его в конструкторе новым списком.

Answer 2

Одним из решений было бы использование split () на входе с соответствующим конструктором Node (обратите внимание, что я заменил String на параметр T для простоты):

class Node {
    public String value;
    public String[] connections;
    public boolean visited;

    public Node (String value, String[] connections) {
        this.value = value;
        this.connections = connections;
        visited = false;
    }

    public boolean isConnected(Node that) {
        boolean res = false;
        for (int i=0; !res && i<this.connections.length; i++) {
            res = (this.connections[i] == that.value);
        }
        return res;
    }

    // more stuff ... :)
}

//read start, end nodes

ArrayList<Node> nodes = new ArrayList<Node>();
for (each line in maze) {
    String[] nodeList = line.split(",");
    nodes.add(nodeList[0], Arrays.copyOfRange(nodeList, 1, nodeList.length));
}

Я думаю, что это будет проще, чем пытаться поддерживать список узлов внутри каждого узла, если остальная часть вашего приложения позволяет просто проверить, подключены ли два узла или один из них был посещен. (также обратите внимание, что вы, вероятно, захотите добавить больше кода в класс Node, чтобы отслеживать начальный и конечный узлы.)

Answer 3

Вы должны написать дополнительный код в отдельном классе, чтобы построить лабиринт.Он будет принимать текстовый ввод и выводить набор связанных узлов.Сами узлы не должны ничего «конструировать» - это просто строительные блоки.

Вот некоторый псевдокод для их соединения:

nameToNodeMap -> dictionary of string to node
for each line in the file
    previous token = null
    loop:
    try to get a token (letter, separated by commas)
    if there was no token
        break out of the loop
    else
        if nameToNodeMap contains that token
            get the node for that token
        else
            create a node
            add it to nameToNodeMap, with the token as the key
        if previous node != null
            link previous node to this node
        previous nope = current node
        goto loop