Skip to content

Prim’s allgorithm in Groovy: inspired by Fortran and Java versions


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.

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<Integer> V
    Collection<Edge> E

    // Dumbest implementation
    List<Integer> 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<Edge> prim(Graph G) {
    Set<Edge> T = []
    Map<Integer, Number> d = [:] + G.V.collect { new MapEntry(it, Double.POSITIVE_INFINITY) }
    Map<Integer, Integer> p = [:] + G.V.collect { new MapEntry(it, null) }
    d[G.V[0]] = 0

    List<Integer> 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<Edge> expected = [
        new Edge(1, 2, 1),
        new Edge(2, 3, 1),
        new Edge(3, 4, 1),
        new Edge(4, 5, 1),
    ]

    Set<Edge> 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<Edge> T = prim(G)
    assert expected.equals(T)
    println "it worked!"
}

testPrim()

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.

2 Comments

  1. Sergey Bondarenko wrote:

    That’s a bit strange – there is no Edge(1, 2, 1) in initial data.
    Why it appears in expected data?

    Posted on 18-Oct-10 at 15:08 | Permalink
  2. It’s there, look how I construct G: new Graph(V: 1..5, E: expected + edges)

    Posted on 19-Oct-10 at 19:02 | Permalink

Post a Comment

Your email is never published nor shared.