Finding all the possible routes from database.

Question

0.00/5 (No votes)

See more:

C#

MySQL

Hello guys,

I am having a problem here.

Is there a way to do this?
Thanks

Posted 14-Mar-11 11:02am

DaveSpikes

Updated 14-Mar-11 11:29am

v3

Add a Solution

Comments

Wendelius 14-Mar-11 17:35pm

Please don't remove the original question after receiving answers. There's no point in doing that especially since the modification history can be browsed by anyone. Also the question and the answers may be useful to some others...

Manfred Rudolf Bihy 14-Mar-11 17:49pm

I have to agree with Mika in this. Changing your question like this is counter productive. Please revert to revision 2. Thank you!

4 solutions

Solution 1

You found (or were given I suspect) one of the hardest problems in CS. It is called "Traveling Salesman Problem"[^]. It is NP-hard but luckily for you one the best investigated problems since it does have many application in real live.
Googling a bit with "Traveling Salesman Problem" or "Traveling Salesman Algorithm" should yield enough results to keep you busy for the next year.

Do some research and you'll surely come up with a solution.

Modification:
Since you didn't introduce any weights (distances, cost) into the edges of the graph, the problem might indeed be easier to solve than the traditional TSP. If you (or your tutor) can accept leaving out loops in the route then termination will even be guaranteed. Something not easily achieved with edges that can carry positive as well as negative weight (distance, cost).

Best regards,

Posted 14-Mar-11 11:15am

Manfred Rudolf Bihy

Updated 14-Mar-11 11:34am

v5

Comments

Wendelius 14-Mar-11 17:26pm

You suspect it was a homework asignment?

Manfred Rudolf Bihy 14-Mar-11 17:30pm

I'm not really sure, but maybe my homework-sensors are just running amok again. :)

Wendelius 14-Mar-11 17:32pm

Oh boy, didn't even think about it... :(

Sergey Alexandrovich Kryukov 14-Mar-11 19:07pm

I would note: hardest to a computer, not for a programmer. I would rather started from solving problem from scratch, a matter of few hours.
My 5 for the answer.
--SA

Espen Harlinn 15-Mar-11 5:00am

Good reply, my 5

Solution 2

Hi,

As far as I know MySQL doesn't support recursive queries (could be old info). However, if that's the case you must 'fix' the longest route so, for example if you can have 4 airports at max your query could be something like:

SQL

SELECT *
FROM Route AS R1
LEFT JOIN Route AS R2 ON R2.From = R1.To
LEFT JOIN Route AS R3 ON R3.From = R2.To
LEFT JOIN Route AS R4 ON R4.From = R3.To
WHERE R1.From = 'Athens'
AND (   R2.To = 'New York'
    OR  R3.To = 'New York'
    OR  R4.To = 'New York')

Posted 14-Mar-11 11:17am

Wendelius

Comments

Manfred Rudolf Bihy 14-Mar-11 17:25pm

Wow! My 5 for this interesting solution design.

If OP set an upper limit and constructed the SQL statement dynamically he/she could even re-try with one to n INNER JOINS. I am even more interested how any SQL server would deal with this performance-wise though. If you're interested in this enough I suggest you write an article where you experiment with max route length and total number of route point connections in the database.

Wendelius 14-Mar-11 17:29pm

Thanks. It could be interesting to create an article about this and include also the weights into it. Have to think about it :)

Manfred Rudolf Bihy 14-Mar-11 17:33pm

Adding weights to the edges would lead away from the straight forward SQL solution you proposed. Looking into the performance issues as a function of (n,m) where n is the number of hops to the destination and m is the total number of edges in the DB might be fun though.

Wendelius 14-Mar-11 17:38pm

You're right. Actually did something similar years ago, but ran into performance issues. The situation may be totally different these days...

Espen Harlinn 15-Mar-11 5:31am

You can implement something like the A* algorithm in PL/SQL or TSQL, and it's highly likely that it would improve the overall performance of the solution - it usually helps to have the data readily at hand :)

Wendelius 15-Mar-11 14:26pm

Yes that's right :)

Solution 4

Here is a really **good looking** solution by Sasha Barber:
WPF: A* search[^]

Best regards
Espen Harlinn

Posted 14-Mar-11 22:53pm

Espen Harlinn

Comments

Sergey Alexandrovich Kryukov 15-Mar-11 16:04pm

Really? Even it this is not answering OPs question, certainly can help as the source of ideas.
Then again, using brute force is enough to solve OP's problem, it only needs simple but accurate algorithm. A couple of simple ideas will do the trick.
--SA

Espen Harlinn 15-Mar-11 16:42pm

Thought Sachas article would catch his attention, and motivate him to evaluate the algorithm, as it's usually a more efficient approach :)

Sergey Alexandrovich Kryukov 16-Mar-11 18:37pm

My 5, by the way.
--SA

Espen Harlinn 16-Mar-11 18:42pm

Thank you, SAKryukov!

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Sergey Alexandrovich Kryukov · Accepted Answer · 2011-03-14T11:24:00

The way is using the brute force, which is a relatively simple problem. The problem is NP-complete, http://en.wikipedia.org/wiki/NP-complete[^], so you'll have a big extremely rapidly growing trouble when the input data set grows.

The problem should be used operating on graphs, see http://en.wikipedia.org/wiki/Graph_(mathematics)[^], http://en.wikipedia.org/wiki/Operations_on_graphs[^].

This is a very simple and detailed overview: http://www.cs.princeton.edu/~rs/talks/PathsInGraphs07.pdf[^].

See this discussion: http://discuss.joelonsoftware.com/default.asp?design.4.310217.12[^].
This is how to find all paths of the fixed length: http://www.perlmonks.org/?node_id=522270[^], you can use this solution in cycle with different lengths starting from 1 and ending with the length for which no solution is found, so the united solution will give you the final answer.
This discussion is about finding all paths:
http://www.google.com/search?hl=en&source=hp&q=all+paths+on+graph&aq=f&aqi=&aql=&oq=[^].

After all, Google this:
http://en.lmgtfy.com/?q=find+all+paths+undirected+graph+%22C%23%22[^].

—SA

Finding all the possible routes from database.

4 solutions

Solution 1

Solution 2

Solution 3

Solution 4

Add your solution here

Preview 0

Existing Members

...or Join us