java - ArrayIndexOutOfBoundsException on generating maze graph with depth first search

Question

I created a program that solves a maze that reads a text file input. I managed to solve it using Depth-first Search and the result was fine on small mazes like this:

Everything was fine solving small to medium mazes but when the maze becomes larger, it gives me an ArrayIndexOutOfBoundsException error (see below).

Enter maze file: test2.txt
Enter start node: 0
Enter goal node: 1
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 207
    at MazeGraph.addArc(MazeGraph.java:95)
    at MazeGraph.<init>(MazeGraph.java:51)
    at MazeSystem.<init>(MazeSystem.java:25)
    at MazeSystem.main(MazeSystem.java:37)
Java Result: 1

My program should read automatically how many nodes are in the test2.txt (this is the large maze file) file but this error happens. The code looks like this:

MazeGraph.java

import java.io.*;
import static java.lang.System.out;
import java.util.*;

/**
 * This class creates a representation of Maze as a Graph by reading from a text
 * file.
 *
 * @author Muhammad
 */
public class MazeGraph {

    final int node; //For declaring constant value of a node.
    int arc;
    List<Integer>[] adjacencyList;
    static Set<Integer> setOfNodes = new HashSet<>();
    private static Scanner scanNodeSize;

    /**
     * This constructors takes an integer parameter for reading node indexes in
     * a list of adjacent nodes.
     *
     * @param node - integer parameter for passing the nodes value from the file
     * and create a list of adjacent nodes.
     */
    MazeGraph(int node) {
        this.node = node;
        this.arc = 0;//initialise to empty arcs
        adjacencyList = (List<Integer>[]) new List[node];
        for (int index = 0; index < node; index++) {
            adjacencyList[index] = new LinkedList<Integer>();
        }
    }

    /**
     * The main constructor that takes a String parameter for reading maze file.
     *
     * @param mazeFile
     */
    public MazeGraph(String mazeFile) {
        this(getNodeSize(mazeFile));
        Scanner scan;
        try {
            //Scan maze file.
            scan = new Scanner(new File(mazeFile));
            /*loop when it has next integer then read two nodes from the file and add arc for it.*/
            while (scan.hasNextInt()) {
                int node1 = scan.nextInt();
                int node2 = scan.nextInt();
                addArc(node1, node2);
            }
        } catch (FileNotFoundException ex) {
            out.println(ex.getMessage());
        }
    }

    /**
     * This method returns a size of the set of nodes by taking a String
     * parameter which the name of the maze file.
     *
     * @param mazeFile - String parameter for reading maze file for scanning the
     * size of the nodes.
     * @return - returns an integer value for the size of the set of nodes.
     */
    public static int getNodeSize(String mazeFile) {

        try {
            scanNodeSize = new Scanner(new File(mazeFile));
            while (scanNodeSize.hasNextInt()) {
                int node1 = scanNodeSize.nextInt();
                int node2 = scanNodeSize.nextInt();
                setOfNodes.add(node1);
                setOfNodes.add(node2);
            }
            return setOfNodes.size();

        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
        return setOfNodes.size();

    }

    /**
     * This method adds an arc by adding two different nodes in array of list
     * called adjacency list.
     *
     * @param node1 - first node.
     * @param node2 - next node.
     */
    private void addArc(int node1, int node2) {
        arc++; //Increase arc by one whenever this addArc method is called.
        adjacencyList[node1].add(node2);
        adjacencyList[node2].add(node1);

    }

    //Print the nodes and its arcs by looping through the adjacency list.
    public void print() {
        out.println(node + " Nodes, " + arc + " Arcs \n");
        for (int fromNode = 0; fromNode < node; fromNode++) {
            out.print(fromNode + " connected to ");
            for (int arcNode : adjacencyList[fromNode]) {
                out.print(arcNode + " ");
            }
            out.println();
        }
    }

    /**
     * This method returns a list of nodes to allow objects to be the target for
     * "for-each" statement in order to iterate through the nodes.
     *
     * @param nodes - an Integer parameter for getting the number of nodes in a
     * list.
     * @return - returns a list of nodes.
     */
    public Iterable<Integer> getAdjacencyList(int nodes) {
        return adjacencyList[nodes];
    }
}

In MazeGraph.java, the getNodeSize method returns an integer that is used for the constructor's parameter. To make it work, I have to take that getNodeSize method out in the constructor's parameter and instead put some larger value there like 300 for example. In stack trace, it says the problem is in the addArc method. I am trying to figure out on how to solve this problem if it works already in other mazes so that it also reads in large mazes automatically. Please, I would be grateful if someone can solve this.

This is the large file.

score 1 · Accepted Answer

好的，问题出在getNodeSize(String). 你回来setOfNodes.size()。问题是如果一个节点是一个单例（即它没有连接弧），那么它就不会在迷宫文件中列出。例如，假设您的迷宫文件是“9999 1”，仅此而已。然后您的getNodeSize()方法将返回 2。然后您的代码将节点数组实例化为大小为 2。然后您尝试在 9999 和 1 之间添加一个弧，但收到一个，ArrayIndexOutOfBoundsException因为数组中只有两个位置，但您正在尝试索引位置 9999。

相反，您应该返回观察到的最大节点 ID 加一。下面的代码实现了这一点：

/**
 * This method returns a size of the set of nodes by taking a String
 * parameter which the name of the maze file.
 *
 * @param mazeFile - String parameter for reading maze file for scanning the
 * size of the nodes.
 * @return - returns an integer value for the size of the set of nodes.
 * @throws FileNotFoundException if the mazeFile could not be found
 */
public static int getNodeSize(String mazeFile) throws FileNotFoundException{
        scanNodeSize = new Scanner(new File(mazeFile));
        while (scanNodeSize.hasNextInt()) {
            int node1 = scanNodeSize.nextInt();
            int node2 = scanNodeSize.nextInt();
            setOfNodes.add(node1);
            setOfNodes.add(node2);
        }

        //Changes begin here
        Integer max = setOfNodes.stream().reduce(Integer::max).get();
        return max+1;
        //Changes end here

}

注意：我删除了 try-catch 块并将其替换为 throws 声明。

更好的方法：通常不赞成将数组和Collection. 使用 a 可能会更好HashMap：

HashMap<Integer,List<Integer>> adjacencyList = new HashMap<>();

您可以通过调用访问任何节点的邻接列表，adjacencyList.get(nodeId)并且您的构造函数可以更改为：

public MazeGraph(String mazeFile) {
    adjacencyMap = new HashMap<>();
    Scanner scan;
    try {
        //Scan maze file.
        scan = new Scanner(new File(mazeFile));
        /*loop when it has next integer then read two nodes from the file and add arc for it.*/
        while (scan.hasNextInt()) {
            int node1 = scan.nextInt();
            int node2 = scan.nextInt();
            List<Integer> node1AdjList = adjacencyMap.getOrDefault(node1,new LinkedList<Integer>());
            List<Integer> node2AdjList = adjacencyMap.getOrDefault(node2,new LinkedList<Integer>());
            node1AdjList.add(node2);
            node2AdjList.add(node1);
            adjacencyMap.put(node1, node1AdjList);
            adjacencyMap.put(node2, node2AdjList);
        }
    } catch (FileNotFoundException ex) {
        out.println(ex.getMessage());
    }
    node = adjacencyMap.keySet().parallelStream().reduce(Integer::max).get();

}

java - ArrayIndexOutOfBoundsException on generating maze graph with depth first search

1 回答 1

Related

Reference