markov cluster algorithm in ruby

mcl.rb

#!/usr/bin/ruby

class MCL
  def initialize(path,min=0.00001,minpred=0.1)
    @minimum=min
    @minimunPred=minpred
    @matrix=Hash.new
    id=0
    
    edgelist=Array.new
    
    open(path){|f|
      f.each{|line|
        line.chomp!
        edgelist.push(line)
      }
    }
    
    edgelist.each{|x|
      ar=x.split(" ")
      if ar.size==3
        ar.pop
      end
      ar.each{|node|
        if [email protected]?(node)
          @matrix[node]=Hash.new
        end
      }
    }
 
    edgelist.each{|x|
      ar=x.split(" ")
      if ar.length==2
        @matrix[ar[0]][ar[1]]=1.0
        @matrix[ar[1]][ar[0]]=1.0
      elsif ar.length==3
        @matrix[ar[0]][ar[1]]=ar[2].to_f
        @matrix[ar[1]][ar[0]]=ar[2].to_f 
      end
    }
    add_loop(@matrix)
    matrix_make_stochastic(@matrix)
    #matrix_dump(@matrix)
  end

  def add_loop(matrix)
    matrix.each_pair{|key,hash|
      max=0.0
      hash.each_value{|val|
        if max<val
          max=val
        end
      }
      if max>0.0
        matrix[key][key]=max
      else
        matrix[key][key]=1.0
      end
    }
  end

  def matrix_dump(matrix)
    matrix.each_pair{|x,y|
      print x + "\n"
      y.each_pair{|z,val|
        print z + "," + val.to_s + ": "
      }
      print "\n"
    }
  end

  def mcl(inflate=1.2)
    chaos=1.0
    iter=1

    while(chaos>0.001)
      matrixsq=matrix_square(@matrix)
      chaos=matrix_inflate(matrixsq,inflate)
      @matrix=matrixsq
      iter+=1
    end
    matrix_interpret(@matrix)
  end
  
  def matrix_interpret(matrix)
    clusters=Hash.new
    attrid=Hash.new
    clid=0.0
    
    matrix.each_key{|key|
      keys=matrix[key].keys
      keys.each{|nb|
        if matrix[key][nb]<@minimunPred
          matrix[key].delete(nb)
        end
      }
    }
    
    attr=Hash.new
    matrix.each_key{|key|
      if matrix[key].key?(key)
        attr[key]=1
      end
    }
    attr.each_key{|a|
      if attrid.key?(a)
        next
      end
      aa=[a]
      while(aa.size()>0)
        bb=[]
        aa.each{|aat|
          attrid[aat]=clid
          matrix[aat].each_key{|akey|
            if attr.key?(akey)
              bb.push(akey)
            end
          }
        }
        aa=bb.select{|b|
          !attrid.key?(b)
        }
      end
      clid+=1
    }

    matrix.each_key{|key|
      if !attr.key?(key)
        matrix[key].keys.select{|x|
          attr.key?(x)
        }.each{|a|
          if  clusters.key?([attrid[a]])
            if clusters[attrid[a]].key?(key)
              clusters[attrid[a]][key]+=1
            else
              clusters[attrid[a]][key]=1
            end
          else
            clusters[attrid[a]]=Hash.new
            clusters[attrid[a]][key]=1
          end
        }
      else
        if !clusters.key?(attrid[key])
          clusters[attrid[key]]=Hash.new
          clusters[attrid[key]][key]=1
        else
          if clusters[attrid[key]].key?(key)
            clusters[attrid[key]][key]+=1 
          else
            clusters[attrid[key]][key]=1
          end
        end
      end
    }
    clusters
  end

  def matrix_square(matrix)
    sq=Hash.new
    matrix.each_key{|key|
      sq[key]=matrix_multiply_vector(matrix,matrix[key])
    }
    sq
  end
  
  def matrix_multiply_vector(matrix,vec)
    w=Hash.new
    vec.each_pair{|x,y|
      matrix[x].each_key{|z|
        if w.key?(z)
          w[z]+=y*matrix[x][z]
        else
          w[z]=y*matrix[x][z]
        end
      }
    }
    w
  end

  def matrix_make_stochastic(matrix)
    matrix_inflate(matrix,1.0)
  end

  def matrix_inflate(matrix,inflate)
    chaos=0.0
    matrix.each_key{|key|
      sum=0.0
      sumsq=0.0
      max=0.0
      matrix[key].keys.each{|row|
        if matrix[key][row] < @minimum
          matrix[key].delete(row)
          next
        end
        matrix[key][row]**=inflate
        sum+=matrix[key][row]
      }

      if(sum>0.0)
        matrix[key].each_key{|row|
          matrix[key][row]/=sum
          sumsq+=matrix[key][row]
          if max<matrix[key][row]
            max=matrix[key][row]
          end
        }
      end
      if chaos < (max-sumsq)
        chaos=max-sumsq
      end
    }
    chaos
  end
end


mcl=MCL.new(ARGV[0])
mcl.mcl().each_pair{|key,val|
  print val.keys.join(",")+"\n"
}