Find if a graph contains cycle

graphCycle.py

def depth_first_search(map, key, visited):
    if key == None: return None
    key = key.lower() if key.lower() in map else key.upper()
    if not key in map: return False 
    if map[key] == None: return False
    for point in map[key]:
        if point.lower() in visited:
            return True
        visited.add(key.lower())
        if depth_first_search(map, point, visited):
            return True
        visited = set()
    return False


def find_cycle(map):
    if map == None: return False
    for point in map:
        if depth_first_search(map, point, set()):
            return True
    return False    

Hello @Fredpwol, thank you for participating in Week 9 of #AlgorithmFridays.

Your solution is clean and easy to read and works for most of the test cases. However it fails the test cases for when any of the adjacent paths to a path has no paths leading out from it (something called a leaf node in Computer science terms).

Here is an example:

map = { 'C': ['A', 'B'] } # 'A' and 'B' have no paths leading out from them

In the above instance, A and B are leaf nodes because there is no path out from them and this is where your solution breaks - specifically on line 4. Ideally there should be a check to see if A or B is a key in the map, something like if key in map

But in all, this was a good attempt and you demonstrated good knowledge of depth first search for solving recursive problems. Kudos to you!

Looking forward to hearing your thoughts.

Hello @meekg33k, Thank you for the feedback I totally overlooked the edge case for leave nodes. I have updated my code to handle that edge case.