How 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

Re: How to detect circle in a directed graph?
 

Hello, I do not have much information to go on however, I’m assuming your directed graph will contain ONLY straight lines and circles.

Your problem is how do you detect a circle automatically right?

Well think of it like this. A circle is a just shape with a closed border. This lends itself a useful property, a property closely linked to the flood fill function used in any good paint utility.

If I draw the outline of a circle or for that matter any other closed polygon, I am able to apply the flood fill algorithm on that shape. If the user clicks on the inside of the shape the flood fill algorithm recursively fills that shape. So effectively, wherever the user clicks on the screen - and the flood fill algorithm has been successful, must mean the user has clicked on a circle. Of course no other bounded shapes exist other than the circle.

I’ve not had time to think about it but that would be my best guess. Good luck.

Re: How to detect circle in a directed graph?
 

research "Hough Transform".

just try searching for "circle detection" on google

Re: How to detect circle in a directed graph?
 

Phaelax,


Maybe I have not made myself understood enough. I mean how to detect cycle in a directed graph -- the directed graph defined in data structure. Coule you help please?


regards,
George

Re: How to detect circle in a directed graph?
 

iamthwee,


Maybe I have not made myself understood enough. I mean how to detect cycle in a directed graph -- the directed graph defined in data structure. Coule you help please?


regards,
George

Re: How to detect circle in a directed graph?
 

cycle, darn typos lol.

Not sure about that though. It would also help if you actually told us why you wanted to do that and for what purpose.

Is this homework, whats the actual question? It might be simpler than what you are trying to do.

Also, are you familiar with the java 2d graphics package?

Re: How to detect circle in a directed graph?
 

iamthwee,


It is not a homework. It is for decision making solution -- like rule based intelligent solution finding application. Different rules are linked together like a graph -- while each rule is a node in the graph.

Actually, it has nothing to do with java 2d -- it is not a graphics application, it is a business intelligence application!


regards,
George

Re: How to detect circle in a directed graph?
 

Ok, now it's clear that it is not a graphics application, although when you used the term ' circle' instead of 'cycle' you can understand where the confusion came from.

It sounds more like you need help with data structures, specifically linked lists. I'm still unsure of what you mean by detect a cycle though.

Does this have anything to do with the other post you have about finding the closest matching words in a dictionary file?

Re: How to detect circle in a directed graph?
 

Agree. It is my typo. I think you have understood my idea now.

The two issues do not have any relationships. They are just two algorithm related issues I am meeting with currently.

Anyway, do you have any idea of the solution?


regards,
George

Re: How to detect circle in a directed graph?
 

Hi,

I wonder why people think about graphics applications when they read "directed graph". Actually, it is clearly defined what that means.

However, you can detect cycles in directed graphs by using the DFS algorithm. (Depth-first-search)

For example consider the following directed graph with the vertices A,B,C,D,E,F,G,H:

C->B
B->A
C->D
D->E
D->G
E->F
F->G
G->H
H->D

I guess you want to graph this on a piece of paper ;)

Let's say that every vertice is marked as "white".
We can only move to "white" vertices from now on.

Now, let's assume our DFS algorithm starts at C (to keep it simple).

We mark C as "gray" and move to B.
We mark B as "gray" and move to A.
We mark A as "gray" and we can't get any further here, so we mark A as "black" and move back to B which we will also mark as "black", since there is no way away from B other than moving to A again which is already "black".
Now, we move back to C which we will leave "gray", since there is still an open way away from C. We move from C to D.
We mark D as "gray" and move to E.
We mark E as "gray" and move to F.
We mark F as "gray" and move to G.
We mark G as "gray" and move to H.
We mark H as "gray" and move to D, which is "GRAY". This means that D is part of the actual path that is being considered by our DFS algorithm. We found a circle!!! This means that whenever we find a vertice (by moving forward) which is marked "gray" we have a cycle, and we then can terminate with return value "true" or whatever ;)

This is supposed to be a short example, you should read over some more detailed description of DFS if you don't understand this. Every vertice in DFS has 3 states, "white", "gray" or "black". You can also say "not processed", "being processed", "processed" or whatever...it's up to you.

This algorithm also works if a directed graph is not strongly connected.