Dijkstra::updatePaths() - Code Metrics - PHPAlgorithms/Dijkstra-s-algorithm - Measure and Improve Code Quality continuously with Scrutinizer

Dijkstra::updatePaths() A
last analyzed 2016-06-09 09:57 UTC

↳ Parent: Dijkstra

Complexity

Conditions	4
Paths	4

Size

Total Lines	14
Code Lines	9

Duplication

Lines	0
Ratio	0 %

Importance

Changes	2
Bugs	0	Features	0

Metric	Value
c	2
b	0
f	0
dl	0
loc	14
rs	9.2
cc	4
eloc	9
nc	4
nop	2

<?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
 * @package PHPAlgorithms
 * @property array $results
 */
class Dijkstra {
    /**
     * @var array $points Array of collected Point objects.
     * @var array $results Array of generated results.
     */
    private $points = array();
    private $results = 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;
    }

    /**
     * @param integer[] $unvisited Array of unvisited points' ids.
     * @param integer[] $visited Array of visited points' ids.
     * @param integer|null $startPoint Start point id.
     * @return integer|null Method returns point identifier where it exists in $unvisited array or null otherwise.
     */
    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)
    {
        $point = $this->getPointID($point);

        if (empty($this->results[$point])) {
            return $this->generateForce($point);
        }

        return $this->results[$point];
    }

    /**
     * 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 generates path for given Point object or point id. It's not watching for existing cache.
     *
     * @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 generateForce($point)
    {
        $point = $this->getPointID($point);

        $startPoint = $point;

        $visited = array();
        $keys = array_keys($this->points);
        $unvisited = array_combine($keys, $keys);
        $paths = array();
        $previous = null;

        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. It's not watching for existing cache.
     *
     * @return Path[][] Two-dimensional array of Path objects.
     * @throws Exception Method throws exception when generate() method throws exception.
     */
    public function generateForceAll()

    {
        $generated = array();

        foreach ($this->points as $index => $point) {
            $generated[$index] = $this->generateForce($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])) {
                $minimalIndex = $index;
                $minimalValue = $relation->distance + $paths[$point]->distance;
            }
        }

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

    /**
     * Method gets from Point object identifier or checks given value. If this value not exists in $points object property then throws exception.
     *
     * @param mixed $point Value to check.
     * @return integer Point identifier.
     * @throws Exception Method throws exception when given value not exists in $points array.
     */
    private function getPointID($point)
    {
        if ($point instanceof Point) {
            $point = $point->id;
        }

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

        return $point;
    }

    /**
     * @param array $reIndex New points' indexes.
     */
    public function reIndex($reIndex)
    {
        if (array_keys($reIndex) != array_keys($this->points)) {
            throw new Exception('You don\'t reindex all keys');
        }

        foreach ($reIndex as $oldIndex => $newIndex) {
            foreach ($reIndex as $oldIndex_ => $newIndex_) {
                if (($oldIndex != $oldIndex_) && ($newIndex == $newIndex_)) {
                    throw new Exception('Array error: two different indexes show to one');
                }
            }
        }

        $points = array();
        $results = array();
        foreach ($reIndex as $oldIndex => $newIndex) {
            $points[$newIndex] = $this->points[$oldIndex];
            $points[$newIndex]->id = $newIndex;

            if (isset($this->results[$oldIndex])) {
                $results[$newIndex] = $this->results[$oldIndex];
            }
        }

        $this->points = $points;
        $this->results = $results;

        return $this;
    }

    /**
     * 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		/**
17		* Class Dijkstra
18		* @package PHPAlgorithms
19		* @property array $results
20		*/
21		class Dijkstra {
22		/**
23		* @var array $points Array of collected Point objects.
24		* @var array $results Array of generated results.
25		*/
26		private $points = array();
27		private $results = array();
28
29		/**
30		* Dijkstra constructor.
31		*
32		* @param Closure\|null $function Anonymous function to create relations.
33		*/
34		public function __construct($function = null)
35		{
36		if (!is_null($function)) {
37		$this->add($function);
38		}
39		}
40
41		/**
42		* Method executes sent function and add result to $points parameter.
43		*
44		* @param Closure $function Anonymous function to create relations.
45		* @return Dijkstra $this Reference to the same object.
46		* @throws Exception Method throws exception when $function argument isn't a Closure object.
47		*/
48		public function add($function)
49		{
50		if (!($function instanceof Closure)) {
51		throw new Exception('Sent argument is not instance of Closure');
52		}
53
54		$creator = new Creator();
55		$function($creator);
56
57		if (empty($this->points)) {
58		$this->points = $creator->dumpPoints();
59		} else {
60		$index = count($this->points);
61
62		foreach ($creator->dumpPoints() as $point) {
63		$this->points[$index] = $point;
64		$point->id = $index;
65
66		$index++;
67		}
68		}
69
70		return $this;
71		}
72
73		/**
74		* Method search unvisited points in neighborhood of sent point.
75		*
76		* @param integer[] $visited Array of visited points' ids.
77		* @param integer $point Point id.
78		* @return boolean True when exists unvisited point in neighborhood or false otherwise.
79		*/
80		private function existsUnvisitedInNeighborhood($visited, $point)
81		{
82		foreach ($this->points[$point]->relations as $relation) {
83		if (!isset($visited[$relation->to->id])) {
84		return true;
85		}
86		}
87
88		return false;
89		}
90
91		/**
92		* @param integer[] $unvisited Array of unvisited points' ids.
93		* @param integer[] $visited Array of visited points' ids.
94		* @param integer\|null $startPoint Start point id.
95		* @return integer\|null Method returns point identifier where it exists in $unvisited array or null otherwise.
96		*/
97		private function findPointWithUncheckedRelation($unvisited, $visited, $startPoint = null)
98		{
99		if (empty($unvisited)) {
100		return null;
101		}
102
103		if (is_null($startPoint)) {
104		foreach ($this->points as $point) {
105		if ($this->existsUnvisitedInNeighborhood($visited, $point->id)) {
106		return $point->id;
107		}
108		}
109		} elseif ($this->existsUnvisitedInNeighborhood($visited, $startPoint)) {
110		return $startPoint;
111		}
112
113		return null;
114		}
115
116		/**
117		* Method generates path for given Point object or point id.
118		*
119		* @param Point\|integer $point Point object or point identification number.
120		* @return Path[] Array of Path objects.
121		* @throws Exception Throws exception when sent point not isset in object's $point array.
122		*/
123		public function generate($point)
124		{
125		$point = $this->getPointID($point);
126
127		if (empty($this->results[$point])) {
128		return $this->generateForce($point);
129		}
130
131		return $this->results[$point];
132		}
133
134		/**
135		* Method generates paths for all defined points.
136		*
137		* @return Path[][] Two-dimensional array of Path objects.
138		* @throws Exception Method throws exception when generate() method throws exception.
139		*/
140	View Code Duplication	public function generateAll()
		0 ignored issues – show Duplication introduced 2016-06-09 09:57 UTC by Report Bug Copy Issue Report This method seems to be duplicated in your project. Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation. You can also find more detailed suggestions in the “Code” section of your repository. Loading history...
141		{
142		$generated = array();
143
144		foreach ($this->points as $index => $point) {
145		$generated[$index] = $this->generate($point);
146		}
147
148		return $generated;
149		}
150
151		/**
152		* Method generates path for given Point object or point id. It's not watching for existing cache.
153		*
154		* @param Point\|integer $point Point object or point identification number.
155		* @return Path[] Array of Path objects.
156		* @throws Exception Throws exception when sent point not isset in object's $point array.
157		*/
158		public function generateForce($point)
159		{
160		$point = $this->getPointID($point);
161
162		$startPoint = $point;
163
164		$visited = array();
165		$keys = array_keys($this->points);
166		$unvisited = array_combine($keys, $keys);
167		$paths = array();
168		$previous = null;
169
170		while (!empty($unvisited) && !is_null($point)) {
171		unset($unvisited[$point]);
172		$visited[$point] = $point;
173
174		if (!isset($paths[$point])) {
175		if (is_null($previous)) {
176		$paths[$point] = new Path();
177		} else {
178		$paths[$point]->copy($paths[$previous]);
179		}
180
181		$paths[$point]->addNode($point);
182		}
183
184		$relation = $this->getMinimalRelation($unvisited, $paths, $point);
185
186		$this->updatePaths($paths, $point);
187
188		$previous = $point;
189
190		if (!is_null($relation)) {
191		$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...
192		->id;
193		} else {
194		$point = $this->findPointWithUncheckedRelation($unvisited, $visited, $startPoint);
195		}
196		};
197
198		return $paths;
199		}
200
201		/**
202		* Method generates paths for all defined points. It's not watching for existing cache.
203		*
204		* @return Path[][] Two-dimensional array of Path objects.
205		* @throws Exception Method throws exception when generate() method throws exception.
206		*/
207	View Code Duplication	public function generateForceAll()
		0 ignored issues – show Duplication introduced 2016-06-09 09:57 UTC by Report Bug Copy Issue Report This method seems to be duplicated in your project. Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation. You can also find more detailed suggestions in the “Code” section of your repository. Loading history...
208		{
209		$generated = array();
210
211		foreach ($this->points as $index => $point) {
212		$generated[$index] = $this->generateForce($point);
213		}
214
215		return $generated;
216		}
217
218		/**
219		* Method try to find minimal relation to another point from given point.
220		*
221		* @param integer[] $unvisited Array of unvisited points' ids.
222		* @param Path[] $paths Array of generated Path objects.
223		* @param integer $point Point integer identifier.
224		* @return Dijkstra\Relation\|null Method returns Relation object or null when minimal relation wasn't found.
225		*/
226		private function getMinimalRelation($unvisited, $paths, $point)
227		{
228		$minimalValue = INF;
229		$minimalIndex = -1;
230
231		foreach ($this->points[$point]->relations as $index => $relation) {
232		if (($minimalValue > ($relation->distance + $paths[$point]->distance)) && isset($unvisited[$relation->to->id])) {
233		$minimalIndex = $index;
234		$minimalValue = $relation->distance + $paths[$point]->distance;
235		}
236		}
237
238		if ($minimalIndex != -1) {
239		return $this->points[$point]
240		->relations[$minimalIndex];
241		} else {
242		return null;
243		}
244		}
245
246		/**
247		* Method gets from Point object identifier or checks given value. If this value not exists in $points object property then throws exception.
248		*
249		* @param mixed $point Value to check.
250		* @return integer Point identifier.
251		* @throws Exception Method throws exception when given value not exists in $points array.
252		*/
253		private function getPointID($point)
254		{
255		if ($point instanceof Point) {
256		$point = $point->id;
257		}
258
259		if (!isset($this->points[$point])) {
260		throw new Exception("Point with id {$point} not exists");
261		}
262
263		return $point;
264		}
265
266		/**
267		* @param array $reIndex New points' indexes.
268		*/
269		public function reIndex($reIndex)
270		{
271		if (array_keys($reIndex) != array_keys($this->points)) {
272		throw new Exception('You don\'t reindex all keys');
273		}
274
275		foreach ($reIndex as $oldIndex => $newIndex) {
276		foreach ($reIndex as $oldIndex_ => $newIndex_) {
277		if (($oldIndex != $oldIndex_) && ($newIndex == $newIndex_)) {
278		throw new Exception('Array error: two different indexes show to one');
279		}
280		}
281		}
282
283		$points = array();
284		$results = array();
285		foreach ($reIndex as $oldIndex => $newIndex) {
286		$points[$newIndex] = $this->points[$oldIndex];
287		$points[$newIndex]->id = $newIndex;
288
289		if (isset($this->results[$oldIndex])) {
290		$results[$newIndex] = $this->results[$oldIndex];
291		}
292		}
293
294		$this->points = $points;
295		$this->results = $results;
296
297		return $this;
298		}
299
300		/**
301		* Method updates existing Path object or create new if it's possible.
302		*
303		* @param Path[] &$paths Array of generated Path[] objects. Given by reference.
304		* @param integer $point Integer point identifier.
305		*/
306		public function updatePaths(&$paths, $point)
307		{
308		foreach ($this->points[$point]->relations as $relation) {
309		if (isset($paths[$relation->to->id])) {
310		if ($paths[$relation->to->id]->distance > ($paths[$point]->distance + $relation->distance)) {
311		$paths[$relation->to->id]->copy($paths[$point])
312		->addNode($relation->to->id, $relation->distance);
313		}
314		} else {
315		$paths[$relation->to->id] = (new Path())->copy($paths[$point])
316		->addNode($relation->to->id, $relation->distance);
317		}
318		}
319		}
320		}
321

PHPAlgorithms / Dijkstra-s-algorithm

Dijkstra::updatePaths() A last analyzed 2016-06-09 09:57 UTC

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like

Dijkstra::updatePaths() A
last analyzed 2016-06-09 09:57 UTC