| 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 |
|