C++ boost prim's algorithm with custom weights?

Question

I'm trying to use boost's prim's algorithm to find the minimum spanning tree using edge weight and an id number instead of just edge weight.

For example, if both edge weights were 1 the id would be compared, whichever one was less would break the tie.

I created an EdgeWeight class and overloaded the < and + operators to do this, then changed the edge_weight_t property from int to EdgeWeight in the hopes it would work.

// TestPrim.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <boost/config.hpp>
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/prim_minimum_spanning_tree.hpp>

using namespace std;

class EdgeWeight{
    public:
    EdgeWeight(){}
    EdgeWeight(int weightIn, int destinationIdIn){
        weight = weightIn;
        destinationId = destinationIdIn;
    }

        bool operator<(const EdgeWeight& rhs) const {
        if (weight < rhs.weight)
            return true;
        else if(weight == rhs.weight){
            if (destinationId < rhs.destinationId)
                return true;
            else
                return false;
        }
        else
            return false;
        }

    EdgeWeight operator+(const EdgeWeight& rhs) const {
        EdgeWeight temp;
        temp.weight = weight + rhs.weight;
        temp.destinationId = destinationId + rhs.destinationId;
        return temp;
        }

    int weight;
    int destinationId;
};


int _tmain(int argc, _TCHAR* argv[])
{
  using namespace boost;
  typedef adjacency_list < vecS, vecS, undirectedS, property<vertex_distance_t, EdgeWeight>,      property < edge_weight_t, EdgeWeight > > Graph;
  typedef std::pair < int, int >E;
  const int num_nodes = 5;
  E edges[] = { E(0, 2), E(1, 3), E(1, 4), E(2, 1), E(2, 3),
    E(3, 4), E(4, 0)
  };
  EdgeWeight weights[] = { EdgeWeight(1, 2), EdgeWeight(1, 3), EdgeWeight(2, 4), 
      EdgeWeight(7, 1), EdgeWeight(3, 3), EdgeWeight(1, 4), EdgeWeight(1, 0) };
  Graph g(edges, edges + sizeof(edges) / sizeof(E), weights, num_nodes);
  property_map<Graph, edge_weight_t>::type weightmap = get(edge_weight, g);
  std::vector < graph_traits < Graph >::vertex_descriptor > p(num_vertices(g));
  prim_minimum_spanning_tree(g, &p[0]);

  for (std::size_t i = 0; i != p.size(); ++i)
    if (p[i] != i)
      std::cout << "parent[" << i << "] = " << p[i] << std::endl;
    else
      std::cout << "parent[" << i << "] = no parent" << std::endl;

  return EXIT_SUCCESS;
}

I got an error, "c:\program files (x86)\microsoft visual studio 10.0\vc\include\limits(92): error C2440: '' : cannot convert from 'int' to 'D' 1> No constructor could take the source type, or constructor overload resolution was ambiguous"

Am I doing this the right way? Is there a better way to do this?

http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/prim_minimum_spanning_tree.html http://www.boost.org/doc/libs/1_38_0/boost/graph/prim_minimum_spanning_tree.hpp

edit: ok so I implemented the weights using cjm's perturbed method for now, but in the future I believe I will have to use the above method somehow, still wondering how to do it

edit2: based on Jeremiah's reponse I changed the vertex_distance_t from int to EdgeWeight but got the same error

Answer 1

Boost's implementation of "Prim's" algorithm (Jarník discovered the algorithm almost thirty years prior to Prim) uses a generic implementation of Dijkstra's algorithm as a subroutine. I'm sure someone thought that this was really clever.

Dijkstra's algorithm needs nonnegative weights that support addition with identity and comparison, and these operations have to be compatible (for all x, y, z, if x <= y, then x + z <= y + z). In practice, the only useful way to instantiate these operations is the customary one (I take this back; it's possible to tiebreak Dijkstra's algorithm the same way), so Boost's implementation of Dijkstra's algorithm sensibly assumes the existence of "infinity" (std::numeric_limits<vertex_distance_t>::max()). It also asserts that all weights are nonnegative.

By contrast, Prim's algorithm needs weights that support only comparison. You might wonder what the "minimum" in "minimum spanning tree" means without addition, but an alternative characterization of a minimum spanning tree is that, for every path P from a vertex u to a vertex v, the longest edge in P is at least as long as the longest edge in the tree's path from u to v.

The result is that Boost's implementation of Prim's algorithm makes some unwarranted assumptions. You can code around them as follows, but Boost does not appear to be contractually obligated not to break this hack in the future.

• Get rid of the addition operator; it's not used.

• Since Boost is going to assert that all of your weights are not less than the default-constructed value, let's make the default "negative infinity".

  #include <limits>
  ...
  EdgeWeight() : weight(numeric_limits<int>::min()),
                 destinationId(numeric_limits<int>::min()) {}
  

• Boost needs "positive infinity", so we need to specialize std::numeric_limits.

  namespace std {
  template<>
  struct numeric_limits<EdgeWeight> {
      static EdgeWeight max() { return EdgeWeight(numeric_limits<int>::max(),
                                                  numeric_limits<int>::max()); }
  };
  }
  

• You can simplify the comparison.

  bool operator<(const EdgeWeight& rhs) const {
      return (weight < rhs.weight ||
              (weight == rhs.weight && destinationId < rhs.destinationId));
  }
  

Answer 2

The vertex distance map's value_type needs to be the same as the edge weight type for the algorithm to work. The documentation implies that (in the first part of the description of distance_map) but does not say it explicitly. I have (since answering this question) clarified and corrected the documentation in the Boost trunk.