CODEWITHSUNDEEP
pythondictionarygraph
J. Doe
J. Doe

Reputation: 13

Detecting cycles in a graph

I want it to return true if there is a cycle and false if there is not. It works if there is only one edge per node...

eg:

walkways_info = """\
U 3
0 1
1 2
2 0
"""'

print(interesting_path_feasible(walkways_info))

But it doesn't work when there are multiple edges per node as the dictionary doesn't hold multiple values.

eg:

walkways_info = """\
U 7
1 2
1 5
1 6
2 3
2 5
3 4
4 5
"""

How would I fix this? Thanks in advance :)

def interesting_path_feasible(walkways_info_str):
    """Determines if a cycle exists"""
    graph_dict = dict(e.split(' ') for e in walkways_info_str.splitlines())
    visited = set()
    path = [object()]
    path_set = set(path)
    stack = [iter(graph_dict)]
    while stack:
        for node in stack[-1]:
            if node in path_set:
                return True
            elif node not in visited:
                visited.add(node)
                path.append(node)
                path_set.add(node)
                stack.append(iter(graph_dict.get(node, ())))
                break
        else:
            path_set.remove(path.pop())
            stack.pop()
    return False

Upvotes: 1

Views: 1276

Answers (1)

Aditya
Aditya

Reputation: 2520

Make the value a list, e.g.

a["abc"] = [1, 2, "bob"]

There are a couple of ways to add values to key, and to create a list if one isn't already there. I'll show one such method in little steps.

key = "somekey" 
a.setdefault(key, []) 
a[key].append(1)

Results:

a {'somekey': [1]}

Next, try:

key = "somekey"
a.setdefault(key, [])
a[key].append(2)

Results:

a {'somekey': [1, 2]}

The magic of setdefault is that it initializes the value for that key if that key is not defined, otherwise it does nothing. Now, noting that setdefault returns the key you can combine these into a single line:

a.setdefault("somekey",[]).append("bob")

Results:

a {'somekey': [1, 2, 'bob']}

Upvotes: 2

Related Questions