API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Apr 20th, 2018
88
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 13.44 KB | None | 0 0
raw download clone embed print report
  1. /*
  2. * WIP Polynomial Time Algorithm: Given 2 Graphs, are they Isomorphic?
  3. * By Karim Ehab ElSheikh 2018-04-20
  4. */
  5.  
  6. using namespace std;
  7. #include<bits/stdc++.h>
  8.  
  9. int n1, n2, n;
  10. multiset<pair<int, int> > e1;
  11. multiset<pair<int, int> > e2;
  12.  
  13. vector<int> g1[100];
  14. vector<int> g2[100];
  15.  
  16. int z[100];
  17.  
  18. bool matched[10000];
  19.  
  20. vector<int> u1;
  21. vector<int> u2;
  22.  
  23. set<pair<int,int> > tp1[100][100];
  24. set<pair<int,int> > tp2[100][100];
  25. multiset<int> t1[100][100];
  26. multiset<int> t2[100][100];
  27.  
  28. bool visited[100];
  29.  
  30. int m[20][100];
  31. int sol[20][100][100];
  32.  
  33. int M[100];
  34. int invM[100];
  35.  
  36. int maximumDepth;
  37.  
  38. bool graph;
  39.  
  40. //debug
  41. #define dump(x) cerr << #x << " = " << (x) << endl
  42. #define write(x) cerr << #x << " = " << (x) << ", "
  43. #define writeI0 cerr << "i = " << 0 << ", "
  44. #define dumpI0 cerr << "i = " << 0 << endl
  45. #define printArray(a,x,y) for(auto it = a+x; it != a+y; it++) (it==a+x)? cout << *it : cout << ' ' << *it; cout << endl
  46. #define printSet(s) if(s.size()==0) cout << "{}"; else for(auto it = s.begin(); it!=s.end(); it++) (it==s.begin())? cout << *it : cout << ' ' << *it; cout << endl
  47. #define printSet2(s) if(s.size()==0) cout << "{}"; else for(auto it = s.begin(); it!=s.end(); it++) (it==s.begin())? cout << *it : cout << ',' << *it;
  48. #define printPairSet(s) for(auto it = s.begin(); it!=s.end(); it++) (it==s.begin())? cout << '(' << it->first << ", " << it->second << ')' : cout << " (" << it->first << ", " << it->second << ')'; cout << endl
  49. #define printVector(x) for(auto it = x.begin(); it!=x.end(); it++) (it==x.begin())? cout << *it : cout << ' ' << *it; cout << endl
  50.  
  51. int dfs(int i, bool grph) {
  52. visited[invM[i]] = true;
  53. int to, degree2, r = 0;
  54. if(!grph) {
  55. for(int j = 0; j < g1[i].size(); j++) {
  56. to = M[g1[i][j]];
  57. if(visited[to]) continue;
  58. r += dfs(to, grph) + 1;
  59. }
  60. }
  61. else {
  62. for(int j = 0; j < g2[i].size(); j++) {
  63. to = g2[i][j];
  64. if(visited[to]) continue;
  65. r += dfs(to, grph) + 1;
  66. }
  67. }
  68. return r;
  69. }
  70.  
  71. void caculateMaximumDepth(int s, int e, bool graph) { // Largest Connected Component, Constant Factor Optimization
  72. int maximumPotentialDepth = e-s;
  73. maximumDepth = maximumPotentialDepth;
  74. for(int i = s; i <= e; i++)
  75. visited[i] = false;
  76.  
  77. if(!graph) {
  78. for(int i = s; i <= e; i++)
  79. if(!visited[i])
  80. maximumDepth = min(maximumDepth, dfs(M[i], false));
  81. }
  82. else {
  83. for(int i = s; i <= e; i++)
  84. if(!visited[i])
  85. maximumDepth = min(maximumDepth, dfs(i, true));
  86. }
  87. }
  88.  
  89. void clearTravellingTable(int s1, int e1, int s2, int e2) {
  90. caculateMaximumDepth(s1, e1, false);
  91. for(int i = s1; i <= e1; i++) {
  92. for(int j = 0; j <= maximumDepth; j++) {
  93. t1[i][j].clear();
  94. }
  95. }
  96. caculateMaximumDepth(s2, e2, true);
  97. for(int i = s2; i <= e2; i++) {
  98. for(int j = 0; j <= maximumDepth; j++) {
  99. t2[i][j].clear();
  100. }
  101. }
  102. }
  103.  
  104. void buildTravellingTable(int s1, int e1, int s2, int e2) {
  105. u1.clear();
  106. for(int i = s1; i <= e1; i++) {
  107. u1.push_back(M[i]);
  108. tp1[i][0].insert(make_pair(M[i], g1[M[i]].size()));
  109. }
  110. for(int i = s2; i <= e2; i++) {
  111. tp2[i][0].insert(make_pair(i, g2[i].size()));
  112. }
  113. sort(u1.begin(), u1.end());
  114.  
  115. int to, node, degree, degree2;
  116.  
  117. caculateMaximumDepth(s1, e1, false);
  118. dump(maximumDepth);
  119. for(int i = s1; i <= e1; i++) {
  120. for(int j = 0; j < maximumDepth; j++) {
  121. for(auto it = tp1[i][j].begin(); it != tp1[i][j].end(); it++) {
  122. node = it->first;
  123. degree = it->second;
  124. for(int k = 0; k < g1[node].size(); k++) {
  125. if(!binary_search(u1.begin(), u1.end(), g1[node][k])) continue;
  126. to = g1[node][k];
  127. degree2 = degree + g1[to].size();
  128. tp1[i][j+1].insert(make_pair(to, degree2));
  129. }
  130. }
  131. }
  132. }
  133.  
  134. caculateMaximumDepth(s2, e2, true);
  135. for(int i = s2; i <= e2; i++) {
  136. for(int j = 0; j < maximumDepth; j++) {
  137. for(auto it = tp1[i][j].begin(); it != tp2[i][j].end(); it++) {
  138. node = it->first;
  139. degree = it->second;
  140. for(int k = 0; k < g2[node].size(); k++) {
  141. if(g2[node][k] < s2 || g2[node][k] > e2) continue;
  142. to = g2[node][k];
  143. degree2 = degree + g2[to].size();
  144. tp2[i][j+1].insert(make_pair(to, degree2));
  145. }
  146. }
  147. }
  148. }
  149.  
  150. for(int i = s1; i <= e1; i++) {
  151. for(int j = 0; j <= maximumDepth; j++) {
  152. for(auto it = tp1[i][j].begin(); it != tp1[i][j].end(); it++)
  153. t1[i][j].insert(it->second);
  154. for(auto it = tp2[i][j].begin(); it != tp2[i][j].end(); it++)
  155. t2[i][j].insert(it->second);
  156. }
  157. }
  158. }
  159.  
  160. auto comp = [] (int x, int y) {
  161. int a, b, cmp;
  162. if(!graph) {
  163. for(int i = 0; i <= maximumDepth; i++) {
  164. for(auto it = t1[x][i].begin(); it != t1[x][i].end(); it++) {
  165. a = t1[x][i].count(*it);
  166. b = t1[y][i].count(*it);
  167. cmp = a - b;
  168. if(cmp < 0) return false;
  169. else if(cmp > 0) return true;
  170. }
  171. a = t1[x][i].size();
  172. b = t1[y][i].size();
  173. cmp = a - b;
  174. if(cmp < 0) return false;
  175. else if(cmp > 0) return true;
  176. }
  177. return true;
  178. }
  179. else {
  180. for(int i = 0; i <= maximumDepth; i++) {
  181. for(auto it = t1[x][i].begin(); it != t1[x][i].end(); it++) {
  182. a = t1[x][i].count(*it);
  183. b = t1[y][i].count(*it);
  184. cmp = a - b;
  185. if(cmp < 0) return false;
  186. else if(cmp > 0) return true;
  187. }
  188. a = t1[x][i].size();
  189. b = t1[y][i].size();
  190. cmp = a - b;
  191. if(cmp < 0) return false;
  192. else if(cmp > 0) return true;
  193. }
  194. return true;
  195. }
  196. };
  197.  
  198. int cmp(multiset<int> x[], multiset<int> y[]) {
  199. int a, b, cmp;
  200. if(!graph) {
  201. for(int i = 0; i <= maximumDepth; i++) {
  202. for(auto it = x[i].begin(); it != x[i].end(); it++) {
  203. a = x[i].count(*it);
  204. b = y[i].count(*it);
  205. cmp = a - b;
  206. if(cmp < 0) return -1;
  207. else if(cmp > 0) return 1;
  208. }
  209. a = x[i].size();
  210. b = y[i].size();
  211. cmp = a - b;
  212. if(cmp < 0) return -1;
  213. else if(cmp > 0) return 1;
  214. }
  215. return 0;
  216. }
  217. else {
  218. for(int i = 0; i <= maximumDepth; i++) {
  219. for(auto it = x[i].begin(); it != x[i].end(); it++) {
  220. a = x[i].count(*it);
  221. b = y[i].count(*it);
  222. cmp = a - b;
  223. if(cmp < 0) return -1;
  224. else if(cmp > 0) return 1;
  225. }
  226. a = x[i].size();
  227. b = y[i].size();
  228. cmp = a - b;
  229. if(cmp < 0) return -1;
  230. else if(cmp > 0) return 1;
  231. }
  232. return 0;
  233. }
  234. }
  235.  
  236. void travellingPartition(int s1, int e1, int s2, int e2) {
  237. clearTravellingTable(s1, e1, s2, e2);
  238. buildTravellingTable(s1, e1, s2, e2);
  239. for(int i = s1; i <= e1; i++)
  240. z[i] = i;
  241. graph = false;
  242. sort(z+s1, z+e1+1, comp);
  243. int mid = (s1+e1)/2;
  244. int a, b;
  245. for(int i = s1+1; i <= mid; i+= 2) {
  246. a = M[z[i]], b = M[z[i-s1+mid]];
  247. swap(M[z[i]], M[z[i-s1+mid]]);
  248. swap(invM[a], invM[b]);
  249. }
  250.  
  251. // graph = true;
  252. // sort(z+s2, z+e2+1, comp);
  253. // int mid = (s2+e2)/2;
  254. // for(int i = s2+1; i <= mid; i+= 2) {
  255. // a = M[i], b = M[i-s2+mid];
  256. // swap(M[i], M[i-s2+mid]);
  257. // swap(invM[a], invM[b]);
  258. // }
  259. }
  260.  
  261. bool sharedEdgesTravelEquivalent(int s1, int e1, int s2, int e2) {
  262. u1.clear();
  263. u2.clear();
  264.  
  265. int node, to;
  266.  
  267. int mid1 = (s1+e1)/2;
  268. for(int i = s1; i <= mid1; i++) {
  269. node = M[i];
  270. for(int j = 0; j < g1[node].size(); j++) {
  271. to = g1[node][j];
  272. if(to > mid1) {
  273. u1.push_back(node);
  274. u1.push_back(to);
  275. }
  276. }
  277. }
  278.  
  279. int mid2 = (s2+e2)/2;
  280. for(int i = s2; i <= mid2; i++) {
  281. node = M[i];
  282. for(int j = 0; j < g2[node].size(); j++) {
  283. to = g2[node][j];
  284. if(to > mid2) {
  285. u2.push_back(node);
  286. u2.push_back(to);
  287. }
  288. }
  289. }
  290.  
  291. sort(u1.begin(), u1.end());
  292. sort(u2.begin(), u2.end());
  293.  
  294. for(int i = 0; i < u1.size(); i++)
  295. matched[i] = 0;
  296.  
  297. bool ok = true;
  298. bool foundMatch;
  299. for(int i = 0; i < u1.size(); i++) {
  300. foundMatch = false;
  301. for(int j = 0; j < u1.size(); j++) { // j can be the same i!!! Necessary for a correct algorithm
  302. if(matched[j]) continue;
  303. if(cmp(t1[i], t1[j]) == 0) {
  304. matched[j] = true;
  305. foundMatch = true;
  306. break;
  307. }
  308. }
  309. if(!foundMatch) {
  310. ok = false;
  311. break;
  312. }
  313. }
  314.  
  315. if(!ok) return false;
  316. else return true;
  317.  
  318. for(int i = 0; i < u2.size(); i++)
  319. matched[i] = 0;
  320.  
  321. for(int i = 0; i < u2.size(); i++) {
  322. foundMatch = false;
  323. for(int j = 0; j < u2.size(); j++) { // j can be the same i!!! Necessary for a correct algorithm
  324. if(matched[j]) continue;
  325. if(cmp(t2[i], t2[j]) == 0) {
  326. matched[j] = true;
  327. foundMatch = true;
  328. break;
  329. }
  330. }
  331. if(!foundMatch) {
  332. ok = false;
  333. break;
  334. }
  335. }
  336.  
  337. if(!ok) return false;
  338. else return true;
  339. }
  340.  
  341. bool areIso(int s1, int e1, int s2, int e2) {
  342. if (s1 == e1 && s2 == e2) {
  343. if(g1[M[s1]].size() == g2[s2].size()) {
  344. swap(M[s1], M[invM[s2]]);
  345. return true;
  346. }
  347. return false;
  348. }
  349. else if (s1 + 1 == e1 && s2 + 1 == e2) {
  350. if(g1[M[s1]].size() == g2[s2].size() && g1[M[e1]].size() == g2[e2].size()) {
  351. swap(M[s1], M[invM[s2]]), swap(M[e1], M[invM[e2]]);
  352. return true;
  353. }
  354. else if(g1[M[s1]].size() == g2[e2].size() && g1[M[e1]].size() == g2[s2].size()) {
  355. swap(M[s1], M[invM[e2]]), swap(M[e1], M[invM[s2]]);
  356. return true;
  357. }
  358. return false;
  359. }
  360.  
  361. int mid1 = (s1+e1)/2;
  362. int mid2 = (s2+e2)/2;
  363. if (areIso(s1, mid1, s2, mid2) && areIso(mid1+1, e1, mid2+1, e2)) {
  364. travellingPartition(s1, e1, s2, e2);
  365. if (sharedEdgesTravelEquivalent(s1, e1, s2, e2)) {
  366. return true;
  367. }
  368. }
  369. else if (areIso(s1, mid1, mid2+1, e2) && areIso(mid1+1, e1, s2, mid2)) {
  370. travellingPartition(s1, e1, s2, e2);
  371. if (sharedEdgesTravelEquivalent(s1, e1, s2, e2)) {
  372. // for(int i = 0; i <= b; i++)
  373. // m[d][i] = m[d+1][i];
  374. for(int i = s1+1; i <= mid; i+= 2) {
  375. a = M[z[i]], b = M[z[i-s1+mid]];
  376. swap(M[z[i]], M[z[i-s1+mid]]);
  377. swap(invM[a], invM[b]);
  378. }
  379. }
  380. }
  381. return false;
  382. }
  383.  
  384. int main() {
  385. cout << "Enter the number of nodes of the 1st Graph:\n";
  386. cin >> n1;
  387. cin.ignore();
  388. cout << "Enter the edges in pseudo-DIMACS format, terminate by \"e\" in a line\n";
  389. string s;
  390. while(true) {
  391. getline(cin, s);
  392. if(s == "e") break;
  393. stringstream ss(s);
  394. ss >> s;
  395. int a, b;
  396. ss >> a >> b;
  397. a--; b--;
  398. e1.insert(make_pair(a, b));
  399. }
  400.  
  401. for(auto it = e1.begin(); it != e1.end(); it++) {
  402. g1[it->first].push_back(it->second);
  403. g1[it->second].push_back(it->first);
  404. }
  405.  
  406. cout << "Enter the number of nodes of the 2nd Graph:\n";
  407. cin >> n2;
  408. cin.ignore();
  409. cout << "Enter the edges in pseudo-DIMACS format, terminate by \"e\" in a line\n";
  410. while(true) {
  411. getline(cin, s);
  412. if(s == "e") break;
  413. stringstream ss(s);
  414. ss >> s;
  415. int a, b;
  416. ss >> a >> b;
  417. a--; b--;
  418. e2.insert(make_pair(a, b));
  419. }
  420.  
  421. for(auto it = e2.begin(); it != e2.end(); it++) {
  422. g2[it->first].push_back(it->second);
  423. g2[it->second].push_back(it->first);
  424. }
  425.  
  426. if(n1 != n2) {
  427. cout << "KABOOM" << endl;
  428. cout << "The given Graph are not Isomorphic\n";
  429. return 0;
  430. }
  431. n = n1;
  432. maximumDepth = n-1;
  433.  
  434. for(int i = 0; i < 20; i++)
  435. for(int j = 0; j < n; j++)
  436. m[i][j] = j;
  437.  
  438. for(int i = 0; i < n; i++) {
  439. M[i] = i;
  440. invM[i] = i;
  441. }
  442.  
  443. for(int i = 0; i < n; i++) {
  444. for(int j = 0; j <= maximumDepth; j++) {
  445. printSet2(t1[i][j]);
  446. cout << ' ';
  447. }
  448. cout << endl;
  449. }
  450.  
  451. // int ans = areIso(0, 0, 0);
  452. // if(ans == 1) {
  453. // cout << "The 2 given Graphs are Isomorphic\n";
  454. // }
  455. // else if(ans == -1) {
  456. // cout << "The 2 given Graphs are not Isomorphic\n";
  457. // }
  458. // else { // ans == 0, (function is bugged)
  459. // cout << "No Answer produced for the 2 given Graphs, check the code for bugs\n";
  460. // }
  461. return 0;
  462. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!