/home/coin/SVN-release/OS-2.4.2/Bcp/examples/MaxCut/Member/MC.cpp

Go to the documentation of this file.
00001 // Copyright (C) 2000, International Business Machines
00002 // Corporation and others.  All Rights Reserved.
00003 
00004 #include "BCP_buffer.hpp"
00005 
00006 #include "MC.hpp"
00007 #include <cmath>
00008 
00009 BCP_buffer&
00010 MC_problem::pack(BCP_buffer& buf)
00011 {
00012   int i, j;
00013   buf.pack(num_nodes).pack(num_edges);
00014   for (i = 0; i < num_edges; ++i) {
00015     buf.pack(edges[i].tail).pack(edges[i].head).pack(edges[i].cost);
00016   }
00017 
00018   const int grid = static_cast<int>(sqrt(num_nodes + 1.0));
00019   const int num_grid_nodes = grid * grid;
00020 
00021   buf.pack(ising_problem);
00022   const bool has_four_cycles = ising_four_cycles != NULL;
00023   buf.pack(has_four_cycles);
00024   if (has_four_cycles)
00025     buf.pack(ising_four_cycles, 4 * num_grid_nodes);
00026 
00027   const bool has_triangles = ising_triangles != NULL;
00028   buf.pack(has_triangles);
00029   if (has_triangles)
00030     buf.pack(ising_triangles, 6 * num_grid_nodes);
00031 
00032   buf.pack(num_structure_type);
00033   if (num_structure_type > 0) {
00034     buf.pack(num_switch_structures, num_structure_type);
00035     for (i = 0; i < num_structure_type; ++i) {
00036       const MC_switch_structure* sw_structs = switch_structures[i];
00037       for (j = 0; j < num_switch_structures[i]; ++j) {
00038         const int num_nodes_j = sw_structs[j].num_nodes;
00039         const int num_neighbors_j = sw_structs[j].num_neighbors;
00040         buf.pack(num_nodes_j).pack(num_neighbors_j);
00041         buf.pack(sw_structs[j].nodes, num_nodes_j + num_neighbors_j);
00042       }
00043     }
00044   }
00045 
00046   const bool has_feas_sol = feas_sol != 0;
00047   buf.pack(has_feas_sol);
00048   if (has_feas_sol) {
00049      buf.pack(feas_sol->sign, feas_sol->num_nodes)
00050         .pack(feas_sol->value, feas_sol->num_edges)
00051         .pack(feas_sol->cost);
00052   }
00053 
00054   return buf;
00055 }
00056 
00057 BCP_buffer&
00058 MC_problem::unpack(BCP_buffer& buf)
00059 {
00060   int i, j;
00061   buf.unpack(num_nodes).unpack(num_edges);
00062   edges = new MC_graph_edge[num_edges];
00063   for (i = 0; i < num_edges; ++i) {
00064     buf.unpack(edges[i].tail).unpack(edges[i].head).unpack(edges[i].cost);
00065   }
00066 
00067   int itmp;
00068 
00069   buf.unpack(ising_problem);
00070   bool has_four_cycles;
00071   buf.unpack(has_four_cycles);
00072   if (has_four_cycles)
00073     buf.unpack(ising_four_cycles, itmp, true /* allocate */);
00074 
00075   bool has_triangles;
00076   buf.unpack(has_triangles);
00077   if (has_triangles)
00078     buf.unpack(ising_triangles, itmp, true /* allocate */);
00079 
00080   buf.unpack(num_structure_type);
00081   if (num_structure_type > 0) {
00082     buf.unpack(num_switch_structures, itmp, true /* allocate */);
00083     switch_structures = new MC_switch_structure*[num_structure_type];
00084     for (i = 0; i < num_structure_type; ++i) {
00085       if (num_switch_structures[i] > 0) {
00086         switch_structures[i] =
00087           new MC_switch_structure[num_switch_structures[i]];
00088         int num_nodes_j;
00089         int num_neighbors_j;
00090         MC_switch_structure* sw_structs = switch_structures[i];
00091         for (j = 0; j < num_switch_structures[i]; ++j) {
00092           buf.unpack(num_nodes_j).unpack(num_neighbors_j);
00093           sw_structs[j].num_nodes = num_nodes_j;
00094           sw_structs[j].num_neighbors = num_neighbors_j;
00095           buf.unpack(sw_structs[j].nodes, itmp, true /* allocate */);
00096           sw_structs[j].neighbors = sw_structs[j].nodes + num_nodes_j;
00097         }
00098       }
00099     }
00100   }
00101 
00102 
00103   bool has_feas_sol;
00104   buf.unpack(has_feas_sol);
00105   if (has_feas_sol) {
00106      int n, m, *s;
00107      double c, *v;
00108      buf.unpack(s, n).unpack(v, m).unpack(c);
00109      feas_sol = new MC_feas_sol(c, n, s, m, v);
00110   }
00111   return buf;
00112 }
00113 
00114 void
00115 MC_problem::create_adj_lists()
00116 {
00117   int i;
00118 
00119   nodes = new MC_graph_node[num_nodes];
00120   for (i = 0; i < num_nodes; ++i)
00121     nodes[i].degree = 0;
00122   for (i = 0; i < num_edges; ++i) {
00123     ++nodes[edges[i].tail].degree;
00124     ++nodes[edges[i].head].degree;
00125   }
00126 
00127   all_adj_list = new MC_adjacency_entry[2 * num_edges];
00128 
00129   int total_degree = 0;
00130   for (i = 0; i < num_nodes; ++i) {
00131     nodes[i].adj_list = all_adj_list + total_degree;
00132     total_degree += nodes[i].degree;
00133   }
00134   
00135   for (i = 0; i < num_nodes; ++i)
00136     nodes[i].degree = 0;
00137 
00138   for (i = 0; i < num_edges; ++i) {
00139     const int t = edges[i].tail;
00140     const int h = edges[i].head;
00141     const double c = edges[i].cost;
00142     const int degt = nodes[t].degree;
00143     const int degh = nodes[h].degree;
00144     nodes[t].adj_list[degt].neighbor = h;
00145     nodes[h].adj_list[degh].neighbor = t;
00146     nodes[t].adj_list[degt].cost = c;
00147     nodes[h].adj_list[degh].cost = c;
00148     nodes[t].adj_list[degt].index = i;
00149     nodes[h].adj_list[degh].index = i;
00150     ++nodes[t].degree;
00151     ++nodes[h].degree;
00152   }
00153 }

Generated on Wed Nov 30 03:03:46 2011 by  doxygen 1.4.7