Diameter_Constraint_Minimum_Spanning_Tree

This example solves a diameter constrained minimum spanning tree problem which objective is to construct a connected graph with minimum edge length.

First we create a complete graph in generate_graph. The number of nodes is specified by the user. After this the edge lenghts are measured with euclidian distances in calculate_edge_lengths.

In the following we create a new instance IP if an SCIL::ILP_Problem as a minimazation problem and construct an auxiliary graph H.

[...]

Next we create a new instance of the symbolic constraint PATH. Its template parameter describes the used graph type. The other parameters are Graph H, the vertex_descriptor u associated with the startnode of the path, the vertex_descriptor v associated with the endvertex of the path and the var_map<edge_descriptor> VM.

We solve the model IP by the command IP.optimize(). This command starts optimization process.

Then we access the solution found by the function IP.optimize and add all edge_descriptor e associated with edges in the minimum spanning tree to the std::list<edge_descriptor> T. Finally we print the edges forming the input graph and the edges in the minimum spanning tree to stdout omitting reverse edges.

#define K 4
using namespace SCIL;

void ComputeDMST(Graph& G, std::list<edge_descriptor>& T) {

   ILP_Problem IP(Optsense_Min);

   Graph H;

   std::map<vertex_descriptor, vertex_descriptor> GtoH[K];

   var_map<edge_descriptor> VM;
   map<edge_descriptor, std::pair<bool, edge_descriptor> > EM;
   BGL_FORALL_VERTICES(u, G, Graph) {
      for(int i=0; i<K; i++) { 
         GtoH[i][u] = add_vertex(H);
         if(i != 0) {
            edge_descriptor f = (add_edge(GtoH[i-1][u], GtoH[i][u], H)).first;
            VM[f] = IP.add_binary_variable(0);
            EM[f] = std::pair<bool, edge_descriptor>(0,f);
         }
      }
   }

   BGL_FORALL_EDGES(e, G, Graph) {
      for(int i=1; i<K; i++) {
         edge_descriptor f = (add_edge(GtoH[i-1][source(e, G)],
                                       GtoH[i][target(e, G)], H)).first;
         VM[f] = IP.add_binary_variable(G[e].distance);
         EM[f] = std::pair<bool, edge_descriptor>(1,e);
      }
   }

   vertex_descriptor s=GtoH[0][*(vertices(G).first)];
   BGL_FORALL_VERTICES(u, G, Graph) {
      IP.add_sym_constraint(new PATH<Graph>(H, s, GtoH[K-1][u], VM));
   }

   IP.optimize();

   BGL_FORALL_EDGES(e, H, Graph)
      if(EM[e].first && (IP.get_solution(VM[e])==1))
         T.push_back(EM[e].second);
}

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);
   }
};