decontamination

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

commit 347510bb35a95aae7764aec63c367012eceebb85
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Sun,  8 Mar 2015 13:34:45 +0100

initial commit

Diffstat:
decontamination.cpp | 130+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
graphs/big | 18++++++++++++++++++
graphs/bigcycle2 | 14++++++++++++++
graphs/cycle | 4++++
graphs/cycle2 | 8++++++++
graphs/line | 8++++++++
graphs/linei | 42++++++++++++++++++++++++++++++++++++++++++
graphs/star | 12++++++++++++
graphs/star2 | 14++++++++++++++
graphs/star3 | 16++++++++++++++++
graphs/star3b | 18++++++++++++++++++
graphs/starau | 18++++++++++++++++++
12 files changed, 302 insertions(+), 0 deletions(-)

diff --git a/decontamination.cpp b/decontamination.cpp @@ -0,0 +1,130 @@ +/* decontamination.cpp -- find decontamination sequence of input graph + * Antoine Amarilli, 2015 + * see http://cstheory.stackexchange.com/q/30592/4795 for problem statement + * + * To use, set MAXN in the code to be more than the number of vertices to + * consider, and compile with g++ -Wall -O3 -std=c++11 + * + * Provide graph in stdin with each edge represented by the source and target + * represented as integers, separated by a space, edges separated by newline. + * EOF terminates. Vertices should be numbered from 0 to n-1. + * + * Output is a decontamination sequence with minimal number of nodes to be + * simultaneously decontaminated, then minimal order, then (normally) minimum in + * lexicographic order, represented as a bit vector of the node contaminations + * separated by the nodes to query. */ + +// max number of vertices, change this +#define MAXN 32 + +#include <cstdio> +#include <iostream> +#include <assert.h> +#include <queue> +#include <bitset> +#include <algorithm> +#include <unordered_map> + +#define max(a, b) ((b)>(a) ? (b) : (a)) + +using namespace std; + +int main() { + // n_vertices, n_edges + int n = 0; + // adjacency lists + int G[MAXN][MAXN]; + // degrees + int nG[MAXN]; + + for (int i = 0; i < MAXN; i++) + nG[i] = 0; + while (true) { + int f, t, ret; + ret = scanf("%d %d\n", &f, &t); + if (ret != 2) + break; + // vertices should be numbered from 0 to n-1 with n <= MAXN + assert(0 <= f && f < MAXN && 0 <= t && t < MAXN); + n = max(n, max(f, t)); + G[f][nG[f]] = t; + nG[f]++; + } + n++; // so that vertices are from 0 to n-1 + + for (int k = 1; k <= n; k++) { + // decontaminate simultaneously k nodes + // do a BFS on configurations + + // queue of configurations to consider + queue<bitset<MAXN> > q; + // predecessor configuration of each reachable configuration + unordered_map<bitset<MAXN>, bitset<MAXN> > p; + // action to reach each reachable configuration from predecessor + unordered_map<bitset<MAXN>, string > a; + + // start configuration + bitset<MAXN> s; + for (int i = 0; i < n; i++) + s.set(i); + q.push(s); + + while (!q.empty()) { + bitset<MAXN> c = q.front(); + if (!c.count()) + break; // target configuration reached + q.pop(); + // http://rosettacode.org/wiki/Combinations#C.2B.2B + string bm(k, 1); + bm.resize(n, 0); + do { + bitset<MAXN> nc; // new possible configuration + for (int i = 0; i < n; i++) + if (c[i] && !bm[i]) + // i is contaminated and was not decontaminated at this turn + for (int j = 0; j < nG[i]; j++) + // all possible contaminations by i + nc.set(G[i][j]); + if (!p.count(nc)) { + // nc was not reachable yet + p[nc] = c; + a[nc] = bm; + q.push(nc); + } + } while (prev_permutation(bm.begin(), bm.end())); + } + + bitset<MAXN> e; + if (p.count(e)) { + // target configuration was reached: all nodes decontaminated + // read back the path to the target configuration + vector<string> v; + do { + v.push_back(e.to_string()); + v.push_back(a[e]); + e = p[e]; + } while (p.count(e) && p[e] != e); + v.push_back(e.to_string()); + // path is in reverse order + reverse(v.begin(), v.end()); + for (unsigned int i = 0; i < v.size(); i++) { + if (i % 2 == 1) { + // display decontamination action + for (int j = 0; j < n; j++) { + if (v[i][j]) + printf("%d ", j); + } + } else { + // display configuration + cout << v[i]; + } + printf("\n"); + } + break; + } + // if target configuration was not reached, increase k + } + + return 0; +} + diff --git a/graphs/big b/graphs/big @@ -0,0 +1,18 @@ +0 1 +1 0 +1 2 +2 1 +2 3 +3 2 +0 4 +4 0 +4 5 +5 4 +5 6 +6 5 +0 7 +7 0 +8 7 +7 8 +8 9 +9 8 diff --git a/graphs/bigcycle2 b/graphs/bigcycle2 @@ -0,0 +1,14 @@ +0 1 +1 0 +1 2 +2 1 +2 3 +3 2 +3 4 +4 3 +4 5 +5 4 +5 6 +6 5 +6 0 +0 6 diff --git a/graphs/cycle b/graphs/cycle @@ -0,0 +1,4 @@ +0 1 +1 2 +2 3 +3 0 diff --git a/graphs/cycle2 b/graphs/cycle2 @@ -0,0 +1,8 @@ +0 1 +1 0 +1 2 +2 1 +2 3 +3 2 +3 0 +0 3 diff --git a/graphs/line b/graphs/line @@ -0,0 +1,8 @@ +0 1 +1 0 +1 2 +2 1 +2 3 +3 2 +3 4 +4 3 diff --git a/graphs/linei b/graphs/linei @@ -0,0 +1,42 @@ +0 1 +1 0 +1 2 +2 1 +2 3 +3 2 +3 4 +4 3 +4 5 +5 4 +5 6 +6 5 +6 7 +7 6 +1 8 +8 1 +1 9 +9 1 +8 10 +10 8 +8 11 +11 8 +3 12 +12 3 +12 13 +13 12 +3 14 +14 3 +14 15 +15 14 +6 16 +16 6 +16 17 +17 16 +6 18 +18 6 +18 19 +19 18 +18 20 +20 18 +20 21 +21 20 diff --git a/graphs/star b/graphs/star @@ -0,0 +1,12 @@ +0 1 +1 0 +1 2 +2 1 +0 3 +3 0 +3 4 +4 3 +0 5 +5 0 +6 5 +5 6 diff --git a/graphs/star2 b/graphs/star2 @@ -0,0 +1,14 @@ +0 1 +1 0 +1 2 +2 1 +0 3 +3 0 +3 4 +4 3 +0 5 +5 0 +6 5 +5 6 +6 7 +7 6 diff --git a/graphs/star3 b/graphs/star3 @@ -0,0 +1,16 @@ +0 1 +1 0 +1 2 +2 1 +0 3 +3 0 +3 4 +4 3 +0 5 +5 0 +6 5 +5 6 +0 6 +6 0 +6 7 +7 6 diff --git a/graphs/star3b b/graphs/star3b @@ -0,0 +1,18 @@ +0 1 +1 0 +1 2 +2 1 +0 3 +3 0 +3 4 +4 3 +0 5 +5 0 +6 5 +5 6 +0 7 +7 0 +8 7 +7 8 +8 9 +9 8 diff --git a/graphs/starau b/graphs/starau @@ -0,0 +1,18 @@ +0 1 +1 0 +1 2 +2 1 +0 3 +3 0 +3 4 +4 3 +0 5 +5 0 +6 5 +5 6 +1 7 +7 1 +7 8 +8 7 +8 9 +9 8