Posted By

trusktr on 04/29/11


Tagged

php simple connected Graphs permutations matrices isomorphism adjacency


Versions (?)

Verifying graph isomorphism in PHP.


 / Published in: PHP
 

A php program to check whether two simple connected graphs are isomorphic.

  1. <?php
  2. function sanitize_output($buffer) {
  3. $search = array(
  4. '/\>[^\S ]+/s', # strip whitespaces after tags, except space
  5. '/[^\S ]+\</s', # strip whitespaces before tags, except space
  6. '/(\s)+/s' # shorten multiple whitespace sequences
  7. );
  8. $replace = array(
  9. '>',
  10. '<',
  11. '\\1'
  12. );
  13. $buffer = preg_replace($search, $replace, $buffer);
  14. return $buffer;
  15. }
  16.  
  17. ob_start("sanitize_output");
  18.  
  19. ?>
  20. <!DOCTYPE html>
  21. <html>
  22. <head>
  23. <title>Verifying Graph Isomorphism</title>
  24. <meta charset="utf-8" />
  25. <style>
  26. #results {
  27. position: relative;
  28. top: 920px;
  29. }
  30. #statistics {
  31. position: absolute;
  32. top: 335px;
  33. }
  34. </style>
  35. </head>
  36. <body>
  37. <div id="wrapper">
  38. <h1>Joe Pea - Verifying Graph Isomorphism</h1>
  39. <?php
  40. function the_verification($labels, &$adjMatrix1, &$adjMatrix2, $clear_static = false) { # The actual verification called inside verify_isomorphism(), assuming both matrices are adjacency matrices of the same size.
  41. $height = sizeof($adjMatrix1);
  42. static $usedItems = array();
  43. static $isomorphic = false; # flag that we set to true if we discover the graphs are isomorphic
  44. if ($clear_static) {
  45. $usedItems = array();
  46. $isomorphic = false;
  47. }
  48. for ($i = 0; $i < sizeof($labels); $i++) {
  49. $item = array_splice($labels, $i, 1); # take item out
  50. $usedItems[] = $item[0];
  51.  
  52. if ( sizeof($labels) == 0 ) { # Houston, we have a permutation
  53. $perm = $usedItems; # the currently $usedItems, at this point, comprise one permutation of the matrix labels.
  54.  
  55. /** Check if the current permutation applied to one graph (the same one each time) produces an identical graph*/
  56. $check_passed = true;
  57. for ($x=0; $x<$height; $x++) {
  58. for ($y=0; $y<$height; $y++) {
  59. if ($adjMatrix1[$x][$y] != $adjMatrix2[ $perm[$x] ][ $perm[$y] ]) { # When this if statement fails, that means we've found a match. For all permutations, except the match (if it exists), the statment will result in the check not passed.
  60. $check_passed = false; # we've found an inconsistency, moving on to next permutation...
  61. break 2; # break out of the 2 for loops.
  62. }
  63. }
  64. }
  65.  
  66. /** If so, we set the flag telling us that the graphs are isomorphic.*/
  67. if ($check_passed) {
  68. $isomorphic = true; # Since a check passed (graphs are isomorphic) set this flag to true for the final output.
  69. }
  70. }
  71. the_verification($labels, &$adjMatrix1, &$adjMatrix2);
  72. array_splice($labels, $i, 0, $item[0]); # put item back
  73. array_pop($usedItems);
  74. }
  75. return ($isomorphic); # Return the result (true for isomorphic, false for not isomorphic)
  76. }
  77.  
  78. function verify_isomorphism(&$adjMatrix1, &$adjMatrix2) { # verify if two graphs are isomorphic, based on their adjacency matrices.
  79. $height1 = sizeof($adjMatrix1); # height of matrix1
  80. $height2 = sizeof($adjMatrix2); # height of matrix2
  81.  
  82. /** Check to make sure the matrices are both square, and both of the same size, otherwise we don't perform the test.*/
  83. $matrices_are_square_and_sameSize = true;
  84. if ($height1 == $height2) { # if the matrices are the same height
  85. for ($i = 0; $i < $height1; $i++) { # then for each row of the matrix
  86. if ( (sizeof($adjMatrix1[$i]) != $height1) or (sizeof($adjMatrix2[$i]) != $height2) ) { # check to see that the size of the rows (the matrix width) are also the matrix height, and therefore square.
  87. $matrices_are_square_and_sameSize = false; # If we have one row that isn't the size of the height, then we have a matrix that isn't square, and therefore not a graph.
  88. break; # if one row is not the size of the matrix height, then one of the matrices is not square. Break so as not to set the following variable true.
  89. }
  90. }
  91. }
  92.  
  93. if ( $matrices_are_square_and_sameSize ) {
  94. $labels = array(); for ($n=0; $n<$height1; $n++) { $labels[] = $n; } # set up the labeling system used to refer to matrix items (e.g. both the columns and rows are labeled as 0,1,2,3,4,5,etc). We will permute this label system to derive the permutations of verifications that we will be doing.
  95. return the_verification($labels, &$adjMatrix1, &$adjMatrix2); # true or false, the graphs match or don't
  96. }
  97. else {
  98. ?><h1>Error: the matrices don't fit the criteria for being adjacency matrices, or the number of vertices don't match.</h1><?
  99. return false;
  100. }
  101. }
  102.  
  103.  
  104.  
  105.  
  106.  
  107.  
  108.  
  109.  
  110.  
  111.  
  112.  
  113. /** Example Problem #1*/ ##########################################################################
  114. $prob1_adjMatrix1 = array(
  115. array(0,1,1,0,1,0),
  116. array(1,0,1,0,0,1),
  117. array(1,1,0,1,0,0),
  118. array(0,0,1,0,1,1),
  119. array(1,0,0,1,0,1),
  120. array(0,1,0,1,1,0)
  121. );
  122. $prob1_adjMatrix2 = array(
  123. array(0,1,0,1,1,0),
  124. array(1,0,1,0,0,1),
  125. array(0,1,0,1,1,0),
  126. array(1,0,1,0,0,1),
  127. array(1,0,1,0,0,1),
  128. array(0,1,0,1,1,0)
  129. );
  130.  
  131. $prob1_graphs_are_isomorphic = verify_isomorphism(&$prob1_adjMatrix1, &$prob1_adjMatrix2);
  132. ?><h3>Problem #1:</h3><?
  133. echo ($prob1_graphs_are_isomorphic ? 'true ' : 'false ');
  134.  
  135.  
  136.  
  137.  
  138.  
  139.  
  140.  
  141.  
  142.  
  143.  
  144. /** Example Problem #2*/ #############################################################################
  145. $prob2_adjMatrix1 = array(
  146. array(0,1,0,1,0),
  147. array(1,0,1,1,1),
  148. array(0,1,0,1,1),
  149. array(1,1,1,0,0),
  150. array(0,1,1,0,0)
  151. );
  152. $prob2_adjMatrix2 = array(
  153. array(0,1,0,1,1),
  154. array(1,0,0,1,0),
  155. array(0,0,0,1,1),
  156. array(1,1,1,0,1),
  157. array(1,0,1,1,0)
  158. );
  159.  
  160. $prob2_graphs_are_isomorphic = verify_isomorphism(&$prob2_adjMatrix1, &$prob2_adjMatrix2, true);
  161. ?><h3>Problem #2:</h3><?
  162. echo ($prob2_graphs_are_isomorphic ? 'true ' : 'false ');
  163. ?>
  164.  
  165.  
  166.  
  167.  
  168.  
  169.  
  170.  
  171. </div>
  172. </body>
  173. </html>

Report this snippet  

You need to login to post a comment.