topic Re: Finding the shortest route between two paths in QlikView

Finding the shortest route between two paths

Anonymous — Mon, 06 Jun 2016 10:26:17 GMT

Hi Guys,

I have a table that is having the train information like train no , train name, source station name, destination station name, distance

the table looks like this:

Train No Train Name Source Station Name Destination Name Distance

--------------------------------------------------------------------------------------------------------------

1 ABC A B 10

2 CDE B E 30

3 EFG E D 40

4 HIJ E F 20

5 KLM B D 10

what I need is if I select Source Station : A and Destination : D then it should give the me list of all the train numbers, I need to connect to reach to the destination using shortest distance .

For example: from A To D : A->B->D = 20 then the train no will be 1,5

2: A->B->E->D= 80 then the train numbers will be 1,2,3

This is what I need , it would be great if anyone can help me finding the solution

Thanks,

Vivek

Re: Finding the shortest route between two paths

Clever_Anjos — Mon, 06 Jun 2016 11:40:08 GMT

Since this calculation involves a recursive calc I don´t think this can be done using regular QlikView expressions. Maybe using a macro (not sure about this)

Dijkstra's algorithm - Wikipedia, the free encyclopedia

Re: Finding the shortest route between two paths

swuehl — Mon, 06 Jun 2016 13:13:13 GMT

Maybe you can create a solution using a script that creates hierarchy tables.

Re: Finding the shortest route between two paths

Anonymous — Mon, 06 Jun 2016 18:20:48 GMT

Hi Swuehl,

Can you give me the expressions that you have used , so that i will try

Thank you,

Vivek

Re: Finding the shortest route between two paths

swuehl — Mon, 06 Jun 2016 19:42:31 GMT

Attached is the script code.

I then created the two list boxes for SourceSelect and DestinationSelect and a straight table:

=Aggr(If(Left(Path,1) = SourceSelect and Right(Path,1) = DestinationSelect, Path),Path)	*sum({<AncestorName = {""}>}Distance)**	Concat(AncestorName,',')
A/B/D	20	1,5
A/B/E/D	80	1,2,3

That's just an outline of a possible solution (not even sure if this will work for more complex scenarios).

Re: Finding the shortest route between two paths

Anonymous — Tue, 07 Jun 2016 08:51:59 GMT

Hi Swuehl,

In the script u have loaded concatenated the following

CONCATENATE

LOAD Null() as [Source Station Name],[Source Station Name] as [Destination Name]

RESIDENT Trains;

Why do we need to do that, if not what will happen can you explain me

Thanks,

Vivek

Re: Finding the shortest route between two paths

swuehl — Tue, 07 Jun 2016 09:23:02 GMT

In a hierarchy LOAD, the root nodes should be loaded with parent node being NULL.

Not sure if we need this here, if you want to know what happens if you remove this part, just try it.

edit: I think if you remove the concatenated records, the HIERARCHY LOAD prefix will not work correctly.

From the HELP:

All nodes with a parent id not found in the node id column (including nodes with missing parent id) will be considered as roots. Also, only nodes with a connection to a root node - direct or indirect - will be loaded, thus avoiding circular references.

Re: Finding the shortest route between two paths

Anonymous — Tue, 07 Jun 2016 10:41:24 GMT

Hi Swuehl,

If a person want to go from B to A , if he selects B in source and A in destination is it possible and if I have a record which shows the information of the train that travels from B to A. In that case what should I do

Thanks

Vivek

Re: Finding the shortest route between two paths

swuehl — Tue, 07 Jun 2016 12:02:52 GMT

It should be possible if your source data actually contains possible routes for that combination of Source and Destination. Currently, in your sample records, it doesn't, right?

Re: Finding the shortest route between two paths

Anonymous — Tue, 07 Jun 2016 12:53:12 GMT

Hi Swuehl,

I tried it by inserting a record but it does not works, should I need to change any thing else.

Please let me know

Thank You,

Vivek

Re: Finding the shortest route between two paths

swuehl — Tue, 07 Jun 2016 16:05:52 GMT

The HIERARCHY LOAD prefix might be limited to routes without possible loops, which I think is hard to ensure.

I've tried to create a similar approach without using the HIERARCHY LOAD prefix, but using a loop that iteratively joins all source stations to the previous destination stations.

=Aggr(If(Left(Path,1) = SourceSelect and Right(Path,1) = DestinationSelect, Path),Path)	TotalDistance	Path
A/B/D	20	A/B/D
A/B/E/D	80	A/B/E/D

edit:

Also attaching a slightly modified version where the selection of source and destination station is linked to the path.

Re: Finding the shortest route between two paths

Anonymous — Wed, 08 Jun 2016 09:05:54 GMT

Hi Swuehl,

When I am connecting it with my data it is taking too much of time and get stuck in the middle, I don't have any clue can you help me out

Thank You,

Vivek

Re: Finding the shortest route between two paths

swuehl — Wed, 08 Jun 2016 09:33:19 GMT

How many stations / connections do you have in your data?

Can you estimate the max number of stations on any given route?

Re: Finding the shortest route between two paths

Anonymous — Wed, 08 Jun 2016 09:49:34 GMT

Hi Swuehl,

I am having total 69K records out of which I am just loading 296 records , still it is loading

What should I do now?, No I can't estimate maximum number of stations for any given route.

Thank you,

Vivek

Re: Finding the shortest route between two paths

Anonymous — Wed, 08 Jun 2016 09:57:07 GMT

Hi Swuehl,

I am having 356 source and 356 destinations , in that case they are connected in the one or the other way I feel

what should I do now?

Thanks,

Vivek

Re: Finding the shortest route between two paths

Anonymous — Thu, 09 Jun 2016 08:49:25 GMT

Hi Swuehl,

I have attached an image in this if I select B as source and E as destination then it give me two train nos :1,2 but ideally it should be 2 I feel , then how can I remove it?.

Sorry for troubling you.

Thanks,

Vivek

Re: Finding the shortest route between two paths

swuehl — Thu, 09 Jun 2016 08:58:37 GMT

Start with limiting the number of hops to evaluate:

Instead of

For i = 1 to FieldValueCount('Destination Name')-1

use a low upper limit, like

For i = 1 to 2

then investigate in the SourceSelect and DestinationSelect, if all possible combinations are possible.

This might not find the optimal path, though.

If you get a feeling for the number of possible routes created, slowly increase the upper limit of the for loop.

It will depend on the properties of your network how much iterations you will need to find all connections and a at least near-optimal route.

Note that this approach is a brute force one, if you need to handle thousands of stations with a lot of possible destinations, this brute force approach will not work (well).

There are specialized tools for route optimization and you might want to have a look into some other external tools as well.

Re: Finding the shortest route between two paths

swuehl — Thu, 09 Jun 2016 12:10:18 GMT

It doesn't look like you are using my latest version?

I don't support version 0.9 anymore

Re: Finding the shortest route between two paths

Anonymous — Thu, 09 Jun 2016 13:33:58 GMT

Hi Swuehl,

I am Using Version 11 , Is it because of that ??

Thank you,

Vivek

Re: Finding the shortest route between two paths

swuehl — Thu, 09 Jun 2016 13:41:19 GMT

No, sorry, I am referring to my latest uploaded QVW sample file.

This should not show the two train numbers when you are expecting only one.

The field is called TrainSeq