Floydwarshall::nodeName() - Code Metrics - Inspection of "feature/nymfonya : Component Math Graph Path Floyd..." - pierre-fromager/nymfonya - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( e936c5...79aed4 )

by Pierre

created 2019-12-11 16:14 UTC

Floydwarshall::nodeName() A

↳ Parent: Floydwarshall

Complexity

Conditions	2
Paths	2

Size

Total Lines	3
Code Lines	1

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	2
CRAP Score	2

Importance

Changes

Metric	Value
cc	2
eloc	1
nc	2
nop	1
dl	0
loc	3
ccs	2
cts	2
cp	1
crap	2
rs	10
c	0
b	0
f	0

<?php

namespace App\Component\Math\Graph\Path;

/**
 * Weighted graph path finder using Floydwarshall method.
 * Constructor expects a weighted square matrix
 * and a nodes name collection to indentify nodes by name if required.
 *
 * @author Pierre Fromager <[email protected]>
 */
class Floydwarshall
{

    /**
     * max nodes
     */
    const INFINITE = 66666;

    /**
     * Distances array
     * @var array
     */
    protected $dist;

    /**
     * Precedence matrix
     * @var array
     */
    protected $pred;

    /**
     * Weights array
     * @var array
     */
    protected $weights;

    /**
     * Number of nodes
     * @var integer
     */
    protected $nodeCount;

    /**
     * Node names list
     * @var array
     */
    protected $nodenames;

    /**
     * path.
     * @var array
     */
    protected $path;

    /**
     * instanciate
     * @param array $weightedMatrix graph weighted square matrice.
     * @param array $nodenames nodes names as array.
     */
    public function __construct(array $weightedMatrix, array $nodenames = [])
    {
        $this->reset();
        $this->weights = $weightedMatrix;
        $this->nodeCount = count($this->weights);
        if (!empty($nodenames) && $this->nodeCount == count($nodenames)) {
            $this->nodenames = $nodenames;
        }
    }

    /**
     * populate from square matrix then calculate distance and precedence
     */
    public function process(): Floydwarshall
    {
        $this->reset();
        $this->populate();
        for ($k = 0; $k < $this->nodeCount; $k++) {
            for ($i = 0; $i < $this->nodeCount; $i++) {
                for ($j = 0; $j < $this->nodeCount; $j++) {
                    $nextDist = $this->dist[$i][$k] + $this->dist[$k][$j];
                    if ($this->dist[$i][$j] > $nextDist) {
                        $this->dist[$i][$j] = $nextDist;
                        $this->pred[$i][$j] = $this->pred[$k][$j];
                    }
                }
            }
        }
        return $this;
    }

    /**
     * return path
     *
     * @param string $src
     * @param string $dst
     * @param boolean $withNames
     * @return array
     */
    public function path(string $src, string $dst, bool $withNames = false): array
    {
        $srcIdx = array_search($src, $this->nodenames);
        $dstIdx = array_search($dst, $this->nodenames);
        $this->path = [];
        $this->searchPath($srcIdx, $dstIdx);
        $this->searchPath($srcIdx, /** @scrutinizer ignore-type */ $dstIdx);
        $path = ($withNames)
            ? array_map(function ($v) {
                return $this->nodenames[$v];
            }, $this->path)
            : $this->path;
        return $path;
    }

    /**
     * recursive search for node path
     *
     * @param integer $i
     * @param integer $j
     * @return Floydwarshall
     */
    protected function searchPath(int $i, int $j): Floydwarshall
    {
        if ($i != $j) {
            $pred = $this->pred[$i][$j];
            $this->searchPath($i, $pred);
        }
        $this->path[] = $j;
        return $this;
    }

    /**
     * return distance matrix
     *
     * @return array
     */
    public function getDistances(): array
    {
        return $this->dist;
    }

    /**
     * return node name from row integer
     *
     * @param integer $i
     * @return string
     */
    public function nodeName(int $i): string
    {
        return (isset($this->nodeName[$i])) ? $this->nodeName[$i] : '';

    }

    /**
     * return distance between two nodes identified by row/col couple.
     * if one member of couple is undefined infinite value is returned.
     *
     * @return float
     */
    public function getDistance(int $i, int $j): float
    {
        return (isset($this->dist[$i][$j])) ? $this->dist[$i][$j] : self::INFINITE;
    }

    /**
     * return precedence matrix
     *
     * @return array
     */
    public function getPrecedences(): array
    {
        return $this->pred;
    }

    /**
     * reset
     *
     * @return Floydwarshall
     */
    protected function reset(): Floydwarshall
    {
        $this->path = [];
        $this->dist = [[]];
        $this->pred = [[]];
        return $this;
    }

    /**
     * populate graph nodes to
     * set distances matrix from weights
     * and set matrix precedences
     *
     * @return Floydwarshall
     */
    protected function populate(): Floydwarshall
    {
        for ($i = 0; $i < $this->nodeCount; $i++) {
            for ($j = 0; $j < $this->nodeCount; $j++) {
                if ($i == $j) {
                    $this->dist[$i][$j] = 0;
                } elseif (isset($this->weights[$i][$j]) && $this->weights[$i][$j] > 0) {
                    $this->dist[$i][$j] = $this->weights[$i][$j];
                } else {
                    $this->dist[$i][$j] = self::INFINITE;
                }
                $this->pred[$i][$j] = $i;
            }
        }
        return $this;
    }
}


pierre-fromager / nymfonya

Push — master ( e936c5...79aed4 )

Floydwarshall::nodeName() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like