File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
The moose likes Java in General and the fly likes Best approach to guarentee acyclic directed graph Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Best approach to guarentee acyclic directed graph" Watch "Best approach to guarentee acyclic directed graph" New topic

Best approach to guarentee acyclic directed graph

Pat Farrell

Joined: Aug 11, 2007
Posts: 4659

There are several fairly easy ways to represent a directed graph of nodes and edges in Java.

But I'm not seeing an obviously good way to test for, and trap, cycles in the graph.

The only clear way that I see is to test before each insert.

Is there a better way?

Jim Yingst

Joined: Jan 30, 2000
Posts: 18671
Well, it may depend on your use case. If you do all your inserts at the beginning to create the graph, then after that you use the graph but never (or very rarely) change it, then it may make more sense to not validate each insert, but instead do a single check of the whole graph after the last insert is complete. I think that might lead to less redundant checking. However if you often need to make small changes to the graph and then use it some more, it makes more sense to just validate each insert. (Also, I think it's probably easier to code.)

Note that if you validate each insert as it's made, you don't need to bother checking the whole graph. You just need to check the paths coming out from the edge you inserted, and see if any of them lead back to the insert point. This should be a fairly simple recursive call. Admittedly it may eventually involve every node and edge in the structure, but at least there shouldn't be any infinite loops.

I've been tossing around a few more elaborate algorithms in my head, but so far I haven't come up with one that's really superior. Some may be more efficient, but the added complexity of the code makes me suspicious, and I haven't convinced myself they're worth doing. I've studied little graph theory, so there may well be a better solution already out there; I just don't know it.

"I'm not back." - Bill Harding, Twister
Pat Farrell

Joined: Aug 11, 2007
Posts: 4659

Clearly how is a bit of an engineering design tradeoff, but I generally prefer to always have a 'good object' and thus much prefer to test for every insert so that you know that its good.
I agree. Here's the link:
subject: Best approach to guarentee acyclic directed graph
It's not a secret anymore!