Advertisement
Guest User

Untitled

a guest
Jan 17th, 2017
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.98 KB | None | 0 0
  1. bool checkIsomorphism(Graph firstGraph, Graph secondGraph)
  2. {
  3.     int nodesCount = firstGraph.nodesCount;
  4.     int secondGraphMatrix[nodesCount][nodesCount]{-1};
  5.     int values[nodesCount];
  6.  
  7.     for (int i = 0; i < nodesCount; i++)
  8.     {
  9.         values[i] = i;
  10.         int ssize = secondGraph.nodes[i].size();
  11.  
  12.         for (int s = 0; s < ssize; s++)
  13.         {
  14.             secondGraphMatrix[i][secondGraph.nodes[i][s]] = s;
  15.         }
  16.     }
  17.  
  18.     do {
  19.         for (int i = 0; i < nodesCount; i++)
  20.         {
  21.             int fsize = firstGraph.nodes[i].size();
  22.             if (secondGraph.nodes[values[i]].size() != firstGraph.nodes[i].size())
  23.                 return false;
  24.             for (int j = 0; j < fsize; j++)
  25.             {
  26.                 if (values[firstGraph.nodes[i][j]] != secondGraph.nodes[values[i]][values[firstGraph.nodes[i][j]]])
  27.                     return false;
  28.             }
  29.         }
  30.     } while (std::next_permutation(values, values + nodesCount));
  31.  
  32. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement