# Sorting a list of lines such that they are successively connected

I have a list of line segments of the form $$\{u_1,u_2,\cdots,u_n\}$$, where $$u_{k}$$ is of the form $$\{\{a_k,b_k\},\{c_k,d_k\}\}$$. I want to sort them as $$\{v_1,v_2,\cdots,v_n\}$$ in such a way that Last[$$v_{k}$$]=First[$$v_{k+1}$$].

I tried the following:

u = {{{1, 2}, {2, 3}}, {{5, 6}, {4, 5}}, {{2, 3}, {5, 6}}};
Sort[u, #1[[2]] == #2[[1]] &]
> {{{5, 6}, {4, 5}}, {{1, 2}, {2, 3}}, {{2, 3}, {5, 6}}}


But this did not work. Is there a fast way to sort such an array?

• Sort[u] would give {{{1, 2}, {2, 3}}, {{2, 3}, {5, 6}}, {{5, 6}, {4, 5}}} which, I believe, is what you want
– eldo
Commented Oct 28, 2023 at 16:59
• @eldo Not really. For instance, with Graphics[Arrow[Sort[{{{1,2},{-2,3}},{{5,6},{4,5}},{{5,6},{-2,3}}}]]] I want to see a connected and directed path. Commented Oct 28, 2023 at 20:34

hPath = Partition[FindHamiltonianPath[UndirectedEdge @@@ #], 2, 1] &;


Thanks: @azerbajdzan for the correction in comments.

Examples:

u1  = {{{1, 2}, {2, 3}}, {{5, 6}, {4, 5}}, {{2, 3}, {5, 6}}};

u2 =  {{{1, 2}, {2, 3}}, {{0, -1}, {4, 5}}, {{2, 3}, {0, -1}}};

hPath @  u1

{{{1, 2}, {2, 3}}, {{2, 3}, {5, 6}}, {{5, 6}, {4, 5}}}

hPath @ u2

{{{1, 2}, {2, 3}}, {{2, 3}, {0, -1}}, {{0, -1}, {4, 5}}}

tSort = Partition[TopologicalSort[DirectedEdge @@@ #], 2, 1] &;


Examples:

u1  = {{{1, 2}, {2, 3}}, {{5, 6}, {4, 5}}, {{2, 3}, {5, 6}}};

u2 =  {{{1, 2}, {2, 3}}, {{0, -1}, {4, 5}}, {{2, 3}, {0, -1}}};

tSort @ u1

{{{1, 2}, {2, 3}}, {{2, 3}, {5, 6}}, {{5, 6}, {4, 5}}}

tSort @ u2

{{{1, 2}, {2, 3}}, {{2, 3}, {0, -1}}, {{0, -1}, {4, 5}}}

• Thank you vry much. Why do you think I get this unexpected arrow? wolframcloud.com/obj/bkarpuz/Published/topologicalsort-error.nb Commented Oct 28, 2023 at 21:16
• @bkarpuz, @kglr: Use the version with FindHamiltonianPath and then use UndirectedEdge instead of DirectedEdge. Commented Oct 28, 2023 at 22:24

Here is what I coded. Here, $$u$$ has a list of lines. $$v$$ is the list of directed lines. To this end, the initial line segment must be specified, i.e., $$v_{1}=u_{15}$$ below.

u={{{42.225,2.74221},{40.6758,2.61411}},{{35.8258,2.42011},{34.7103,2.37161}},
{{40.0938,2.58501},{38.7358,2.51711}},{{33.6806,2.30737},{34.7103,2.37161}},
{{43.3275,2.86894},{42.225,2.74221}},{{32.4793,2.26491},{33.6806,2.30737}},
{{31.3595,2.21913},{32.4793,2.26491}},{{37.0383,2.46861},{35.8258,2.42011}},
{{43.9156,2.97301},{43.3275,2.86894}},{{30.5079,2.15657},{31.3595,2.21913}},
{{28.5811,2.01504},{29.4814,2.08117}},{{38.7358,2.51711},{37.0383,2.46861}},
{{44.4976,3.25431},{43.9156,2.97301}},{{40.6758,2.61411},{40.0938,2.58501}},
{{27.7263,1.93511},{28.5811,2.01504}},{{29.4814,2.08117},{30.5079,2.15657}}};
v=Table[Null,{k,1,Length[u]}];