Revision: 45397
Updated Code
at April 29, 2011 07:24 by trusktr
Updated Code
<?php
function sanitize_output($buffer) {
$search = array(
'/\>[^\S ]+/s', # strip whitespaces after tags, except space
'/[^\S ]+\</s', # strip whitespaces before tags, except space
'/(\s)+/s' # shorten multiple whitespace sequences
);
$replace = array(
'>',
'<',
'\\1'
);
$buffer = preg_replace($search, $replace, $buffer);
return $buffer;
}
ob_start("sanitize_output");
?>
<!DOCTYPE html>
<html>
<head>
<title>Verifying Graph Isomorphism</title>
<meta charset="utf-8" />
<style>
#results {
position: relative;
top: 920px;
}
#statistics {
position: absolute;
top: 335px;
}
</style>
</head>
<body>
<div id="wrapper">
<h1>Joe Pea - Verifying Graph Isomorphism</h1>
<?php
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.
$height = sizeof($adjMatrix1);
static $usedItems = array();
static $isomorphic = false; # flag that we set to true if we discover the graphs are isomorphic
if ($clear_static) {
$usedItems = array();
$isomorphic = false;
}
for ($i = 0; $i < sizeof($labels); $i++) {
$item = array_splice($labels, $i, 1); # take item out
$usedItems[] = $item[0];
if ( sizeof($labels) == 0 ) { # Houston, we have a permutation
$perm = $usedItems; # the currently $usedItems, at this point, comprise one permutation of the matrix labels.
/** Check if the current permutation applied to one graph (the same one each time) produces an identical graph*/
$check_passed = true;
for ($x=0; $x<$height; $x++) {
for ($y=0; $y<$height; $y++) {
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.
$check_passed = false; # we've found an inconsistency, moving on to next permutation...
break 2; # break out of the 2 for loops.
}
}
}
/** If so, we set the flag telling us that the graphs are isomorphic.*/
if ($check_passed) {
$isomorphic = true; # Since a check passed (graphs are isomorphic) set this flag to true for the final output.
}
}
the_verification($labels, &$adjMatrix1, &$adjMatrix2);
array_splice($labels, $i, 0, $item[0]); # put item back
array_pop($usedItems);
}
return ($isomorphic); # Return the result (true for isomorphic, false for not isomorphic)
}
function verify_isomorphism(&$adjMatrix1, &$adjMatrix2) { # verify if two graphs are isomorphic, based on their adjacency matrices.
$height1 = sizeof($adjMatrix1); # height of matrix1
$height2 = sizeof($adjMatrix2); # height of matrix2
/** Check to make sure the matrices are both square, and both of the same size, otherwise we don't perform the test.*/
$matrices_are_square_and_sameSize = true;
if ($height1 == $height2) { # if the matrices are the same height
for ($i = 0; $i < $height1; $i++) { # then for each row of the matrix
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.
$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.
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.
}
}
}
if ( $matrices_are_square_and_sameSize ) {
$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.
return the_verification($labels, &$adjMatrix1, &$adjMatrix2); # true or false, the graphs match or don't
}
else {
?><h1>Error: the matrices don't fit the criteria for being adjacency matrices, or the number of vertices don't match.</h1><?
return false;
}
}
/** Example Problem #1*/ ##########################################################################
$prob1_adjMatrix1 = array(
array(0,1,1,0,1,0),
array(1,0,1,0,0,1),
array(1,1,0,1,0,0),
array(0,0,1,0,1,1),
array(1,0,0,1,0,1),
array(0,1,0,1,1,0)
);
$prob1_adjMatrix2 = array(
array(0,1,0,1,1,0),
array(1,0,1,0,0,1),
array(0,1,0,1,1,0),
array(1,0,1,0,0,1),
array(1,0,1,0,0,1),
array(0,1,0,1,1,0)
);
$prob1_graphs_are_isomorphic = verify_isomorphism(&$prob1_adjMatrix1, &$prob1_adjMatrix2);
?><h3>Problem #1:</h3><?
echo ($prob1_graphs_are_isomorphic ? 'true ' : 'false ');
/** Example Problem #2*/ #############################################################################
$prob2_adjMatrix1 = array(
array(0,1,0,1,0),
array(1,0,1,1,1),
array(0,1,0,1,1),
array(1,1,1,0,0),
array(0,1,1,0,0)
);
$prob2_adjMatrix2 = array(
array(0,1,0,1,1),
array(1,0,0,1,0),
array(0,0,0,1,1),
array(1,1,1,0,1),
array(1,0,1,1,0)
);
$prob2_graphs_are_isomorphic = verify_isomorphism(&$prob2_adjMatrix1, &$prob2_adjMatrix2, true);
?><h3>Problem #2:</h3><?
echo ($prob2_graphs_are_isomorphic ? 'true ' : 'false ');
?>
</div>
</body>
</html>
Revision: 45396
Initial Code
Initial URL
Initial Description
Initial Title
Initial Tags
Initial Language
at April 29, 2011 07:20 by trusktr
Initial Code
<?php
function sanitize_output($buffer) {
$search = array(
'/\>[^\S ]+/s', # strip whitespaces after tags, except space
'/[^\S ]+\</s', # strip whitespaces before tags, except space
'/(\s)+/s' # shorten multiple whitespace sequences
);
$replace = array(
'>',
'<',
'\\1'
);
$buffer = preg_replace($search, $replace, $buffer);
return $buffer;
}
ob_start("sanitize_output");
?>
<!DOCTYPE html>
<html>
<head>
<title>Verifying Graph Isomorphism</title>
<meta charset="utf-8" />
<style>
#results {
position: relative;
top: 920px;
}
#statistics {
position: absolute;
top: 335px;
}
</style>
</head>
<body>
<div id="wrapper">
<h1>Joe Pea - Verifying Graph Isomorphism</h1>
<?php
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.
$height = sizeof($adjMatrix1);
static $usedItems = array();
static $isomorphic = false; # flag that we set to true if we discover the graphs are isomorphic
if ($clear_static) {
$usedItems = array();
$isomorphic = false;
}
for ($i = 0; $i < sizeof($labels); $i++) {
$item = array_splice($labels, $i, 1); # take item out
$usedItems[] = $item[0];
if ( sizeof($labels) == 0 ) { # Houston, we have a permutation
$perm = $usedItems; # the currently $usedItems, at this point, comprise one permutation of the matrix labels.
/** Check if the current permutation applied to one graph (the same one each time) produces an identical graph*/
$check_passed = true;
for ($x=0; $x<$height; $x++) {
for ($y=0; $y<$height; $y++) {
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.
$check_passed = false; # we've found an inconsistency, moving on to next permutation...
break 2; # break out of the 2 for loops.
}
}
}
/** If so, we set the flag telling us that the graphs are isomorphic.*/
if ($check_passed) {
$isomorphic = true; # Since a check passed (graphs are isomorphic) set this flag to true for the final output.
}
}
the_verification($labels, &$adjMatrix1, &$adjMatrix2);
array_splice($labels, $i, 0, $item[0]); # put item back
array_pop($usedItems);
}
return ($isomorphic); # Return the result (true for isomorphic, false for not isomorphic)
}
function verify_isomorphism(&$adjMatrix1, &$adjMatrix2) { # verify if two graphs are isomorphic, based on their adjacency matrices.
$height1 = sizeof($adjMatrix1); # height of matrix1
$height2 = sizeof($adjMatrix2); # height of matrix2
/** Check to make sure the matrices are both square, and both of the same size, otherwise we don't perform the test.*/
$matrices_are_square_and_sameSize = true;
if ($height1 == $height2) { # if the matrices are the same height
for ($i = 0; $i < $height1; $i++) { # then for each row of the matrix
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.
$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.
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.
}
}
}
if ( $matrices_are_square_and_sameSize ) {
$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.
return the_verification($labels, &$adjMatrix1, &$adjMatrix2); # true or false, the graphs match or don't
}
else {
?><h1>Error: the matrices don't fit the criteria for being adjacency matrices, or the number of vertices don't match.</h1><?
return false;
}
}
/** Problem #1*/ ##########################################################################
$prob1_adjMatrix1 = array(
array(0,1,1,0,1,0),
array(1,0,1,0,0,1),
array(1,1,0,1,0,0),
array(0,0,1,0,1,1),
array(1,0,0,1,0,1),
array(0,1,0,1,1,0)
);
$prob1_adjMatrix2 = array(
array(0,1,0,1,1,0),
array(1,0,1,0,0,1),
array(0,1,0,1,1,0),
array(1,0,1,0,0,1),
array(1,0,1,0,0,1),
array(0,1,0,1,1,0)
);
$prob1_graphs_are_isomorphic = verify_isomorphism(&$prob1_adjMatrix1, &$prob1_adjMatrix2);
?><h3>Problem #1:</h3><?
echo ($prob1_graphs_are_isomorphic ? 'true ' : 'false ');
/** Problem #2*/ #############################################################################
$prob2_adjMatrix1 = array(
array(0,1,0,1,0),
array(1,0,1,1,1),
array(0,1,0,1,1),
array(1,1,1,0,0),
array(0,1,1,0,0)
);
$prob2_adjMatrix2 = array(
array(0,1,0,1,1),
array(1,0,0,1,0),
array(0,0,0,1,1),
array(1,1,1,0,1),
array(1,0,1,1,0)
);
$prob2_graphs_are_isomorphic = verify_isomorphism(&$prob2_adjMatrix1, &$prob2_adjMatrix2, true);
?><h3>Problem #2:</h3><?
echo ($prob2_graphs_are_isomorphic ? 'true ' : 'false ');
?>
</div>
</body>
</html>
Initial URL
Initial Description
A php program to check whether two simple connected graphs are isomorphic.
Initial Title
Verifying graph isomorphism in PHP.
Initial Tags
php, simple
Initial Language
PHP