samtregar has asked for the wisdom of the Perl Monks concerning the following question:
- I have a cyclic directed graph.
- Evaluating the linking of nodes is expensive.
- The graph may be very large.
- Most nodes do not participate in cycles.
- There are many types of nodes, each with their own linking constraints.
- My job is to load the graph from disk into a relational database where links work via sequentially allocated IDs.
My problem is that cycles give my code indigestion, because I'm trying to evaluate the graph by looking through nodes in order (which is more-or-less random). When I find a case that's causing a cycle (i.e. an A node is linking through a B node back to A via the C link type) I go into the code for type A and apply a local fix. This usually means I create the ID for A early so that B can find it at the right point.
Obviously my solution isn't a good one. It takes time every time a new circular link condition pops up. It's also a ticking bomb since I have no confidence that I've really found them all.
This seems like a problem that should have a known comp-sci solution. Does anyone know it? Links to references are fine.
Thanks,
-sam