--- /dev/null
+<?php
+
+/**
+ * EasyRdf
+ *
+ * LICENSE
+ *
+ * Copyright (c) 2013 Nicholas J Humfrey. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright notice,
+ * this list of conditions and the following disclaimer in the documentation
+ * and/or other materials provided with the distribution.
+ * 3. The name of the author 'Nicholas J Humfrey" may be used to endorse or
+ * promote products derived from this software without specific prior
+ * written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * @package EasyRdf
+ * @copyright Copyright (c) 2013 Nicholas J Humfrey
+ * @license http://www.opensource.org/licenses/bsd-license.php
+ */
+
+/**
+ * Functions for comparing two graphs with each other
+ *
+ * Based on rdf-isomorphic.rb by Ben Lavender:
+ * https://github.com/ruby-rdf/rdf-isomorphic
+ *
+ * @package EasyRdf
+ * @copyright Copyright (c) 2013 Nicholas J Humfrey
+ * @license http://www.opensource.org/licenses/bsd-license.php
+ */
+class EasyRdf_Isomorphic
+{
+ /**
+ * Check if one graph is isomorphic (equal) to another graph
+ *
+ * For example:
+ * $graphA = EasyRdf_Graph::newAndLoad('http://example.com/a.ttl');
+ * $graphB = EasyRdf_Graph::newAndLoad('http://example.com/b.ttl');
+ * if (EasyRdf_Isomorphic::isomorphic($graphA, $graphB)) print "Equal!";
+ *
+ * @param object EasyRdf_Graph $graphA The first graph to be compared
+ * @param object EasyRdf_Graph $graphB The second graph to be compared
+ * @return boolean True if the two graphs are isomorphic
+ */
+ public static function isomorphic($graphA, $graphB)
+ {
+ return is_array(self::bijectionBetween($graphA, $graphB));
+ }
+
+ /**
+ * Returns an associative array of bnode identifiers representing an isomorphic
+ * bijection of one EasyRdf_Graph to another EasyRdf_Graph's blank nodes or
+ * null if a bijection cannot be found.
+ *
+ * @param object EasyRdf_Graph $graphA The first graph to be compared
+ * @param object EasyRdf_Graph $graphB The second graph to be compared
+ * @return array bnode mapping from $graphA to $graphB
+ */
+ public static function bijectionBetween($graphA, $graphB)
+ {
+ $bnodesA = array();
+ $bnodesB = array();
+ $statementsA = array();
+ $statementsB = array();
+
+ // Quick initial check: are there differing numbers of subjects?
+ if (self::countSubjects($graphA) != self::countSubjects($graphB)) {
+ return null;
+ }
+
+ // Check if all the statements in Graph A exist in Graph B
+ $groundedStatementsMatch = self::groundedStatementsMatch($graphA, $graphB, $bnodesA, $statementsA);
+
+ if ($groundedStatementsMatch) {
+ // Check if all the statements in Graph B exist in Graph A
+ $groundedStatementsMatch = self::groundedStatementsMatch($graphB, $graphA, $bnodesB, $statementsB);
+ }
+
+ if ($groundedStatementsMatch === false) {
+ // The grounded statements do not match
+ return null;
+ } elseif (count($bnodesA) > 0 or count($bnodesB > 0)) {
+ // There are blank nodes - build a bi-jection
+ return self::buildBijectionTo($statementsA, $bnodesA, $statementsB, $bnodesB);
+ } else {
+ // No bnodes and the grounded statements match
+ return array();
+ }
+ }
+
+ /**
+ * Count the number of subjects in a graph
+ * @ignore
+ */
+ private static function countSubjects($graph)
+ {
+ return count($graph->toRdfPhp());
+ }
+
+ /**
+ * Check if all the statements in $graphA also appear in $graphB
+ * @ignore
+ */
+ private static function groundedStatementsMatch($graphA, $graphB, &$bnodes, &$anonStatements)
+ {
+ $groundedStatementsMatch = true;
+
+ foreach ($graphA->toRdfPhp() as $subject => $properties) {
+ if (substr($subject, 0, 2) == '_:') {
+ array_push($bnodes, $subject);
+ $subjectIsBnode = true;
+ } else {
+ $subjectIsBnode = false;
+ }
+
+ foreach ($properties as $property => $values) {
+ foreach ($values as $value) {
+ if ($value['type'] == 'uri' and substr($value['value'], 0, 2) == '_:') {
+ array_push($bnodes, $value['value']);
+ $objectIsBnode = true;
+ } else {
+ $objectIsBnode = false;
+ }
+
+ if ($groundedStatementsMatch and
+ $subjectIsBnode === false and
+ $objectIsBnode === false and
+ $graphB->hasProperty($subject, $property, $value) === false
+ ) {
+ $groundedStatementsMatch = false;
+ }
+
+ if ($subjectIsBnode or $objectIsBnode) {
+ array_push(
+ $anonStatements,
+ array(
+ array('type' => $subjectIsBnode ? 'bnode' : 'uri', 'value' => $subject),
+ array('type' => 'uri', 'value' => $property),
+ $value
+ )
+ );
+ }
+ }
+ }
+ }
+
+ return $groundedStatementsMatch;
+ }
+
+ /**
+ * The main recursive bijection algorithm.
+ *
+ * This algorithm is very similar to the one explained by Jeremy Carroll in
+ * http://www.hpl.hp.com/techreports/2001/HPL-2001-293.pdf. Page 12 has the
+ * relevant pseudocode.
+ *
+ * @ignore
+ */
+ private static function buildBijectionTo
+ (
+ $statementsA,
+ $nodesA,
+ $statementsB,
+ $nodesB,
+ $groundedHashesA = array(),
+ $groundedHashesB = array()
+ ) {
+
+ // Create a hash signature of every node, based on the signature of
+ // statements it exists in.
+ // We also save hashes of nodes that cannot be reliably known; we will use
+ // that information to eliminate possible recursion combinations.
+ //
+ // Any mappings given in the method parameters are considered grounded.
+ list($hashesA, $ungroundedHashesA) = self::hashNodes($statementsA, $nodesA, $groundedHashesA);
+ list($hashesB, $ungroundedHashesB) = self::hashNodes($statementsB, $nodesB, $groundedHashesB);
+
+ // Grounded hashes are built at the same rate between the two graphs (if
+ // they are isomorphic). If there exists a grounded node in one that is
+ // not in the other, we can just return. Ungrounded nodes might still
+ // conflict, so we don't check them. This is a little bit messy in the
+ // middle of the method, and probably slows down isomorphic checks, but
+ // prevents almost-isomorphic cases from getting nutty.
+ foreach ($hashesA as $nodeA => $hashA) {
+ if (!in_array($hashA, $hashesB)) {
+ return null;
+ }
+ }
+ foreach ($hashesB as $nodeB => $hashB) {
+ if (!in_array($hashB, $hashesA)) {
+ return null;
+ }
+ }
+
+ // Using the created hashes, map nodes to other_nodes
+ // Ungrounded hashes will also be equal, but we keep the distinction
+ // around for when we recurse later (we only recurse on ungrounded nodes)
+ $bijection = array();
+ foreach ($nodesA as $nodeA) {
+ $foundNode = null;
+ foreach ($ungroundedHashesB as $nodeB => $hashB) {
+ if ($ungroundedHashesA[$nodeA] == $hashB) {
+ $foundNode = $nodeB;
+ }
+ }
+
+ if ($foundNode) {
+ $bijection[$nodeA] = $foundNode;
+
+ // Deletion is required to keep counts even; two nodes with identical
+ // signatures can biject to each other at random.
+ unset($ungroundedHashesB[$foundNode]);
+ }
+ }
+
+ // bijection is now a mapping of nodes to other_nodes. If all are
+ // accounted for on both sides, we have a bijection.
+ //
+ // If not, we will speculatively mark pairs with matching ungrounded
+ // hashes as bijected and recurse.
+ $bijectionA = array_keys($bijection);
+ $bijectionB = array_values($bijection);
+ sort($bijectionA);
+ sort($nodesA);
+ sort($bijectionB);
+ sort($nodesB);
+ if ($bijectionA != $nodesA or $bijectionB != $nodesB) {
+ $bijection = null;
+
+ foreach ($nodesA as $nodeA) {
+
+ // We don't replace grounded nodes' hashes
+ if (isset($hashesA[$nodeA])) {
+ continue;
+ }
+
+ foreach ($nodesB as $nodeB) {
+ // We don't replace grounded nodesB's hashes
+ if (isset($hashesB[$nodeB])) {
+ continue;
+ }
+
+ // The ungrounded signature must match for this to potentially work
+ if ($ungroundedHashesA[$nodeA] != $ungroundedHashesB[$nodeB]) {
+ continue;
+ }
+
+ $hash = sha1($nodeA);
+ $hashesA[$nodeA] = $hash;
+ $hashesB[$nodeB] = $hash;
+ $bijection = self::buildBijectionTo(
+ $statementsA,
+ $nodesA,
+ $statementsB,
+ $nodesA,
+ $hashesA,
+ $hashesB
+ );
+ }
+ }
+ }
+
+ return $bijection;
+ }
+
+ /**
+ * Given a set of statements, create a mapping of node => SHA1 for a given
+ * set of blank nodes. grounded_hashes is a mapping of node => SHA1 pairs
+ * that we will take as a given, and use those to make more specific
+ * signatures of other nodes.
+ *
+ * Returns a tuple of associative arrats: one of grounded hashes, and one of all
+ * hashes. grounded hashes are based on non-blank nodes and grounded blank
+ * nodes, and can be used to determine if a node's signature matches
+ * another.
+ *
+ * @ignore
+ */
+ private static function hashNodes($statements, $nodes, $groundedHahes)
+ {
+ $hashes = $groundedHahes;
+ $ungroundedHashes = array();
+ $hashNeeded = true;
+
+ // We may have to go over the list multiple times. If a node is marked as
+ // grounded, other nodes can then use it to decide their own state of
+ // grounded.
+ while ($hashNeeded) {
+ $startingGroundedNodes = count($hashes);
+ foreach ($nodes as $node) {
+ if (!isset($hashes[$node])) {
+ $hash = self::nodeHashFor($node, $statements, $hashes);
+ if (self::nodeIsGrounded($node, $statements, $hashes)) {
+ $hashes[$node] = $hash;
+ }
+ }
+ $ungroundedHashes[$node] = $hash;
+ }
+
+ // after going over the list, any nodes with a unique hash can be marked
+ // as grounded, even if we have not tied them back to a root yet.
+ $uniques = array();
+ foreach ($ungroundedHashes as $node => $hash) {
+ $uniques[$hash] = isset($uniques[$hash]) ? false : $node;
+ }
+ foreach ($uniques as $hash => $node) {
+ if ($node) {
+ $hashes[$node] = $hash;
+ }
+ }
+ $hashNeeded = ($startingGroundedNodes != count($hashes));
+ }
+
+ return array($hashes, $ungroundedHashes);
+ }
+
+ /**
+ * Generate a hash for a node based on the signature of the statements it
+ * appears in. Signatures consist of grounded elements in statements
+ * associated with a node, that is, anything but an ungrounded anonymous
+ * node. Creating the hash is simply hashing a sorted list of each
+ * statement's signature, which is itself a concatenation of the string form
+ * of all grounded elements.
+ *
+ * Nodes other than the given node are considered grounded if they are a
+ * member in the given hash.
+ *
+ * Returns a tuple consisting of grounded being true or false and the string
+ * for the hash
+ *
+ * @ignore
+ */
+ private static function nodeHashFor($node, $statements, $hashes)
+ {
+ $statement_signatures = array();
+ foreach ($statements as $statement) {
+ foreach ($statement as $n) {
+ if ($n['type'] != 'literal' and $n['value'] == $node) {
+ array_push(
+ $statement_signatures,
+ self::hashStringFor($statement, $hashes, $node)
+ );
+ }
+ }
+ }
+
+ // Note that we sort the signatures--without a canonical ordering,
+ // we might get different hashes for equivalent nodes
+ sort($statement_signatures);
+
+ // Convert statements into one long string and hash it
+ return sha1(implode('', $statement_signatures));
+ }
+
+ /**
+ * Returns true if a given node is grounded
+ * A node is groundd if it is not a blank node or it is included
+ * in the given mapping of grounded nodes.
+ *
+ * @ignore
+ */
+ private static function nodeIsGrounded($node, $statements, $hashes)
+ {
+ $grounded = true;
+ foreach ($statements as $statement) {
+ if (in_array($node, $statement)) {
+ foreach ($statement as $resource) {
+ if ($node['type'] != 'bnode' or
+ isset($hashes[$node['value']]) or
+ $resource == $node
+ ) {
+ $grounded = false;
+ }
+ }
+ }
+ }
+ return $grounded;
+ }
+
+ /**
+ * Provide a string signature for the given statement, collecting
+ * string signatures for grounded node elements.
+ *
+ * @ignore
+ */
+ private static function hashStringFor($statement, $hashes, $node)
+ {
+ $str = "";
+ foreach ($statement as $r) {
+ $str .= self::stringForNode($r, $hashes, $node);
+ }
+ return $str;
+ }
+
+ /**
+ * Provides a string for the given node for use in a string signature
+ * Non-anonymous nodes will return their string form. Grounded anonymous
+ * nodes will return their hashed form.
+ *
+ * @ignore
+ */
+ private static function stringForNode($node, $hashes, $target)
+ {
+ if (is_null($node)) {
+ return "";
+ } elseif ($node['type'] == 'bnode') {
+ if ($node['value'] == $target) {
+ return "itself";
+ } elseif (isset($hashes[$node['value']])) {
+ return $hashes[$node['value']];
+ } else {
+ return "a blank node";
+ }
+ } else {
+ $s = new EasyRdf_Serialiser_Ntriples();
+ return $s->serialiseValue($node);
+ }
+ }
+}
projects / yaffs-website / blobdiff