Karger's Min-Cut

links-own [capacity]
globals [
  mean-mincut
  mincuts
  all-neighbors
  sim-num
]

to setup
  clear-all
  reset-ticks
  set mean-mincut 0
  set all-neighbors []
  set mincuts []
  create-nodes
  create-edges
end 

to recover-initial
  clear-turtles
  create-nodes
  create-edges
end 

to create-nodes
  create-turtles num-nodes
  layout-circle sort turtles (world-width / 2.5 - 1)
  ask turtles [set shape "circle"]
  ask turtles [set color blue]
  ask turtles [set label who]
end 

to create-edges
  foreach sort turtles [t -> create-edge t ]
end 

to create-edge [t]
  ask t [
    ifelse (length all-neighbors < who + 1)
    [
      let my-neighbors-list []
      let my-neighbors n-of (min(list random-poisson (mean-density * num-nodes / 100) (count turtles - 1))) other turtles
      (foreach (list my-neighbors) [
        t_ -> set my-neighbors-list lput [who] of t_ my-neighbors-list
      ])
      set my-neighbors-list item 0 my-neighbors-list
      set all-neighbors insert-item who all-neighbors my-neighbors-list
      create-links-with my-neighbors [set capacity 1 set label capacity]
    ]
    [
      let my-neighbors-list item who all-neighbors
      (foreach (my-neighbors-list) [
        t_ -> create-link-with turtle t_ [set capacity 1 set label capacity]
        ]
      )
    ]
  ]
end 

to contract-once
  ifelse (count links <= 1) [ print "can't contract anymore" ]
  [
    let edge one-of links
    let smooshee [end1] of edge
    let smoosher [end2] of edge
    let smooshee-edges [my-links] of smooshee
    ask smooshee-edges [
      let endpoint end1
      if endpoint = smooshee [set endpoint end2]
      if(endpoint != smoosher)[
        let cap capacity
        ask smoosher [
          ifelse (link-with endpoint != nobody)
          ; update weight if already exists
          [
            ask link-with endpoint [set capacity capacity + cap set label capacity]
          ]
          ; create link otherwise
          [
            create-link-with endpoint [set capacity cap set label capacity]
          ]
        ]
      ]
    ]
    ask smooshee [die]
  ]
  tick
end 

to contract
  while [count links > 1] [contract-once]
  let mincut [capacity] of one-of links
  set mean-mincut (mean-mincut * length mincuts + mincut) / (length mincuts + 1)
  set mincuts lput mincut mincuts
end 

to run-sim
  recover-initial
  contract
  set sim-num sim-num + 1
end