Dijkstra::getMinimalRelation() - Code Metrics - Inspection of "Small optimization works." - PHPAlgorithms/Dijkstra-s-algorithm - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( f52c87...2cae32 )

by Ventaquil

created 2016-04-09 18:39 UTC

Dijkstra::getMinimalRelation() B

↳ Parent: Dijkstra

Complexity

Conditions	5
Paths	6

Size

Total Lines	19
Code Lines	12

Duplication

Lines	0
Ratio	0 %

Importance

Changes	2
Bugs	0	Features	0

Metric	Value
c	2
b	0
f	0
dl	0
loc	19
rs	8.8571
cc	5
eloc	12
nc	6
nop	3

<?php

/**
 * @author ventaquil <[email protected]>
 * @licence MIT
 */

namespace PHPAlgorithms;

use Closure;
use PHPAlgorithms\Dijkstra\Creator;
use PHPAlgorithms\Dijkstra\Exceptions\Exception;
use PHPAlgorithms\Dijkstra\Path;
use PHPAlgorithms\Dijkstra\Point;

class Dijkstra {
    /**
     * @var array
     */
    private $points = array();

    /**
     * Dijkstra constructor.
     *
     * @param Closure|null $function Anonymous function to create relations.
     */
    public function __construct($function = null)
    {
        if (!is_null($function)) {
            $this->add($function);
        }
    }

    /**
     * Method executes sent function and add result to $points parameter.
     *
     * @param Closure $function Anonymous function to create relations.
     * @return Dijkstra $this Reference to the same object.
     * @throws Exception Method throws exception when $function argument isn't a Closure object.
     */
    public function add($function)
    {
        if (!($function instanceof Closure)) {
            throw new Exception('Sent argument is not instance of Closure');
        }

        $creator = new Creator();
        $function($creator);

        if (empty($this->points)) {
            $this->points = $creator->dumpPoints();
        } else {
            $index = count($this->points);

            foreach ($creator->dumpPoints() as $point) {
                $this->points[$index] = $point;
                $point->id = $index;

                $index++;
            }
        }

        return $this;
    }

    /**
     * Method search unvisited points in neighborhood of sent point.
     *
     * @param integer[] $visited Array of visited points' ids.
     * @param integer $point Point id.
     * @return boolean True when exists unvisited point in neighborhood or false otherwise.
     */
    private function existsUnvisitedInNeighborhood($visited, $point)
    {
        foreach ($this->points[$point]->relations as $relation) {
            if (!isset($visited[$relation->to->id])) {
                return true;
            }
        }

        return false;
    }

    private function findPointWithUncheckedRelation($unvisited, $visited, $startPoint = null)
    {
        if (empty($unvisited)) {
            return null;
        }

        if (is_null($startPoint)) {
            foreach ($this->points as $point) {
                if ($this->existsUnvisitedInNeighborhood($visited, $point->id)) {
                    return $point->id;
                }
            }
        } elseif ($this->existsUnvisitedInNeighborhood($visited, $startPoint)) {
            return $startPoint;
        }

        return null;
    }

    /**
     * Method generates path for given Point object or point id.
     *
     * @param Point|integer $point Point object or point identification number.
     * @return Path[] Array of Path objects.
     * @throws Exception Throws exception when sent point not isset in object's $point array.
     */
    public function generate($point)
    {
        if ($point instanceof Point) {
            $point = $point->id;
        }

        if (!isset($this->points[$point])) {
            throw new Exception("Point with id {$point} not exists");
        }

        $startPoint = $point;

        $visited = array();
        $unvisited = array_keys($this->points);
        $paths = array();
        $previous = null;
        $relation = null;
$myVar = 'Value';
$higher = false;

if (rand(1, 6) > 3) {
    $higher = true;
} else {
    $higher = false;
}

        while (!empty($unvisited) && !is_null($point)) {
            unset($unvisited[$point]);
            $visited[$point] = $point;

            if (!isset($paths[$point])) {
                if (is_null($previous)) {
                    $paths[$point] = new Path();
                } else {
                    $paths[$point]->copy($paths[$previous]);
                }

                $paths[$point]->addNode($point);
            }

            $relation = $this->getMinimalRelation($unvisited, $paths, $point);

            $this->updatePaths($paths, $point);

            $previous = $point;

            if (!is_null($relation)) {
                $point = $relation->to
<?php

/**
 * @property int $x
 * @property int $y
 * @property string $text
 */
class MyLabel
{
    private $properties;

    private $allowedProperties = array('x', 'y', 'text');

    public function __get($name)
    {
        if (isset($properties[$name]) && in_array($name, $this->allowedProperties)) {
            return $properties[$name];
        } else {
            return null;
        }
    }

    public function __set($name, $value)
    {
        if (in_array($name, $this->allowedProperties)) {
            $properties[$name] = $value;
        } else {
            throw new \LogicException("Property $name is not defined.");
        }
    }

}
                                  ->id;
            } else {
                $point = $this->findPointWithUncheckedRelation($unvisited, $visited, $startPoint);
            }
        };

        return $paths;
    }

    /**
     * Method generates paths for all defined points.
     *
     * @return Path[][] Two-dimensional array of Path objects.
     * @throws Exception Method throws exception when generate() method throws exception.
     */
    public function generateAll()
    {
        $generated = array();

        foreach ($this->points as $index => $point) {
            $generated[$index] = $this->generate($point);
        }

        return $generated;
    }

    /**
     * Method try to find minimal relation to another point from given point.
     * 
     * @param integer[] $unvisited Array of unvisited points' ids.
     * @param Path[] $paths Array of generated Path objects.
     * @param integer $point Point integer identifier.
     * @return Dijkstra\Relation|null Method returns Relation object or null when minimal relation wasn't found.
     */
    private function getMinimalRelation($unvisited, $paths, $point)
    {
        $minimalValue = INF;
        $minimalIndex = -1;

        foreach ($this->points[$point]->relations as $index => $relation) {
            if (($minimalValue > ($relation->distance + $paths[$point]->distance)) && isset($unvisited[$relation->to->id])) {
<?php

/**
 * @property int $x
 * @property int $y
 * @property string $text
 */
class MyLabel
{
    private $properties;

    private $allowedProperties = array('x', 'y', 'text');

    public function __get($name)
    {
        if (isset($properties[$name]) && in_array($name, $this->allowedProperties)) {
            return $properties[$name];
        } else {
            return null;
        }
    }

    public function __set($name, $value)
    {
        if (in_array($name, $this->allowedProperties)) {
            $properties[$name] = $value;
        } else {
            throw new \LogicException("Property $name is not defined.");
        }
    }

}
                $minimalIndex = $index;
                $minimalValue = $relation->distance + $paths[$point]->distance;
<?php

/**
 * @property int $x
 * @property int $y
 * @property string $text
 */
class MyLabel
{
    private $properties;

    private $allowedProperties = array('x', 'y', 'text');

    public function __get($name)
    {
        if (isset($properties[$name]) && in_array($name, $this->allowedProperties)) {
            return $properties[$name];
        } else {
            return null;
        }
    }

    public function __set($name, $value)
    {
        if (in_array($name, $this->allowedProperties)) {
            $properties[$name] = $value;
        } else {
            throw new \LogicException("Property $name is not defined.");
        }
    }

}
            }
        }

        if ($minimalIndex != -1) {
            return $this->points[$point]
                        ->relations[$minimalIndex];
        } else {
            return null;
        }
    }

    /**
     * Method updates existing Path object or create new if it's possible.
     * 
     * @param Path[] &$paths Array of generated Path[] objects. Given by reference.
     * @param integer $point Integer point identifier.
     */
    public function updatePaths(&$paths, $point)
    {
        foreach ($this->points[$point]->relations as $relation) {
            if (isset($paths[$relation->to->id])) {
                if ($paths[$relation->to->id]->distance > ($paths[$point]->distance + $relation->distance)) {
                    $paths[$relation->to->id]->copy($paths[$point])
                                             ->addNode($relation->to->id, $relation->distance);
                }
            } else {
                $paths[$relation->to->id] = (new Path())->copy($paths[$point])
                                                        ->addNode($relation->to->id, $relation->distance);
            }
        }
    }
}


1			<?php
2
3			/**
4			* @author ventaquil <[email protected]>
5			* @licence MIT
6			*/
7
8			namespace PHPAlgorithms;
9
10			use Closure;
11			use PHPAlgorithms\Dijkstra\Creator;
12			use PHPAlgorithms\Dijkstra\Exceptions\Exception;
13			use PHPAlgorithms\Dijkstra\Path;
14			use PHPAlgorithms\Dijkstra\Point;
15
16			class Dijkstra {
17			/**
18			* @var array
19			*/
20			private $points = array();
21
22			/**
23			* Dijkstra constructor.
24			*
25			* @param Closure\|null $function Anonymous function to create relations.
26			*/
27			public function __construct($function = null)
28			{
29			if (!is_null($function)) {
30			$this->add($function);
31			}
32			}
33
34			/**
35			* Method executes sent function and add result to $points parameter.
36			*
37			* @param Closure $function Anonymous function to create relations.
38			* @return Dijkstra $this Reference to the same object.
39			* @throws Exception Method throws exception when $function argument isn't a Closure object.
40			*/
41			public function add($function)
42			{
43			if (!($function instanceof Closure)) {
44			throw new Exception('Sent argument is not instance of Closure');
45			}
46
47			$creator = new Creator();
48			$function($creator);
49
50			if (empty($this->points)) {
51			$this->points = $creator->dumpPoints();
52			} else {
53			$index = count($this->points);
54
55			foreach ($creator->dumpPoints() as $point) {
56			$this->points[$index] = $point;
57			$point->id = $index;
58
59			$index++;
60			}
61			}
62
63			return $this;
64			}
65
66			/**
67			* Method search unvisited points in neighborhood of sent point.
68			*
69			* @param integer[] $visited Array of visited points' ids.
70			* @param integer $point Point id.
71			* @return boolean True when exists unvisited point in neighborhood or false otherwise.
72			*/
73			private function existsUnvisitedInNeighborhood($visited, $point)
74			{
75			foreach ($this->points[$point]->relations as $relation) {
76			if (!isset($visited[$relation->to->id])) {
77			return true;
78			}
79			}
80
81			return false;
82			}
83
84			private function findPointWithUncheckedRelation($unvisited, $visited, $startPoint = null)
85			{
86			if (empty($unvisited)) {
87			return null;
88			}
89
90			if (is_null($startPoint)) {
91			foreach ($this->points as $point) {
92			if ($this->existsUnvisitedInNeighborhood($visited, $point->id)) {
93			return $point->id;
94			}
95			}
96			} elseif ($this->existsUnvisitedInNeighborhood($visited, $startPoint)) {
97			return $startPoint;
98			}
99
100			return null;
101			}
102
103			/**
104			* Method generates path for given Point object or point id.
105			*
106			* @param Point\|integer $point Point object or point identification number.
107			* @return Path[] Array of Path objects.
108			* @throws Exception Throws exception when sent point not isset in object's $point array.
109			*/
110			public function generate($point)
111			{
112			if ($point instanceof Point) {
113			$point = $point->id;
114			}
115
116			if (!isset($this->points[$point])) {
117			throw new Exception("Point with id {$point} not exists");
118			}
119
120			$startPoint = $point;
121
122			$visited = array();
123			$unvisited = array_keys($this->points);
124			$paths = array();
125			$previous = null;
126			$relation = null;
			0 ignored issues – show Unused Code introduced 2016-04-09 18:41 UTC by Report Bug Copy Issue Report `$relation` is not used, you could remove the assignment. This check looks for variable assignements that are either overwritten by other assignments or where the variable is not used subsequently. $myVar = 'Value'; $higher = false; if (rand(1, 6) > 3) { $higher = true; } else { $higher = false; } Both the `$myVar` assignment in line 1 and the `$higher` assignment in line 2 are dead. The first because `$myVar` is never used and the second because `$higher` is always overwritten for every possible time line. Loading history...
127
128			while (!empty($unvisited) && !is_null($point)) {
129			unset($unvisited[$point]);
130			$visited[$point] = $point;
131
132			if (!isset($paths[$point])) {
133			if (is_null($previous)) {
134			$paths[$point] = new Path();
135			} else {
136			$paths[$point]->copy($paths[$previous]);
137			}
138
139			$paths[$point]->addNode($point);
140			}
141
142			$relation = $this->getMinimalRelation($unvisited, $paths, $point);
143
144			$this->updatePaths($paths, $point);
145
146			$previous = $point;
147
148			if (!is_null($relation)) {
149			$point = $relation->to
			0 ignored issues – show Documentation introduced 2016-04-09 18:41 UTC by Report Bug Copy Issue Report The property `$to` is declared protected in `PHPAlgorithms\GraphTools\AbstractLine`. Since you implemented `__get()`, maybe consider adding a @property or @property-read annotation. This makes it easier for IDEs to provide auto-completion. Since your code implements the magic setter `_set`, this function will be called for any write access on an undefined variable. You can add the `@property` annotation to your class or interface to document the existence of this variable. <?php /** * @property int $x * @property int $y * @property string $text */ class MyLabel { private $properties; private $allowedProperties = array('x', 'y', 'text'); public function __get($name) { if (isset($properties[$name]) && in_array($name, $this->allowedProperties)) { return $properties[$name]; } else { return null; } } public function __set($name, $value) { if (in_array($name, $this->allowedProperties)) { $properties[$name] = $value; } else { throw new \LogicException("Property $name is not defined."); } } } Since the property has write access only, you can use the @property-write annotation instead. Of course, you may also just have mistyped another name, in which case you should fix the error. See also the PhpDoc documentation for @property. Loading history...
150			->id;
151			} else {
152			$point = $this->findPointWithUncheckedRelation($unvisited, $visited, $startPoint);
153			}
154			};
155
156			return $paths;
157			}
158
159			/**
160			* Method generates paths for all defined points.
161			*
162			* @return Path[][] Two-dimensional array of Path objects.
163			* @throws Exception Method throws exception when generate() method throws exception.
164			*/
165			public function generateAll()
166			{
167			$generated = array();
168
169			foreach ($this->points as $index => $point) {
170			$generated[$index] = $this->generate($point);
171			}
172
173			return $generated;
174			}
175
176			/**
177			* Method try to find minimal relation to another point from given point.
178			*
179			* @param integer[] $unvisited Array of unvisited points' ids.
180			* @param Path[] $paths Array of generated Path objects.
181			* @param integer $point Point integer identifier.
182			* @return Dijkstra\Relation\|null Method returns Relation object or null when minimal relation wasn't found.
183			*/
184			private function getMinimalRelation($unvisited, $paths, $point)
185			{
186			$minimalValue = INF;
187			$minimalIndex = -1;
188
189			foreach ($this->points[$point]->relations as $index => $relation) {
190			if (($minimalValue > ($relation->distance + $paths[$point]->distance)) && isset($unvisited[$relation->to->id])) {
			0 ignored issues – show Documentation introduced 2016-04-09 18:41 UTC by Report Bug Copy Issue Report The property `$distance` is declared private in `PHPAlgorithms\Dijkstra\Path`. Since you implemented `__get()`, maybe consider adding a @property or @property-read annotation. This makes it easier for IDEs to provide auto-completion. Since your code implements the magic setter `_set`, this function will be called for any write access on an undefined variable. You can add the `@property` annotation to your class or interface to document the existence of this variable. <?php /** * @property int $x * @property int $y * @property string $text */ class MyLabel { private $properties; private $allowedProperties = array('x', 'y', 'text'); public function __get($name) { if (isset($properties[$name]) && in_array($name, $this->allowedProperties)) { return $properties[$name]; } else { return null; } } public function __set($name, $value) { if (in_array($name, $this->allowedProperties)) { $properties[$name] = $value; } else { throw new \LogicException("Property $name is not defined."); } } } Since the property has write access only, you can use the @property-write annotation instead. Of course, you may also just have mistyped another name, in which case you should fix the error. See also the PhpDoc documentation for @property. Loading history...
191			$minimalIndex = $index;
192			$minimalValue = $relation->distance + $paths[$point]->distance;
			0 ignored issues – show Documentation introduced 2016-04-09 18:41 UTC by Report Bug Copy Issue Report The property `$distance` is declared private in `PHPAlgorithms\Dijkstra\Path`. Since you implemented `__get()`, maybe consider adding a @property or @property-read annotation. This makes it easier for IDEs to provide auto-completion. Since your code implements the magic setter `_set`, this function will be called for any write access on an undefined variable. You can add the `@property` annotation to your class or interface to document the existence of this variable. <?php /** * @property int $x * @property int $y * @property string $text */ class MyLabel { private $properties; private $allowedProperties = array('x', 'y', 'text'); public function __get($name) { if (isset($properties[$name]) && in_array($name, $this->allowedProperties)) { return $properties[$name]; } else { return null; } } public function __set($name, $value) { if (in_array($name, $this->allowedProperties)) { $properties[$name] = $value; } else { throw new \LogicException("Property $name is not defined."); } } } Since the property has write access only, you can use the @property-write annotation instead. Of course, you may also just have mistyped another name, in which case you should fix the error. See also the PhpDoc documentation for @property. Loading history...
193			}
194			}
195
196			if ($minimalIndex != -1) {
197			return $this->points[$point]
198			->relations[$minimalIndex];
199			} else {
200			return null;
201			}
202			}
203
204			/**
205			* Method updates existing Path object or create new if it's possible.
206			*
207			* @param Path[] &$paths Array of generated Path[] objects. Given by reference.
208			* @param integer $point Integer point identifier.
209			*/
210			public function updatePaths(&$paths, $point)
211			{
212			foreach ($this->points[$point]->relations as $relation) {
213			if (isset($paths[$relation->to->id])) {
214			if ($paths[$relation->to->id]->distance > ($paths[$point]->distance + $relation->distance)) {
215			$paths[$relation->to->id]->copy($paths[$point])
216			->addNode($relation->to->id, $relation->distance);
217			}
218			} else {
219			$paths[$relation->to->id] = (new Path())->copy($paths[$point])
220			->addNode($relation->to->id, $relation->distance);
221			}
222			}
223			}
224			}
225

PHPAlgorithms / Dijkstra-s-algorithm

Push — master ( f52c87...2cae32 )

Dijkstra::getMinimalRelation() B

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like