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

Go to the documentation of this file.
00001 // Copyright (C) 2000, International Business Machines
00002 // Corporation and others.  All Rights Reserved.
00003 #include <fstream>
00004 #include <algorithm>
00005 
00006 #include "BCP_tm.hpp"
00007 
00008 #include "MC_init.hpp"
00009 #include "MC_cut.hpp"
00010 #include "MC_tm.hpp"
00011 #include "MC_lp.hpp"
00012 
00013 //#############################################################################
00014 
00015 USER_initialize * BCP_user_init()
00016 {
00017    return new MC_initialize;
00018 }
00019 
00020 //#############################################################################
00021 
00022 BCP_user_pack*
00023 MC_initialize::packer_init(BCP_user_class* p)
00024 {
00025   return new MC_packer;
00026 }
00027 
00028 //-----------------------------------------------------------------------------
00029 
00030 void
00031 MC_packer::pack_cut_algo(const BCP_cut_algo* cut, BCP_buffer& buf)
00032 {
00033   const MC_cycle_cut* mc_cycle_cut = dynamic_cast<const MC_cycle_cut*>(cut);
00034   if (mc_cycle_cut) {
00035     mc_cycle_cut->pack(buf);
00036     return;
00037   }
00038   const MC_explicit_dense_cut* mc_dense_cut =
00039     dynamic_cast<const MC_explicit_dense_cut*>(cut);
00040   if (mc_dense_cut) {
00041     mc_dense_cut->pack(buf);
00042     return;
00043   }
00044   throw BCP_fatal_error("MC_packer::pack_cut_algo() : unknown cut type!\n");
00045 }
00046 
00047 //-----------------------------------------------------------------------------
00048 
00049 BCP_cut_algo*
00050 MC_packer::unpack_cut_algo(BCP_buffer& buf)
00051 {
00052   MC_cut_t type;
00053   buf.unpack(type);
00054   BCP_cut_algo* cut;
00055   switch (type) {
00056   case MC_cut_t__cycle: cut = new MC_cycle_cut(buf); break;
00057   case MC_cut_t__explicit_dense: cut = new MC_explicit_dense_cut(buf); break;
00058   default: throw BCP_fatal_error("\
00059 MC_packer::unpack_cut_algo() : unknown cut type!\n");
00060   }
00061   return cut;
00062 }
00063 
00064 //#############################################################################
00065 
00066 void MC_read_parameters(MC_tm& tm, const char * paramfile);
00067 void MC_readproblem(MC_tm& tm);
00068 
00069 //-----------------------------------------------------------------------------
00070 
00071 BCP_tm_user *
00072 MC_initialize::tm_init(BCP_tm_prob& p,
00073                        const int argnum, const char * const * arglist)
00074 {
00075    MC_tm* tm = new MC_tm;
00076 
00077    MC_read_parameters(*tm, arglist[1]);
00078    MC_readproblem(*tm);
00079 
00080    MC_problem &mc = tm->mc;
00081    if (mc.ising_problem) {
00082       const int grid = static_cast<int>(sqrt(mc.num_nodes + 1.0));
00083       const int num_grid_nodes = grid * grid;
00084       const bool has_extra_node = (mc.num_nodes != num_grid_nodes);
00085       const double granularity = has_extra_node ? .99 : 1.99;
00086       p.par.set_entry(BCP_tm_par::Granularity, granularity);
00087       p.slave_pars.lp.set_entry(BCP_lp_par::Granularity, granularity);
00088    }
00089 
00090    return tm;
00091 }
00092 
00093 //-----------------------------------------------------------------------------
00094 
00095 BCP_lp_user *
00096 MC_initialize::lp_init(BCP_lp_prob& p)
00097 {
00098    MC_lp* lp = new MC_lp;
00099    return lp;
00100 }
00101 
00102 //#############################################################################
00103 
00104 void MC_read_parameters(MC_tm& tm, const char * paramfile)
00105 {
00106    tm.tm_par.read_from_file(paramfile);
00107    tm.lp_par.read_from_file(paramfile);
00108 }
00109 
00110 //#############################################################################
00111 
00112 int
00113 MC_components(const int n, const int m, const MC_graph_edge* edges,
00114               int* component)
00115 {
00116   // See the MC_kruskal.cpp file.
00117   // This is the same algorithm, just here we don't need all those things that
00118   // are computed there
00119   int * first_on_chain = component;
00120   int * last_on_chain = new int[n];
00121   int * next_on_chain = new int[n];
00122   int * size_of_chain = new int[n];
00123 
00124   CoinIotaN(first_on_chain, n, 0);
00125   CoinIotaN(last_on_chain, n, 0);
00126   CoinFillN(next_on_chain, n, -1);
00127   CoinFillN(size_of_chain, n, 1);
00128 
00129   int tree_size = 0;
00130 
00131   int label_s = -1; // shorter chain head
00132   int label_l = -1; // longer chain head
00133   for (int k = 0; k < m; ++k) {
00134     const int i = edges[k].tail;
00135     const int j = edges[k].head;
00136     const int label_i = first_on_chain[i];
00137     const int label_j = first_on_chain[j];
00138     if (label_i == label_j)
00139       continue;
00140     if (size_of_chain[label_i] > size_of_chain[label_j]) {
00141       label_s = label_j;
00142       label_l = label_i;
00143     } else {
00144       label_s = label_i;
00145       label_l = label_j;
00146     }
00147     ++tree_size;
00148     for (int l = label_s; l != -1; l = next_on_chain[l]) {
00149       first_on_chain[l] = label_l;
00150     }
00151     next_on_chain[last_on_chain[label_l]] = label_s;
00152     last_on_chain[label_l] = last_on_chain[label_s];
00153     size_of_chain[label_l] += size_of_chain[label_s];
00154   }
00155   
00156   delete[] last_on_chain;
00157   delete[] next_on_chain;
00158   delete[] size_of_chain;
00159 
00160   return tree_size;
00161 }
00162 
00163 //#############################################################################
00164 
00165 static void
00166 MC_fill_structure(const MC_problem& mc, MC_switch_structure& swstruct,
00167                   const int num_nodes, const int * nodes)
00168 {
00169   const int * nodes_end = nodes + num_nodes;
00170   // count the edges going to real neighbors
00171   int outedges = 0;
00172   int i, j;
00173   for (i = 0; i < num_nodes; ++i) {
00174     MC_adjacency_entry* adj_list = mc.nodes[nodes[i]].adj_list;
00175     for (j = mc.nodes[nodes[i]].degree - 1; j >= 0; --j) {
00176       if (std::find(nodes, nodes_end, adj_list[j].neighbor) == nodes_end)
00177         ++outedges;
00178     }
00179   }
00180   swstruct.num_nodes = num_nodes;
00181   swstruct.num_neighbors = outedges;
00182   swstruct.nodes = new int[num_nodes + outedges];
00183   swstruct.neighbors = swstruct.nodes + num_nodes;
00184   CoinDisjointCopyN(nodes, num_nodes, swstruct.nodes);
00185   outedges = 0;
00186   for (i = 0; i < num_nodes; ++i) {
00187     MC_adjacency_entry* adj_list = mc.nodes[nodes[i]].adj_list;
00188     for (j = mc.nodes[nodes[i]].degree - 1; j >= 0; --j) {
00189       if (std::find(nodes, nodes_end, adj_list[j].neighbor) == nodes_end)
00190         swstruct.neighbors[outedges++] = adj_list[j].index;
00191     }
00192   }
00193 }
00194 
00195 //#############################################################################
00196 
00197 typedef std::pair<int,int> intpair;
00198 
00199 static inline bool
00200 operator<(const intpair& ip0, const intpair& ip1)
00201 {
00202   return ((ip0.first < ip1.first) ||
00203           ((ip0.first == ip1.first) && (ip0.second < ip1.second)));
00204 }
00205 
00206 void MC_readproblem(MC_tm& tm)
00207 {
00208   int i, j, k;
00209   MC_problem &mc = tm.mc;
00210 
00211   std::ifstream file(tm.tm_par.entry(MC_tm_par::InputFile).c_str());
00212   if (! file) {
00213     throw BCP_fatal_error("Can't open input file!\n");
00214   }
00215 
00216   char line[1000];
00217 
00218   double rescale = 1;
00219   for (int lose = tm.tm_par.entry(MC_tm_par::DigitsToLose); lose > 0; --lose) {
00220      rescale *= 10.0;
00221   }
00222 
00223   file.getline(line, 999);
00224   int len = strlen(line);
00225   if (strncmp(line, "DESC: ggrid", CoinMin(len, 11)) == 0) {
00226      // Ising problem generated by ggrid. Parse the info.
00227      mc.ising_problem = true;
00228      printf("Ising problem detected.\n");
00229      file.getline(line, 999);
00230      sscanf(line, "DESC: scaling: %lf", &mc.scaling_factor);
00231      mc.scaling_factor /= rescale;
00232   }
00233   while (strncmp(line, "DESC:", CoinMin(len, 5)) == 0) {
00234      file.getline(line, 999);
00235   }
00236 
00237   sscanf(line, "%i%i", &mc.num_nodes, &mc.num_edges);
00238 
00239   const int n = mc.num_nodes;
00240   const int m = mc.num_edges;
00241   // this will be definitely enough, even for new edges to connect
00242   // disconnected components.
00243   mc.edges = new MC_graph_edge[m + n];
00244 
00245   std::map<intpair, int> edge_map;
00246 
00247   double cost;
00248   intpair ip;
00249   for (i = 0, k = 0; i < m; ++i) {
00250     file.getline(line, 999);
00251     sscanf(line, "%i%i%lf", &ip.first, &ip.second, &cost);
00252     if (ip.first < 0 || ip.first >= n || ip.second < 0 || ip.second >= n ||
00253         (ip.first == ip.second)) {
00254       char errmsg[200];
00255       sprintf(errmsg, " bad endnodes %i %i\n", ip.first, ip.second);
00256       throw BCP_fatal_error(errmsg);
00257     }
00258     if (ip.first > ip.second)
00259       std::swap(ip.first, ip.second);
00260     const std::map<intpair, int>::const_iterator em = edge_map.find(ip);
00261     if (em != edge_map.end()) {
00262       printf("Warning: edge (%i,%i) appears once again.\n",
00263              ip.first, ip.second);
00264       printf("         Collapsing the parallel edges.\n");
00265       mc.edges[em->second].cost += cost;
00266     } else {
00267       edge_map[ip] = k;
00268       mc.edges[k].tail = ip.first;
00269       mc.edges[k].head = ip.second;
00270       mc.edges[k++].cost = cost;
00271     }
00272   }
00273   mc.num_edges = k;
00274 
00275   file.close();
00276 
00277   // throw out the 0 cost edges if it's not an ising problem. For ising
00278   // problems it's worth to keep the 0 cost edges because then the structure
00279   // is preserved.
00280   if (! mc.ising_problem) {
00281     for (i = 0, k = 0; i < mc.num_edges; ++i) {
00282       if (mc.edges[i].cost == 0.0) {
00283         printf("Warning: Discarded edge (%i,%i) as it has final cost 0.\n",
00284                mc.edges[i].tail, mc.edges[i].head);
00285       } else {
00286         mc.edges[k].tail =  mc.edges[i].tail;
00287         mc.edges[k].head =  mc.edges[i].head;
00288         mc.edges[k++].cost =  mc.edges[i].cost;
00289       }
00290     }
00291     mc.num_edges = k;
00292 
00293     // Check connectivity
00294     int * components = new int[mc.num_nodes];
00295     const int comp_num =
00296       mc.num_nodes - MC_components(mc.num_nodes, mc.num_edges,
00297                                    mc.edges, components);
00298     if (comp_num > 1) {
00299       printf("There are %i components in the graph. Adding 0 cost edges.\n",
00300              comp_num);
00301       std::set<int> seen;
00302       seen.insert(components[0]);
00303       for (i = 0; i < mc.num_nodes; ++i) {
00304         if (seen.find(components[i]) == seen.end()) {
00305           // not seen component. connect it
00306           mc.edges[mc.num_edges].tail = 0;
00307           mc.edges[mc.num_edges].head = i;
00308           mc.edges[mc.num_edges++].cost = 0;
00309           seen.insert(components[i]);
00310         }
00311       }
00312     }
00313     delete[] components;
00314   }
00315 
00316   // rescale the edges
00317   for (i = 0; i < mc.num_edges; ++i) {
00318      const double c = mc.edges[i].cost;
00319      mc.edges[i].cost = floor(c / rescale + 0.5);
00320   }
00321   
00322 
00323   // Negate the cost of the edges (minimizing!) and compute their sum
00324   mc.sum_edge_weight = 0;
00325   for (i = 0; i < mc.num_edges; ++i) {
00326     const double c = - mc.edges[i].cost;
00327     mc.edges[i].cost = c;
00328     mc.sum_edge_weight += c;
00329   }
00330 
00331   mc.create_adj_lists();
00332 
00333   if (mc.ising_problem) {
00334     const int grid = static_cast<int>(sqrt(mc.num_nodes + 1.0));
00335     const int num_grid_nodes = grid * grid;
00336     const int num_grid_edges = 2 * num_grid_nodes;
00337     const int vertical = num_grid_nodes;
00338     {
00339       // enumerate the 4-cycles
00340       mc.ising_four_cycles = new int[num_grid_nodes * 4];
00341       int * cycle = mc.ising_four_cycles;
00342       for (i = 0; i < grid; ++i) {
00343         for (j = 0; j < grid; ++j) {
00344           // (i,j) -> (i,j+1)
00345           cycle[0] = i*grid + j;
00346           // (i,j+1) -> (i+1,j+1)
00347           cycle[1] = vertical + i*grid + ((j+1) % grid);
00348           // (i+1,j) -> (i+1,j+1)
00349           cycle[2] = ((i+1) % grid) * grid + j;
00350           // (i,j) -> (i+1,j)
00351           cycle[3] = vertical + i*grid + j;
00352           cycle += 4;
00353         }
00354       }
00355     }
00356 
00357     const bool has_extra_node = (mc.num_nodes != num_grid_nodes);
00358     if (has_extra_node) {
00359       // enumerate the triangles
00360       mc.ising_triangles = new int[2 * num_grid_nodes * 3];
00361       int * triangle = mc.ising_triangles;
00362       for (i = 0; i < grid; ++i) {
00363         for (j = 0; j < grid; ++j) {
00364           // (i,j) -> (i,j+1) -> extra_node ->
00365           triangle[0] = i*grid + j;
00366           triangle[1] = num_grid_edges + i*grid + j;
00367           triangle[2] = num_grid_edges + i*grid + ((j+1) % grid);
00368           if (triangle[1] > triangle[2])
00369             std::swap(triangle[1], triangle[2]);
00370           triangle += 3;
00371           // (i,j) -> (i+1,j) -> extra_node ->
00372           triangle[0] = vertical + i*grid + j;
00373           triangle[1] = num_grid_edges + i*grid + j;
00374           triangle[2] = num_grid_edges + ((i+1) % grid) * grid + j;
00375           if (triangle[1] > triangle[2])
00376             std::swap(triangle[1], triangle[2]);
00377           triangle += 3;
00378         }
00379       }
00380     }
00381 
00382     mc.num_structure_type = 5;
00383 
00384     mc.num_switch_structures = new int[mc.num_structure_type];
00385     mc.switch_structures = new MC_switch_structure*[mc.num_structure_type];
00386 
00387     // three-node connected structures
00388     {
00389       mc.num_switch_structures[0] = num_grid_nodes * 6;
00390       mc.switch_structures[0] = new MC_switch_structure[num_grid_nodes * 6];
00391       MC_switch_structure * next_struct = mc.switch_structures[0];
00392 
00393       int nodes[3];
00394 
00395       // enumerate the outgoing edges of three long chains
00396       for (i = 0; i < grid; ++i) {
00397         for (j = 0; j < grid; ++j) {
00398           //-------------------------------------------------------------------
00399           // the three nodes: (i-1,j), (i,j), (i+1,j)
00400           //  |
00401           //  |
00402           nodes[0] = ((i+grid-1)%grid) * grid + j;
00403           nodes[1] = i * grid + j;
00404           nodes[2] = ((i+1)%grid) * grid + j;
00405           MC_fill_structure(mc, *next_struct, 3, nodes);
00406           if (next_struct->num_neighbors != 8 + (has_extra_node ? 3 : 0))
00407             abort();
00408           ++next_struct;
00409 
00410           //-------------------------------------------------------------------
00411           // the three nodes: (i,j-1), (i,j), (i,j+1)
00412           //  --
00413           nodes[0] = i * grid + ((j+grid-1)%grid);
00414           nodes[1] = i * grid + j;
00415           nodes[2] = i * grid + ((j+1)%grid);
00416           MC_fill_structure(mc, *next_struct, 3, nodes);
00417           if (next_struct->num_neighbors != 8 + (has_extra_node ? 3 : 0))
00418             abort();
00419           ++next_struct;
00420 
00421           //-------------------------------------------------------------------
00422           // the three nodes: (i-1,j), (i,j), (i,j+1)
00423           //  |_
00424           nodes[0] = ((i+grid-1)%grid) * grid + j;
00425           nodes[1] = i * grid + j;
00426           nodes[2] = i * grid + ((j+1)%grid);
00427           MC_fill_structure(mc, *next_struct, 3, nodes);
00428           if (next_struct->num_neighbors != 8 + (has_extra_node ? 3 : 0))
00429             abort();
00430           ++next_struct;
00431 
00432           //-------------------------------------------------------------------
00433           // (i,j+1), (i,j), (i+1,j)
00434           //   _
00435           //  |
00436           nodes[0] = i * grid + ((j+1)%grid);
00437           nodes[1] = i * grid + j;
00438           nodes[2] = ((i+1)%grid) * grid + j;
00439           MC_fill_structure(mc, *next_struct, 3, nodes);
00440           if (next_struct->num_neighbors != 8 + (has_extra_node ? 3 : 0))
00441             abort();
00442           ++next_struct;
00443 
00444           //-------------------------------------------------------------------
00445           // the three nodes: (i+1,j), (i,j), (i,j-1)
00446           //  _
00447           //   |
00448           nodes[0] = ((i+1)%grid) * grid + j;
00449           nodes[1] = i * grid + j;
00450           nodes[2] = i * grid + ((j+grid-1)%grid);
00451           MC_fill_structure(mc, *next_struct, 3, nodes);
00452           if (next_struct->num_neighbors != 8 + (has_extra_node ? 3 : 0))
00453             abort();
00454           ++next_struct;
00455 
00456           //-------------------------------------------------------------------
00457           // the three nodes: (i,j-1), (i,j), (i-1,j)
00458           //  _|
00459           nodes[0] = i * grid + ((j+grid-1)%grid);
00460           nodes[1] = i * grid + j;
00461           nodes[2] = ((i+grid-1)%grid) * grid + j;
00462           MC_fill_structure(mc, *next_struct, 3, nodes);
00463           if (next_struct->num_neighbors != 8 + (has_extra_node ? 3 : 0))
00464             abort();
00465           ++next_struct;
00466         }
00467       }
00468     }
00469 
00470     //=========================================================================
00471 
00472     // different four-node connected structures
00473 
00474     // first
00475     {
00476       mc.num_switch_structures[1] = 4 * num_grid_nodes;
00477       mc.switch_structures[1] = new MC_switch_structure[4 * num_grid_nodes];
00478       MC_switch_structure * next_struct = mc.switch_structures[1];
00479 
00480       int nodes[4];
00481 
00482       // List the outgoing edges from every square
00483       for (i = 0; i < grid; ++i) {
00484         for (j = 0; j < grid; ++j) {
00485           // _|_
00486           nodes[0] = i * grid + j;
00487           nodes[1] = i * grid + ((j-1+grid)%grid);
00488           nodes[2] = ((i-1+grid)%grid) * grid + j;
00489           nodes[3] = i * grid + ((j+1)%grid);
00490           MC_fill_structure(mc, *next_struct, 4, nodes);
00491           if (next_struct->num_neighbors != 10 + (has_extra_node ? 4 : 0))
00492             abort();
00493           ++next_struct;
00494 
00495           // |_
00496           // |
00497           nodes[0] = i * grid + j;
00498           nodes[1] = ((i-1+grid)%grid) * grid + j;
00499           nodes[2] = i * grid + ((j+1)%grid);
00500           nodes[3] = ((i+1)%grid) * grid + j;
00501           MC_fill_structure(mc, *next_struct, 4, nodes);
00502           if (next_struct->num_neighbors != 10 + (has_extra_node ? 4 : 0))
00503             abort();
00504           ++next_struct;
00505 
00506           // _ _
00507           //  |
00508           nodes[0] = i * grid + j;
00509           nodes[1] = i * grid + ((j+1)%grid);
00510           nodes[2] = ((i+1)%grid) * grid + j;
00511           nodes[3] = i * grid + ((j-1+grid)%grid);
00512           MC_fill_structure(mc, *next_struct, 4, nodes);
00513           if (next_struct->num_neighbors != 10 + (has_extra_node ? 4 : 0))
00514             abort();
00515           ++next_struct;
00516 
00517           // _|
00518           //  |
00519           nodes[0] = i * grid + j;
00520           nodes[1] = ((i+1)%grid) * grid + j;
00521           nodes[2] = i * grid + ((j-1+grid)%grid);
00522           nodes[3] = ((i-1+grid)%grid) * grid + j;
00523           MC_fill_structure(mc, *next_struct, 4, nodes);
00524           if (next_struct->num_neighbors != 10 + (has_extra_node ? 4 : 0))
00525             abort();
00526           ++next_struct;
00527         }
00528       }
00529     }
00530     //-------------------------------------------------------------------------
00531     // second
00532     {
00533       mc.num_switch_structures[2] = 4 * num_grid_nodes;
00534       mc.switch_structures[2] = new MC_switch_structure[4 * num_grid_nodes];
00535       MC_switch_structure * next_struct = mc.switch_structures[2];
00536 
00537       int nodes[4];
00538 
00539       for (i = 0; i < grid; ++i) {
00540         for (j = 0; j < grid; ++j) {
00541           //   _
00542           // _|
00543           nodes[0] = i * grid + j;
00544           nodes[1] = i * grid + ((j+1)%grid);
00545           nodes[2] = ((i-1+grid)%grid) * grid + ((j+1)%grid);
00546           nodes[3] = ((i-1+grid)%grid) * grid + ((j+2)%grid);
00547           MC_fill_structure(mc, *next_struct, 4, nodes);
00548           if (next_struct->num_neighbors != 10 + (has_extra_node ? 4 : 0))
00549             abort();
00550           ++next_struct;
00551 
00552           // _
00553           //  |_
00554           nodes[0] = i * grid + j;
00555           nodes[1] = i * grid + ((j+1)%grid);
00556           nodes[2] = ((i+1)%grid) * grid + ((j+1)%grid);
00557           nodes[3] = ((i+1)%grid) * grid + ((j+2)%grid);
00558           MC_fill_structure(mc, *next_struct, 4, nodes);
00559           if (next_struct->num_neighbors != 10 + (has_extra_node ? 4 : 0))
00560             abort();
00561           ++next_struct;
00562 
00563           // |_
00564           //   |
00565           nodes[0] = i * grid + j;
00566           nodes[1] = ((i+1)%grid) * grid + j;
00567           nodes[2] = ((i+1)%grid) * grid + ((j+1)%grid);
00568           nodes[3] = ((i+2)%grid) * grid + ((j+1)%grid);
00569           MC_fill_structure(mc, *next_struct, 4, nodes);
00570           if (next_struct->num_neighbors != 10 + (has_extra_node ? 4 : 0))
00571             abort();
00572           ++next_struct;
00573 
00574           //  _|
00575           // |
00576           nodes[0] = i * grid + j;
00577           nodes[1] = ((i+1)%grid) * grid + j;
00578           nodes[2] = ((i+1)%grid) * grid + ((j-1+grid)%grid);
00579           nodes[3] = ((i+2)%grid) * grid + ((j-1+grid)%grid);
00580           MC_fill_structure(mc, *next_struct, 4, nodes);
00581           if (next_struct->num_neighbors != 10 + (has_extra_node ? 4 : 0))
00582             abort();
00583           ++next_struct;
00584         }
00585       }
00586     }
00587     //-------------------------------------------------------------------------
00588     // third
00589     {
00590       mc.num_switch_structures[3] = num_grid_nodes;
00591       mc.switch_structures[3] = new MC_switch_structure[num_grid_nodes];
00592       MC_switch_structure * next_struct = mc.switch_structures[3];
00593 
00594       int nodes[4];
00595 
00596       for (i = 0; i < grid; ++i) {
00597         for (j = 0; j < grid; ++j) {
00598           // the square is (i,j), (i,j+1), (i+1,j+1), (i+1,j)
00599           //  _
00600           // |_|
00601           nodes[0] = i * grid + j;
00602           nodes[1] = i * grid + ((j+1)%grid);
00603           nodes[2] = ((i+1)%grid) * grid + ((j+1)%grid);
00604           nodes[3] = ((i+1)%grid) * grid + j;
00605           MC_fill_structure(mc, *next_struct, 4, nodes);
00606           if (next_struct->num_neighbors != 8 + (has_extra_node ? 4 : 0))
00607             abort();
00608           ++next_struct;
00609         }
00610       }
00611     }
00612 
00613     //=========================================================================
00614 
00615     // a 6-node connected structures
00616 
00617     {
00618       mc.num_switch_structures[4] = 2 * num_grid_nodes;
00619       mc.switch_structures[4] = new MC_switch_structure[2 * num_grid_nodes];
00620       MC_switch_structure * next_struct = mc.switch_structures[4];
00621 
00622       int nodes[6];
00623 
00624       for (i = 0; i < grid; ++i) {
00625         for (j = 0; j < grid; ++j) {
00626           //  _ _
00627           // |_|_|
00628           nodes[0] = i * grid + j;
00629           nodes[1] = i * grid + ((j+1)%grid);
00630           nodes[2] = i * grid + ((j+2)%grid);
00631           nodes[3] = ((i+1)%grid) * grid + j;
00632           nodes[4] = ((i+1)%grid) * grid + ((j+1)%grid);
00633           nodes[5] = ((i+1)%grid) * grid + ((j+2)%grid);
00634           MC_fill_structure(mc, *next_struct, 6, nodes);
00635           if (next_struct->num_neighbors != 10 + (has_extra_node ? 6 : 0))
00636             abort();
00637           ++next_struct;
00638 
00639           //  _ 
00640           // |_|
00641           // |_|
00642           nodes[0] = i * grid + j;
00643           nodes[1] = i * grid + ((j+1)%grid);
00644           nodes[2] = ((i+1)%grid) * grid + j;
00645           nodes[3] = ((i+1)%grid) * grid + ((j+1)%grid);
00646           nodes[4] = ((i+2)%grid) * grid + j;
00647           nodes[5] = ((i+2)%grid) * grid + ((j+1)%grid);
00648           MC_fill_structure(mc, *next_struct, 6, nodes);
00649           if (next_struct->num_neighbors != 10 + (has_extra_node ? 6 : 0))
00650             abort();
00651           ++next_struct;
00652         }
00653       }
00654     }
00655   }
00656 
00657   if (tm.tm_par.entry(MC_tm_par::FeasSolFile).length() > 0) {
00658      std::ifstream solfile(tm.tm_par.entry(MC_tm_par::FeasSolFile).c_str());
00659      if (! solfile) {
00660         throw BCP_fatal_error("Can't open feas solution file!\n");
00661      }
00662      int* s = new int[mc.num_nodes];
00663      for (i = 0; i < mc.num_nodes; ++i) {
00664         solfile.getline(line, 999);
00665         sscanf(line, "%i", s+i);
00666      }
00667      solfile.close();
00668      mc.feas_sol = new MC_feas_sol(mc.num_nodes, s, mc.num_edges, mc.edges);
00669      printf("\nMC: value of input solution: %.0f\n\n", mc.feas_sol->cost);
00670   }
00671 }

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