00001
00002
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
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
00091 int num_nodes;
00092 int num_edges;
00093
00094
00095 MC_graph_edge* edges;
00096 MC_graph_node* nodes;
00097 MC_adjacency_entry* all_adj_list;
00098
00099 bool ising_problem;
00100
00101 double sum_edge_weight;
00102 double scaling_factor;
00103
00104
00105 int* ising_four_cycles;
00106
00107 int* ising_triangles;
00108
00109 int num_structure_type;
00110 int * num_switch_structures;
00111 MC_switch_structure** switch_structures;
00112
00113
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
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
00156
00157 class MC_path_node {
00158 public:
00159 bool processed;
00160 int degree;
00161
00162 int parent;
00163
00164 int edge_to_parent;
00165
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