 |
 | Home | Contact Us | FAQ | Search & Site Map | Link to Us |
 | Sign In | Join | Other 45 Sites in Network |
Java Forum / First Aid / January 2006How to detect circle in a directed graph?
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 > 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)? The usual solution is a DFS. I suppose in the rare circumstance that most graphs will have a cycle somewhere near the root, a BFS could be faster on average. Or, if you somehow know where to start looking for likely cycles, you could come up with some sort of out-of-order search. Larry, >> Hello everyone, >> [quoted text clipped - 8 lines] >where to start looking for likely cycles, you could come up >with some sort of out-of-order search. I agree with your points. Do you know whether there exists an algorithm do detect a cycle inside of a graph? I want to make a reference to exiting algorithms and then do some enhancements according to your suggestions. regards, George > 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)? DFS seems to be the way to go, once you reach a node by two different paths, you have a cycle.  SignatureYou can't run away forever, But there's nothing wrong with getting a good head start. --- Jim Steinman, "Rock and Roll Dreams Come Through" Stefan, >> Hello everyone, >> [quoted text clipped - 4 lines] >DFS seems to be the way to go, once you reach a node by two different >paths, you have a cycle. 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 > Stefan, > [quoted text clipped - 10 lines] > > I have tried this method. I do not think this method is correct. If you reach a node that has been visited but not fully explored, the edge that got you there is part of a cycle. Larry, >> Stefan, >> [quoted text clipped - 4 lines] >If you reach a node that has been visited but not fully >explored, the edge that got you there is part of a cycle. Anyway, do you have any simple implementation or mathematics proof of your idea? I do not think it is a formal algorithm solution description. regards, George > Larry, > [quoted text clipped - 9 lines] > Anyway, do you have any simple implementation or mathematics proof of your > idea? I do not think it is a formal algorithm solution description. Informally: nodes that are visited but not fully explored have a path to the current node, so if you reach one of them it is by a cycle. Since the search is exhaustive for each node, any cycle that includes a node will be found before that node is fully explored. For a formal proof, do a Google search for graph cycle dfs proof Here is the first result: http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthS earch.htm > 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)? I think Hare & Tortoise is the conventional algorithm. http://www.google.com/search?q=%22hare+and+tortoise%22+algorithm Tom Hawtin SignatureUnemployed English Java programmer http://jroller.com/page/tackline/ >> My application needs a feature to detect whether a directed graph >> contains [quoted text clipped - 5 lines] > > http://www.google.com/search?q=%22hare+and+tortoise%22+algorithm I believe that only applies to singly-linked structures. >>>My application needs a feature to detect whether a directed graph >>>contains [quoted text clipped - 7 lines] > > I believe that only applies to singly-linked structures. Is it difficult to adapt for directed graphs. Tom Hawtin SignatureUnemployed English Java programmer http://jroller.com/page/tackline/ >>>>My application needs a feature to detect whether a directed graph >>>>contains [quoted text clipped - 9 lines] > > Is it difficult to adapt for directed graphs. Impossible, if the goal is O(1) space complexity. I guess you could use a graph walk that reverses only at fully explored nodes, which might make a fun animation but would be less time and space efficient than a DFS cycle test. Larry, >>>>>My application needs a feature to detect whether a directed graph >>>>>contains [quoted text clipped - 7 lines] >would be less time and space efficient than a DFS cycle >test. I can not believe that cycle detection algorithm can work with only O(1). Could you privide sample implementation or reference resource please? regards, George > Larry, > [quoted text clipped - 12 lines] > I can not believe that cycle detection algorithm can work with only O(1). > Could you privide sample implementation or reference resource please? That is my point. Hare & Tortoise uses O(1) space for cycle detection in a linked list. This is its main benefit over the obvious algorithm, which uses O(n) space. The speed may be slightly slower or faster than the obvious algorithm by a constant factor. For the Hare & Tortoise style cycle detection algorithm for directed graphs that I propose above, the space and time complexity is the same as for DFS, and I would expect space and time use to be worse by constant factors, so there would be no practical benefit. It should work though. For a depth first graph walk that reverses only at fully explored nodes, any repeated edge is part of a cycle, and if a cycle exists, the walk will become trapped in it. If the follower catches the leader at the same edge (not just the same node), a cycle has been found. Larry, >> Larry, >> [quoted text clipped - 16 lines] >trapped in it. If the follower catches the leader at the same >edge (not just the same node), a cycle has been found. Thank you very much for your reply! I think your idea of using DFS to detect cycle in a graph is a great one! I am wondering whether you have any implementation of this idea in pseudo- code? regards, George > Thank you very much for your reply! I think your idea of using DFS to > detect > cycle in a graph is a great one! It's not my idea, it's the standard way of doing it. My idea was using a modified DFS to adapt Hare & Tortise to general directed graphs for no good reason (except maybe a nifty animation). DFS cycle detection is something like this: boolean hasCycle(Graph g) { foreach(Node n in g with no parent nodes) { if(visitNode(n)) return true } return false } boolean visitNode(Node n) { markVisited(n) foreach(Node c in children of n) { if(isVisited(c)) return !isFullyExplored(c) if(visitNode(c)) return true } markFullyExplored(n) return false } Larry, >> Thank you very much for your reply! I think your idea of using DFS to >> detect [quoted text clipped - 26 lines] > return false >} Thank you very much for your reply! regards, George George2 via JavaKB.com skrev: > Hello everyone, > [quoted text clipped - 8 lines] > Message posted via JavaKB.com > http://www.javakb.com/Uwe/Forums.aspx/java-setup/200601/1 Slightly OP, you could have a look at the code for an open-source cyclic-dependency checker: http://classycle.sourceforge.net/ The code's uncommented, though, and I can't see immediate documentation. .ed -- www.EdmundKirwan.com - Home of The Fractal Class Composition. iamfractal, >George2 via JavaKB.com skrev: > [quoted text clipped - 15 lines] >-- >www.EdmundKirwan.com - Home of The Fractal Class Composition. The tool is very useful! Thank you very much! regards, George Free MagazinesGet these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...
|
Reply to this Message
|
 Sign In
 Join
 My Latest Posts My Monitored Threads My Blog My Photo Gallery My Profile My Homepage Start New Thread Enable EMail Alerts Rate this Thread
|
©2008 Advenet LLC Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.