| Server IP : 134.29.175.74 / Your IP : 216.73.216.160 Web Server : nginx/1.10.2 System : Windows NT CST-WEBSERVER 10.0 build 19045 (Windows 10) i586 User : Administrator ( 0) PHP Version : 7.1.0 Disable Function : NONE MySQL : OFF | cURL : ON | WGET : OFF | Perl : OFF | Python : OFF | Sudo : OFF | Pkexec : OFF Directory : C:/nginx/html/Student/JimMartinson/Lab12/drupal/vendor/easyrdf/easyrdf/lib/EasyRdf/ |
Upload File : |
<?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);
}
}
}