Karger's Min-Cut

Karger's Min-Cut preview image

This model is seeking new collaborators — would you please help?

1 collaborator

Default-person Ali Akhtari (Author)

Tags

computer science 

Tagged by Ali Akhtari 6 months ago

flow models 

Tagged by Ali Akhtari 6 months ago

maximum flow 

Tagged by Ali Akhtari 6 months ago

networks 

Tagged by Ali Akhtari 6 months ago

Visible to everyone | Changeable by everyone
Model was written in NetLogo 6.2.2 • Viewed 72 times • Downloaded 2 times • Run 0 times
Download the 'Karger's Min-Cut' modelDownload this modelEmbed this model

Do you have questions or comments about this model? Ask them here! (You'll first need to log in.)


Comments and Questions

Please start the discussion about this model! (You'll first need to log in.)

Click to Run Model

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 

There is only one version of this model, created 6 months ago by Ali Akhtari.

Attached files

File Type Description Last updated
Karger's Min-Cut.png preview Preview for 'Karger's Min-Cut' 6 months ago, by Ali Akhtari Download

This model does not have any ancestors.

This model does not have any descendants.