list manipulation - Computing the equivalence classes of the symmetric transitive closure of a relation
I have a list of pairs, for example:
pairs={{13, 10}, {12, 14}, {10, 36}, {35, 11}, {3, 5}, {1, 6},
{20, 24}, {21, 22}, {33, 7}, {31, 8}, {31, 27}, {32, 25},
{21, 35}, {34, 19}, {18, 15}, {14, 16}, {9, 5}, {4, 7},
{1, 13}, {15, 2}, {6, 36}, {4, 34}, {8, 2}, {9, 3}, {25, 20},
{19, 26}, {22, 11}, {23, 12}, {32, 28}, {30, 33}, {23, 16},
{24, 17}, {29, 27}, {26, 30}, {17, 28}, {18, 29}};
pairs
can be seen as the definition of a relation $R$. $x$ and $y$ satisfy the relation if and only if {x,y}
$\in$ pairs
. I need to compute the equivalence classes of the symmetric transitive closure of $R$.
In other words, I need to compute a list eqvclss
. The elements of eqvclss
are lists themselves. For example, 13, 10, 36, 6, 1, ... should all be in the same list in eqvclss
. (If you understand that, then I explained the question properly; if you don't, say so in the comments so I can try to improve).
Answer
ConnectedComponents
Using Daniel Lichtblau's answer to a related question
ConnectedComponents[pairs] //Sort /@ # & //Sort (* thanks: CarlWoll *)
{{3, 5, 9},
{11, 21, 22, 35},
{12, 14, 16, 23},
{1, 6, 10, 13, 36},
{17, 20, 24, 25, 28, 32},
{2, 8, 15, 18, 27, 29, 31},
{4, 7, 19, 26, 30, 33, 34}}
In versions prior to 10.3 use
ConnectedComponents[Graph[UndirectedEdge @@@ pairs]] //Sort /@ # & //Sort
MatrixPower
Implementing transitive closure using MatrixPower
:
m = Max@pairs;
(*the adjacency matrix of atomic elements in pairs:*)
SparseArray[pairs ~Append~ {i_, i_} -> 1, {m, m}];
(*symmetrize the adjacency matrix:*)
% + %\[Transpose] // Sign;
(*find the transitive closure:*)
Sign @ MatrixPower[N@%, m];
(*eliminate duplicate rows,and extract the atomic elements of pairs in each row:*)
Select[DeleteDuplicates @ Normal @ %, Tr@# > 1 &];
Join @@ Position[#, 1] & /@ %;
(*organize:*)
Sort[Sort /@ %]
{{3, 5, 9},
{11, 21, 22, 35},
{12, 14, 16, 23},
{1, 6, 10, 13, 36},
{17, 20, 24, 25, 28, 32},
{2, 8, 15, 18, 27, 29, 31},
{4, 7, 19, 26, 30, 33, 34}}
Comments
Post a Comment