# Best approach to guarentee acyclic directed graph

Jim Yingst

Wanderer

Sheriff

Sheriff

Posts: 18671

posted 9 years ago

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

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*