https://github.com/ASchidler/coloring
Tip revision: dd03517187447fd44cfd9f03db6ab7313a21a64a authored by Andre Schidler on 14 March 2022, 12:24:58 UTC
Initial commit
Initial commit
Tip revision: dd03517
conflict_graph.cpp
//
// Created on 22.10.21.
//
#include "conflict_graph.h"
#include "solution.h"
void planarity::find_color_subgraph(const ConflictGraph& g, Coloring& coloring, const string& filename) {
vector<dynamic_bitset<>> partitions(coloring.numColors, dynamic_bitset<>(g.getNumNodes()));
dynamic_bitset<> component(g.getNumNodes());
dynamic_bitset<> new_nodes(g.getNumNodes());
auto findNeighbor = [&] (node_t node, color_t color) {
new_nodes.reset();
dynamic_bitset<> node_colors(color);
for (auto n2=g.adjacency[node].find_first(); n2 != dynamic_bitset<>::npos; n2 = g.adjacency[node].find_next(n2)) {
if (coloring.coloring[n2] < color) {
if (!node_colors.test(coloring.coloring[n2])) {
node_colors[coloring.coloring[n2]] = true;
new_nodes.set(n2);
}
}
}
if (node_colors.all()) {
component.set(node);
component |= new_nodes;
return true;
} else {
node_colors.flip();
auto new_c = node_colors.find_first();
coloring.coloring[node] = new_c;
partitions[color][node] = false;
partitions[new_c][node] = true;
cout << "Skip " << color << endl;
}
return false;
};
for (node_t n=0; n < g.getNumNodes(); n++) {
partitions[coloring.coloring[n]].set(n);
}
bool done = false;
for (node_t n=0; n < g.getNumNodes() && ! done; n++) {
if (coloring.coloring[n] == coloring.numColors - 1) {
component.reset();
color_t cc = coloring.numColors - 1;
if (findNeighbor(n, cc)) {
node_t c_n = n;
while (cc > 0) {
cc--;
auto modified_nb = g.adjacency[c_n] & partitions[cc];
auto modified_nb1 = modified_nb & component;
auto modified_nb2 = modified_nb - component;
bool found_nb = false;
for (auto n2 = modified_nb1.find_first(); n2 != dynamic_bitset<>::npos; n2 = modified_nb1.find_next(n2)) {
if (findNeighbor(n2, cc)) {
c_n = n2;
found_nb = true;
break;
}
}
if (! found_nb) {
for (auto n2 = modified_nb2.find_first(); n2 != dynamic_bitset<>::npos; n2 = modified_nb2.find_next(n2)) {
if (findNeighbor(n2, cc)) {
c_n = n2;
found_nb = true;
break;
}
}
if (! found_nb)
break;
}
}
done = cc == 0;
}
}
}
if (! done)
cout << "Failed" << endl;
assert(g.verify(coloring.coloring));
cout << component.count() << " Nodes" << endl;
if (!filename.empty()) {
ofstream myfile(filename);
if (myfile.is_open()) {
auto n = component.find_first();
myfile << n;
for (; n != dynamic_bitset<>::npos; n = component.find_next(n)) {
myfile << "," << n;
}
myfile << endl;
myfile.close();
}
}
}