decontamination

graph decontamination problem
git clone https://a3nm.net/git/decontamination/
Log | Files | Refs

commit 2ddc413376990ab4b2fc8ca95d266906d6cf644d
parent 79c11486db2d98a8c6672548ad5a9cd2959fc293
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Tue, 29 Nov 2022 09:38:22 +0100

options

Diffstat:
decontamination.cpp | 21+++++++++++++++++----
1 file changed, 17 insertions(+), 4 deletions(-)

diff --git a/decontamination.cpp b/decontamination.cpp @@ -15,7 +15,13 @@ * separated by the nodes to query. */ // max number of vertices, change this -#define MAXN 10 +#define MAXN 5 + +// if set, only display the graph, not the strategy +#define DISPLAYGRAPH 0 + +// maximal number of nodes to shoot simultaneously +#define MAXK 1 #include <cstdio> #include <iostream> @@ -36,6 +42,7 @@ int main() { int G[MAXN][MAXN]; // degrees int nG[MAXN]; + bool found_solution = false; for (int i = 0; i < MAXN; i++) nG[i] = 0; @@ -52,7 +59,7 @@ int main() { } n++; // so that vertices are from 0 to n-1 - for (int k = 1; k <= 1; k++) { + for (int k = 1; k <= MAXK; k++) { // decontaminate simultaneously k nodes // do a BFS on configurations @@ -89,7 +96,8 @@ int main() { for (int j = 0; j < nG[i]; j++) // all possible contaminations by i nc.set(G[i][j]); - cout << c << " -> " << nc << " [label='" << myidx << "'];" << endl; + if (DISPLAYGRAPH) + cout << c << " -> " << nc << " [label='" << myidx << "'];" << endl; //cout << nc << endl; if (!p.count(nc)) { // nc was not reachable yet @@ -100,7 +108,8 @@ int main() { } while (prev_permutation(bm.begin(), bm.end())); } - return 0; + if (DISPLAYGRAPH) + return 0; bitset<MAXN> e; if (p.count(e)) { @@ -128,11 +137,15 @@ int main() { } printf("\n"); } + found_solution = true; break; } // if target configuration was not reached, increase k } + if (!found_solution) + printf("no solution found\n"); + return 0; }