Posted By

trusktr on 04/29/11
Tagged

php
simple
Versions (?)

Last Edited at 04/29/11 07:20am
Statistics

Viewed 733 times
Favorited by 0 user(s)
Related snippets

Verifying graph isomorphism in PHP.

/ Published in: PHP
A php program to check whether two simple connected graphs are isomorphic.
Expand | Embed | Plain Text
Copy this code and paste it in your HTML
<?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>