/home/coin/SVN-release/Bcp-1.2.1/Applications/MaxCut/include/MC.hpp

Go to the documentation of this file.
00001 // Copyright (C) 2000, International Business Machines
00002 // Corporation and others.  All Rights Reserved.
00003 #ifndef _MC_H
00004 #define _MC_H
00005 
00006 #include "BCP_vector.hpp"
00007 
00008 class BCP_buffer;
00009 
00010 class MC_adjacency_entry {
00011 public:
00012     int neighbor;
00013     int index;
00014     double cost;
00015     MC_adjacency_entry() : neighbor(-1), cost(0.0) {}
00016     MC_adjacency_entry(int n, double c) : neighbor(n), cost(c) {}
00017 };
00018 
00019 class MC_graph_node {
00020 public:
00021     int degree;
00022     MC_adjacency_entry* adj_list;
00023     MC_graph_node() : degree(-1), adj_list(0) {}
00024     MC_graph_node(int d, MC_adjacency_entry* l) : degree(d), adj_list(l) {}
00025 };
00026 
00027 class MC_graph_edge {
00028 public:
00029     int tail;
00030     int head;
00031     double cost;
00032 public:
00033     MC_graph_edge() : tail(-1), head(-1), cost(0.0) {}
00034     MC_graph_edge(int t, int h, double c) : tail(t), head(h), cost(c) {}
00035 };
00036 
00037 class MC_switch_structure {
00038 private:
00039     MC_switch_structure(const MC_switch_structure&);
00040     MC_switch_structure& operator=(const MC_switch_structure&);
00041 public:
00042     int num_nodes;
00043     int num_neighbors;
00044     int * nodes;
00045     int * neighbors;
00046     MC_switch_structure() :
00047         num_nodes(0), num_neighbors(0), nodes(0), neighbors(0) {}
00048     ~MC_switch_structure() {
00049         delete[] nodes;
00050         // neighbors is the second part of the nodes array
00051     }
00052 };
00053 
00054 class MC_feas_sol {
00055 public:
00056     double cost;
00057     int num_nodes;
00058     int* sign;
00059     int num_edges;
00060     double* value;
00061     MC_feas_sol(const int nnodes, int*& s,
00062                 const int nedges, const MC_graph_edge* edges) :
00063         num_nodes(nnodes),
00064         sign(s),
00065         num_edges(nedges),
00066         value(new double[nedges])
00067     {
00068         cost = 0;
00069         for (int i = 0; i < nedges; ++i) {
00070             value[i] = sign[edges[i].tail] == sign[edges[i].head] ? 0 : 1;
00071             cost += value[i] * edges[i].cost;
00072         }
00073         s = 0;
00074     }
00075     MC_feas_sol(const double c,
00076                 const int nnodes, int*& s,
00077                 const int nedges, double*& v) :
00078         cost(c), num_nodes(nnodes), sign(s), num_edges(nedges), value(v) {
00079         s = 0;
00080         v = 0;
00081     }
00082     ~MC_feas_sol() {
00083         delete[] value;
00084         delete[] sign;
00085     }
00086 };
00087 
00088 class MC_problem {
00089 public:
00090     // This data relates to the regular graph
00091     int num_nodes;
00092     int num_edges;
00093     // These arrays are constant arrays, better have them as real arrays
00094     // instead of BCP_vec's
00095     MC_graph_edge* edges;
00096     MC_graph_node* nodes;
00097     MC_adjacency_entry* all_adj_list;
00098 
00099     bool ising_problem;
00100     // These data members are used only if an Ising problem is solved
00101     double sum_edge_weight;
00102     double scaling_factor;
00103 
00104     // the squares of the grid
00105     int* ising_four_cycles;
00106     // the triangles if there is an external magnetic point
00107     int* ising_triangles;
00108 
00109     int num_structure_type;
00110     int * num_switch_structures;
00111     MC_switch_structure** switch_structures;
00112 
00113     // for testing we can read in a feas soln
00114     MC_feas_sol* feas_sol;
00115 
00116 public:
00117     MC_problem() :
00118         num_nodes(0), num_edges(0), edges(0), nodes(0), all_adj_list(0),
00119         ising_problem(false), sum_edge_weight(0.0), scaling_factor(1.0),
00120         ising_four_cycles(0), ising_triangles(0),
00121         num_structure_type(0), num_switch_structures(0), switch_structures(0),
00122         feas_sol(0)
00123     {}
00124     ~MC_problem() {
00125         delete[] edges;
00126         delete[] nodes;
00127         delete[] all_adj_list;
00128         delete[] ising_four_cycles;
00129         delete[] ising_triangles;
00130         for (int i = 0; i < num_structure_type; ++i) {
00131             delete[] switch_structures[i];
00132         }
00133         delete[] switch_structures;
00134         delete[] num_switch_structures;
00135         delete feas_sol;
00136     }
00137 
00138     void create_adj_lists();
00139     BCP_buffer& pack(BCP_buffer& buf);
00140     BCP_buffer& unpack(BCP_buffer& buf);
00141 };
00142 
00143 //#############################################################################
00144 
00145 // A class to hold adjacency entries during shortest path computation
00146 
00147 class MC_path_adj_entry {
00148 public:
00149     int neighbor;
00150     int orig_edge;
00151     double cost;
00152     MC_path_adj_entry() : neighbor(-1), orig_edge(-1), cost(0.0) {}
00153 };
00154 
00155 // A class to hold nodes during shortest path computation
00156 
00157 class MC_path_node {
00158 public:
00159     bool processed;
00160     int degree;
00161     // the predecessor node in the shortest path tree
00162     int parent;
00163     // the edge (in the original edge list!) to the parent node
00164     int edge_to_parent;
00165     // distance from the root node
00166     double distance;
00167     MC_path_adj_entry* adj_list;
00168 
00169     MC_path_node() : processed(false), degree(-1), parent(-1),
00170                      edge_to_parent(-1), distance(-1.0), adj_list(0) {}
00171 };
00172 
00173 //#############################################################################
00174 
00175 struct MC_path_node_ptr_compare {
00176     inline bool operator() (const MC_path_node* node0,
00177                             const MC_path_node* node1) {
00178         return node0->distance < node1->distance;
00179     }
00180 };
00181 
00182 #endif

Generated on Thu Jan 15 03:00:58 2009 for coin-Bcp by  doxygen 1.4.7