dmst.cc

#include <boost/foreach.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/iteration_macros.hpp>
#include <math.h>
#include <scil/scil.h>
#include <scil/constraints/path.h>
#include <stdlib.h>
#include <time.h>

using namespace boost;

//Vertex properties
struct vertex_properties {
   int x;
   int y;
   //trivial constructor
   vertex_properties() {}
   //constructor setting coordinates
   vertex_properties(int _x, int _y) {
      x = _x;
      y = _y;
   }
};

//Edge properties
struct edge_properties {
   double distance;
   /* back_edge is true this edge is a reverse edge (v,u) to an already
      existing edge (u,v) and will not be displayed in the output. The edge
      (v,u) is necessary because the constraint PATH used in function 
      ComputeDMST requires a directed graph. The edge (v,u) is not necessary for
      the output since Diameter_MST is a problem on undirected Graphs.
    */
   bool back_edge;
};

typedef adjacency_list<vecS, vecS, directedS, vertex_properties,
                       edge_properties> Graph;
typedef graph_traits<Graph>::edge_descriptor edge_descriptor;
typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor;

#include "compute_dmst.cc"

void make_complete(Graph &G) {
   //Add edges
   graph_traits<Graph>::vertex_iterator v_it, u_it, v_it_end, u_it_end;
   for(tie(v_it, v_it_end) = vertices(G); v_it != v_it_end; v_it++)
      for(tie(u_it, u_it_end) = vertices(G); u_it != u_it_end; u_it++)
         if (*u_it != * v_it) {
            edge_descriptor e = add_edge(*u_it, *v_it, G).first;
            // Set property back_edge to true if an edge (u,v) already exists
            G[e].back_edge = edge(*v_it, *u_it, G).second;
         }
}

void generate_graph(Graph &G) {
   int n;

   std::cout << "Please enter the number of nodes: ";
   std::cin >> n;
   std::cout << std::endl;

   //Assign random vertex coordinates
   srand(time(NULL));

   for(int i=0; i<n; i++) {
      vertex_properties vp((rand() % 20),(rand() % 20));
      add_vertex(vp, G);
   }
   make_complete(G);
}

//Calculate Euclidian distances for all edges
void calculate_edge_lengths(Graph &G) {
   BGL_FORALL_EDGES(e, G, Graph) {
      double xDifference = G[source(e,G)].x - G[target(e,G)].x;
      double yDifference = G[source(e,G)].y - G[target(e,G)].y;
      G[e].distance = sqrt(pow(xDifference,2)+pow(yDifference,2));
   }
}

int main() {
   Graph G;
   generate_graph(G);

   calculate_edge_lengths(G);

   std::list<edge_descriptor> T;
   ComputeDMST(G, T);

   //Generate Output

   std::cout << "Constructed Graph:\n";
   BGL_FORALL_EDGES(e, G, Graph) {
      //Do not display reverse edges
      if (!G[e].back_edge)
         printf("x1: %d y1: %d x2: %d y2: %d d: %f\n", G[source(e,G)].x,
                G[source(e,G)].y, G[target(e,G)].x, G[target(e,G)].y,
                G[e].distance);
   }

   std::cout << "\nDiameter_MST:\n";
   BOOST_FOREACH(edge_descriptor e, T) {
      //Swap output if e is a reverse edge
      if (!G[e].back_edge)
         printf("x1: %d y1: %d x2: %d y2: %d d: %f\n", G[source(e,G)].x, 
                G[source(e,G)].y, G[target(e,G)].x, G[target(e,G)].y,
                G[e].distance);
      else
         printf("x1: %d y1: %d x2: %d y2: %d d: %f\n", G[target(e,G)].x, 
                G[target(e,G)].y, G[source(e,G)].x, G[source(e,G)].y,
                G[e].distance);
   }
};

---