How would I approach this problem in Mathematica?
I’m actually trying to route a string of lights, either to the vertices or to the edges.
This is nice. But in general I think you’d want "Skeleton" instead of the vertex coordinates, to enforce that only edges be used. Sere second Basic Example on the ref guide page for FindShortestTour`.
Also it is possible that the poster would really want to use FindHamiltonianPath instead.
Thank you, that’s just what I wanted. Amazing!
But now I’m wondering if there’s a way to find a path that follows every edge? Clearly some edges have to be covered twice.
… that’s just what I wanted.[…] But now I’m wondering if there’s a way to find a path that follows every edge?
Hmm - interesting problem! One simple approach might be to create points along the edges …
lineEndPts = N[First /@ PolyhedronData["TruncatedIcosahedron", "Lines"]];
linePts = DeleteDuplicates@Flatten[Subdivide[#1, #2, 10] & @@@ lineEndPts, 1];
Graphics3D[Point[linePts]]
… and then calculate the shortest tour along these points:
{length, order} = FindShortestTour[linePts];
gr = PolyhedronData["TruncatedIcosahedron", "Graphics3D"];
Graphics3D[{List @@ gr, Red, Thick, Line[1.05 linePts[[order]]]}]
If you can live with the fact that some of the edges are not covered in one go, then this might serve as a solution.
Yes, this seems to be the better idea for this case, as - if vertices are numbered accordingly - it gives a plan on how to proceed:
graph = Graph[PolyhedronData["TruncatedIcosahedron", "Skeleton"], VertexLabels -> Automatic];
(* path from vertex 9 to vertex 11 - as an example: *)
hp = FindHamiltonianPath[graph, 9, 11];
HighlightGraph[graph, PathGraph[hp], EdgeShapeFunction -> ({Thickness[.02], Line[#]} &)]
It might be sufficient just to add midpoints, provided it is done as a graph (so midpoints can only connect to their two vertex neighbors).
I’m wondering if there’s a way to find a path that follows every edge?
It looks to me that FindPostmanTour[] is what’s wanted:
Graph3D[DirectedEdge @@@ First[FindPostmanTour[PolyhedronData["TruncatedIcosahedron", "Skeleton"]]]]
@J. M. : This definitely is the ultimate solution (+1) - thanks for sharing!
Thank you all!
That looks like the right solution. Now I have to build a frame with light sockets in the middle of each edge.
I’ll be 3D printing for a while!
I have 100 LEDs on hand, individually controllable, with a Teensy computer chip to drive them.
I’m going to need to step through the Graph3D so I can keep my place as I go!