00001
00002
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 );
00074
00075 bool has_triangles;
00076 buf.unpack(has_triangles);
00077 if (has_triangles)
00078 buf.unpack(ising_triangles, itmp, true );
00079
00080 buf.unpack(num_structure_type);
00081 if (num_structure_type > 0) {
00082 buf.unpack(num_switch_structures, itmp, true );
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 );
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 }