http://qs1969.pair.com?node_id=457942


in reply to In search of an algorithm for loading cyclic graphs

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.

  1. 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.
  2. Second, topologically sort this tree into a sequential set of IDs.
  3. Finally, add back in the deleted links you stored from the first step.
Update: fixed a couple of typos.

-Mark

Replies are listed 'Best First'.
Re^2: In search of an algorithm for loading cyclic graphs
by samtregar (Abbot) on May 17, 2005 at 19:12 UTC
    Thanks, this makes sense. I'm concerned about how this will perform on large graphs but perhaps the only way to find out is to try it. The advantage of my current approach is that it only makes one pass over the data and it's hard to beat that for speed...

    -sam