k-Means

extensions [mapreduce]

breed [points point]
breed [centroids centroid]

globals [centers ]

to test
  ask points [die]
  ask centroids [die]
  load-points "input/points4.txt"
  init
  kmeans
end 

to load
  load-points word "input/" input
end 

to load-points [#filename]
  file-open #filename
  while[not file-at-end?][
    let line file-read-line
    ; show word "line " line
    if (length line) > 0 [
      let split-pos position " " line
      let px (substring line 0 split-pos)
      let py substring line (split-pos + 1) (length line)
      create-points 1 [
        setxy (read-from-string px) (read-from-string py)
        set shape "dot"
        set color white
      ]
    ]
  ]
  file-close
end 

to-report point-list []
  let #list []
  ; let id 0
  ask points [
   ; show xcor
   ; set id (id + 1)
   let cords list xcor ycor
   set #list (lput (list who (list cords)) #list)
  ]
  
  report #list
end 

to-report euclidean-distance [#p1x #p1y #p2x #p2y]
  report sqrt ((#p1x - #p2x)*(#p1x - #p2x) + (#p1y - #p2y)*(#p1y - #p2y))
end 

to-report vecsub [#p1 #p2]
  let p1x first #p1
  let p1y first bf #p1
  let p2x first #p2
  let p2y first bf #p2
  report list (p1x - (p1x - p2x) / 2) (p1y - (p1y - p2y) / 2)
end 

to-report newMeans [#key #acc #value]
  let val read-from-string #value
  ifelse #acc = []
  [
    ; search for the point in the list of centers
    let cents centers
    let id (read-from-string #key)
    while [(not empty? cents) and (first first cents) != id][set cents bf cents]
    ifelse not empty? cents [
      ;exract coordinates
      let centr first cents
      
      report vecsub (bf centr) val]
    ; there has been a mistake in the data. Keep accumulator
    [report #acc]
  ]
  [report vecsub #acc val]
end 

to-report nearestCenter [#key #value]
  let nearest -1
  let mindist 99999
  foreach centers [
    let id first ?
    let x first butfirst ?
    let y first butfirst butfirst ?
    let dist 0
    set dist (euclidean-distance (first #value) (first butfirst #value) x y)
    if dist < mindist [
     set mindist dist
     set nearest id
    ]
  ]
  
  report nearest
end 

to mapper [#key #value]
  ; Parse input
  let val read-from-string #value
  
  ; determine nearest center
  let nearest (nearestCenter (read-from-string #key) val)
  
  ; output
  mapreduce:emit nearest #value
end 

to centroids-to-centers
  set centers []
  ask centroids [
    set centers fput (list who pxcor pycor) centers
  ]
end 

to init
  ask centroids [die]
  ; initially guess centroids
  ask n-of k points [hatch-centroids 1[
        set shape "dot"
        set color 15 ]]
end 

to kmeans
  repeat iterations [
    ; create the list of centers
    centroids-to-centers
    
    let res mapreduce point-list
    
    ; adapt centroids
    foreach res [
      let id first ?
      let x (first last ?)
      let y (last last ?)
      ask centroid id [ setxy x y ]
    ]
    show "recentering done"
    color-partitions
  ]
end 

to color-partitions
  let cl []
  ask centroids [set cl fput who cl]
  set cl sort cl
  
  foreach point-list [
    ; show (first ?)
    ; show (first last ?)
    let nc nearestCenter (first ?) (first last ?)
    ; show "jjj"
    let cid nc
    let tcl cl
    let c 25
    while [(first tcl) != cid] [set c (c + 10) set tcl bf tcl]
    ask point (first ?) [set color c]
  ]
end 

to-report mapreduce [#input]
  reset-ticks
  
  let res mapreduce:mapreduce "mapper" "newMeans" [] #input
  
  while [mapreduce:running?] [
   every 0.5 [
       ; print mapreduce:map-progress
       ; print mapreduce:reduce-progress
       ; plot 1
       tick
     ]
  ]
  tick
  
  print "done"
  report mapreduce:result res
end