Debian Codegraph @

doc/minimcl

raw
1 #!/usr/local/bin/perl -w
2
3 # (C) Copyright 2006 Stijn van Dongen
4 #
5 # This file is part of MCL. You can redistribute and/or modify MCL under the
6 # terms of the GNU General Public License; either version 2 of the License or
7 # (at your option) any later version. You should have received a copy of the
8 # GPL along with MCL, in the file COPYING.
9
10
11 sub explain {
12 print <<EOH;
13 purpose:
14 A small mcl implementation for educational purposes. It uses terse perl
15 though, so the education might be twofold.
16
17 implementation:
18 It is hash based, which implies that we get sparse matrices easily but at
19 the cost of using hashes. The hash-based matrices only store non-zero
20 entries.
21
22 The code is pretty straightforward. The interpretation routine implements
23 the mapping as described in the publications referenced in the (maxi) mcl
24 manual.
25
26 bonus:
27 Since the implementation is hash based you can use any type of labels, not
28 necessarily numbers.
29
30 Usage:
31 minimcl [--I=<num>] [--verbose] LABEL-INPUT
32
33 This means --I=<num> is optional (with 2.0 the default) and so is --verbose.
34 LABEL-INPUT should be a file name or stream (STDIN) where each line is of
35 the form
36 LABEL1 LABEL2 NUMBER
37 or
38 LABEL1 LABEL2
39 EOH
40 }
41
42 use strict;
43 use Getopt::Long;
44
45 $::verbose = 0;
46 my $I = 2.0;
47 my $help = 0;
48
49 if (!@ARGV) {
50 print STDERR "issue 'minimcl --help' for help\n";
51 print STDERR "expecting STDIN now\n";
52 }
53
54 if
55 (! GetOptions
56 ( "verbose" => \$::verbose
57 , "I=f" => \$I
58 , "help" => \$help
59 )
60 )
61 { print STDERR "option processing failed\n";
62 exit(1);
63 }
64
65 &explain && exit(0) if $help;
66
67 my $mx = {};
68
69 while (<>) {
70 next if /^\s*#/;
71 if (/(\S+)\s+(\S+)\s+(\S+)/) {
72 my ($x, $y, $val) = ($1, $2, $3);
73 $val = 1.0 if $val !~ /^[0-9]/;
74 $mx->{$x}{$y} = $val+0;
75 $mx->{$y}{$x} = $val+0;
76 }
77 elsif (/(\S+)\s+(\S+)/) {
78 $mx->{$1}{$2} = 1.0;
79 $mx->{$2}{$1} = 1.0;
80 }
81 }
82
83 matrix_add_loops($mx);
84 matrix_make_stochastic($mx);
85 matrix_dump($mx, 3, "start") if $::verbose;
86
87 my ($cl, $limit) = mcl($mx, $I);
88
89 matrix_dump($limit, 1, "limit") if $::verbose;
90 matrix_dump($cl, 0, "clustering");
91
92
93 sub mcl {
94 my ($mx, $I) = @_;
95 my $chaos = 1;
96 my $ite = 1;
97 while ($chaos > 0.001) {
98 my $sq = matrix_square($mx);
99 my $progress = sprintf "chaos %.5f ite %d", $chaos, $ite;
100 matrix_dump($sq, 3, "X $progress") if $::verbose;
101 $chaos = matrix_inflate($sq, $I);
102 matrix_dump($sq, 3, sprintf "I $progress") if $::verbose;
103 print STDERR "$progress\n" if !$::verbose;
104 $mx = $sq;
105 $ite++;
106 }
107 my $cl = matrix_interpret($mx);
108 return ($cl, $mx);
109 }
110
111 # dangersign:
112 # can this yield a < b < c < a ?
113
114 sub cmpany { local $^W = 0; $a <=> $b || $a cmp $b }
115
116 sub matrix_dump {
117 my ($mx, $modes, $msg) = @_;
118 print "($msg\n";
119 for my $n (sort cmpany keys %$mx) {
120 my @nb = $modes & 2
121 ? map { sprintf "%s:%.3f", $_, $mx->{$n}{$_}; } sort cmpany keys %{$mx->{$n}}
122 : map { sprintf "%s", $_; } sort cmpany keys %{$mx->{$n}};
123 local $" = "\t";
124 if ($modes & 1) {
125 printf "%-20s%s\n", $n, "@nb";
126 }
127 else {
128 print "@nb\n";
129 }
130 }
131 print ")\n";
132 }
133
134
135 sub matrix_square {
136 my ($mx) = @_;
137 my $sq = {};
138 my @nodes = keys %$mx;
139 for my $n (@nodes) {
140 $sq->{$n} = matrix_multiply_vector($mx, $mx->{$n});
141 }
142 return $sq;
143 }
144
145
146 sub matrix_multiply_vector {
147 my ($mx, $v) = @_;
148 my $w = {};
149 for my $e (keys %$v) {
150 my $val = $v->{$e};
151 for my $f (keys %{$mx->{$e}}) {
152 $w->{$f} += $val * $mx->{$e}{$f};
153 }
154 }
155 return $w;
156 }
157
158
159 sub matrix_make_stochastic {
160 my ($mx) = @_;
161 matrix_inflate($mx, 1); # return value chaos is meaningless for
162 # non stochastic input.
163 }
164
165 sub matrix_add_loops {
166 my ($mx) = @_;
167 for my $n (keys %$mx) {
168 my $max = vector_max($mx->{$n});
169 $mx->{$n}{$n} = $max ? $max : 1;
170 }
171 }
172
173 sub vector_max {
174 my ($v) = (@_);
175 my $max = 0;
176 for my $n (keys %$v) {
177 $max = $v->{$n} if $v->{$n} > $max;
178 }
179 return $max;
180 }
181
182 sub vector_sum {
183 my ($v, $p) = (@_);
184 my $sum = 0;
185 for my $n (keys %$v) {
186 $sum += $v->{$n} ** $p;
187 }
188 return $sum;
189 }
190
191
192 sub matrix_inflate { # prunes small elements as well.
193 my ($mx, $I) = @_;
194 my @nodes = keys %$mx;
195 my $chaos = 0;
196 for my $n (@nodes) {
197 my $sum = 0;
198 my $sumsq = 0;
199 my $max = 0;
200 for my $nb (keys %{$mx->{$n}}) {
201 if ($mx->{$n}{$nb} < 0.00001) {
202 delete($mx->{$n}{$nb});
203 next;
204 }
205 $mx->{$n}{$nb} **= $I;
206 $sum += $mx->{$n}{$nb};
207 }
208 if ($sum) {
209 for my $nb (keys %{$mx->{$n}}) {
210 $mx->{$n}{$nb} /= $sum;
211 $sumsq += $mx->{$n}{$nb} ** 2; # sum x_i^2 over stochastic vector x
212 $max = $mx->{$n}{$nb} if $max < $mx->{$n}{$nb};
213 }
214 }
215 $chaos = $max - $sumsq if $max - $sumsq > $chaos;
216 }
217 return $chaos; # only meaningful if input is stochastic
218 }
219
220
221 # assumes but does not check doubly idempotent matrix.
222 # can handle attractor systems of size < 10.
223 sub matrix_interpret { # recognizes/preserves overlap.
224
225 my ($limit) = @_;
226 my $clusters= {}; # hash of arrayrefs.
227 my $attrid = {};
228 my $clid = 0;
229
230 for my $n (keys %$limit) { # crude removal of small elements.
231 for my $nb (keys %{$limit->{$n}}) {
232 delete $limit->{$n}{$nb} if $limit->{$n}{$nb} < 0.1;
233 }
234 }
235 my $attr = { map { ($_, 1) } grep { $limit->{$_}{$_} } keys %$limit };
236 # _ contract 'connected attractors', assign cluster id.
237 for my $a (keys %$attr) {
238 next if defined($attrid->{$a});
239 my @aa = ($a);
240 while (@aa) {
241 my @bb = ();
242 for my $aa (@aa) {
243 $attrid->{$aa} = $clid;
244 push @bb, grep { defined($attr->{$_}) } keys %{$limit->{$aa}};
245 }
246 @aa = grep { !defined($attrid->{$_}) } @bb;
247 }
248 $clid++;
249 }
250 for my $n (keys %$limit) {
251 if (!defined($attr->{$n})) { # look at attractors
252 for my $a (grep { defined($attr->{$_}) } keys %{$limit->{$n}}) {
253 $clusters->{$attrid->{$a}}{$n}++;
254 }
255 }
256 else {
257 $clusters->{$attrid->{$n}}{$n}++;
258 }
259 }
260 return $clusters;
261 }
262
263