# decontamination

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

decontamination.cpp (4282B)

```      1 /* decontamination.cpp -- find decontamination sequence of input graph
2  * Antoine Amarilli, 2015
3  * see http://cstheory.stackexchange.com/q/30592/4795 for problem statement
4  *
5  * To use, set MAXN in the code to be more than the number of vertices to
6  * consider, and compile with g++ -Wall -O3 -std=c++11
7  *
8  * Provide graph in stdin with each edge represented by the source and target
9  * represented as integers, separated by a space, edges separated by newline.
10  * EOF terminates. Vertices should be numbered from 0 to n-1.
11  *
12  * Output is a decontamination sequence with minimal number of nodes to be
13  * simultaneously decontaminated, then minimal order, then (normally) minimum in
14  * lexicographic order, represented as a bit vector of the node contaminations
15  * separated by the nodes to query. */
16
17 // max number of vertices, change this
18 #define MAXN 5
19
20 // if set, only display the graph, not the strategy
21 #define DISPLAYGRAPH 0
22
23 // maximal number of nodes to shoot simultaneously
24 #define MAXK 1
25
26 #include <cstdio>
27 #include <iostream>
28 #include <assert.h>
29 #include <queue>
30 #include <bitset>
31 #include <algorithm>
32 #include <unordered_map>
33
34 #define max(a, b) ((b)>(a) ? (b) : (a))
35
36 using namespace std;
37
38 int main() {
39   // n_vertices, n_edges
40   int n = 0;
42   int G[MAXN][MAXN];
43   // degrees
44   int nG[MAXN];
45   bool found_solution = false;
46
47   for (int i = 0; i < MAXN; i++)
48     nG[i] = 0;
49   while (true) {
50     int f, t, ret;
51     ret = scanf("%d %d\n", &f, &t);
52     if (ret != 2)
53       break;
54     // vertices should be numbered from 0 to n-1 with n <= MAXN
55     assert(0 <= f && f < MAXN && 0 <= t && t < MAXN);
56     n = max(n, max(f, t));
57     G[f][nG[f]] = t;
58     nG[f]++;
59   }
60   n++; // so that vertices are from 0 to n-1
61
62   for (int k = 1; k <= MAXK; k++) {
63     // decontaminate simultaneously k nodes
64     // do a BFS on configurations
65
66     // queue of configurations to consider
67     queue<bitset<MAXN> > q;
68     // predecessor configuration of each reachable configuration
69     unordered_map<bitset<MAXN>, bitset<MAXN> > p;
70     // action to reach each reachable configuration from predecessor
71     unordered_map<bitset<MAXN>, string > a;
72
73     // start configuration
74     bitset<MAXN> s;
75     for (int i = 0; i < n; i++)
76       s.set(i);
77     q.push(s);
78
79     while (!q.empty()) {
80       bitset<MAXN> c = q.front();
81       if (!c.count())
82         break; // target configuration reached
83       q.pop();
84       // http://rosettacode.org/wiki/Combinations#C.2B.2B
85       string bm(k, 1);
86       bm.resize(n, 0);
87       do {
88         bitset<MAXN> nc; // new possible configuration
89         int myidx = -1;
90         for (int i = 0; i < n; i++)
91           if (bm[i])
92             myidx = i;
93         for (int i = 0; i < n; i++)
94           if (c[i] && !bm[i])
95             // i is contaminated and was not decontaminated at this turn
96             for (int j = 0; j < nG[i]; j++)
97               // all possible contaminations by i
98               nc.set(G[i][j]);
99         if (DISPLAYGRAPH)
100           cout << c << " -> " << nc << " [label='" << myidx << "'];" << endl;
101         //cout << nc << endl;
102         if (!p.count(nc)) {
103           // nc was not reachable yet
104           p[nc] = c;
105           a[nc] = bm;
106           q.push(nc);
107         }
108       } while (prev_permutation(bm.begin(), bm.end()));
109     }
110
111     if (DISPLAYGRAPH)
112       return 0;
113
114     bitset<MAXN> e;
115     if (p.count(e)) {
116       // target configuration was reached: all nodes decontaminated
117       // read back the path to the target configuration
118       vector<string> v;
119       do {
120         v.push_back(e.to_string());
121         v.push_back(a[e]);
122         e = p[e];
123       } while (p.count(e) && p[e] != e);
124       v.push_back(e.to_string());
125       // path is in reverse order
126       reverse(v.begin(), v.end());
127       for (unsigned int i = 0; i < v.size(); i++) {
128         if (i % 2 == 1) {
129           // display decontamination action
130           for (int j = 0; j < n; j++) {
131             if (v[i][j])
132               printf("%d ", j);
133           }
134         } else {
135           // display configuration
136           cout << v[i];
137         }
138         printf("\n");
139       }
140       found_solution = true;
141       break;
142     }
143     // if target configuration was not reached, increase k
144   }
145
146   if (!found_solution)
147     printf("no solution found\n");
148
149   return 0;
150 }
151
```