Help: Shortest distance touching all points

[MJ]

Dear all,

I am basically a GIS student with less knowledge of graph theory. I am working on a GIS project, and I am stuck on a challenge. 

I believe the solution I am looking for is easily achievable using networkx python package. So, I am humbly requesting the group members to suggest a solution.

The requirement is to find the shortest path that touches all the points in a 2-D platform. The starting and ending can be any point, but the route should touch all the inputs points, and the path should be of the least length.

Let me jump straight into the code blocks I have prepared for this purpose, hoping this could help understand the situation clearly.

## creating random 50 points.

import random

from shapely.geometry import Point

minx, miny, maxx, maxy = 100, 500, 200, 600

ptList = []

ptList2 = []

for _ in range(50):

    pnt = Point(random.uniform(minx, maxx), random.uniform(miny, maxy)) # A GIS object.

    ptList.append(pnt)

    pt_xy = pnt.x, pnt.y

    ptList2.append(pt_xy)

## Creating a distance matrix

import math

def compute_euclidean_distance_matrix(locations):

    distances = {}

    for from_counter, from_node in enumerate(locations):

        distances[from_counter] = {}

        for to_counter, to_node in enumerate(locations):

            if from_counter == to_counter:

                distances[from_counter][to_counter] = 0

            else:

                # Euclidean distance

                distances[from_counter][to_counter] = (int(

                    math.hypot((from_node[0] - to_node[0]),

                               (from_node[1] - to_node[1]))))

    return distances

distance_matrix = compute_euclidean_distance_matrix(ptList2)

## Creating a graph variable

from networkx import *

g = Graph()

for i in range(len(distance_matrix)):

    source = i

    curr_pt_dist = distance_matrix[i]

    for j in range(len(curr_pt_dist)):

        dest = j

        eucl = curr_pt_dist[j]

        g.add_edge(source, dest, weight = eucl)

Note: The weight assigned is the distance between the source and destination point.

-> Here onwards, I have tried various functions provided in the networkx library. However, I couldn't derive a solution.

A sample image that shows the required result is shown for reference. Any lead is well appreciated.

Thanking you

Riyas MJ

Ph.D. Scholar

Dept. of Applied Geology,

Indian Institute of Technology, Dhanbad

India

[Dan Schult]

You should look at the literature for the traveling salesman problem.
In NetworkX see the functions related to that.

It is in general a difficult problem but I think those are the tools we provide for what you are doing.

[Riyas M. J]

Dear Dan Schult,

Thanks for the response. My requirement is different from the traveling salesman problem (TSP). In TSP, the salesman will come back to the origin, which is not efficient if the requirement is only to touch all the points. I have tried TSP already, and I am attaching a snapshot of the result. If you look closer, the route starts from the left side, and it goes to the right side, touching all the points at the bottom. Then the route turns back and moves towards the origin, touching all the points on top. The top points are actually near the bottom ones, and it would have touched while going to the right side itself. But TSP was designed to make a return to the origin. 

Thank you

Riyas M.J.

[Peter Stahlecker]

Just convert it to a Hamiltonian (or TSP) path by removing the longest edge.

networkx has such a function to find the (approximately) shortest path.

Peter

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/1d80e5cd-a172-49e5-be92-73ee8af1486bn%40googlegroups.com.

--

Best regards,

Peter Stahlecker

[Dan Schult]

The TSP solver in NetworkX 2.6.3 actually has a keyword argument `cycle=True` which you can set to `False`.

[Riyas M. J]

Thank you so much for the suggestions, I value them a lot.

Now I understand that what I am looking for is the shortest Hamiltonian path, thanks to Peter. With that clue, I found the cycle=False option suggested by Dan Schult. Now I am able to derive a solution. However, what I am getting is not an efficient route. I found problems in many nodes.

I am attaching two snapshots with black circles representing the faulty routes. I am also attaching the code so that the problem can be reproduced in a few clicks. 

Please note that the code has additional functionalities such as min/max distance between the random points.

But in essence, it performs the same task in finding the route. I am unable to understand why do these issues are happening. Kindly have a look. 

Thank you all.

Riyas

[Peter Stahlecker]

Dear Riyas,

Frankly, I do not see from the pictures you included, that the paths are wrong.

From what I could gather from the pictures, your scales on the i-axis / y_axis seem different. (I mean: one centimeter in the picture on x / y axis represent different lengths in your model).

If I am right, this may make a visual judgement more difficult.

Or did you find shorter paths by some brute method, like calculating all possible paths?

Peter

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discu...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/c95fee89-97e7-44ff-b2a1-54ee82416eaan%40googlegroups.com.

[David Orme]

Dear Riyas,

One thing that occurs to me from tackling a similar problem in a GIS setting is that you might be expecting ’neighbour-to-neighbour’ connections. With your current graph, I think you have all points connected, and the algorithm can find long-distance shortcuts and crossings that give a shorter path. If that is the correct definition of the graph you want to use, then I think Peter is right that you have the correct solutions.

If not, then you may need to define the graph diffently? Perhaps by using a Voronoi diagram to define nearest neighbours and hence reduce the graph edges to adjacent neighbours? That is only one possible definition though! An analogy for the TSP in its classic geographic setting is that there is a defined set of roads - not roads between _all_ cities.

Cheers,

David

To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/CABKqA0aHOpghpBfQUwnK%2B89ZDbewz6kr%3D_2LQ-4ye0p-%3D9ZqXw%40mail.gmail.com.

[Peter Stahlecker]

Dear all,

I have no idea what a GIS setting means, so my comment may be totally wrong.

As I understood Riyas, he puts nodes in a plane and the edge weights are the Euklidian distance of the points. This means his graph is complete, as all points have distances from each other, so a Hamiltonian path does exist. Hence the chances are large (but not 100%) that the function finds the shortest one.

(I think to find the shortest one by brute force may impossible, as for even 25 nodes about  25! = 1.5… x 10**25 paths would have to be calculated)

Peter 

To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/9F347FAD-77BA-41A8-9833-9EB026D5209A%40gmail.com.

[David Orme]

Dear Peter,

What I mean is that the disconnect between Riyas expectation and what networkx gives could be that the complete graph is not the correct model for their problem. If you have in mind something like a classic TSP with an incomplete graph representing a road network, then you may have to go _through_ certain nodes to get to more distant nodes. 

Cheers,

David

To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/CABKqA0a2UWBSxfrbKeCLXgB6d6wqs%3DghiG5cDk56tG9PHhUfgA%40mail.gmail.com.

[Peter Stahlecker]

Dear David,

Now I understand, thanks!

As I understood the networkx function Riyas is using, it can also handle this situation - but I never actually tried it.

Only Riyas‘ question got me to play around with Hamiltonian paths.

Take care, Peter

To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/91A0D191-8A46-4565-A624-9BED649AEE4A%40gmail.com.

[Riyas M. J]

Hello all,

Thanks for the discussion.

As Peter mentioned, the X & Y are different from the initial sample code I provided. The plot is from the real data of my project. However, if you run the python code I shared, it will result in the same plot I shared. In both cases, the circumstances are exactly the same as several points in a 2-D plane. Also, pls ignore the blue extent, that's my area of interest. Since this won't make any change in the result, pls ignore the platform difference.

To clarify that the route I derived was wrong, I edited a subset of the image I shared before (nx2.png) and drew the correct route which is significantly less in travel length. Pls find the attachment.  

As David mentioned, Delaunay triangulation is a possibility. But there is a very high chance that several points will be missed in the route. An example diagram is attached.
I don't mind cross-over and long-distance shortcuts but it is a problem if the route is not effective (pls find the attachment distance.png). Also, in the case of brute force, it is not a solution if the number of points is large.  

I really appreciate the suggestions. Thanks again.

Riyas

[Peter Stahlecker]

Dear Riyas,

How do you know your route is better than the one suggested by the program?

Did you calculate both routes?

As I understand, programs to find shortest Hamiltonian paths will find it with high probability, but not assuredly so as the problem in NP hard.

Take care, Peter

To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/365516b2-b10f-41ce-939a-3cb929570028n%40googlegroups.com.

[Dan Schult]

It is probably important to note that TSP is a really hard problem. There are no algorithms that will 

1) scale to large networks

2) be guaranteed to get the best solution

The "best" algorithms ensure that you get to every point, but only ensure that you are within

(1+eps) of the best solution length. (I think eps is about 0.5 for the algorithms in NX. It's in the docs.) 

[David Menéndez Hurtado]

Hi, Riyas. 

Your graphs seem rather small, so I think you can squeeze some performance using genetic algorithms. Try increasingly more permutations until you run out of time.

The examples you shown should be easy to fix that way. 

To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/365516b2-b10f-41ce-939a-3cb929570028n%40googlegroups.com.

[Nicolas Cadieux]

Le 14 janv. 2022 à 06:52, Peter Stahlecker <peter.st...@gmail.com> a écrit :



Dear all,

I have no idea what a GIS setting means, so my comment may be totally wrong.

Lol most people out there are like us.  We understand what « GIS settings means… »but adventure in network math with little knowledge of networks!

GIS stands for Geographic Informations Systems  and is basically a group of software that combines, the equivalent of photoshop, Excel, AutoCAD with one of your favourite statistical package… all under on roof. Think of Google Earth on steroids. Then you can use these tools for terrain mapping, 3D modelling, drawing, image manipulation and analysis, data management, statistical modelling… When talking  “networks” in a “GIS setting”, we mean road, River, water, pipe networks that normally follow other rules like trafic laws (one ways, no left turns…) , gravity (water flow direction…) and things like that in addition to some basic topology rules like self touching edges, or concept like objects (line, points, polygons…) being crossed (highway overpass…), touched, by other object or being within or contained by other objects…  (island in a lake….) 

Just my grain of salt!

Nicolas

To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/CABKqA0a2UWBSxfrbKeCLXgB6d6wqs%3DghiG5cDk56tG9PHhUfgA%40mail.gmail.com.

[Peter Stahlecker]

Dear Nicolas,

Thanks a lot for the explanation! Now I can at least imagine what it is!

I frankly had never heard of GIS - despite my 66 years of age!  :-))

Take care!

Peter

To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/376980BC-42A1-4977-94AA-764EB8392416%40gmail.com.

[Nicolas Cadieux]

Going on 52 and still understand only about 5% of what you people are doing! :) 

Ignorance is bliss… I guess! :)

Cheers!

Nicolas Cadieux

https://gitlab.com/njacadieux

Le 14 janv. 2022 à 10:04, Peter Stahlecker <peter.st...@gmail.com> a écrit :



To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/CABKqA0YqwtM44DC920AtYoD%3DpcKGqBG--7iVGuSf7J1zQuZGEg%40mail.gmail.com.

[Riyas M. J]

Dear all, 

I am sorry that I would have already done Nicolas did, thanks a lot Nicolas. 

The way I can describe GIS for this group is that, for a GIS person, X and Y axis of graphs will be the longitude and latitude of the Earth. I hope this makes sense when it comes to finding the shortest path in the graph :)

Responding to Peter, I have calculated the distance differences. To prove it, I have calculated the total distance for of route derived by networkx and the same after making a minor modification in the route. The distance difference in the modified route is found to be less. (result is attached)

Note: Pls ignore the distance unit, bcs as I mentioned, it is the actual distance on Earth to travel through those locations in meters. Just wanted to prove that the altered path is better than the derived product. 

In terms of increasing permutation, I tried but it didn't help. 

I accept Dan Schult. This problem is complicated especially when the nodes are more. Brute force is the best option, in which all the possible routes will be measured and identify the best route. But it isn't practical for a large number of points. 

I strongly believe that there will be smarter approaches. In fact, the derived products are near to perfection. It will be perfect and pretty well useful for many applications if this glitch can be identified and resolved. 

Thanks all

[Peter Stahlecker]

:-))     :-))

To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/C21AAFCC-22DF-42CE-A826-9FDFCA2C25A6%40gmail.com.

[Peter Stahlecker]

Dear Riyas,

I guess, if you find a solution to the TSP in polynomial time you may be awarded the Fields medal.  :-))

Take care, Peter

To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/13212d57-0a3c-4803-962c-d78c00823b13n%40googlegroups.com.

[Riyas M. J]

Dear Peter,

That's funny because I don't even know the basics of graph theory :-P 

However, I am sure there are better solutions than this. May not be direct, but with some bypassing, I strongly believe something better can be derived. I am really glad that all of you made sincere efforts to tackle this challenge. I am still on the hunt and I will share if I could come up with any better solution. It is been really a pleasure to have this discussion with all of you. Thanks a lot.

I am still open for suggestions though!

Best regards

Riyas

[Harris Teague]

In my understanding, state-of-the-art solutions to TSP and related problems are here https://www.math.uwaterloo.ca/tsp/concorde.html

It says they allow slight modifications of the problem, and it seems to me that removing the "return to start" part would be in that class, but I haven't tried it.

[Harris Teague]

I also found this:

https://stackoverflow.com/questions/6733999/what-is-the-problem-name-for-traveling-salesman-problemtsp-without-considering/7158721#7158721