title: C++ boost prim's algorithm with custom weights?
body: <p>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.</p>
  
  <p>For example, if both edge weights were 1 the id would be compared, whichever one was less would break the tie.</p>
  
  <p>I created an EdgeWeight class and overloaded the &lt; and + operators to do this, then changed the edge_weight_t property from int to EdgeWeight in the hopes it would work.</p>
  
  <pre><code>// TestPrim.cpp : Defines the entry point for the console application.
  //
  
  #include "stdafx.h"
  
  #include &lt;boost/config.hpp&gt;
  #include &lt;iostream&gt;
  #include &lt;boost/graph/adjacency_list.hpp&gt;
  #include &lt;boost/graph/prim_minimum_spanning_tree.hpp&gt;
  
  using namespace std;
  
  class EdgeWeight{
      public:
      EdgeWeight(){}
      EdgeWeight(int weightIn, int destinationIdIn){
          weight = weightIn;
          destinationId = destinationIdIn;
      }
  
          bool operator&lt;(const EdgeWeight&amp; rhs) const {
          if (weight &lt; rhs.weight)
              return true;
          else if(weight == rhs.weight){
              if (destinationId &lt; rhs.destinationId)
                  return true;
              else
                  return false;
          }
          else
              return false;
          }
  
      EdgeWeight operator+(const EdgeWeight&amp; 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 &lt; vecS, vecS, undirectedS, property&lt;vertex_distance_t, EdgeWeight&gt;,      property &lt; edge_weight_t, EdgeWeight &gt; &gt; Graph;
    typedef std::pair &lt; int, int &gt;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&lt;Graph, edge_weight_t&gt;::type weightmap = get(edge_weight, g);
    std::vector &lt; graph_traits &lt; Graph &gt;::vertex_descriptor &gt; p(num_vertices(g));
    prim_minimum_spanning_tree(g, &amp;p[0]);
  
    for (std::size_t i = 0; i != p.size(); ++i)
      if (p[i] != i)
        std::cout &lt;&lt; "parent[" &lt;&lt; i &lt;&lt; "] = " &lt;&lt; p[i] &lt;&lt; std::endl;
      else
        std::cout &lt;&lt; "parent[" &lt;&lt; i &lt;&lt; "] = no parent" &lt;&lt; std::endl;
  
    return EXIT_SUCCESS;
  }
  </code></pre>
  
  <p>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"</p>
  
  <p>Am I doing this the right way?  Is there a better way to do this?</p>
  
  <p><a href="http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/prim_minimum_spanning_tree.html" rel="nofollow">http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/prim_minimum_spanning_tree.html</a>
  http://www.boost.org/doc/libs/1_38_0/boost/graph/prim_minimum_spanning_tree.hpp</p>
  
  <p>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</p>
  
  <p>edit2: based on Jeremiah's reponse I changed the vertex_distance_t from int to EdgeWeight but got the same error</p>