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;
     41   // adjacency lists
     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