Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I have this problem I think you may help me with.
P.S. I'm not sure how to call this, so if anyone finds a more appropriate title, please do edit.

Background

  • I'm making this application for searching bus transit lines.
  • Bus lines are a 3 digit number, and is unique and will never change.
  • The requirement is to be able to search for lines from stop A to stop B.
  • The user interface is already successful in hinting the user to only use valid stop names.
  • The requirement is to be able to display if a route has a direct line, and if not, display a 2-line and even 3-line combination.

Example:

I need to get from point A to point D. The program should show:

  • If there's a direct line A-D.
  • If not, display alternative, 2 line combos, such as A-C, C-D.
  • If there aren't any 2-line combos, search for 3-line combos: A-B, B-C, C-D.

Of course, the app should display bus line numbers, as well as when to switch buses.

What I have:

My database is structured as follows (simplified, actual database includes locations and times and whatnot):

+-----------+
| bus_stops |
+----+------+
| id | name |
+----+------+

+-------------------------------+
|    lines_stops_relationship   |
+-------------+---------+-------+
|  bus_line   | stop_id | order |
+-------------+---------+-------+

Where lines_stops_relationship describe a many-to-many relationship between the bus lines and the stops.

Order, signifies the order in which stops appear in a single line. Not all lines go back and forth, and order has meaning (point A with order 2 comes after point B with order 1).

The Problem

  • We find out if a line can pass through the route easily enough. Just search for a single line which passes through both points in the correct order.
  • How can I find if there's a 2/3 line combo? I was thinking to search for a line which matches the source stop, and one for the destination stop, and see if I can get a common stop between them, where the user can switch buses. How do I remember that stop?
  • 3 line combo is even trickier, I find a line for the source, and a line for the destination, and then what? Search for a line which has 2 stops I guess, but again, How do I remember the stops?

tl;dr

How do I remember results from a query to be able to use it again? I'm hoping to achieve this in a single query (for each, a query for 1-line routes, a query for 2, and a query for 3-line combos).

Note: I don't mind if someone suggests a completely different approach than what I have, I'm open to any solutions.

Will award any assistance with a cookie and an upvote. Thanks in advance!

share|improve this question
2  
en.wikipedia.org/wiki/Dijkstra%27s_algorithm –  eggyal Jun 6 '12 at 9:40
    
@eggyal: I have no distances over the nodes. Also, I'm limited in movement inside of the network (i.e. only certain bus lines move from point A to point B). Is it still useful for me? –  Madara Uchiha Jun 6 '12 at 9:44
    
I would also suggest to use a stored procedure over a single query for this - if it's even possible to do it with a single query. There you can easily store results / variables and reuse them. –  Katai Jun 6 '12 at 9:45
1  
@Truth It's probably best to give you some tuts: mysqltutorial.org/stored-procedures-loop.aspx (loops), mysqltutorial.org/… (cases) - combined with something like the dijkstra algorithm, you should be able to solve your problem. Basically, it's like a php function - but on mysql –  Katai Jun 6 '12 at 9:52
1  
Seems to already be on Stack Overflow - this link has multiple solutions though none are in MySQL at this time. (There are several answers that don't summarize easily and link rot probably isn't an issue since if that site goes away this one probably does as well. Plus it has lots of upvotes). –  psr Jun 6 '12 at 17:00
show 6 more comments

migrated from stackoverflow.com Jun 6 '12 at 10:57

This question came from our site for professional and enthusiast programmers.

2 Answers

up vote 3 down vote accepted

You may not want to make this drastic of a change at this point, but what you describe is exactly the use case for Graph Databases. Graph Databases are based on graph theory, which is what you are touching upon by trying to find a path between 'X' and 'Y' across a directed graph of bus routes.

If you haven't already looked into one, take a peek at something like Neo4J. It has a REST API and you can find PHP clients for it.

You'll find a bunch of people of Stack Overflow who could help with the implementation side of things.

share|improve this answer
1  
I'm currently at the thinking phase, I can change anything. I will check your links. Also, this question came from Stack Overflow, I know they can help me implement it :) –  Madara Uchiha Jun 6 '12 at 13:06
1  
I was going to suggest recursive queries, but it seems MySQL doesn't support those so this answer might be better. –  FrustratedWithFormsDesigner Jun 6 '12 at 13:42
    
@FrustratedWithFormsDesigner There might be a very awkward MySQL solution that would combine SP and an adjacency list, but I don't think it's even worth the time thinking about it. –  Yannis Rizos Jun 6 '12 at 15:24
    
@YannisRizos: It might be a good code golf challenge, maybe? ;) –  FrustratedWithFormsDesigner Jun 6 '12 at 15:34
1  
@FrustratedWithFormsDesigner Nah, this is a good code golf challenge –  Yannis Rizos Jun 6 '12 at 15:40
add comment

Let's say a user wants to go from $start_id to $end_id (both are valid stop_id values). You may use these queries to find a valid route from $start_id to $end_id:

  1. Search for direct route (single line):

    SELECT *
    FROM bus_stops bs1, bus_stops bs2
    WHERE bs1.stop_id=$start_id AND bs2.stop_id=$end_id AND bs1.bus_line=bs2.bus_line
    
  2. If there's no result with the previous query, then search for a route using 2 lignes:

    SELECT *
    FROM bus_stops bs1, bus_stops bs2, bus_stops bs3, bus_stops bs4
    WHERE bs1.stop_id=$start_id
        AND bs1.bus_line=bs2.bus_line
    AND bs2.stop_id=bs3.stop_id
        AND bs3.bus_line=bs4.bus_line
    AND bs4.stop_id=$end_id
    

Replace * with the fields you really need to retrieve.

share|improve this answer
    
Hello Jocelyn and welcome! Please read our editing help page thoroughly to find out how you can get the most out of Markdown. I've edited your answer this time, you can check its revision history to see what edits I made. –  Yannis Rizos Jun 6 '12 at 11:30
    
Why are you selecting from the same database 4 times in a row? –  Madara Uchiha Jun 6 '12 at 13:13
    
And what happens if you need one more bus line (bus_stops bs5) to complete the route? –  FrustratedWithFormsDesigner Jun 6 '12 at 13:39
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.