Beefy Boxes and Bandwidth Generously Provided by pair Networks
Do you know where your variables are?
 
PerlMonks  

Re: In search of an algorithm for loading cyclic graphs

by kvale (Monsignor)
on May 17, 2005 at 18:50 UTC ( #457942=note: print w/replies, xml ) Need Help??


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

  • Comment on Re: In search of an algorithm for loading cyclic graphs

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

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://457942]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (1)
As of 2023-02-06 20:51 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    I prefer not to run the latest version of Perl because:







    Results (36 votes). Check out past polls.

    Notices?