Dijkstra::reIndex() - Code Metrics - Inspection of "ReIndex Dijkstra results." - PHPAlgorithms/Dijkstra-s-algorithm - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( d7d46b...7438b4 )

by Ventaquil

created 2016-06-09 07:29 UTC

Dijkstra::reIndex() C

↳ Parent: Dijkstra

Complexity

Conditions	7
Paths	8

Size

Total Lines	24
Code Lines	13

Duplication

Lines	0
Ratio	0 %

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
c	1
b	0
f	0
dl	0
loc	24
rs	6.7272
cc	7
eloc	13
nc	8
nop	1

<?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
 */
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;
    }

    /**
     * @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);

        $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.
     *
     * @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])) {
                $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();
        foreach ($reIndex as $oldIndex => $newIndex) {
            $points[$newIndex] = $this->points[$oldIndex];
            $points[$newIndex]->id = $newIndex;
        }

        $this->points = $points;

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

PHPAlgorithms / Dijkstra-s-algorithm

Push — master ( d7d46b...7438b4 )

Dijkstra::reIndex() C

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like