Kruskal's algorithm

Question

I'm working through Coffeescript implementing simple algorithms (started with Prim's as reviewed in this previous post) and wrote out Kruskal's algorithm as below, with a few helper functions. I'd appreciate any and all feedback, especially on making this script more idiomatic.

# 
# graph information
#

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

edgesDir = {
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},
}

edgesConDir =
0: [1,5],
1: [1, 2],
2: [1, 3],
3: [3, 5],
4: [2, 4],
5: [3, 4],
6: [0, 1]

NUM_NODES = Object.keys(nodesDir).length
NODES = [0...NUM_NODES]
MAX_WEIGHT = 10000
EDGE_WEIGHTS = [99, 2, 2, 1, 1, 5, 10]

# 
# helper functions
#

sortByKey = (array, key) ->
    array.sort((a, b) -> a[key] - b[key])

# returns array where all array elements previously 
# equal to before are set to after
convertAll = (array, before, after) ->
    ((if el != before then el else after) for el in array)   

# source: https://coffeescript-cookbook.github.io/chapters/arrays/removing-duplicate-elements-from-arrays
Array::unique = ->
  output = {}
  output[@[key]] = @[key] for key in [0...@length]
  value for key, value of output

# 
# traversal algorithm
#

# Kruskal algorithm as implemented in Skiena 198
kruskal = (nodesDir, edgesDir) ->
    edgesReturn = []
    edges = ( {i:i, weight:el} for el, i in EDGE_WEIGHTS)
    nodeComponents = ( i for el, i in NODES )
    sortByKey(edges, 'weight')
    nodesUn = nodeComponents.unique()
    while nodesUn.length > 1
        newEdge = edges.shift()
        nodesToTry = edgesConDir[newEdge.i]
        if nodeComponents[nodesToTry[0]] != nodeComponents[nodesToTry[1]]
            edgesReturn.push newEdge.i
            nodeComponents = convertAll(nodeComponents, nodeComponents[nodesToTry[1]], nodeComponents[nodesToTry[0]])
            nodesUn = nodeComponents.unique()
    edgesReturn

Answer 1

Disclaimer: I don't know coffeescript, but I do know a little javascript

Most of the code is understandable, even for me not knowing coffeescript, but it is obfuscated by bad naming and laziness. So I would opt for better naming a lot of places:

• el to edge or element or even better names
• nodesUn rename to uniqueNodes
• edgesConDir, nodesDir and edgesDir, maybe rename to edgeConnections/nodeConnections, nodes and edges?

I would also fix the spacing, so that it is consitent. In the three lists/dictionaries/... at the top you vary between having spaces around : or not. Personally I like to see stuff with spaces after the separators, so I would try to be consistent with using 5: {3:3, 1:0} (that is spaces after at least the initial colon and after commas.

It seems like your code might be faulty as you have braces around the edgesDir but not around the two others? Are the braces optional? If so, it would look better if you used the same for very similar lists.

Regarding that last code block I would perhaps include a little more vertical space. And possibly, it it's legal, replace the nodesToTry with fromNode, toNode = edgesConDir[newEdge.i] or similar. That would make the following lines easier to read, I think.