Results 1 to 8 of 8
  1. #1
    Join Date
    Sep 2005
    Posts
    2

    Unanswered: Graph Routing - A real challenge

    Hi,

    I tried to do this my self but I'm not a DBA and am new to MySQL (I work with Oracle mostly, and have a team of DBAs who do this stuff for me, but this job is for a different company so I cant use my team) so I thought I'd ask you guys for an idea on how I can do this:

    I have two tables, defining a graph:

    t_Items and t_Relations.

    t_Items is basically a list of items, identified by a unique ID.

    |ID | Name
    ---------------
    | 0 | item 0
    ---------------
    | 1 | item 1
    ---------------
    | 2 | item 2
    ---------------
    | 3 | item 3
    ---------------

    t_Relations defines relations between two items.

    | FirstID | SecondID
    ------------------------
    | 0 | 1
    ------------------------
    | 1 | 3
    ------------------------
    | 3 | 5
    ------------------------

    This means I have a graph of nodes with relations between them (in both directions).

    What I need is a stored procedure which selects all the "Routes" from one node to another and logs them in another table: t_Routes.

    The way it would be used is - I would call a stored procedure (I'm using MySQL 5) giving it two Node IDs as parameters.
    Then I'd be able to select all the rows from t_routes for these two IDs and I'd have a row for each route.

    How can I do this? I racked my head for several days and couldnt come to a solution which worked. I heard there are some briliant minds (DBAs ) here so I hope you dont let me down!!

    Thanks for any help or advice you may be able to give!

    Gidi

  2. #2
    Join Date
    Apr 2002
    Location
    Toronto, Canada
    Posts
    20,002
    Quote Originally Posted by GMMorris
    I heard there are some briliant minds (DBAs ) here
    the set of brilliant minds here and the set of DBAs here are not necessarily congruent sets

    i'm neither of the above, and i can't help you

    i just remember from one of my college math courses that the number of different paths increases astronomically as the number of nodes increases, and that the problem of traversing all possible paths is non-trivial
    rudy.ca | @rudydotca
    Buy my SitePoint book: Simply SQL

  3. #3
    Join Date
    Oct 2002
    Location
    greenwich.ct.us
    Posts
    279
    If this were ORACLE, you could be done in about 30 seconds with a CONNECT BY. However, it's not. You are looking at using recursion (in the client on 4.x, maybe with a stored procedure in 5) to traverse your graph.

  4. #4
    Join Date
    Oct 2002
    Location
    greenwich.ct.us
    Posts
    279

  5. #5
    Join Date
    Apr 2002
    Location
    Toronto, Canada
    Posts
    20,002
    jeff, the only problem is, this isn't hierarchical data
    rudy.ca | @rudydotca
    Buy my SitePoint book: Simply SQL

  6. #6
    Join Date
    Oct 2002
    Location
    greenwich.ct.us
    Posts
    279
    same basic concept.

  7. #7
    Join Date
    Apr 2002
    Location
    Toronto, Canada
    Posts
    20,002
    no, it isn't

    how many ways can you get from 1 to 5 in this graph?
    Attached Thumbnails Attached Thumbnails graph.gif  
    rudy.ca | @rudydotca
    Buy my SitePoint book: Simply SQL

  8. #8
    Join Date
    Sep 2005
    Posts
    2
    Yea, I know all the things you guys said, any solutions in mind?

    As far as the actualy code goes- I'd rather it be in an SP rather than the software, to save my self SELECTing all the nodes...

    As far as the Number of routes goes- I dont really need all- just a few of the shortest, lets say 3-5 routes. Each relation has a Weight and I'd need the routes with the heighest weight... (the # of nodes should come into play too, actually. meaning if I have two routesd one has a weight of 10 and 5 nodes, if may still come second to a routes with a weight of 5 with 3 nodes in it.)

    Any ideas how I can solve this problem? It has to be MySQL, and it isn't heirarchial so the above link is of no use (I've read it before, but I appreciate the post anyway ).

    Edit:: My real problem is that I cant figure out a way to prevent my recursion from going through the same node twice. Since the relations between the nodes are bi-directional it is very likely that my loops will rech nodes that they have already visited, and I can't allow that. I need each node to be visited only once.
    Last edited by GMMorris; 09-27-05 at 03:28.

Posting Permissions

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