Re: Computing sets of equivalences
- To: mathgroup at smc.vnet.net
- Subject: [mg46459] Re: Computing sets of equivalences
- From: "Carl K. Woll" <carl at woll2woll.com>
- Date: Thu, 19 Feb 2004 03:02:14 -0500 (EST)
- References: <s033a657.090@gw-poa1.usm.maine.edu>
- Sender: owner-wri-mathgroup at wolfram.com
Mariusz,
Repeated pairs certainly need to be removed, but I believe sorting is
unnecessary.
Good point on realizing that generating the equivalence classes as you go
through the pairs is not necessary, since my set function and your lab data
structure already contain that information.
However, in order to create the equivalence classes from your lab data
structure you need to Sort and Split. These are quick functions, but things
would go more quickly if you didn't need to do them, and if you create your
equivalences on the go (as I did) you won't need to use Sort or Split. My
method of augmenting equivalence classes was quite slow, and it would be
better to use the classic approach of augmenting sets by using {new, old},
so that the equivalence set looks like:
{_,{_,{_,{_,...}}}}
and then Flatten this data structure. If this is confusing, review the notes
to Append, or do a search on why using Append to create a large set is so
slow.
At any rate, here is a revised version of my previous attempt.
addequiv[{a_, b_}] :=
If[ ! ValueQ[set[a]],
If[ ! ValueQ[set[b]], set[a] = set[b] = p[index++];
equivset[set[a]] = {a, b};, set[a] = set[b];
equivset[set[a]] = {a, equivset[set[a]]};],
If[ ! ValueQ[set[b]], set[b] = set[a];
equivset[set[a]] = {b, equivset[set[a]]};,
equivset[set[a]] = {equivset[set[a]], equivset[set[b]]};
equivset[set[b]] =. ; set[b] = set[a];]]
getequivs[eq_] := Block[{index = 1, set, equivset, p}, addequiv /@ eq;
Flatten /@ DownValues[equivset][[All, 2]]]
I created a test set of equivalences as follows:
badperm = DeleteCases[ToCycles[RandomPermutation[2000]], {_}];
perm = badperm /. Thread[Union[Flatten[badperm]] ->
Range[Length[Flatten[badperm]]]];
equivs = Flatten[(Partition[#1, 2, 1] & ) /@ perm, 1];
My getequivs is faster on my machine, and appears to scale linearly with
test size, while your connComponents appears to scale quadratically.
Interesting problem!
Carl Woll
----- Original Message -----
From: "Mariusz Jankowski" <mjankowski at usm.maine.edu>
To: mathgroup at smc.vnet.net
Subject: [mg46459] Re: Computing sets of equivalences
> Carl, this is beautiful, a ten-fold improvement in speed!
>
> I have never used indexed variables (downvalues) in my programming so
> this was a great eye opener. I went back to my copy of D. Wagner's book
> and reviewed the topic a bit more. Great thanks.
>
> However, your solution gave me an idea for a "more traditional"
> approach to solving the problem:
>
> labelVertex[{a_,b_}]:=
> If[lab[[a, 2]] == 0,
> If[lab[[b, 2]] == 0, lab[[a, 2]] = lab[[b, 2]] = index++, lab[[a,
> 2]] = lab[[b, 2]] ],
> If[lab[[b, 2]] == 0, lab[[b, 2]] = lab[[a, 2]], If[lab[[a,2]] !=
> lab[[b, 2]], lab[[b, 2]] = lab[[a,2]]]]];
>
> connComponents[eq_] := Block[{lab = Thread[{Union[Flatten[eq]], 0}],
> index=1},
> labelVertex/@eq;
> #[[All,2]]& /@ Split[Sort[Reverse /@ lab], #1[[1]]==#2[[1]]&]]
>
> I believe the above works as long as the pairs of equivalences are
> initially sorted. I also remove repeated and reversed pairs. So I
> pre-process my pairs as follows:
>
> Union[Sort/@data]
>
> Then, on the several examples I tried your code and mine give the same
> results.
>
>
> Bye, Mariusz
>
> = = = = = = = = = = = = = = = = = = = =
> Mariusz Jankowski, Ph.D.
> Electrical Engineering
> University of Southern Maine
> Gorham, Maine 04038
> phone/fax: (207)-780-5580/5129
> mailto:mjankowski at usm.maine.edu
> http://www.ee.usm.maine.edu
>
>