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

• sunny: thanks for the additional comments. Quite useful especially to a CoffeeScript newbie like myself.
• sunny: perhaps I misunderstood your comments, but I think there is a mistake in your recommendation for finding the minimum value and its key. I tried the following: getMinKeyValuePair = (obj) -> return [-1, -1] if Object.keys(obj).length < 1 min_v = MAX_WEIGHT [min_k, min_v] = [k, v] for k, v of obj when v < min_v but this actually returns many key value pairs not just one.
• Shanoor: Actually, I didn't made any change to the logic of your code, just some tips for a shorter code. It's because you removed the [min_k, min_v] at the end of your function (compare the generated code with and without, there is an array created in the loop if you remove that line). Generally speaking, coffeescript can be tricky, when I started with coffeescript, I always generated the javascript to check if my code was still doing the same thing.

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.

• sunny: many thanks for the thorough comments. I am not sure about avoiding the delete. I'm with you on avoiding side effects, so I suppose I can move it to the main function where I use it...
• Flambino: @sunny That would be a better solution, yes. The point is really just to keep the function focussed on 1 task: Finding the minimum. Having it also delete properties goes beyond that