This week's book giveaway is in the OCAJP forum.
We're giving away four copies of Programmer's Guide to Java SE 8 Oracle Certified Associate (OCA) and have Khalid A Mughal & Rolf W Rasmussen on-line!
See this thread for details.
Win a copy of Programmer's Guide to Java SE 8 Oracle Certified Associate (OCA) this week in the OCAJP forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Best approach to guarentee acyclic directed graph

 
Pat Farrell
Rancher
Posts: 4678
7
Linux Mac OS X VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?

Thanks
Pat
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Pat Farrell
Rancher
Posts: 4678
7
Linux Mac OS X VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Don't get me started about those stupid light bulbs.
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic