4
$\begingroup$

Edit: After John L.'s reminder, there is a specific term, namely "Hamiltonian walk" for my previous question. See How can we find a shortest closed walk passing through all vertices?. So I made the appropriate modification.

A Hamiltonian walk on a connected graph is a closed walk of minimal length which visits every vertex of a graph (and may visit vertices and edges multiple times).

Please note that there is a distinction between a Hamiltonian walk and a Hamiltonian cycle. Any graph can have a Hamiltonian walk, but not necessarily a Hamiltonian cycle. And it is definitely not the Hamiltonian path that the answer from David G. Stork.

The length of a walk is the number of edges it has, counting repeated edges as many times as they appear.

I'm not sure if such a problem has been extensively studied. For example, our graph is Coxeter graph; if we choose the start vertex $“1”$, then find the shortest distance from $“1”$ passing through all vertices and returning back to $“1”$.

g = GraphData["CoxeterGraph"];
Graph[g, VertexLabels -> "Name"]

enter image description here

It seems that the function FindShortestPath is still far from the desired goal.

Another example, we choose $v$ as the start vertex.

Graph[{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}, {Null, SparseArray[Automatic, {13, 13}, 0, {1, {{0, 4, 5, 7, 9, 12, 14, 18, 21, 22, 28, 32, 36, 38}, {{5}, {7}, {10}, {11}, {10}, {4}, {10}, {3}, {10}, {1}, {6}, {7}, {5}, {7}, {1}, {5}, {6}, {8}, {7}, {11}, {13}, {12}, {1}, {2}, {3}, {4}, {11}, {12}, {1}, {8}, {10}, {12}, {9}, {10}, {11}, {13}, {8}, {12}}}, Pattern}]}, {FormatType -> TraditionalForm}]

enter image description here

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Have you seen this? cs.stackexchange.com/questions/43731/… $\endgroup$
    – flinty
    May 12 at 9:39
  • $\begingroup$ ^ based on that, you should be able to augment your graphs into complete graphs. Connect two vertices with an edge, where the weight is the length of the shortest path between them, then solve a normal TSP problem, then translate the edges back into real shortest paths. This will be horrendously inefficient for very large graphs, but I don't think your particular graphs are that big. $\endgroup$
    – flinty
    May 12 at 9:47
  • $\begingroup$ @flinty Thank you for reminding me of this method. But I still don't understand why this method is feasible. $\endgroup$
    – licheng
    May 12 at 12:33
  • $\begingroup$ it's practical and feasible because the complete graph is not too large for these particular cases. Hamiltonian Path is NP-Complete and full TSP beyond just the decision problem is harder. I have a feeling that shortest Hamiltonian walk might be even harder than that because there are a lot more walks with repeats (technically infinitely many), so a heuristic solution might be the best you can do, practically speaking. $\endgroup$
    – flinty
    May 12 at 14:18

2 Answers 2

Reset to default
4
$\begingroup$

Update: If you don't care about returning to the starting vertex, then you can replace this line:

(* remove Method -> "AllTours" if this takes too long *)
{tourlength, tour} = FindShortestTour[cg, Method->"AllTours"];

... with this:

tour = FindHamiltonianPath[cg, DistanceFunction -> (GraphDistance[g, #, #2] &)];

This gives a path with the same length as David G. Stork's answer for the first graph. But in the second graph I get a length 14 walk.

According the discussion here it's possible to formulate this as a Travelling Salesman Problem by augmenting the sparse graph into a complete graph by adding edges. These new edges represent shortest paths between any two vertices in the original graph and have weight equal to the path length.

As the augmented graph is a complete graph, this means bad performance when the vertex count gets even a little large because the edge count goes up rapidly. Fortunately, your graphs are fairly small.

Once we've found the shortest tour in the complete graph, we can translate edge pairs back into paths in the original graph. These paths can go back through vertices and edges we've already covered, so we get the desired effect with repeat vertices.

Remove["Global`*"];
g = GraphData["CoxeterGraph"];
spf = FindShortestPath[g];
augment =
  Association[
   UndirectedEdge @@ # -> spf @@ # & /@ Subsets[VertexList@g, {2}]];
(* construct the complete graph. Don't use CompleteGraph because it renames vertices *)
cg = RelationGraph[Not@*SameQ, VertexList[g], DirectedEdges -> False];
cg = SetProperty[cg, EdgeWeight -> (Length[augment[#]]-1 & /@ EdgeList[cg])];

(* remove Method -> "AllTours" if this takes too long *)
{tourlength, tour} = FindShortestTour[cg, Method->"AllTours"];

finaltour = 
 DeleteAdjacentDuplicates@Flatten[spf @@@ Partition[tour, 2, 1]]

{1, 24, 23, 26, 12, 13, 25, 20, 21, 27, 15, 16, 17, 18, 19, 28, 11, 
10, 9, 22, 9, 8, 7, 6, 5, 4, 3, 2, 1, 14, 1}

PathGraph won't highlight the graph because of the repeat vertices, so I have no pretty pictures to show unfortunately.

Note: Shortest path edge weights may be a suboptimal heuristic in non-Metric-TSP problems where the triangle inequality doesn't hold. In that case we must also consider connecting vertex pairs with all possible paths between them, because we might reach an overall lower tour length by including a few long paths. This is of course highly impractical though as the number of paths in the complete graph is enormous.

For the second graph I get this result using this method. Notice that neither FindShortestTour nor FindHamiltonianPath work on this graph, but my method does because it allows repeats. I removed Method->"AllTours" here because it was taking a long time:

{1, 5, 6, 7, 8, 13, 12, 9, 12, 11, 10, 3, 4, 10, 2, 10, 1}
Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks. I'm not confident about this method (not your codes). I wonder if there is a rigorous proof that this transformation is indeed correct. Of course, this seems to go beyond the scope of this stack. But it's always good to be cautious. $\endgroup$
    – licheng
    May 12 at 13:23
  • $\begingroup$ @licheng it is definitely correct in that it will always generate a path through all vertices. It might not be optimal in the sense of the note in the answer - I'm not 100% sure on that. I think it would be worth trying it out on some worst-case scenario graphs, e.g ones where you need lots of repeats and see what kind of path lengths you get and if you can do better by hand. $\endgroup$
    – flinty
    May 12 at 14:07
  • $\begingroup$ @licheng it does seem to work poorly with certain simple cases, like this very basic line graph g = {1 \[UndirectedEdge] 2, 1 \[UndirectedEdge] 3, 3 \[UndirectedEdge] 4}; giving {1, 2, 1, 3, 4} which puts an unnecessary repeat of 1 in there when it could just do {1,2,3,4} $\endgroup$
    – flinty
    May 12 at 14:50
  • 1
    $\begingroup$ @licheng Apparently FindHamiltonianPath doesn't take into account weights as I expected so was giving bad results for the weighted complete graph. See discussion here . I've fixed this by adding DistanceFunction -> (GraphDistance[g, #, #2] &) and it now gives the expected {2, 1, 3, 4} for the above case. $\endgroup$
    – flinty
    May 12 at 15:17
3
$\begingroup$

Note that your question need not refer to any specific vertex $v$. See why?

And yes, Hamiltonian paths have been studied extensively.

    g = GraphData["CoxeterGraph"];
    ham = FindHamiltonianPath[g];
    HighlightGraph[g, PathGraph[ham]]

Hamiltonian Path

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Indeed, the examples I gave are quite special. The Hamiltonian path also does not meet my expectations because in my case, both vertices and edges can be repeated. The graph I'm considering is more general and may not necessarily contain a Hamiltonian path. Even if this graph does contain a Hamiltonian path, since we need to return to the starting point, the shortest close walk is still not this Hamiltonian path, and some other walk needs to be added. (Of course, if this graph is Hamiltonian, then the Hamiltonian cycle is undoubtedly one of the shortest closed walks) $\endgroup$
    – licheng
    May 12 at 1:48
  • $\begingroup$ I have only researched the Chinese Postman Problem and the Traveling Salesman Problem. They each have their own characteristics, but at first glance, they are different from my problem. The Chinese Postman Problem allows each edge to be traversed exactly once (i.e., edges cannot be repeated), while the Traveling Salesman Problem allows each vertex to be traversed exactly once (i.e., vertices cannot be repeated). My problem is more flexible. I'm not sure whether it can be reduced to these two problems. $\endgroup$
    – licheng
    May 12 at 1:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.