Results 1 to 3 of 3
  1. #1
    Join Date
    Mar 2006
    Posts
    1

    Question How do I model a directed graph?

    Hi all!

    Any ideas on how to model a directed acyclic graph (DAG) i postgresql? I need the model to be efficient with respect to traversing the graph.

    Please see the attached image for an example.

    A typical query on the graph is to traverse backwards following all paths from a given node to it's "start nodes" (i.e. nodes with in-degree 0; the nodes named 'f' in the figure).

    As an example, given the node 'c3' in the figure I'd like to be able to retrieve all "connecting" nodes, i.e. c1, c2, f1, f2, f3.

    Anybody have experience with modeling graphs? I suspect I have to be careful not to run into performance problems on larger graphs (i.e. milions of nodes). As can be seen from the figure, any node can reference any number of nodes, and any node can be references by any number of nodes, i.e. a many-to-many between nodes.


    Thank you!
    Attached Thumbnails Attached Thumbnails graph.jpg  

  2. #2
    Join Date
    Jun 2004
    Location
    Arizona, USA
    Posts
    1,848
    I've never thought about modelling a network diagram like this. Maybe a self referencing, many-many relationship? You would have to explicitly exclude (maybe via trigger?) a node referencing itself.
    Lou
    使大吃一惊
    "Lisa, in this house, we obey the laws of thermodynamics!" - Homer Simpson
    "I have my standards. They may be low, but I have them!" - Bette Middler
    "It's a book about a Spanish guy named Manual. You should read it." - Dilbert


  3. #3
    Join Date
    Feb 2004
    Location
    In front of the computer
    Posts
    15,579
    They're already covering Section C now? I didn't think we were that far into the semester!

    -PatP

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •