Simple algorithm to find cycles in edge list

Question

I have the edge list of an undirected graph which consists of disjoint "cycles" only. Example:

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

Each vertex has exactly two edges connecting to it. Each cycle has at least three vertices. The vertices are denoted by integers $1..n$. The edge list is given in some random order. The edges appear in random orientations (i.e. {1,2} might be given as {2,1})

I need to break the graph into cycles and sort the vertices in the order they're connected. For example, if the input is:

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

then I want the output

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

The first sublist corresponds to the tetragon, the second one corresponds to the triangle. The vertices must appear in the order they're connected.

Performance requirements: the maximum vertex count is a few thousand---it should run near-instantaneously for an input of this size. An $n \log n$ solution is possible. However, I'm more interested in a concise and elegant solution than a performant one using e.g. Compile.

Note: while it was easiest to state the problem in terms of graphs, it's not really a graph theoretical problem, so don't feel compelled to use Graph unless it's really advantageous.

---

Clarification: This question is not (only) about finding connected components. It is about ordering vertices along the cycles. Actually my practical problem is that I have the edges of a polygon in random order and orientation, and I need to sort them so I can use them in Polygon and related primitives.

A sample dataset can be downloaded using Import["http://w504215.open.ge.tt/1/files/3XgvcEF/0/blob?download", "WDX"].

Answer 1

Edited to account for @Szabolcs comment

A index-disordered edge list (a bit different from yours):

el = {{3, 2}, {1, 3}, {2, 5}, {5, 8}, {4, 7}, {7, 6}, {6, 4}, {8, 1}}

Let's visualize with labels

gr = Graph[el, VertexLabels -> "Name", PlotRangePadding -> .2]

This will pick up the cycles but reorder them (as @Szabolcs reflects in the comment)

In[1]:= ConnectedComponents[gr]

Out[1]= {{1, 2, 3, 5, 8}, {4, 6, 7}}

We see this ordering is wrong because there is no edge between vertices 1 and 2. This more elaborate line will work:

In[2]:= Map[First, (FindHamiltonianCycle /@ (Subgraph[gr, #] & /@ 
         ConnectedComponents[gr])), {3}]

Out[2]= {{{1, 3, 2, 5, 8}}, {{4, 6, 7}}}

FindEulerianCycle would work too.

I wonder how it scales if you check this on your ~1000 vertex case.

Answer 2

Perhaps ExtractCycles (in the Combinatorica package) does what you require?

Needs["Combinatorica`"]
ExtractCycles@FromUnorderedPairs@el

gives

(* {{7, 4, 6, 7}, {8, 1, 3, 2, 5, 8}} *)

Your sample dataset produces 4 cycles:

ExtractCycles@FromUnorderedPairs@data

the first of which is the following:

(* {522, 518, 521, 527, 532, 535, 541, 550, 558, 563, 567, 578, 589, 593, 603, 608, 611, 615, 627, 638, 649, 659, 668, 674, 681, 689, 700, 712, 715, 720, 725, 734, 743, 750, 755, 771, 786, 793, 801, 812, 823, 829, 834, 837, 850, 861, 869, 877, 881, 890, 899, 906, 917, 929, 932, 935, 941, 949, 955, 966, 977, 981, 985, 995, 1005, 1009, 1013, 1018, 1021, 1025, 1029, 1032, 1030, 1026, 1022, 1016, 1014, 1010, 1006, 1002, 986, 982, 978, 974, 956, 952, 942, 937, 934, 930, 926, 903, 900, 896, 882, 878, 874, 862, 858, 839, 835, 832, 824, 820, 802, 798, 785, 782, 758, 744, 740, 726, 716, 711, 708, 690, 686, 671, 669, 666, 650, 640, 636, 616, 612, 607, 604, 594, 590, 586, 568, 564, 560, 542, 538, 536, 530, 528, 524, 522} *)