Prim's algorithm in CoffeeScript

Question

I'm just starting to learn CoffeeScript and am trying to work through simple examples, this one being Prim's algorithm. I'd like feedback on everything but especially on making this script take advantage of the features of CoffeeScript most effectively.

nodes_dir = {
0 : [1],
1 : [0, 2, 3, 5],
2 : [1, 4],
3 : [1, 4, 5],
4 : [2, 3],
5: [1, 3]
}

edges_dir = {
0: {1:6}
1: {2:1, 3: 2, 5:0, 0:6},
2: {1:1, 4:4},
3: {1:2, 4:5, 5:3},
4:{2:4, 3:5},
5:{3:3, 1:0},
}

MAX_WEIGHT = 10000
NUM_NODES = 6
EDGE_WEIGHTS = [99, 2, 2, 1, 1, 5, 10]

get_min_key_value = (obj) ->
    if Object.keys(obj).length < 1
        return [-1, -1]
    min_k = MAX_WEIGHT 
    min_v = MAX_WEIGHT
    for k, v of obj
        if v < min_v
          min_v = v
          min_k = k
    delete obj[min_k]
    [min_k, min_v]


# Prims algorithm as implemented in Skiena p 195
prim = (nodes_dir, edges_dir) ->
   # record-keeping arrays
   intree = []
   distance = []
   link = []
   parent = []

   # set default values for record-keeping arrays
   for i in [1..NUM_NODES]
       intree.push -1
       distance.push MAX_WEIGHT
       link.push -1
       parent.push -1

   links = []
   link_add = -1
   current_node = 0

   while intree[current_node] < 0
      # add new node and new edge to record of edges/nodes
      intree[current_node] = 1
      links.push link[current_node] if link[current_node] > 0

      # update any distances to tree that have become shorter with addition of new node
      p = edges_dir[current_node] 
      for k,v of p
          weight = EDGE_WEIGHTS[v]
          if distance[k] > weight and intree[k] < 0
              distance[k] = weight
              link[k] = v
              parent[k] = current_node

      # determine which node is now closest to tree and add it
      dist = MAX_WEIGHT
      for i in [0..NUM_NODES-1]
          if intree[i] < 0 and dist > distance[i]            
              dist = distance[i]
              current_node = i
              link_add = link[i]

   links


f = prim(nodes_dir, edges_dir)
alert f

Answer 1

This already seems pretty good considering you just started learning coffeescript.

for k, v of obj
     if v < min_v
       min_v = v
       min_k = k

Personally, I'm a huge fan of comprehensions. I would change the above to the following.

for k, v of obj when v < min_v
    min_v = v
    min_k = k

Your declarations at the top can be refined. No need for brackets/commas.

nodes_dir = {
0 : [1],
1 : [0, 2, 3, 5],
2 : [1, 4],
3 : [1, 4, 5],
4 : [2, 3],
5: [1, 3]
}

Can be simplified to just

nodes_dir =
    0: [1]
    1: [0, 2, 3, 5]
    2: [1, 4]
    3: [1, 4, 5]
    4: [2, 3]
    5: [1, 3]

Regarding the following

links.push link[current_node] if link[current_node] > 0

Don't lookup the value in the array based on the index twice.

linkNode = link[current_node]
links.push linkNode if linkNode > 0

Lastly,

intree = []
distance = []
link = []
parent = []

# set default values for record-keeping arrays
for i in [1..NUM_NODES]
    intree.push -1
    distance.push MAX_WEIGHT
    link.push -1
    parent.push -1

I would suggest creating an object that has these four arrays as properties, as well as putting that initialization code (the for loop) inside it's own method. This would add to clarity/reusability. Also, put all this code inside a coffeescript class declaration, which has a huge host of benefits.

Answer 2

To add on the previous answers, this loop:

for k, v of obj
    if v < min_v
        min_v = v
        min_k = k

can be reduced to one line

[min_v, min_k] = [v, k] for k, v of obj when v < min_v

Also, if you can use ES6, this initialization code:

intree = []
distance = []
link = []
parent = []

for i in [1..NUM_NODES]
    intree.push -1
    distance.push MAX_WEIGHT
    link.push -1
    parent.push -1

can be shorter and more elegant:

distance = new Array(NUM_NODES).fill(MAX_WEIGHT)
intree = new Array(NUM_NODES).fill(-1)
link = Array.from(intree)
parent = Array.from(intree)

Array.from clones an array so no references issue here.

Few other things, instead of

min_k = MAX_WEIGHT
min_v = MAX_WEIGHT

you can write min_k = min_v = MAX_WEIGHT, we're dealing with numbers so no reference issues.

This return within an if

if Object.keys(obj).length < 1
    return [-1, -1]

can be written in one line return [-1, -1] if Object.keys(obj).length < 1

Answer 3

@Brad M already pointed out most of the stuff I'd have pointed out too. These are just some additional things

• CoffeeScript is still JavaScript, so it's typically written in camelCase - not snake_case.

• I'd avoid calling delete in get_min_key_value. Better to just let it return the min key, and let the caller worry about the rest, than to have a function with such side-effects.
  However, it seems you're not actually using this function, so really it should probably just be deleted. Still, if you do need it, I'd suggest something like this:

  getKeyForMinimumValue = (obj) ->
    minValue = MAX_WEIGHT
    for own key, value of obj when value < minValue # use own to only iterate instance properties
      [minKey, minValue] = [key, value]
    minKey
  

  It's different, as it'll only return the key, or return undefined; not the key/value pair or [-1, -1]. But it's certainly shorter

• Instead of doing this [0..NUM_NODES-1], use a half-open range: [0...NUM_NODES] (three dots; excludes the end value).

• ... though, instead of having a separate, hard-coded value of the number of nodes, just use Object.keys(nodes_dir).length.