37 #ifndef GCG_ROWGRAPH_WEIGHTED_DEF_H_
38 #define GCG_ROWGRAPH_WEIGHTED_DEF_H_
62 this->
name = string(
"rowgraph_weighted");
90 assert(conss != NULL);
96 this->nconss = nconss_;
98 SCIP_CALL( this->graph.addNNodes(this->nconss) );
101 for( i = 0; i < this->nconss; ++i )
106 SCIP_CALL( SCIPgetConsNVars(this->scip_, conss[i], &ncurvars1, &success) );
115 SCIP_CALL( SCIPallocBufferArray(this->scip_, &curvars1, ncurvars1) );
116 SCIP_CALL( SCIPgetConsVars(this->scip_, conss[i], curvars1, ncurvars1, &success) );
120 for( j = 0; j < i; ++j )
124 SCIP_CALL( SCIPgetConsNVars(this->scip_, conss[j], &ncurvars2, &success) );
134 SCIP_CALL( SCIPallocBufferArray(this->scip_, &curvars2, ncurvars2) );
135 SCIP_CALL( SCIPgetConsVars(this->scip_, conss[j], curvars2, ncurvars2, &success) );
145 for( k = 0; k < ncurvars1; ++k )
153 if( SCIPgetStage(this->scip_) >= SCIP_STAGE_TRANSFORMED)
154 var1 = SCIPvarGetProbvar(curvars1[k]);
158 assert(var1 != NULL);
159 varIndex1 = SCIPvarGetProbindex(var1);
160 assert(varIndex1 >= 0);
161 assert(varIndex1 < this->nvars);
163 for( l = 0; l < ncurvars2; ++l )
171 if( SCIPgetStage(this->scip_) >= SCIP_STAGE_TRANSFORMED)
172 var2 = SCIPvarGetProbvar(curvars2[l]);
176 assert(var2 != NULL);
177 varIndex2 = SCIPvarGetProbindex(var2);
178 assert(varIndex2 >= 0);
179 assert(varIndex2 < this->nvars);
181 if(varIndex1 == varIndex2)
194 double edge_weight = calculateSimilarity(a, b, c, dist, w_type, i==j);
195 this->graph.addEdge(i, j, edge_weight);
198 SCIPfreeBufferArray(this->scip_, &curvars2);
200 SCIPfreeBufferArray(this->scip_, &curvars1);
205 this->graph.normalize();
208 return SCIP_INVALIDCALL;
212 SCIP_CALL( this->graph.flush() );
214 assert(this->graph.getNNodes() == nconss_);
233 vector<int> conssForGraph;
234 vector<int> varsForGraph;
235 vector<bool> varsBool(partialdec->
getNVars(),
false);
236 vector<bool> conssBool(partialdec->
getNConss(),
false);
237 unordered_map<int, int> oldToNewConsIndex;
238 unordered_map<int, int> oldToNewVarIndex;
250 varsBool[var] =
true;
251 conssBool[cons] =
true;
261 varsForGraph.push_back(var);
267 conssForGraph.push_back(cons);
270 this->nvars = (int)varsForGraph.size();
271 this->nconss = (int)conssForGraph.size();
272 assert(this->nconss > 0);
273 assert(this->nvars > 0);
275 for(
int v = 0; v < (int)varsForGraph.size(); ++v)
277 int oldVarId = varsForGraph[v];
278 oldToNewVarIndex.insert({oldVarId,v});
280 for(
int c = 0; c < (int)conssForGraph.size(); ++c)
282 int oldConsId = conssForGraph[c];
283 oldToNewConsIndex.insert({oldConsId,c});
288 SCIP_CALL( this->graph.addNNodes(this->nconss) );
291 for( i = 0; i < this->nconss; ++i )
293 int cons1 = conssForGraph[i];
294 assert(conssBool[cons1]);
297 for( j = 0; j < i; ++j )
299 int cons2 = conssForGraph[j];
311 assert(varsBool[var1]);
345 double edge_weight = calculateSimilarity(a, b, c, dist, w_type, i==j);
346 this->graph.addEdge(oldToNewConsIndex[cons1], oldToNewConsIndex[cons2], edge_weight);
354 this->graph.normalize();
357 return SCIP_INVALIDCALL;
361 SCIP_CALL( this->graph.flush() );
371 if(_c == 0 && _b == 0)
return 1e-10;
375 if(_c == 0 && _b == 0)
return (1.0 - 1e-10);
378 double a = (double)_a;
379 double b = (double)_b;
380 double c = (double)_c;
383 result = (a/(a+b) + a/(a+c)) / 2.0;
389 result = a / (a+b+c);
392 result = a / (sqrt(a+b)*sqrt(a+c));
395 result = a / MIN(a+b, a+c);
403 assert(result >= 0.0);
404 assert(result <= 1.0);
409 result *= (1 - 1e-10);
414 result = 1.0 - result;
423 assert((
int)labels.size() == graph.getNNodes());
424 set<int> diff_blocks_beginning;
425 for(
auto curr_int = labels.begin(), end = labels.end(); curr_int != end; ++curr_int)
427 diff_blocks_beginning.insert(*curr_int);
430 bool skip_me =
false;
431 if(diff_blocks_beginning.size() == labels.size())
436 if(enabled && !skip_me)
438 this->non_cl = (int)labels.size();
440 vector< vector<int> > all_labels_in_col(this->nvars);
443 vector< map<int, int> > all_label_occ_in_col(this->nvars);
446 vector<int> col_labels(this->nvars, -1);
448 SCIP_CONS** conss = SCIPgetConss(this->scip_);
452 for(
auto i = 0; i < this->nconss; i++)
456 SCIP_CALL( SCIPgetConsNVars(this->scip_, conss[i], &ncurvars, &success) );
465 SCIP_CALL( SCIPallocBufferArray(this->scip_, &curvars, ncurvars) );
466 SCIP_CALL( SCIPgetConsVars(this->scip_, conss[i], curvars, ncurvars, &success) );
469 for(
auto j = 0; j < ncurvars; j++)
476 if( SCIPgetStage(this->scip_) >= SCIP_STAGE_TRANSFORMED)
477 var = SCIPvarGetProbvar(curvars[j]);
482 int varIndex = SCIPvarGetProbindex(var);
483 assert(varIndex >= 0);
484 assert(varIndex < this->nvars);
487 all_labels_in_col[varIndex].push_back(labels[i]);
488 all_label_occ_in_col[varIndex][labels[i]]++;
490 SCIPfreeBufferArray(this->scip_, &curvars);
494 for(
auto i = 0; i < this->nvars; i++)
496 auto pr = max_element
498 all_label_occ_in_col[i].begin(), all_label_occ_in_col[i].end(),
499 [] (
const pair<int,int> & p1,
const pair<int,int> & p2) {
500 return p1.second < p2.second;
504 col_labels[i] = pr->first;
508 for(
auto i = 0; i < this->nconss; i++)
512 SCIP_CALL( SCIPgetConsNVars(this->scip_, conss[i], &ncurvars1, &success) );
521 SCIP_CALL( SCIPallocBufferArray(this->scip_, &curvars1, ncurvars1) );
522 SCIP_CALL( SCIPgetConsVars(this->scip_, conss[i], curvars1, ncurvars1, &success) );
525 for(
auto j = 0; j < ncurvars1; j++)
532 if( SCIPgetStage(this->scip_) >= SCIP_STAGE_TRANSFORMED)
533 var1 = SCIPvarGetProbvar(curvars1[j]);
537 assert(var1 != NULL);
538 int varIndex = SCIPvarGetProbindex(var1);
539 assert(varIndex >= 0);
540 assert(varIndex < this->nvars);
544 if(col_labels[varIndex] != labels[i])
550 all_label_occ_in_col[varIndex][labels[i]]--;
551 auto pr = max_element
553 all_label_occ_in_col[varIndex].begin(), all_label_occ_in_col[varIndex].end(),
554 [] (
const pair<int,int> & p1,
const pair<int,int> & p2) {
555 return p1.second < p2.second;
558 col_labels[varIndex] = pr->first;
561 SCIPfreeBufferArray(this->scip_, &curvars1);
570 set<int> diff_blocks;
572 for(
auto curr_int = labels.begin(), end = labels.end(); curr_int != end; ++curr_int)
574 diff_blocks.insert(*curr_int);
577 const int non_cl_pts = count(labels.begin(), labels.end(), -1);
580 this->n_blocks = diff_blocks.size() - 1;
584 this->n_blocks = diff_blocks.size();
586 this->non_cl = non_cl_pts;
588 map<int,int> labels_fix;
590 if(this->non_cl > 0) new_label = -1;
593 for(
int old_label: diff_blocks)
595 labels_fix[old_label] = new_label;
598 for(
int i = 0; i < (int)labels.size(); i++)
600 labels[i] = labels_fix[labels[i]];
605 for(
int i = 0; i < (int)labels.size(); i++)
607 this->graph.setPartition(i, labels[i]);
615 assert((
int)labels.size() == graph.getNNodes());
616 set<int> diff_blocks_beginning;
617 for(
auto curr_int = labels.begin(), end = labels.end(); curr_int != end; ++curr_int)
619 diff_blocks_beginning.insert(*curr_int);
621 bool skip_me =
false;
622 if(diff_blocks_beginning.size() == labels.size())
627 if(enabled && !skip_me)
630 vector<int> conssForGraph;
631 vector<int> varsForGraph;
632 vector<bool> varsBool(partialdec->
getNVars(),
false);
633 vector<bool> conssBool(partialdec->
getNConss(),
false);
634 unordered_map<int, int> oldToNewConsIndex;
635 unordered_map<int, int> oldToNewVarIndex;
647 varsBool[var] =
true;
648 conssBool[cons] =
true;
657 if(varsBool[var] ==
true)
658 varsForGraph.push_back(var);
663 if(conssBool[cons] ==
true)
664 conssForGraph.push_back(cons);
667 assert(this->nvars == (
int) varsForGraph.size());
668 assert(this->nconss == (
int) conssForGraph.size());
670 sort(conssForGraph.begin(), conssForGraph.end());
671 sort(varsForGraph.begin(), varsForGraph.end());
674 for(
int v = 0; v < this->nvars; ++v)
676 int oldVarId = varsForGraph[v];
677 oldToNewVarIndex.insert({oldVarId,v});
680 for(
int c = 0; c < this->nconss; ++c)
682 int oldConsId = conssForGraph[c];
683 oldToNewConsIndex.insert({oldConsId,c});
686 this->non_cl = (int)labels.size();
688 vector< vector<int> > all_labels_in_col(this->nvars);
691 vector< map<int, int> > all_label_occ_in_col(this->nvars);
694 vector<int> col_labels(this->nvars, -1);
698 for(
size_t c = 0; c < conssForGraph.size(); c++)
700 int cons = conssForGraph[c];
701 int consIndex = oldToNewConsIndex[cons];
702 assert(consIndex >= 0);
703 assert(consIndex < this->nconss);
707 if(find(varsForGraph.begin(), varsForGraph.end(), var) == varsForGraph.end())
709 int varIndex = oldToNewVarIndex[var];
710 assert(varIndex >= 0);
711 assert(varIndex < this->nvars);
712 all_labels_in_col[varIndex].push_back(labels[consIndex]);
717 for(
size_t v = 0; v < varsForGraph.size(); ++v)
719 int var = varsForGraph[v];
720 int varIndex = oldToNewVarIndex[var];
721 assert(varIndex >= 0);
722 assert(varIndex < this->nvars);
724 auto pr = max_element
726 all_label_occ_in_col[varIndex].begin(), all_label_occ_in_col[varIndex].end(),
727 [] (
const pair<int,int> & p1,
const pair<int,int> & p2) {
728 return p1.second < p2.second;
731 col_labels[varIndex] = pr->first;
736 for(
size_t c = 0; c < conssForGraph.size(); ++c)
738 int cons = conssForGraph[c];
740 int consIndex = oldToNewConsIndex[cons];
741 assert(consIndex >= 0);
742 assert(consIndex < this->nconss);
746 if(find(varsForGraph.begin(), varsForGraph.end(), var) == varsForGraph.end())
748 int varIndex = oldToNewVarIndex[var];
749 assert(varIndex >= 0);
750 assert(varIndex < this->nvars);
753 if(col_labels[varIndex] != labels[consIndex])
755 labels.at(consIndex) = -1;
759 all_label_occ_in_col[varIndex][labels[consIndex]]--;
760 auto pr = max_element
762 all_label_occ_in_col[varIndex].begin(), all_label_occ_in_col[varIndex].end(),
763 [] (
const pair<int,int> & p1,
const pair<int,int> & p2) {
764 return p1.second < p2.second;
767 col_labels[varIndex] = pr->first;
777 set<int> diff_blocks;
779 for(
auto curr_int = labels.begin(), end = labels.end(); curr_int != end; ++curr_int)
781 diff_blocks.insert(*curr_int);
784 const int non_cl_pts = count(labels.begin(), labels.end(), -1);
787 this->n_blocks = diff_blocks.size() - 1;
791 this->n_blocks = diff_blocks.size();
793 this->non_cl = non_cl_pts;
795 map<int,int> labels_fix;
797 if(this->non_cl > 0) new_label = -1;
800 for(
int old_label: diff_blocks)
802 labels_fix[old_label] = new_label;
805 for(
int i = 0; i < (int)labels.size(); i++)
807 labels[i] = labels_fix[labels[i]];
812 for(
int i = 0; i < (int)labels.size(); i++)
814 this->graph.setPartition(i, labels[i]);
822 SCIP_RETCODE RowGraphWeighted<GraphGCG>::postProcessStableSet(vector<int>& labels,
bool enabled)
824 assert((
int)labels.size() == graph.getNNodes());
825 set<int> diff_blocks_beginning;
826 for(
auto curr_int = labels.begin(), end = labels.end(); curr_int != end; ++curr_int)
828 diff_blocks_beginning.insert(*curr_int);
830 bool skip_me =
false;
831 if(diff_blocks_beginning.size() == labels.size())
838 if(enabled && !skip_me)
842 this->non_cl = (int)labels.size();
844 vector< vector<int> > all_ind_in_col(this->nvars);
847 SCIP_CONS** conss = SCIPgetConss(this->scip_);
851 for(
int i = 0; i < this->nconss; ++i )
856 SCIP_CALL( SCIPgetConsNVars(this->scip_, conss[i], &ncurvars1, &success) );
865 SCIP_CALL( SCIPallocBufferArray(this->scip_, &curvars1, ncurvars1) );
866 SCIP_CALL( SCIPgetConsVars(this->scip_, conss[i], curvars1, ncurvars1, &success) );
870 for(
int j = 0; j < i; ++j )
872 if(labels[i] == labels[j])
continue;
874 SCIP_Bool continueloop;
876 SCIP_CALL( SCIPgetConsNVars(this->scip_, conss[j], &ncurvars2, &success) );
881 continueloop = FALSE;
886 SCIP_CALL( SCIPallocBufferArray(this->scip_, &curvars2, ncurvars2) );
887 SCIP_CALL( SCIPgetConsVars(this->scip_, conss[j], curvars2, ncurvars2, &success) );
894 for(
int k = 0; k < ncurvars1; ++k )
902 if( SCIPgetStage(this->scip_) >= SCIP_STAGE_TRANSFORMED)
903 var1 = SCIPvarGetProbvar(curvars1[k]);
907 assert(var1 != NULL);
908 varIndex1 = SCIPvarGetProbindex(var1);
909 assert(varIndex1 >= 0);
910 assert(varIndex1 < this->nvars);
912 for(
int l = 0; l < ncurvars2; ++l )
920 if( SCIPgetStage(this->scip_) >= SCIP_STAGE_TRANSFORMED)
921 var2 = SCIPvarGetProbvar(curvars2[l]);
925 assert(var2 != NULL);
926 varIndex2 = SCIPvarGetProbindex(var2);
927 assert(varIndex2 >= 0);
928 assert(varIndex2 < this->nvars);
930 if(varIndex1 == varIndex2)
934 stable_set_graph.
addEdge(i, j);
947 SCIPfreeBufferArray(this->scip_, &curvars2);
949 SCIPfreeBufferArray(this->scip_, &curvars1);
953 vector<int> stable_set;
954 vector<int> no_stable_set;
955 while(!stable_set_graph.empty()){
956 int current = stable_set_graph.top().first;
957 stable_set.push_back(current);
958 set<int> neighbors = stable_set_graph.
getNeighbors(current);
959 stable_set_graph.pop();
960 for(
auto neighbor : neighbors){
961 stable_set_graph.
removeNode(neighbor, no_stable_set);
967 for(
int to_remove : no_stable_set)
970 labels[to_remove] = -1;
979 set<int> diff_blocks;
980 for(
auto curr_int = labels.begin(), end = labels.end(); curr_int != end; ++curr_int)
982 diff_blocks.insert(*curr_int);
985 const int non_cl_pts = count(labels.begin(), labels.end(), -1);
988 this->n_blocks = diff_blocks.size() - 1;
992 this->n_blocks = diff_blocks.size();
994 this->non_cl = non_cl_pts;
996 map<int,int> labels_fix;
998 if(this->non_cl > 0) new_label = -1;
1001 for(
int old_label: diff_blocks)
1003 labels_fix[old_label] = new_label;
1006 for(
int i = 0; i < (int)labels.size(); i++)
1008 labels[i] = labels_fix[labels[i]];
1013 for(
int i = 0; i < (int)labels.size(); i++)
1015 this->graph.setPartition(i, labels[i]);
1022 SCIP_RETCODE RowGraphWeighted<GraphGCG>::postProcessStableSetForPartialGraph(
gcg::DETPROBDATA* detprobdata,
gcg::PARTIALDECOMP* partialdec, vector<int>& labels,
bool enabled)
1024 assert((
int)labels.size() == graph.getNNodes());
1025 set<int> diff_blocks_beginning;
1026 for(
auto curr_int = labels.begin(), end = labels.end(); curr_int != end; ++curr_int)
1028 diff_blocks_beginning.insert(*curr_int);
1030 bool skip_me =
false;
1031 if(diff_blocks_beginning.size() == labels.size())
1039 if(enabled && !skip_me)
1042 vector<int> conssForGraph;
1043 vector<int> varsForGraph;
1044 vector<bool> varsBool(partialdec->
getNVars(),
false);
1045 vector<bool> conssBool(partialdec->
getNConss(),
false);
1046 unordered_map<int, int> oldToNewConsIndex;
1047 unordered_map<int, int> oldToNewVarIndex;
1059 varsBool[var] =
true;
1060 conssBool[cons] =
true;
1069 if(varsBool[var] ==
true)
1070 varsForGraph.push_back(var);
1075 if(conssBool[cons] ==
true)
1076 conssForGraph.push_back(cons);
1079 assert(this->nvars == (
int) varsForGraph.size());
1080 assert(this->nconss == (
int) conssForGraph.size());
1082 sort(conssForGraph.begin(), conssForGraph.end());
1083 sort(varsForGraph.begin(), varsForGraph.end());
1086 for(
int v = 0; v < this->nvars; ++v)
1088 int oldVarId = varsForGraph[v];
1089 oldToNewVarIndex.insert({oldVarId,v});
1092 for(
int c = 0; c < this->nconss; ++c)
1094 int oldConsId = conssForGraph[c];
1095 oldToNewConsIndex.insert({oldConsId,c});
1099 this->non_cl = (int)labels.size();
1101 vector< vector<int> > all_ind_in_col(this->nvars);
1104 for(
int c = 0; c < this->nconss; ++c)
1106 int cons1 = conssForGraph[c];
1107 int consIndex1 = oldToNewConsIndex[cons1];
1108 assert(consIndex1 >= 0);
1109 assert(consIndex1 < this->nconss);
1117 for(
int d = 0; d < c; ++d )
1119 int cons2 = conssForGraph[d];
1120 int consIndex2 = oldToNewConsIndex[cons2];
1121 assert(consIndex2 >= 0);
1122 assert(consIndex2 < this->nconss);
1123 if(labels[consIndex1] == labels[consIndex2])
1125 SCIP_Bool continueloop = FALSE;
1136 if(find(varsForGraph.begin(), varsForGraph.end(), var1) == varsForGraph.end())
1138 int varIndex1 = oldToNewVarIndex[var1];
1139 assert(varIndex1 >= 0);
1140 assert(varIndex1 < this->nvars);
1144 if(find(varsForGraph.begin(), varsForGraph.end(), var2) == varsForGraph.end())
1146 int varIndex2 = oldToNewVarIndex[var2];
1147 assert(varIndex2 >= 0);
1148 assert(varIndex2 < this->nvars);
1149 if(varIndex1 == varIndex2)
1151 stable_set_graph.
addNode(consIndex1);
1152 stable_set_graph.
addNode(consIndex2);
1153 stable_set_graph.
addEdge(consIndex1, consIndex2);
1154 continueloop = TRUE;
1165 vector<int> stable_set;
1166 vector<int> no_stable_set;
1167 while(!stable_set_graph.empty()){
1168 int current = stable_set_graph.top().first;
1169 stable_set.push_back(current);
1170 set<int> neighbors = stable_set_graph.
getNeighbors(current);
1171 stable_set_graph.pop();
1172 for(
auto neighbor : neighbors){
1173 stable_set_graph.
removeNode(neighbor, no_stable_set);
1179 for(
int to_remove : no_stable_set)
1181 labels[to_remove] = -1;
1190 set<int> diff_blocks;
1191 for(
auto curr_int = labels.begin(), end = labels.end(); curr_int != end; ++curr_int)
1193 diff_blocks.insert(*curr_int);
1196 const int non_cl_pts = count(labels.begin(), labels.end(), -1);
1199 this->n_blocks = diff_blocks.size() - 1;
1203 this->n_blocks = diff_blocks.size();
1205 this->non_cl = non_cl_pts;
1207 map<int,int> labels_fix;
1209 if(this->non_cl > 0) new_label = -1;
1212 for(
int old_label: diff_blocks)
1214 labels_fix[old_label] = new_label;
1217 for(
int i = 0; i < (int)labels.size(); i++)
1219 labels[i] = labels_fix[labels[i]];
1224 for(
int i = 0; i < (int)labels.size(); i++)
1226 this->graph.setPartition(i, labels[i]);
1236 assert((
int)labels.size() == graph.getNNodes());
1238 SCIP_CALL( postProcess(labels, postprocenable) );
1247 assert((
int)labels.size() == graph.getNNodes());
1249 SCIP_CALL( postProcessForPartialGraph(detprobdata, partialdec, labels, postprocenable) );
1259 assert((
int)labels.size() == graph.getNNodes());
1261 SCIP_CALL( postProcess(labels, postprocenable) );
1270 assert((
int)labels.size() == graph.getNNodes());
1272 SCIP_CALL( postProcessForPartialGraph(detprobdata, partialdec, labels, postprocenable) );
1281 assert((
int)labels.size() == graph.getNNodes());
1283 SCIP_CALL( postProcess(labels, postprocenable) );
1292 assert((
int)labels.size() == graph.getNNodes());
1294 SCIP_CALL( postProcessForPartialGraph(detprobdata, partialdec, labels, postprocenable) );
1301 _n_blocks = n_blocks;
1315 return this->graph.getEdgeWeightPercentile(q);