How to detect circle in a directed graph?

[George2]

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

[iamthwee]

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.

[Phaelax]

research "Hough Transform".

just try searching for "circle detection" on google

[George2]

Phaelax,

research "Hough Transform".

just try searching for "circle detection" on google

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

[George2]

iamthwee,

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.

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

[iamthwee]

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?

[George2]

iamthwee,

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?

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

[iamthwee]

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?

[George2]

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.

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

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

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

[LupoXY]

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.

[iamthwee]

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

Actually if you read the entire post, he used the word circle, instead of cycle.

To most intelligent people that would mean something completely different to cycle.

Isn't it possible that he could have had finished the first stage in his program, which is the algorithm you have outlined, and then has moved onto a 2d realisation, whereby there was a need to detect a circle?

:rolleyes:

[server_crash]

Actually if you read the entire post, he used the word circle, instead of cycle.

To most intelligent people that would mean something completely different to cycle.

Isn't it possible that he could have had finished the first stage in his program, which is the algorithm you have outlined, and then has moved onto a 2d realisation, whereby there was a need to detect a circle?

:rolleyes:

What is up with your attitude? In almost every post you have some little smart remark. That person made a very nice (long) post. And if you look a few posts before, you made a typo using cycles. Leave it up to the thread creator wether the post was helpful or not and get rid of your piss poor attitude.

[iamthwee]

And if you look a few posts before, you made a typo using cycles.

I'm looking...but no I can't find it. :p

That person made a very nice (long) post.

Yes and I'm not debating that. He said ...

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

Personally, I take that to be an attack on my original post. And since the typo was not mine, regarding the word cycle instead of circle, I have the right to defend myself?

Leave it up to the thread creator wether the post was helpful or not and get rid of your piss poor attitude.

;)

I would never attack you though. You helped me create an executable jar file.
:cheesy: :cheesy:

[Dani]

Let's get back on track to the question please. I would hate to see this thread turn sour.

[LupoXY]

Hi,

by the way DFS has linear growth ( O(n) ), meaning that it is pretty efficient.

I believe that there is no faster algorithm for your problem, in terms of efficiency.

[John B. Martin]

I'd like to thank George2 for raising the question and LupoXY for the exhaustive answer. I've just encountered the same problem, and thanks to you guys I found the solution pretty fast.

[mayne]

slt tt monde je besoins de votre aide
j'ai un code en java netbeans de detection d'image hough_cercles mais je n'arrive pas a l'implimenté dans mon pogramme alors est ce que il ya quelqu'un qui peut m'idé le plustot possible et de me contacté sur mon e-mail [e-mail] ;)