Specify source node in TPS (cycle=False)

[Riyas M. J]

Hello all,

I am looking for a solution to specify the initial node in TSP route derived by the function 'networkx.algorithms.approximation.traveling_salesman.traveling_salesman_problem'. Pls note that I am sticking with this function because I can assign 'cycle=False' so that the solution won't be prepared in a way the route will come back to the origin point.

I can see the option to specify the source node in the function 'networkx.algorithms.approximation.traveling_salesman.greedy_tsp'. Similarly, is there any way I can forcefully define the initial node of the routing in TSP (that doesn't cycle back)?

Thank you!

[Dan Schult]

The `cycle=False` option simply finds the best cycle and then removes the longest edge from that cycle.

To specify the starting point, proceed similarly. Find the best cycle, then remove the longer of the two

edges attached to your starting point. 

Note that this might make the resulting solution slightly less optimal in that it doesn't explore 

other "tours" that have the ability to remove a longer edge in this last step.  But all the methods 

are heuristic and thus don't pretend to give the exact optimal solution. So this will not affect the

length of your results much.

[David Menéndez Hurtado]

Another option is to remove the starting node, compute the cycle, and find the closest point to attach to it, considering that you can also remove the longest link on that second node.

/David 

--
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/CA%2BXMcTN%2BLJXe3FC0sDNQhgedzKRjQGsi5%2BP0Qq_BuzLYZHQtfg%40mail.gmail.com.

[Peter Stahlecker]

Really simple !!

Even I did not ask the question: thanks a lot!

[Riyas M. J]

Hello Dan,

It didn't work out for me. The process I followed in detail.

> Prepared nx.Graph()

> Computed the TSP 

> Identified the point I wanted as the first point in the route (initial point)

> Identified the points that are connected to the initial point.

> Checked the distance from the initial point to both the points that are connected to it in TSP path derived.

> Among the connected two points, identified the farthest one from the initial point.

> Prepared nx.Graph again without the farthest point

> Computed TSP again.

I didn't get the initial point I chose in the second path I derived. I am not very strong in Graph theory. So there is a chance I did something really blunder. Pls clarify the issue.

Thank you

[Peter Stahlecker]

Dear Ryas,

As I understood Dan, and what I understand from graph theory ( I am no expert, but I did study it a bit) it is like this:

- you find your Hamiltonian cycle.

- you select your starting point, which should be connected to exactly two nodes in your cycle.

- you remove the 'longer' one of the two edges

==> you have your path with your starting point.

NB: 

As I understand it, the TSP is NP complete, so exact solutions become unfeasible for larger graphs.

I believe, the routine in networkx guaranties that the Hamiltonian cycle it produces is at most 1.5 times as long as the optimal cycle

--
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/c26c6b44-860c-4d24-bd23-013af25903d9n%40googlegroups.com.

[Dan Schult]

Well said Peter!

Thanks!

[Peter Stahlecker]

Thanks for the compliment! I am no expert so good to hear that I understood the matter.

On Fri 11. Feb 2022 at 13:21, Dan Schult <dsc...@colgate.edu> wrote:

Well said Peter!

Thanks!

--
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/CA%2BXMcTOUFRNn5-QPH%3DTZVp1%2Bf%2B9Av3AeCSRWaa7bJtz5Hpc0rA%40mail.gmail.com.

--

Best regards,

Peter Stahlecker

[Riyas M. J]

Hi Dan and Peter,

I am new to graph theory and I am using it for a completely different application. So pls consider me as a newbie.

Comparing what Peter has mentioned and what I did, the only difference I can understand is I calculated TSP instead of the hamiltonian cycle. Apart from that, I hope I did the same as Peter and Dan suggested.  

Also, I believe TSP with 'cycle=True' is the hamiltonian cycle. 

Am I missing something?

Best regards

[Peter Stahlecker]

Dear Ryan,

As I understand it, a solution to the TSP and a Hamiltonian cycle are exactly the same thing: Find a shortest cycle, which visits every node exactly once, traverses every edge at most once and returns to the start (hence a cycle). However, I did not check the formal definitions in Wikipedia. Maybe the TSP allows that edges be traversed more than once?

Take care, Peter

To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/733af2ce-8fe5-48d6-9f3b-0b5a0aee7f59n%40googlegroups.com.

[Peter Stahlecker]

Dear Ryan,

Did you use the networkx routine attached below?

It seems to explain very well what is does:

As I understand it:

A Hamiltonian cycle has to visit ALL nodes in the graph.

In the TSP, the nodes to be visited may be specified, need not be all nodes of your graph.

To make the cycle into a path, it simply removes the longest edge in the cycle.

In your case, as you want to specify the starting point, you remove the longer of the two edges of your starting point. This may make your solution a bit worse, as Dan pointed out.

NB: I am semi retired, so I have time to look at these things, don‘t worry!

Peter

[Matt Schwennesen]

Helllo!

Using networkx.algorithms.approximation.traveling_salesman.traveling_salesman_problem as mentioned in Peter's last email is probably the best method you could use, however the method that was outlined here is not quite correct with regard to the pre and post processing that this function performs.

> Prepared nx.Graph()

> Computed the TSP 

> Identified the point I wanted as the first point in the route (initial point)

> Identified the points that are connected to the initial point.

> Checked the distance from the initial point to both the points that are connected to it in TSP path derived.

> Among the connected two points, identified the farthest one from the initial point.

Up until this point, everything makes sense, however there are a few issues this the last part involving re-computing the TSP tour. The traveling salesman problem is only defined on complete graphs, which has all possible edges between every pair of vertices. If your graph is missing edges, the traveling_salesman_problem function will create that edge using the shortest path between the two vertices as the weight for the new edge, so even if you remove the problem edge from the original TSP solution, once the function is called a second time an edge with possibly different weight will be inserted into the graph we use in the background to actually solve the traveling salesman problem. Additionally, removing the vertex at the other end of the edge you wish to remove will actually solve a different instance of the traveling salesman problem and the result will most likely but be able to be used within the context of the original graph. 

Instead of modifying the graph itself to use the desired starting point, you should modify the list returned from the function. If cycle=true, the same node will be the first and last element in the returned list and the two edges connected to that node will be the slices containing the first two and last two elements of the tour. What you want to do is change the list so that your desired starting node is at the beginning of the list. Something like using the deque object in the python collections should be able to rotate the list around and pull off the nodes of the tour. I first idea here is to enqueue everything except the duplicate last element of the list and rotate the queue so that the desired starting node is the head of the queue and the other end of the edge to be removed is the tail of the queue (note that the queue may need to be reversed depending on which direction the solution returned by the traveling_salesman_problem travels the cycle it finds), then dequeue everything to get the path you need.  

As Dan mentioned, this function will find the optimal cycle even if cycle is set to false but the solution will be within 3 / 2 of the optimal solution if using the Christofides algorithm. Using the tsp greedy function mentioned in the original post is not guaranteed to be within these bounds since eventually it only has one choice of which is the nearest unvisited vertex and the cost of that edge could be very bad. Overall, I suspect that the best approach is to work using cycle=true and transform the output cycle to have the desired start. 

I hope that this helps,

Matt

[Peter Stahlecker]

Dear Matt,

Thanks a lot for your detailed explanation of the inner working of that function in networkx!

If I understood you correctly, it is like this:

- I start with a (incomplete) graph G

- I find the TSP cycle. This gives me the TSP path by ‚mentally‘ removing the longest edge incident with my starting node, let‘s call it e.

- if I remove this edge from G, I get a different graph GG := G \ {e}.

- if I apply the TSP function of networks on GG, I likely get another TSP cycle, as GG is a graph different from G.

Is my understanding correct?

Thanks a lot!

Peter 

To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/3d1c7092-e3a1-4a15-8686-f30aaf8a5746n%40googlegroups.com.

[Matt Schwennesen]

Hello Peter,

Essentially yes. Since GG is not G, the TSP cycle will almost certainly be different since the function completes the graph using the shortest paths between all pairs of non-adjacent vertices and the result of this process is that the weight of edge e has been changed but is still present in the graph for which the TSP tour is computed. Because the cycle returned by the function will likely be different, there is no intuitive way to map from the tour on GG back to a tour on G with the desired starting node which is why I think that transforming the returned list from the TSP function is probably the best way to set the starting node.

[Peter Stahlecker]

Dear Matt,

Thanks, I think, I am clear now!

Just for curiosity: 

I programmed a complete graph, where the nodes are uniformly distributed points in the [0, 1] x [0, 1] plane, with the weights of the edges being their length. 

I applied the TSP function to this graph, and drew pictures. One can see from the pictures, that the TSP function could have done ‚better‘ in some places - as one would expect as the TSP function looks for a ‚good‘ approximation. The ‚errors‘ did not appear to be serious. Just a visualization, how well TSP works: ‚Optically‘ the errors were much smaller than the „1.5 bound!“ given in the netwrokx notes.

Take care, Peter

To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/eced696f-ae85-4d58-9025-de249db438a5n%40googlegroups.com.