Skip to content

Instantly share code, notes, and snippets.

@deedee47
Created June 5, 2021 23:03
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save deedee47/0b89cfdf224d90faff061287774e57d0 to your computer and use it in GitHub Desktop.
Save deedee47/0b89cfdf224d90faff061287774e57d0 to your computer and use it in GitHub Desktop.
Detects if there is at least a cyclic path in all available routes
public boolean isThereCycle(Map<Character, List<Character>> map){
if(map == null || map.isEmpty()) return false;
//use each node as starting point
for(char item : map.keySet()){
//create new tracking experience for each start point
Stack<Character> trackPad = new Stack<>();
List<Character> visitedPoints = new ArrayList<>();
visitedPoints.add(item);
trackPad.addAll(map.get(item));
while(!trackPad.isEmpty()){
char subItem = trackPad.pop();
//check if subpath leads back to origin
//if key is not found, return a default list - handles null exceptions
if(map.getOrDefault(subItem, new ArrayList<>()).contains(item)) return true;
//avoid re-processing a path
if(!visitedPoints.contains(subItem)){
trackPad.addAll(map.getOrDefault(subItem, new ArrayList<>()));
visitedPoints.add(subItem);
}
}
}
return false;
}
@deedee47
Copy link
Author

Hi @meekgeek, true, I agree the use case is valid. Surprisingly it returns true when i debugged it with the example. Thanks for the feedback

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment