Re: Add terms surrounded by zero together in matrix
- To: mathgroup at smc.vnet.net
- Subject: [mg59174] Re: Add terms surrounded by zero together in matrix
- From: "Carl K. Woll" <carlw at u.washington.edu>
- Date: Sun, 31 Jul 2005 01:30:45 -0400 (EDT)
- Organization: University of Washington
- References: <dcccur$3j7$1@smc.vnet.net> <dcf34j$lf9$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
"Paul Abbott" <paul at physics.uwa.edu.au> wrote:
> In article <dcccur$3j7$1 at smc.vnet.net>,
> "mchangun at gmail.com" <mchangun at gmail.com> wrote:
>
>> I think this is a rather tough problem to solve. I'm stumped and would
>> really appreciated it if someone can come up with a solution.
>>
>> What i want to do is this. Suppose i have the following matrix:
>>
>> 0 0 0 1 0
>> 0 0 1 2 0
>> 0 0 0 2 1
>> 1 3 0 0 0
>> 0 0 0 0 0
>> 0 0 0 0 0
>> 0 0 1 1 0
>> 5 0 3 0 0
>> 0 0 0 0 0
>> 0 0 0 3 1
>>
>> I'd like to go through it and sum the elements which are surrounded by
>> zeros. So for the above case, an output:
>>
>> [7 4 5 5 4]
>>
>> is required. The order in which the groups surrounded by zero is
>> summed does not matter.
>>
>> The elements are always integers greater than 0.
>
> Have a look at the literature on percolation clusters and in the
> MathGroup archive.
>
> I would have thought that you could use
>
> << Statistics`ClusterAnalysis`
>
> to solve this, but I could not get it to work right. The basic idea I
> had was to locate the non-zero entries in
>
> dat = {{0, 0, 0, 1, 0}, {0, 0, 1, 2, 0}, {0, 0, 0, 2, 1},
> {1, 3, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0},
> {0, 0, 1, 1, 0}, {5, 0, 3, 0, 0}, {0, 0, 0, 0, 0},
> {0, 0, 0, 3, 1}};
>
> using Position:
>
> pos = Position[dat, n_Integer /; n > 0]
>
> and then apply FindClusters to these positions. For example,
>
> cl = FindClusters[pos, DistanceFunction -> BrayCurtisDistance]
>
Paul,
Using Statistics`ClusterAnalysis` is a great idea. Here are some
modifications to your approach to get it to work. First, use SparseArray to
get the positions:
In[13]:=
datarules=Most[ArrayRules[SparseArray[dat]]]
Out[13]=
{{1, 4} -> 1, {2, 3} -> 1, {2, 4} -> 2, {3, 4} -> 2,
{3, 5} -> 1, {4, 1} -> 1, {4, 2} -> 3, {7, 3} -> 1,
{7, 4} -> 1, {8, 1} -> 5, {8, 3} -> 3, {10, 4} -> 3,
{10, 5} -> 1}
Next, define a distance function which yields 0 for identical elements, 1
for adjacent elements, and a big number (I used 10) for nonadjacent
elements.
myDistance[d1_, d2_] := Clip[Total[Abs[d1 - d2]], {0, 1}, {10, 10}]
Then, use FindClusters with method Agglomerate:
In[17]:=
FindClusters[datarules,Method->Agglomerate,DistanceFunction->myDistance]
Out[17]=
{{1, 1, 2, 2, 1}, {1, 3}, {1, 1, 3}, {5}, {3, 1}}
Finally, total the cluster values:
In[18]:=
Total/@%
Out[18]=
{7, 4, 5, 5, 4}
Here is a function to do the above:
In[25]:=
ClusterSums[array_]:=Module[{datarules,clusteredvalues},
datarules=Most[ArrayRules[SparseArray[array]]];
clusteredvalues=
FindClusters[datarules,Method->Agglomerate,
DistanceFunction->(Clip[Total[Abs[Subtract[##]]],{0,1},{10,10}]&)];
Total/@clusteredvalues]
And a check on our data:
In[26]:=
ClusterSums[dat]
Out[26]=
{7, 4, 5, 5, 4}
As a bonus, the approach used by ClusterSums will be able to handle arrays
with any dimension.
Now the question is how does this perform compared to the other approaches
offered on mathgroup?
[snip]
--
> Paul Abbott Phone: +61 8 6488 2734
> School of Physics, M013 Fax: +61 8 6488 1014
> The University of Western Australia (CRICOS Provider No 00126G)
> AUSTRALIA http://physics.uwa.edu.au/~paul
> http://InternationalMathematicaSymposium.org/IMS2005/
>
Carl Woll
Wolfram Research