Find all cycles in directed graph

Asked Jul 20 '16 at 13:35

Active Jul 20 '16 at 18:20

Viewed 689 times

I'm using the following python code to find out any cycle in graph but it doesn't return correct results

for node in graph:
    new_path=node
    path = node
    for adjacent in graph.get(node, []):
        if not adjacent in new_path:
            new_path = list(path)
            new_path.append(adjacent)
        else:
            print (new_path)

Could you please help me find any cycles in the graph?

Input Sample:

graph = {
    '181': set(['284','248','247','350']),
    '350': set(['400', '401']),
    '400': set(['181', '654'])
}

Desired Output:

181 350 400 181

My code does not currently output anything.

edited Jul 20 '16 at 17:36

Mad Physicist

107,652
25
181
264

asked Jul 20 '16 at 13:35

Siavash R

What inputs, what are you expecting to get out, what are you actually getting out? – Mad Physicist Jul 20 '16 at 14:23
@MadPhysicist Input: graph in standard structure of python. Out put, list of cycles paths. – Siavash R Jul 20 '16 at 16:21
I meant an actual sample input, output and explanation of how it differs from the expected. – Mad Physicist Jul 20 '16 at 16:22
@MadPhysicist I've attached samples – Siavash R Jul 20 '16 at 16:28
And what are you expecting to see? – Mad Physicist Jul 20 '16 at 16:34
Alternatively, what are you seeing instead of the sample output? It is not clear of the sample output is what you want or what you are actually getting. – Mad Physicist Jul 20 '16 at 16:34
@MadPhysicist nothing in results. I said the sample output – Siavash R Jul 20 '16 at 16:35
Your output looks fine. What is the actual problem? – Mad Physicist Jul 20 '16 at 16:45
BTW, you can define a `set` with just `{'284','248','247','350'}`. No need for the `set([])` part. – Mad Physicist Jul 20 '16 at 16:47
It doesn't returns value – Siavash R Jul 20 '16 at 16:53
That's because you aren't returning a value anywhere? Please provide more context. Is this in a function somewhere? – Mad Physicist Jul 20 '16 at 16:54
@MadPhysicist no just a simulation which includes just this function – Siavash R Jul 20 '16 at 16:57
And it's producing the expected output. So what do you mean that it doesn't return a value? – Mad Physicist Jul 20 '16 at 16:58
In this time it doesn't return any result. Nothing! – Siavash R Jul 20 '16 at 17:12
I think I understand now. Sorry about the miscommunication. Close vote removed. – Mad Physicist Jul 20 '16 at 17:38
One more request. Could you please explain what you think your code is doing? – Mad Physicist Jul 20 '16 at 17:40
@MadPhysicist well I think it starts from a node and for each adjacent to the node, checks whether the adjacent is located on path or not. Then detects the cycles. – Siavash R Jul 20 '16 at 18:13
You reset the path on every iteration of the outer loop. This looks like a problem better solved by recursion. – Mad Physicist Jul 20 '16 at 18:23
http://stackoverflow.com/users/2988730/mad-physicist suggests that I point out that this problem has been answered elsewhere: http://stackoverflow.com/questions/261573/best-algorithm-for-detecting-cycles-in-a-directed-graph. – Bill Bell Jul 20 '16 at 19:26

Find all cycles in directed graph

0 Answers0