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

comment on

( #3333=superdoc: print w/replies, xml ) Need Help??
Ahoy Monks. I need an algorithm, I just don't know which one. Here's my problem:

  • 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


In reply to In search of an algorithm for loading cyclic graphs by samtregar

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or How to display code and escape characters are good places to start.
Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (3)
As of 2023-01-29 19:56 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?