Implementation Of Page Rank in PHP

<?php
/*
 *
 * @Author: Zuhair Mirza
 * @Implementation Of Page Rank in PHP
 * @Date : 18-November-2014
 *
<!--
 PageRank is an algorithm used by Google Search to rank websites in their search engine results. PageRank was named after Larry Page, one of the founders of Google. PageRank is a way of measuring the importance of website pages. According to Google:PageRank works by counting the number and quality of links to a page to determine a rough estimate of how important the website   is.The underlying assumption is that more important websites are  likely to receive more links from other websites.
-->

$links = array(
    1 => array(5),
    2 => array(4, 7, 8, 9),
    3 => array(1, 3, 7),
    4 => array(1, 2, 4, 8),
    5 => array(1, 6, 7, 9),
    6 => array(1, 5),
    8 => array(3, 4, 6, 8),
    9 => array(1, 8)
);

$pageRank = calculatePageRank($links);

var_dump($pageRank);
?>

<!--If we look at this link graph, a few things stand out. Page 1 is pointed to by almost everything, so is presumably very good. Page 4 is also very popular, so should be expected to rank well. We can then calculate the PageRank by running our iterative process.

We've got a hard limit of 100 iterations, but we also keep track of the amount of change between one set of PageRanks and the next.

If that change drops below a set level (here 0.00005) the process decides it's stable enough and stops.-->

<?php

function calculatePageRank($linkGraph, $dampingFactor = 0.15) {

 
    $pageRank = array();
    $tempRank = array();
    $nodeCount = count($linkGraph);

 
    // initialise the PR as 1/n
    foreach ($linkGraph as $node => $outbound) {
        $pageRank[$node] = 1 / $nodeCount;
        $tempRank[$node] = 0;
    }


    $change = 1;
    $i = 0;
    while ($change > 0.00005 && $i < 100) {
        $change = 0;
        $i++;

        // distribute the PR of each page
        foreach ($linkGraph as $node => $outbound) {
            $outboundCount = count($outbound);
            foreach ($outbound as $link) {
                $tempRank[$link] += $pageRank[$node] / $outboundCount;
            }
        }

        $total = 0;
        // calculate the new PR using the damping factor
        foreach ($linkGraph as $node => $outbound) {
            $tempRank[$node] = ($dampingFactor / $nodeCount) + (1 - $dampingFactor) * $tempRank[$node];
            $change += abs($pageRank[$node] - $tempRank[$node]);
            $pageRank[$node] = $tempRank[$node];
            $tempRank[$node] = 0;
            $total += $pageRank[$node];
        }

        // Normalise the page ranks so it's all a proportion 0-1
        foreach ($pageRank as $node => $score) {
            $pageRank[$node] /= $total;
        }
    }

    return $pageRank;
}
?>

Find Google Page Rank in PHP

<?php

/*
 *
 * @Author: Zuhair Mirza
 * @Implementation Of Google Page Rank in PHP
 * @Date : 17-November-2014
 *
 * Google PageRank (Google PR) is one of the methods Google uses to determine a page's relevance
 * or importance. Important pages receive a higher PageRank and are more likely to appear at the top
 * of the search results. Google PageRank (PR) is a measure from 0 - 10. Google Pagerank is based
 * on backlinks.
 *
 */


$url = 'http://en.wikipedia.org/';

$pr = new GooglePageRank();
echo "$url has Google PageRank: " . $pr->get_google_pagerank($url);



class GooglePageRank {

    public function get_google_pagerank($url) {
       
        $query = "http://toolbarqueries.google.com/tbr?client=navclient-auto&ch=" . $this->CheckHash($this->HashURL($url)) . "&features=Rank&q=info:" . $url . "&num=100&filter=0";
       
        $data = file_get_contents($query);
               
        $pos = strpos($data, "Rank_");
        if ($pos === false) {
           
        } else {
            $pagerank = substr($data, $pos + 9);
            return $pagerank;
        }
    }

    public function StrToNum($Str, $Check, $Magic) {
        $Int32Unit = 4294967296; // 2^32
        $length = strlen($Str);
        for ($i = 0; $i < $length; $i++) {
            $Check *= $Magic;
            if ($Check >= $Int32Unit) {
                $Check = ($Check - $Int32Unit * (int) ($Check / $Int32Unit));
                $Check = ($Check < -2147483648) ? ($Check + $Int32Unit) : $Check;
            }
            $Check += ord($Str{$i});
        }
        return $Check;
    }

    public function HashURL($String) {
        $Check1 = $this->StrToNum($String, 0x1505, 0x21);
        $Check2 = $this->StrToNum($String, 0, 0x1003F);
        $Check1 >>= 2;
        $Check1 = (($Check1 >> 4) & 0x3FFFFC0 ) | ($Check1 & 0x3F);
        $Check1 = (($Check1 >> 4) & 0x3FFC00 ) | ($Check1 & 0x3FF);
        $Check1 = (($Check1 >> 4) & 0x3C000 ) | ($Check1 & 0x3FFF);
        $T1 = (((($Check1 & 0x3C0) << 4) | ($Check1 & 0x3C)) << 2 ) | ($Check2 & 0xF0F );
        $T2 = (((($Check1 & 0xFFFFC000) << 4) | ($Check1 & 0x3C00)) << 0xA) | ($Check2 & 0xF0F0000 );
        return ($T1 | $T2);
    }

    public function CheckHash($Hashnum) {
        $CheckByte = 0;
        $Flag = 0;
        $HashStr = sprintf('%u', $Hashnum);
        $length = strlen($HashStr);
        for ($i = $length - 1; $i >= 0; $i --) {
            $Re = $HashStr{$i};
            if (1 === ($Flag % 2)) {
                $Re += $Re;
                $Re = (int) ($Re / 10) + ($Re % 10);
            }
            $CheckByte += $Re;
            $Flag ++;
        }
        $CheckByte %= 10;
        if (0 !== $CheckByte) {
            $CheckByte = 10 - $CheckByte;
            if (1 === ($Flag % 2)) {
                if (1 === ($CheckByte % 2)) {
                    $CheckByte += 9;
                }
                $CheckByte >>= 1;
            }
        }
        return '7' . $CheckByte . $HashStr;
    }

}

?>

Implementation Of Bellman Ford Algorithm in PHP

<?php

/*
 *
 * @Author: Zuhair Mirza
 * @Implementation Of Bellman Ford Algorithm in PHP
 * @Date : 01-June-2014
 *
 * The Bellman–Ford algorithm is an algorithm that computes shortest
 * paths from a single source vertex to all of the other vertices in a weighted digraph
 *
 */

define('INFINITY', 10000000);

$matrix = array(
    0 => array(0, 3, 4),
    1 => array(0, 0, 2),
    2 => array(0, -2, 0),
);

$len = count($matrix);

$dist = array();

BellmanFord($matrix, $dist, 0);

// [0, 2, 4]
var_dump($dist);

function BellmanFord(&$matrix, &$dist, $start) {
    global $len;

    foreach (array_keys($matrix) as $vertex) {
        $dist[$vertex] = INFINITY;
        if ($vertex == $start) {
            $dist[$vertex] = 0;
        }
    }

    for ($k = 0; $k < $len - 1; $k++) {
        for ($i = 0; $i < $len; $i++) {
            for ($j = 0; $j < $len; $j++) {

                echo $i . "--" . $dist[$i] . "<br/>";
                echo $j . "--" . $dist[$j] . "<br/>";
                echo $matrix[$j][$i] . "<br/>";
                echo "-------------<br/>";

                if ($dist[$i] > $dist[$j] + $matrix[$j][$i]) {
                    $dist[$i] = $dist[$j] + $matrix[$j][$i];
                    echo "------Done-------<br/>";
                }
            }
        }

        for ($i = 0; $i < $len; $i++) {
            for ($j = 0; $j < $len; $j++) {
                if ($dist[$i] > $dist[$j] + $matrix[$j][$i]) {
                    echo 'The graph contains a negative cycle!';
                }
            }
        }
    }
}

?>

Implementation Of Levenshtein Distance Algorithm in PHP

<?php

/*
 *
 * @Author: Zuhair Mirza
 * @Implementation Of Levenshtein Distance Algorithm (Edit Distance) in PHP
 * @Date : 04-May-2013
 *
 */

$s1 = "POLYNOMIAL";
$s2 = "EXPONENTIAL";

LevenshteinDistance($s1, $s2);


function LevenshteinDistance($s, $t) {
    $m = strlen($s);
    $n = strlen($t);

    for ($i = 0; $i <= $m; $i++)
        $d[$i][0] = $i;
    for ($j = 0; $j <= $n; $j++)
        $d[0][$j] = $j;

    for ($i = 1; $i <= $m; $i++) {
        for ($j = 1; $j <= $n; $j++) {

            $c = ($s[$i - 1] == $t[$j - 1]) ? 0 : 1;
            $d[$i][$j] = min($d[$i - 1][$j] + 1, $d[$i][$j - 1] + 1, $d[$i - 1][$j - 1] + $c);
        }
    }

    printMatrix($d, $s, $t);

    return $d[$m][$n];
}

function flip_row_col_array($array) {
    $out = array();
    foreach ($array as $rowkey => $row) {
        foreach ($row as $colkey => $col) {
            $out[$colkey][$rowkey] = $col;
        }
    }
    return $out;
}

function printMatrix($d, $str1, $str2) {

    $array = flip_row_col_array($d);
    echo "<table border = '1'>";
    echo "<tr>";
    echo "<td>";
    echo "</td>";
    echo "<td colspan=11>";
    echo $str1;
    echo "</td>";
    echo "</tr>";

    $str2 = str_split($str2);

    $count = 0;

    foreach ($array as $j => $value) {

        echo "<tr>";

        foreach ($value as $i => $node) {

            if ($i == 0):

                if ($count == 0):
                    echo "<td>";
                    echo "</td>";
                else:
                    echo "<td>";
                    echo $str2[$j - 1];
                    echo "</td>";

                endif;
                $count++;
            endif;

            echo "<td>";
            echo $node;
            echo "</td>";
        }
        echo "</tr>";
    }
    echo "</table>";
}

?>

Implementation Of Breadth First Search in PHP

<?php

/*
 *
 * @Author: Zuhair Mirza
 * @Implementation Of Breadth First Search in PHP
 * @Date : 04-May-2013
 *
 */


$g = array(
    0 => array(0, 1, 1, 0, 0, 0),
    1 => array(1, 0, 0, 1, 0, 0),
    2 => array(1, 0, 0, 1, 0, 0),
    3 => array(0, 1, 1, 0, 1, 0),
    4 => array(0, 0, 0, 1, 0, 1),
    5 => array(0, 0, 0, 0, 1, 0),
);

function init(&$visited, &$graph) {
    foreach ($graph as $key => $vertex) {
        $visited[$key] = 0;
    }
}

function breadth_first(&$graph, $start, $visited) {
    // create an empty queue
    $q = array();

    // initially enqueue only the starting vertex
    array_push($q, $start);
    $visited[$start] = 1;
    echo $start . "\n";


    while (count($q)) {
        $t = array_shift($q);
       
        foreach ($graph[$t] as $key => $vertex) {
            if (!$visited[$key] && $vertex == 1) {
                $visited[$key] = 1;
                array_push($q, $key);              
                echo $key . "\t";
            }
        }
        echo "\n";
    }
}

$visited = array();
init($visited, $g);

breadth_first($g, 2, $visited);
?>

Implementation Of Depth First Search in PHP

<?php

/*
 *
 * @Author: Zuhair Mirza
 * @Implementation Of Depth First Search in PHP
 * @Date : 04-May-2013
 *
 */


class Graph {

    protected $_len = 0;
    protected $_g = array();
    protected $_visited = array();

    public function __construct() {
        $this->_g = array(
            array(0, 1, 1, 0, 0, 0),
            array(1, 0, 0, 1, 0, 0),
            array(1, 0, 0, 1, 1, 1),
            array(0, 1, 1, 0, 1, 0),
            array(0, 0, 1, 1, 0, 1),
            array(0, 0, 1, 0, 1, 0),
        );

        $this->_len = count($this->_g);

        $this->_initVisited();
    }

    protected function _initVisited() {
        for ($i = 0; $i < $this->_len; $i++) {
            $this->_visited[$i] = 0;
        }
    }

    public function depthFirst($vertex) {
        $this->_visited[$vertex] = 1;

        echo $vertex . "\n";

        for ($i = 0; $i < $this->_len; $i++) {

            //d(0,$vertex,$this->_g[$vertex][$i],$i);
            if ($this->_g[$vertex][$i] == 1 && !$this->_visited[$i]) {
                $this->depthFirst($i);
            }
        }
    }

}

$g = new Graph();
// 2 0 1 3 4 5
//$g->depthFirst(2);
//$g->depthFirst(0);
$g->depthFirst(2);
?>

Monkey Minimum Number of Jumps Algorithm

<?php

/*
 *
 * Subject : Design & Analysis of Algorithms
 *
 * Question :
 *
  Billo is a monkey trained by our beloved Raju. Billo can perform jumping very eccentrically.
  Given an array of positive integers in which each element represents number of possible hop
  choices that he can jump. Starting with array index=0, design an algorithm that finds the
  minimum number of jumps to reach the end of the array.
  Example:
  Input: A[] = {1, 3, 5, 8, 4, 2, 6, 7, 6, 8, 9}
  Output: 3
  Initially Billo is sitting at index 0. As A[0]=1, he can jump at most 1 hop, i.e., to index 1. At
  index 1, A[1]=3, so he can jump at most 3 hops (to index 2, 3 or 4). Optimally, he can reach
  last position of A in 3 jumps (0 -> 1 -> 3-> 10).
 *
 * @Author: Zuhair Mirza
 * @Date : 4-May-2014
 *
 */

$array = array(1, 3, 5, 8, 4, 2, 6, 7, 6, 8, 9);
//$array = array(1, 4, 3, 8, 5, 6, 2, 9, 7, 8);
//$array = array(1, 4, 3, 2, 5, 6, 2, 9, 7, 8, 9, 8);

$nodeIndex = 0;
$nodeValue = $array[$nodeIndex] + $nodeIndex;

echo $nodeIndex . "->";
$maxKey = runAlgo($array, $nodeIndex, $nodeValue);

function runAlgo($array, $start, $node) {

    for ($j = $start; $j <= $node; $j++) {
        if (isset($array[$j])):
            $newArray[$j] = $array[$j];
        endif;
    }

    if (end($newArray) >= end($array)):

        $maxsIndex = count($array) - 1;
        echo $maxsIndex;
        exit();

    else:

        $maxsIndex = array_keys($newArray, max($newArray));
        echo $maxsIndex[0] . "->";
        $nodeIndex = $maxsIndex[0];
        $nodeValue = $array[$nodeIndex] + $maxsIndex[0];
        $maxKey3 = runAlgo($array, $nodeIndex, $nodeValue);

    endif;

?>

How to detect face in PHP

Download full code of FACE DETECTION ( including .json and .dat ) file link : https://github.com/mauricesvay/php-facedetection

Here is index.php file code :

<?php

include "FaceDetector.php";

$detector = new svay\FaceDetector();
$detector->faceDetect('lena512color.jpg');
$detector->toJpeg();

?>

Here is FaceDetector.php Library File Code


<?php
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
//
// @Author Karthik Tharavaad
//         karthik_tharavaad@yahoo.com
// @Contributor Maurice Svay
//              maurice@svay.Com

namespace svay;

class FaceDetector
{

    protected $detection_data;
    protected $canvas;
    protected $face;
    private $reduced_canvas;

    public function __construct($detection_file = 'detection.dat')
    {
        if (is_file($detection_file)) {
            $this->detection_data = unserialize(file_get_contents($detection_file));
        } else {
            throw new Exception("Couldn't load detection data");
        }
    }

    public function faceDetect($file)
    {
        if (is_resource($file)) {

            $this->canvas = $file;

        } elseif (is_file($file)) {

            $this->canvas = imagecreatefromjpeg($file);

        } else {

            throw new Exception("Can not load $file");
        }

        $im_width = imagesx($this->canvas);
        $im_height = imagesy($this->canvas);

        //Resample before detection?
        $ratio = 0;
        $diff_width = 320 - $im_width;
        $diff_height = 240 - $im_height;
        if ($diff_width > $diff_height) {
            $ratio = $im_width / 320;
        } else {
            $ratio = $im_height / 240;
        }

        if ($ratio != 0) {
            $this->reduced_canvas = imagecreatetruecolor($im_width / $ratio, $im_height / $ratio);

            imagecopyresampled(
                $this->reduced_canvas,
                $this->canvas,
                0,
                0,
                0,
                0,
                $im_width / $ratio,
                $im_height / $ratio,
                $im_width,
                $im_height
            );

            $stats = $this->getImgStats($this->reduced_canvas);

            $this->face = $this->doDetectGreedyBigToSmall(
                $stats['ii'],
                $stats['ii2'],
                $stats['width'],
                $stats['height']
            );

            if ($this->face['w'] > 0) {
                $this->face['x'] *= $ratio;
                $this->face['y'] *= $ratio;
                $this->face['w'] *= $ratio;
            }
        } else {
            $stats = $this->getImgStats($this->canvas);

            $this->face = $this->doDetectGreedyBigToSmall(
                $stats['ii'],
                $stats['ii2'],
                $stats['width'],
                $stats['height']
            );
        }
        return ($this->face['w'] > 0);
    }


    public function toJpeg()
    {
        $color = imagecolorallocate($this->canvas, 255, 0, 0); //red

        imagerectangle(
            $this->canvas,
            $this->face['x'],
            $this->face['y'],
            $this->face['x']+$this->face['w'],
            $this->face['y']+ $this->face['w'],
            $color
        );

        header('Content-type: image/jpeg');
        imagejpeg($this->canvas);
    }

    public function toJson()
    {
        return json_encode($this->face);
    }

    public function getFace()
    {
        return $this->face;
    }

    protected function getImgStats($canvas)
    {
        $image_width = imagesx($canvas);
        $image_height = imagesy($canvas);
        $iis =  $this->computeII($canvas, $image_width, $image_height);
        return array(
            'width' => $image_width,
            'height' => $image_height,
            'ii' => $iis['ii'],
            'ii2' => $iis['ii2']
        );
    }

    protected function computeII($canvas, $image_width, $image_height)
    {
        $ii_w = $image_width+1;
        $ii_h = $image_height+1;
        $ii = array();
        $ii2 = array();

        for ($i=0; $i<$ii_w; $i++) {
            $ii[$i] = 0;
            $ii2[$i] = 0;
        }

        for ($i=1; $i<$ii_h-1; $i++) {
            $ii[$i*$ii_w] = 0;
            $ii2[$i*$ii_w] = 0;
            $rowsum = 0;
            $rowsum2 = 0;
            for ($j=1; $j<$ii_w-1; $j++) {
                $rgb = ImageColorAt($canvas, $j, $i);
                $red = ($rgb >> 16) & 0xFF;
                $green = ($rgb >> 8) & 0xFF;
                $blue = $rgb & 0xFF;
                $grey = (0.2989*$red + 0.587*$green + 0.114*$blue)>>0;  // this is what matlab uses
                $rowsum += $grey;
                $rowsum2 += $grey*$grey;

                $ii_above = ($i-1)*$ii_w + $j;
                $ii_this = $i*$ii_w + $j;

                $ii[$ii_this] = $ii[$ii_above] + $rowsum;
                $ii2[$ii_this] = $ii2[$ii_above] + $rowsum2;
            }
        }
        return array('ii'=>$ii, 'ii2' => $ii2);
    }

    protected function doDetectGreedyBigToSmall($ii, $ii2, $width, $height)
    {
        $s_w = $width/20.0;
        $s_h = $height/20.0;
        $start_scale = $s_h < $s_w ? $s_h : $s_w;
        $scale_update = 1 / 1.2;
        for ($scale = $start_scale; $scale > 1; $scale *= $scale_update) {
            $w = (20*$scale) >> 0;
            $endx = $width - $w - 1;
            $endy = $height - $w - 1;
            $step = max($scale, 2) >> 0;
            $inv_area = 1 / ($w*$w);
            for ($y = 0; $y < $endy; $y += $step) {
                for ($x = 0; $x < $endx; $x += $step) {
                    $passed = $this->detectOnSubImage($x, $y, $scale, $ii, $ii2, $w, $width+1, $inv_area);
                    if ($passed) {
                        return array('x'=>$x, 'y'=>$y, 'w'=>$w);
                    }
                } // end x
            } // end y
        }  // end scale
        return null;
    }

    protected function detectOnSubImage($x, $y, $scale, $ii, $ii2, $w, $iiw, $inv_area)
    {
        $mean  = ($ii[($y+$w)*$iiw + $x + $w] + $ii[$y*$iiw+$x] - $ii[($y+$w)*$iiw+$x] - $ii[$y*$iiw+$x+$w])*$inv_area;

        $vnorm = ($ii2[($y+$w)*$iiw + $x + $w]
                  + $ii2[$y*$iiw+$x]
                  - $ii2[($y+$w)*$iiw+$x]
                  - $ii2[$y*$iiw+$x+$w])*$inv_area - ($mean*$mean);

        $vnorm = $vnorm > 1 ? sqrt($vnorm) : 1;

        $passed = true;
        for ($i_stage = 0; $i_stage < count($this->detection_data); $i_stage++) {
            $stage = $this->detection_data[$i_stage];
            $trees = $stage[0];

            $stage_thresh = $stage[1];
            $stage_sum = 0;

            for ($i_tree = 0; $i_tree < count($trees); $i_tree++) {
                $tree = $trees[$i_tree];
                $current_node = $tree[0];
                $tree_sum = 0;
                while ($current_node != null) {
                    $vals = $current_node[0];
                    $node_thresh = $vals[0];
                    $leftval = $vals[1];
                    $rightval = $vals[2];
                    $leftidx = $vals[3];
                    $rightidx = $vals[4];
                    $rects = $current_node[1];

                    $rect_sum = 0;
                    for ($i_rect = 0; $i_rect < count($rects); $i_rect++) {
                        $s = $scale;
                        $rect = $rects[$i_rect];
                        $rx = ($rect[0]*$s+$x)>>0;
                        $ry = ($rect[1]*$s+$y)>>0;
                        $rw = ($rect[2]*$s)>>0;
                        $rh = ($rect[3]*$s)>>0;
                        $wt = $rect[4];

                        $r_sum = ($ii[($ry+$rh)*$iiw + $rx + $rw]
                                  + $ii[$ry*$iiw+$rx]
                                  - $ii[($ry+$rh)*$iiw+$rx]
                                  - $ii[$ry*$iiw+$rx+$rw])*$wt;

                        $rect_sum += $r_sum;
                    }

                    $rect_sum *= $inv_area;

                    $current_node = null;

                    if ($rect_sum >= $node_thresh*$vnorm) {

                        if ($rightidx == -1) {

                            $tree_sum = $rightval;

                        } else {

                            $current_node = $tree[$rightidx];

                        }

                    } else {

                        if ($leftidx == -1) {

                            $tree_sum = $leftval;

                        } else {

                            $current_node = $tree[$leftidx];
                        }
                    }
                }

                $stage_sum += $tree_sum;
            }
            if ($stage_sum < $stage_thresh) {
                return false;
            }
        }
        return true;
    }
}