Query on tg_all_path algorithm

GSQL Queries
#1

Hi All

We have a use-case on routing cabs for which we are using tg_all_path algorithm to generate all the possible paths between multiple sources and destinations. When a smaller dataset with around 40 people is considered, the algorithm works fine generating combinations but when the data is scaled 3 fold the algorithm seems to take longer time and doesn’t return anything but is hanging. We are using the free cluster instance.

For around 30 people the algorithm generates around 5-6 lakhs combinations upto a depth of 5 but when the data is scaled to 150, the algorithm is supposed to generate upto 2 million combinations and this is when it hangs.

@Jon_Herke or anyone who could please help me on this. Is this because of the free cluster instance or anything to do with the inbuilt algorithm?

#3

@Jon_Herke @Mentat Guys Any Idea About This issue ?

#4

Basically, yes, your instance is too small to support that size of combinations.

You can try moving to a larger instance (more RAM more CPUs) or you can try using some kind of heuristic to prune your options at each hop e.g. by distance or direction of travel. That will shrink your combinations.

2 Likes
#5

Thank you @Mentat I’ll try using heuristics to limit the number of combinations.