|
Vitali V. Valiayeu presents his humble share for Graph
Isomorphism Problem http://sourceforge.net/projects/griso funkybee@yandex.ru |
|
|
|
|
|
Now, what does it do. The main (and sole) culprit here is function foo(). It gets as its input adjacency matrix adj[nv][nv] of a graph, calculate the fingerprint (as I call it)
of the graph and returns this fingerprint as another matrix, res[(nv * (nv - 1)) / 2][?] (how many columns will be in it depends on the input graph). This calculation of fingerprint is rather a dynamic scanning of the
graph while filling of res[][] because I do it by exactly (nv
* (nv - 1)) / 2 bfs traversings, starting
each traversing from each pair of different nodes (v1 < v2, here v1,
v2 are numbers of starting verteces). Inside of each bfs and on each its level I populate two temp 1D
vectors: d[] and e[]. Like this: let [1, 3, 7] are nodes just visited on the current level of a bfs and [4, 5, 6, 11] are nodes that will be visited after we jump to the next
level (i.e. they are adjacent to “old” nodes). Now I count how many each node from [1, 3, 7] has adjacent to it nodes
from [4, 5, 6, 11] and store these values in vector d[]. And in vice versa direction, I count how many each node from [4, 5, 6,
11] has adjacent to it nodes from [1, 3, 7] and store these values in vector e[]. After bfs-ing from each starting pair (v1, v2) I sort d[] and e[] and
push them into res[u], where “u” is # of row corresponding to pair (v1, v2) (from two nested for(){for(){}} statements (see code)). After processing all such pairs I sort vector res[] and return it as
the output of function foo(). Note: the foo() is absolutely insensitive to is its input graph
indirected or is it directed. ============== Now (no surprise) my strong conviction is: graphs G1 and G2 are isomorphic IIF foo(G1) = foo(G2) PS Below and after C++ code I include input file (iso1.txt) with 11 (22,
of course) sample graphs for testing. |
|
|
|
|
|
C++ code: |
|
|
/* griso.cpp */ #include <time.h> #include <stdio.h> #include <iostream> #include <algorithm> #include <vector> #include <string> using namespace std; vector<vector<int> > foo(vector<string> &adj) { int nv = adj.size(); vector<vector<int> > res((nv * (nv - 1)) / 2); int u = -1; for (int v1 = 0; v1 < nv; ++v1) { for (int v2 = v1 + 1; v2 < nv; ++v2) { ++u; vector<bool> b(nv); vector<int> p, q; p.push_back(v1); p.push_back(v2); b[v1] = true; b[v2] = true; while (!p.empty()) {
q.clear();
vector<bool> c = b;
vector<int> d;
vector<int> e(nv);
for (size_t i = 0; i < p.size(); ++i) {
int cnt = 0;
for (int j = 0; j < nv; ++j) { if (adj[p[i]][j] != '0') { if (!c[j]) { ++cnt; --e[j]; if (!b[j]) { b[j] = true; q.push_back(j); } } }
}
if (cnt) d.push_back(cnt);
}
if (q.empty()) break;
sort(d.begin(), d.end());
for (size_t k = 0; k < d.size(); ++k)
res[u].push_back(d[k]);
sort(e.begin(), e.end());
for (size_t k = 0; k < e.size() && e[k]; ++k)
res[u].push_back(e[k]);
p.swap(q); } } } sort(res.begin(), res.end()); return res; } int main() { clock_t start = clock(); freopen("iso1.txt", "r", stdin); freopen("iso2.txt", "w", stdout); int n; while (cin >> n) { vector<string> adj1(n), adj2(n); for (int i = 0; i < n; ++i) cin >> adj1[i]; for (int i = 0; i < n; ++i) cin >> adj2[i]; vector<vector<int> > res1 = foo(adj1); vector<vector<int> > res2 = foo(adj2); cout << "n = " << n << ": "; if (res1 == res2) cout << "YES\n"; else cout << "NO==============\n"; } printf("\n===time===\n%.3f\n", (double)(clock() - start) / CLOCKS_PER_SEC); return 0; } |
|
|
iso1.txt |
iso2.txt (this file will be
created by griso.exe) |
|
17 01101000110001011 10110100011000101 11011010001100010 01101101000110001 10110110100011000 01011011010001100 00101101101000110 00010110110100011 10001011011010001 11000101101101000 01100010110110100 00110001011011010 00011000101101101 10001100010110110 01000110001011011 10100011000101101 11010001100010110 00000101101011110 00111001000110110 01001110001101100 01001101110000101 01110000111001010 10110011010001100 00100101011100011 11010110100100010 10011001001101001 00011110000011011 10101010100000111 01100011100011001 11000000010101111 10101100110110000 11110100001010001 11001011011010000 00010010111110100 10 0100101000 1010000100 0101000010 0010100001 1001010000 0000100110 1000000011 0100010001 0010011000 0001001100 0001010001 0001101000 0000001101 1100000100 0100000011 1000001010 0110010000 0011000010 0000110100 1010100000 12 011001110000 101111000000 110100011000 011010001100 010101000110 110010100010 100001010011 101000101001 001100010101 000110001011 000011100101 000000111110 001001001101 000110011001 100001011010 010010110010 010100100101 101000100110 000111000110 011100001010 111000010001 100011100001 001101110000 110010001100 20 01001000000001000000 10100000000100000000 01010000010000000000 00101001000000000000 10010100000000000000 00001010000000100000 00000101000000001000 00010010100000000000 00000001010000000100 00100000101000000000 00000000010100000010 01000000001010000000 00000000000101000001 10000000000010100000 00000100000001010000 00000000000000101001 00000010000000010100 00000000100000001010 00000000001000000101 00000000000010010010 00000101000001000000 00011100000000000000 00010000000000100010 01100000000000000100 01000000100001000000 11000000000000100000 00000000000000001110 10000000011000000000 00001000000100000100 00000001000010010000 00000001000000100001 00000000100010001000 00000000010101000000 10001000000010000000 00100100001000000000 00000000010000001001 00000010000100010000 00010010100000000000 00100010000000000001 00000000001000010010 30 010000000000000000000100000001 101000001000000000000000000000 010100000000000000000000010000 001010000000100000000000000000 000101000000000001000000000000 000010100000000000000010000000 000001010000000000000000000100 000000101000001000000000000000 010000010100000000000000000000 000000001010000000100000000000 000000000101000000000001000000 000000000010100000000000000010 000100000001010000000000000000 000000000000101000001000000000 000000010000010100000000000000 000000000000001010000000100000 000000000000000101000000000001 000010000000000010100000000000 000000000100000001010000000000 000000000000000000101000001000 000000000000010000010100000000 100000000000000000001010000000 000001000000000000000101000000 000000000010000000000010100000 000000000000000100000001010000 001000000000000000000000101000 000000000000000000010000010100 000000100000000000000000001010 000000000001000000000000000101 100000000000000010000000000010 000000000000010001000000000100 000010000000000000001000100000 000000000010000000001001000000 000000100100001000000000000000 010000011000000000000000000000 000000000001000010000000001000 000100000000000010000000100000 000010000000000000100010000000 000010000001000100000000000000 000100000000100100000000000000 001000000000000000010100000000 000001001000000000000000000100 000000000100010000000000010000 100000000000100000100000000000 000100000000000000000011000000 000000001100000000010000000000 000001100000000000000100000000 100000000000000000000000100001 000000010000010000000100000000 000000000010000100000000000001 011000000000000000000000010000 000000000010000010100000000000 000000010000001000000000000010 001000000000001000000000000100 010000100000000001000000000000 000000000000100000001000001000 000001000000000000000000010010 100000000001000000000001000000 000000000000000000000010001001 000000000000000001010000000010 4 0111 1001 1000 1100 0101 1010 0101 1010 6 010010 101000 010101 001010 100100 001000 011000 100000 100101 001010 000101 100010 20 01111000100000000000 10110100010000000000 11010010001000000000 11100001000100000000 10000111000010000000 01001011000001000000 00101101000000100000 00011110000000010000 10000000011100001000 01000000101100000100 00100000110100000010 00010000111000000001 00001000000001110100 00000100000010111000 00000010000011010001 00000001000011100010 00000000100001000111 00000000010010001011 00000000001000011101 00000000000100101110 01111000100000000000 10110100010000000000 11010010001000000000 11100001000100000000 10000111000010000000 01001011000000000001 00101101000000100000 00011110000000000100 10000000011100001000 01000000101101000000 00100000110100000010 00010000111000010000 00001000000001100101 00000000010010011010 00000010000010010101 00000000000101101010 00000000100001010110 00000001000010101001 00000000001001011001 00000100000010100110 25 0000000000111111000000000 0000000000110000111100000 0000000000101000100011100 0000000000100100010010011 0000000000011000001001011 0000000000010010000110110 0000000000001001010100101 0000000000000110101000101 0000000000000101100101010 0000000000000011011011000 1111000000000000000000000 1100110000000000000000000 1010101000000000000000000 1001000110000000000000000 1000010101000000000000000 1000001011000000000000000 0110000110000000000000000 0101001001000000000000000 0100100101000000000000000 0100011010000000000000000 0011010001000000000000000 0010100011000000000000000 0010011100000000000000000 0001110010000000000000000 0001101100000000000000000 0000000000111111000000000 0000000000110000111100000 0000000000101000100011100 0000000000100100010010011 0000000000011000001001011 0000000000010010000110110 0000000000001001010100101 0000000000000110101000101 0000000000000101001111000 0000000000000011110001010 1111000000000000000000000 1100110000000000000000000 1010101000000000000000000 1001000110000000000000000 1000010101000000000000000 1000001011000000000000000 0110000101000000000000000 0101001001000000000000000 0100100110000000000000000 0100011010000000000000000 0011010010000000000000000 0010100011000000000000000 0010011100000000000000000 0001110001000000000000000 0001101100000000000000000 25 0111111111111000000000000 1011111000000111111000000 1101111000000000000111111 1110000111000111000111000 1110000100110100110100110 1110000010101010101010101 1110000001011001011001011 1001100011100101001000111 1001010101001000111101100 1001001110010010110010011 1000110100011011001110010 1000101001101110010011100 1000011010110101100101001 0101100100011011100001101 0101010001110100101011010 0101001100101100011110001 0100110011001110010100011 0100101011010001101110100 0100011110100011010001110 0011100010101001110011010 0011010001110011010100101 0011001010011110001100110 0010110110010100011011001 0010101101100010101101001 0010011101001101100010110 0111111111111000000000000 1011111000000111111000000 1101111000000000000111111 1110000111000111000111000 1110000100110100110100110 1110000010101010101010101 1110000001011001011001011 1001100011100101001000111 1001010101010010110001101 1001001110001000111110010 1000110100011110001011010 1000101010101011010101100 1000011001110101100110001 0101100100101001110011001 0101010010110001101101010 0101001100011110001100101 0100110011001110010100011 0100101011010100101011100 0100011101100011010010110 0011100001011011100010110 0011010001101100011101100 0011001010110110010010011 0010110110010001011110001 0010101101100010101101001 0010011110001101100001110 40 0000010001100001000000100000110001101011 0010001000100010100010010000000100011011 0100100010000001000011000110101001000001 0000010000010000100001110110010100000101 0010000100100010000000100101100110100100 1001000010000000000110000011100110010010 0100000001010000010001000001111110001000 0000100000011101000011000000010100110010 0010010000000100110001000001000001111100 1000001000000110000001001110000010110001 1100100000001000010000010010010011010100 0001001100000011010100000000100001010101 0000000100100000011101000111000000001011 0000000111000010001010010010110000001100 0100100001010100100100100011000001000010 1010000100010000101000100010001010011000 0101000010000011011000000100010010100010 0000001010111000100010101010100000100000 0000000000001101100000011001100111000001 0000010000011010000010010100001011101000 0110010100000100010100101000010010000001 0011001111001000000000110000000011000010 1001100000000011010011011001000000001000 0101000000100100001101100000101000110000 0000000001000000011010100100001101010110 0011100001001000100100001000110000011000 0011010001101111010000000000001100000000 0000111010001010001000100000011000010001 1010111000010100011000010100000000000010 1001001100100100100010000101001001000000 0010001000000001000100011011010000100110 0101111100000000001000001010000001101000 0000111001100001101111000000000000000100 1010000010110010001101001000010100000000 1000100111000000110100010000001100000001 0100010111110001000000011101000000000000 1100001010001101000100100100000100000100 0001100010110100000000001000001010001011 1100010100001010100001001000101000000100 1111000001011000001010000001000000100100 0100000001010000001011100000100010000111 1000000100001011000001000011001011001000 0001000010000101100010000000101110001010 0010000000011000000111110100001001010000 0000001000000100100001111010001000001101 0000000100000011010010111100000110000100 0000100000000010001100000000011111010110 0100010010010100000100100001011100000001 0010000101101000100100001000000011000101 1000000010000000010000101100011001101010 0000000010001000000011010011010100100110 1001000100000110100000010000110001100100 0101000010100110011000100000000000011100 0010100100011001011001001000010000000010 0100011000011000100110001000000000101010 0110010000000100000000000110000001110111 0010100010010010001000100111000010100000 0000010001001100001100010010101010100000 1000001000001100110010000101000101000001 0001001110000010010001000110100000000011 1011010000100010001000001010011000000001 1101100000100100000100001100000110100000 1001110101001000100000000010000100010010 0001110000110000010000000001000011001011 0000110011000110000011000001100001010000 0001010001000001101101000001010000001100 0100100000100001110110100000110001000000 0100000100100000101000011100101000010010 1010000000010000010100001011000100011100 0000001101110100000010000110000010011000 0111101101000000010010000001000000100100 0010011100100000001001100000100001101000 1110011010000000110001010000010000010000 0101001011010001001000011010000100000000 0000000001110011110001000000001100010001 0001001000001001000000101001110010100001 0110100001001010000000010100110100000001 1000111010111001000000000100101000000000 1010001001100111000100110001000000000000 1000100110000001001110010000000000111000 |
n = 17: YES n = 10: YES n = 12: YES n = 20: YES n = 30: YES n = 4: NO============== n = 6: NO============== n = 20: NO============== n = 25: NO============== n = 25: NO============== n = 40: NO============== ===time=== 0.266 |