code name

A friend of mine defended Fortran against half-literate coders on an example of Prim’s allgorithm.

Good pretext for another language comparison. Let’s see Groovy vs Java vs good old Fortran.

Great Fortran implementation

Great Java implementation by Bruno R. Preiss, P.Eng. and scientist.

Some beginner’s C+ implementation (or is it just a link farm? Whatever).

And here’s the algorithm in Groovy, copied as precisely as possible from pseudocode in Russian Wikipedia article.

[sourcecode language=’groovy’]
class Edge {
Integer v1
Integer v2
Integer weight

Edge(Integer v1, Integer v2, Integer w) {
this.v1 = v1
this.v2 = v2
this.weight = w
}

boolean contains(Integer v) { v1 == v || v2 == v }
Integer otherThan(Integer v) { v1 == v ? v2 : v1 }
}

class Graph {
List V
Collection E

// Dumbest implementation
List getIncident(Integer v) { E.findAll{ it.contains(v) }.collect{ it.otherThan(v) } }
Edge findEdge(Integer v1, Integer v2) { E.find{ it.contains(v1) && it.contains(v2) } }
Number weight(Integer v1, Integer v2) { findEdge(v1, v2)?.weight ?: Double.POSITIVE_INFINITY }
}

Collection prim(Graph G) {
Set T = []
Map d = [:] + G.V.collect { new MapEntry(it, Double.POSITIVE_INFINITY) }
Map p = [:] + G.V.collect { new MapEntry(it, null) }
d[G.V[0]] = 0

List Q = G.V.collect{it}
Q.metaClass.extractMin = { ->
// Dumbest implementation
int minimum = Q.min { d[it] }
int indexOfMinimum = Q.indexOf(minimum) // here Groovy fails to make a shortcut.
return Q.remove(indexOfMinimum)
}

Integer v = Q.extractMin()
while (!Q.isEmpty()) {
G.getIncident(v).each { Integer u ->
if(Q.contains(u) && G.weight(u, v) < d[u]) { d[u] = G.weight(u, v) p[u] = v } } v = Q.extractMin() T << G.findEdge(p[v], v) } return T } void testPrim() { Set expected = [
new Edge(1, 2, 1),
new Edge(2, 3, 1),
new Edge(3, 4, 1),
new Edge(4, 5, 1),
]

Set edges = [
new Edge(1, 3, 2),
new Edge(1, 4, 3),
new Edge(1, 5, 2),
new Edge(2, 4, 7),
new Edge(3, 5, 2),
]

Graph G = new Graph(V: 1..5, E: expected + edges)

Set T = prim(G)
assert expected.equals(T)
println “it worked!”
}

testPrim()[/sourcecode]

Not too bad, er? I see only a couple of Groovy overhead points: constructing a Map from collect{}, and absence of findIndexOfMin().
Of course, we could avoid long type declarations, but I like strict typing.
Make your conclusions.