Win a copy of The Way of the Web Tester: A Beginner's Guide to Automating Tests this week in the Testing forum!

# Best approach to guarentee acyclic directed graph

Pat Farrell
Rancher
Posts: 4678
7
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
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
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.