Java: How does my Prim's look?

Question

I am trying to implement Prim's minimum spanning tree algorithm with JGraphT. How does it look?

One issue I ran into was JGraphT's handling of everything like it's directed. So sometimes it is necessary to make some awkward calls to reverse g.getEdgeSource(e) and g.getEdgeTarget(e) if they didn't happen to be right.

I tried to implement this originally with JGraphT's Fibonacci Heap but it was too hard so I just did a regular PQ.

Instead of setting weights of non-existent edges to infinity, I just didn't add it to the queue.

Advice? Stylistic issues? Glaring inefficiencies? Code I should be using instead of rolling my own?

public static Graph<String, DefaultWeightedEdge> primPQ(final WeightedGraph<String, DefaultWeightedEdge> g, String root) {
  Graph<String, DefaultWeightedEdge> mst = new SimpleWeightedGraph<String, DefaultWeightedEdge>(DefaultWeightedEdge.class);
  Queue<DefaultWeightedEdge> pq = new PriorityQueue<DefaultWeightedEdge>(g.vertexSet().size(), new Comparator<DefaultWeightedEdge>() {
    @Override
    public int compare(DefaultWeightedEdge o1, DefaultWeightedEdge o2) {
      if (g.getEdgeWeight(o1) < g.getEdgeWeight(o2)) {
        return -1;
      }
      if (g.getEdgeWeight(o1) > g.getEdgeWeight(o2)) {
        return 1;
      } 
      return 0;
    }
  });

  mst.addVertex(root);
  DefaultWeightedEdge link;

  for (String v : g.vertexSet()) {
    link = g.getEdge(root, v);
    if (link != null) {
      pq.add(link);
    }
  }

  //this is made difficult by JGraphT's assumption that everything is directed
  DefaultWeightedEdge minEdge = pq.poll();
  String toAdd;
  String alreadyFound;
  String tmp;

  while (minEdge != null) {
    // guessing at which is in the MST
    toAdd = g.getEdgeTarget(minEdge);
    alreadyFound = g.getEdgeSource(minEdge);

    if (!(mst.containsVertex(toAdd) && mst.containsVertex(alreadyFound))) {
      // swap if backwards
      if (mst.containsVertex(toAdd)) {
        tmp = toAdd;
        toAdd = alreadyFound;
        alreadyFound = tmp;
      }
      mst.addVertex(toAdd);
      mst.addEdge(alreadyFound, toAdd, minEdge);
      System.out.format("%s --> %s\n", g.getEdgeSource(minEdge), toAdd);

      for (String v : g.vertexSet()) {
        if (! mst.containsVertex(v)) {
          link = g.getEdge(toAdd, v);
          if (pq.contains(link)) {
            g.setEdgeWeight(minEdge, Math.min(g.getEdgeWeight(minEdge), g.getEdgeWeight(link)));
          }
          if (link != null && ! pq.contains(link)) {
            pq.add(link);
          }
        }
      }
    }
    minEdge = pq.poll();
  }
  return mst;
}

Answer 1

Hi,

I have compared the result of your algorithm to one mine which was a homework and it both gives the same minimum total weight, keep it up !

Answer 2

Both while increasing the number of edges and the number of vertices, I get different results, I'll be back...

Answer 3

OKAY, it looks fine now.

By the way, my exercise was a bit tricky: I had to write an algorithm that finds the minimum spanning tree indeed, but my algorithm had to proceed by elimination on the edges. I wrote something that uses some depth first traversal to find cycles and then eliminates the most weighted edge by "coloring" it red..

Your PRIM alg yields the same minimum total weight than my alg for 4 randomly generated graphs that have N=200 nodes and various values M=(N*(N-1)/k) for k=2,3,4,8 for the number of edges.

At first sight, I would have tought this kind of testing was overkill, but it was not !