decontamination

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

decontamination.cpp (4398B)

      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 // if set, symmetrize graph
     24 #define UNDIRECTED 1
     25 
     26 // maximal number of nodes to shoot simultaneously
     27 #define MAXK 1
     28 
     29 #include <cstdio>
     30 #include <iostream>
     31 #include <assert.h>
     32 #include <queue>
     33 #include <bitset>
     34 #include <algorithm>
     35 #include <unordered_map>
     36 
     37 #define max(a, b) ((b)>(a) ? (b) : (a))
     38 
     39 using namespace std;
     40 
     41 int main() {
     42   // n_vertices, n_edges
     43   int n = 0;
     44   // adjacency lists
     45   int G[MAXN][MAXN];
     46   // degrees
     47   int nG[MAXN];
     48   bool found_solution = false;
     49 
     50   for (int i = 0; i < MAXN; i++)
     51     nG[i] = 0;
     52   while (true) {
     53     int f, t, ret;
     54     ret = scanf("%d %d\n", &f, &t);
     55     if (ret != 2)
     56       break;
     57     // vertices should be numbered from 0 to n-1 with n <= MAXN
     58     assert(0 <= f && f < MAXN && 0 <= t && t < MAXN);
     59     n = max(n, max(f, t));
     60     G[f][nG[f]] = t;
     61     nG[f]++;
     62     if (UNDIRECTED) {
     63       G[t][nG[t]] = f;
     64       nG[t]++;
     65     }
     66   }
     67   n++; // so that vertices are from 0 to n-1
     68 
     69   for (int k = 1; k <= MAXK; k++) {
     70     // decontaminate simultaneously k nodes
     71     // do a BFS on configurations
     72 
     73     // queue of configurations to consider
     74     queue<bitset<MAXN> > q;
     75     // predecessor configuration of each reachable configuration
     76     unordered_map<bitset<MAXN>, bitset<MAXN> > p;
     77     // action to reach each reachable configuration from predecessor
     78     unordered_map<bitset<MAXN>, string > a;
     79 
     80     // start configuration
     81     bitset<MAXN> s;
     82     for (int i = 0; i < n; i++)
     83       s.set(i);
     84     q.push(s);
     85 
     86     while (!q.empty()) {
     87       bitset<MAXN> c = q.front();
     88       if (!c.count())
     89         break; // target configuration reached
     90       q.pop();
     91       // http://rosettacode.org/wiki/Combinations#C.2B.2B
     92       string bm(k, 1);
     93       bm.resize(n, 0);
     94       do {
     95         bitset<MAXN> nc; // new possible configuration
     96         int myidx = -1;
     97         for (int i = 0; i < n; i++)
     98           if (bm[i])
     99             myidx = i;
    100         for (int i = 0; i < n; i++)
    101           if (c[i] && !bm[i])
    102             // i is contaminated and was not decontaminated at this turn
    103             for (int j = 0; j < nG[i]; j++)
    104               // all possible contaminations by i
    105               nc.set(G[i][j]);
    106         if (DISPLAYGRAPH)
    107           cout << c << " -> " << nc << " [label='" << myidx << "'];" << endl;
    108         //cout << nc << endl;
    109         if (!p.count(nc)) {
    110           // nc was not reachable yet
    111           p[nc] = c;
    112           a[nc] = bm;
    113           q.push(nc);
    114         }
    115       } while (prev_permutation(bm.begin(), bm.end()));
    116     }
    117 
    118     if (DISPLAYGRAPH)
    119       return 0;
    120 
    121     bitset<MAXN> e;
    122     if (p.count(e)) {
    123       // target configuration was reached: all nodes decontaminated
    124       // read back the path to the target configuration
    125       vector<string> v;
    126       do {
    127         v.push_back(e.to_string());
    128         v.push_back(a[e]);
    129         e = p[e];
    130       } while (p.count(e) && p[e] != e);
    131       v.push_back(e.to_string());
    132       // path is in reverse order
    133       reverse(v.begin(), v.end());
    134       for (unsigned int i = 0; i < v.size(); i++) {
    135         if (i % 2 == 1) {
    136           // display decontamination action
    137           for (int j = 0; j < n; j++) {
    138             if (v[i][j])
    139               printf("%d ", j);
    140           }
    141         } else {
    142           // display configuration
    143           cout << v[i];
    144         }
    145         printf("\n");
    146       }
    147       found_solution = true;
    148       break;
    149     }
    150     // if target configuration was not reached, increase k
    151   }
    152 
    153   if (!found_solution)
    154     printf("no solution found\n");
    155 
    156   return 0;
    157 }
    158