programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Paul Clapham
• Ron McLeod
• Jeanne Boyarsky
• Tim Cooke
Sheriffs:
• Liutauras Vilda
• paul wheaton
• Henry Wong
Saloon Keepers:
• Tim Moores
• Tim Holloway
• Stephan van Hulst
• Carey Brown
• Frits Walraven
Bartenders:
• Piet Souris
• Himai Minh

# How to detect circle in a directed graph?

Ranch Hand
Posts: 125
• Number of slices to send:
Optional 'thank-you' note:
Hello everyone,

My application needs a feature to detect whether a directed graph contains circle. Does anyone know any efficient implementation? Which implementation is the best (most efficient)?

thanks in advance & happy new year,
George

Ranch Hand
Posts: 70
• Number of slices to send:
Optional 'thank-you' note:
Hi,

Otherwise to detect a circle in a graph ,
keep track of nodes visited starting from a particular node,(using a set may be helpful) and if u get same node from where you started ,you have detected a circle.

Ranch Hand
Posts: 71
• Number of slices to send:
Optional 'thank-you' note:
Tarjan's algorithm for detecting cycles will find cycles in O(n+e) time in a directed graph with n vertices and e edges.

George Lin
Ranch Hand
Posts: 125
• Number of slices to send:
Optional 'thank-you' note:
Virag,

Originally posted by Virag Saksena:
Tarjan's algorithm for detecting cycles will find cycles in O(n+e) time in a directed graph with n vertices and e edges.

It seems very efficient! But I can not find the algorithm you mentioned from Google by searching key words "Tarjan cycle graph". Could you help to provide more information please?

regards,
George

George Lin
Ranch Hand
Posts: 125
• Number of slices to send:
Optional 'thank-you' note:
vivekkumar,

Originally posted by vivekkumar sharma:
Hi,

I do made a search before I posted this question before. The issue is that, I do not know the name of the algorithm so that I can not find much useful information from Google. Could you help please? :-)

Originally posted by vivekkumar sharma:
Otherwise to detect a circle in a graph ,
keep track of nodes visited starting from a particular node,(using a set may be helpful) and if u get same node from where you started ,you have detected a circle.

I have tried this method. I do not think this method is correct. For example, suppose in a simple graph, there are four nodes, A, B, C, D. The directed graph has the following edges,

A-->B
A-->C
B-->D
C-->D

In this graph, there is no cycle. But when running your method, since node D will be accessed twice both by node B and by node C, the directed graph will be detected cycle by your method.

Maybe I do not quite understand your method, could you provide a simple implementaion of your method please?

regards,
George

Greenhorn
Posts: 10
• Number of slices to send:
Optional 'thank-you' note:
George,

I tried to implement a sample implementation with a simple DataStructure "NodeLink" to indicate "From" and "To" vertices of a link.

Following are the steps to approach this problem
1)Make an appropriate data structure to represent the graph, its vertices and node links.
2)Construct partial graphs for each entry in the nodelinks i.e all the vertices approachable from a given vertex.
3)Iterate through the partial graphs constructed to see if any node is visited more than once in a subgraph.

In the program below, I used a hastable to keep track of nodes and the number of times visited count. I would initialize the hashtable with "0 visit counts" for each partial graph.

I hope this helps!

-Praveena

Virag Saksena
Ranch Hand
Posts: 71
• Number of slices to send:
Optional 'thank-you' note:
George,
You can try searching for
robert tarjan strongly connected components in a directed graph
If you can't find it, send me a private message, and I'll send you a copy

 The two armies met. But instead of battle, they decided to eat some pie and contemplate this tiny ad: free, earth-friendly heat - a kickstarter for putting coin in your pocket while saving the earth https://coderanch.com/t/751654/free-earth-friendly-heat-kickstarter