assign/singlepointoffailure.cpp at master · pradg73/assign · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <bits/stdc++.h>
using namespace std;

void print(auto& v)
{

    for (auto vi : v)
    {
        for (auto i: vi)
            cout << i << " ";
        cout << "\n";
    }

}
struct Visitor
{
    std::vector<std::vector<int>>& cons;
    size_t N;

    Visitor(std::vector<std::vector<int>> &_connections):
    cons(_connections), N(cons.size()){ print(cons);}

    std::queue<int> q;
    std::set<int> visited;
    int visit (int _i, int j) // if cannot reach i to j, return 1 else 0
    {
        cout << "visit " << _i << "," << j << "\n";
        visited.clear();
        queue<int> empty;
        q.swap(empty);

        q.push(_i);

        while(!q.empty())
        {
            int i = q.front(); q.pop();
            visited.insert(i);
            cout << "visiting " << i << endl;
            for (int k = 0; k < N; ++k)
            {
                cout << "check " << i << "," << k << " " << cons[i][k] <<"\n";
                //           cout << "size " << cons->size() << endl;
                // cout << "size i" << (*cons)[i].size() << endl;

                if (cons[i][k] == 0) continue;

                if (k == j) return 0;

                if (visited.find(k) == visited.end())
                {
                    cout << "pushing " << k << endl;
                    q.push(k);
                }
            }
        }
        return 1;
    }
};

int singlePointOfFailure(std::vector<std::vector<int>> &connections) {

    size_t N = connections.size();
    Visitor v(connections);
    int f(0);
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
        {
            if (i >= j) continue;
            if (connections[i][j] == 0)
                continue;

            connections[i][j] = 0;
            f += v.visit(i,j);
            cout << "f " << f << endl;
            connections[i][j] = 1;
        }
    return f;
}

int main(void)
{
    std::vector<std::vector<int>> v =
        {{0, 1, 1, 1, 1}, {1, 0, 0, 0, 0}, {1, 0, 0, 0, 0}, {1, 0, 0, 0, 0}, {1, 0, 0, 0, 0}};
    //print (v);

    std::vector<std::vector<int>> v1 ={{0,1},{1,0}};

     std::vector<std::vector<int>> v2 = {{0,1,1},
                                         {1,0,1},
                                         {1,1,0}};

     std::vector<std::vector<int>> v3 =
         {{0,1,1,0,0,0,0},
          {1,0,1,0,0,0,0},
          {1,1,0,0,0,0,1},
          {0,0,0,0,1,1,1},
          {0,0,0,1,0,1,0},
          {0,0,0,1,1,0,0},
          {0,0,1,1,0,0,0}};

    int f = singlePointOfFailure(v3);
    cout << f << endl;
}