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.

• Jason C: If the HashMap does not contain the specified index, indexToIndecies.get(...) will return null. You will have to check for that.
• Marsellus Wallace: this smells like recursion...

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.

• SimonC: This could end up causing a stack overflow with a cycle in the graph (assuming the stack size didn't allow Integer.MAX_VALUE frames on the stack).
• Zim-Zam O'Pootertoot: @SimonC Good point, I've added a guard to terminate the recursion if count exceeds the number of keys in the map
• SimonC: another option would be to pass a set of visited indecies in the recursive call. That would provide much faster cycle detection.
• Zim-Zam O'Pootertoot: @SimonC That speeds up cycle detection, but slows down the case where there aren't any cycles since you'll be creating a bunch of sets that won't be used. I'm operating on the assumption that cycles are rare, in which case it's faster to use a guard on count; if cycles are common then it would make more sense to use a set of visited values as you suggest.