One common algorithm for converting a directed graph into an ordered set (i.e., your sequential IDs) is a topological sort. The problem here is that you have cycles, which generate ambiguous sorts. Thus you cannot accomplish your job as specified.
Your 'local fix' is to break the cycle by supplying a point outside the set of sequenial IDs. If this is kosher, then I would attempt to solve your problem in three steps.
- First, do a breadth-first search of the graph starting from the root node. When you encounter a cycle (a node previously searched), delete that link from the graph and save the link for later use. After all nodes have been searched, you are left with an acyclic graph, or tree.
- Second, topologically sort this tree into a sequential set of IDs.
- Finally, add back in the deleted links you stored from the first step.
Update: fixed a couple of typos.
