Searching LinkedHashMap Using nested for loops

Question

I have a LinkedHashMap like so

LinkedHashMap <Integer, ArrayList<Integer>> indexToIndecies = new LinkedHashMap <Integer ,ArrayList<Integer>>();

I have a method public int searchGraph(int baseIndex, int searchIndex, int count)

the point of this search method is; when some one enters baseIndex, which is a key, it has to find how many "clicks" it takes to get to the searchIndex. the values of the keys are the indexes to which they relate. So a "click" would be going from one key to another. So if my hashmap looks like:

0[2]
1[0, 3]
2[0, 5]
3[0, 2, 4, 5]
4[5]
5[2]
6[3, 4, 5]
7[1, 4]

to get from 0 to 5 takes two clicks.

so this is the code I have for my method:

public int searchGraph(int baseIndex, int searchIndex, int count)
{
    if (baseIndex == searchIndex)
    {

        return count;
    }
    if (searchIndex > indexToIndecies.size()-1){

        return -3;
    }
    else{

        for (int i = 0; i < indexToIndecies.get(baseIndex).size(); i++)
        {
            for (int x = 0; x< indexToIndecies.get(baseIndex).size(); x++){

                if (indexToIndecies.get(baseIndex).get(x) == searchIndex){

                    return count;
                }
                else{
                    count++;
                }

            }

            baseIndex = (indexToIndecies.get(baseIndex)).get(i);            

        }

        return count;
    }

}

Works fine If The baseIndex and seachIndex I give it has an association, however if it doesn't I am not sure how to catch that... Any help will be appreciated.

Answer 1

Right now you're not accounting for the possibility that there may be multiple paths from the baseIndex to the searchIndex - presumably you want the shortest path if this is the case. One way to correct for this is to replace the nested for loops with a single for loop around a recursive call. Return Integer.MAX_VALUE if a path isn't found, then if your shortest path has a count of Integer.MAX_VALUE then you'll know that you weren't able to find a path. (If you DID find a path with a count of Integer.MAX_VALUE then something probably went wrong with your path-finding algorithm - you shouldn't have paths that are that long.) If you want to use nested loops instead of recursion then you can convert the recursive call into a loop by using your own stack variable.

public int searchGraph(int baseIndex, int searchIndex, int count) {
    if(baseIndex == searchIndex) {
        return count;
    } else if(count > indexToIndecies.size()) {
        return Integer.MAX_VALUE; // cycle in graph
    } else {
        int returnVal = Integer.MAX_VALUE;
        for(int i = 0; i < indexToIndecies.get(baseIndex).size(); i++) {
            int temp = searchGraph(indexToIndecies.get(baseIndex).get(i), searchIndex, count + 1);
            returnVal = temp < returnVal ? temp : returnVal;
        }
        return returnVal;
    }
}

This should return the shortest path, and if it returns Integer.MAX_VALUE then a path wasn't found.

Another option is to return an Integer instead of an int, in which case you can return a null in the case that you couldn't find a path.

Edit: SimonC pointed out in the comments that a cycle in the graph could cause a stack overflow. I've corrected for this by returning Integer.MAX_VALUE if count exceeds indexToIndecies.size(), since count shouldn't exceed the number of keys in the map.