Dijkstra::generate() - Code Metrics - Inspection of "Added method getPointID()." - PHPAlgorithms/Dijkstra-s-algorithm - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( 2cae32...d86569 )

by Ventaquil

created 2016-04-09 18:54 UTC

Dijkstra::generate() B

↳ Parent: Dijkstra

Complexity

Conditions	6
Paths	7

Size

Total Lines	41
Code Lines	25

Duplication

Lines	0
Ratio	0 %

Importance

Changes	4
Bugs	0	Features	1

Metric	Value
c	4
b	0
f	1
dl	0
loc	41
rs	8.439
cc	6
eloc	25
nc	7
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();
        $unvisited = array_keys($this->points);
        $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;
    }

    /**
     * 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			$unvisited = array_keys($this->points);
128			$paths = array();
129			$previous = null;
130
131			while (!empty($unvisited) && !is_null($point)) {
132			unset($unvisited[$point]);
133			$visited[$point] = $point;
134
135			if (!isset($paths[$point])) {
136			if (is_null($previous)) {
137			$paths[$point] = new Path();
138			} else {
139			$paths[$point]->copy($paths[$previous]);
140			}
141
142			$paths[$point]->addNode($point);
143			}
144
145			$relation = $this->getMinimalRelation($unvisited, $paths, $point);
146
147			$this->updatePaths($paths, $point);
148
149			$previous = $point;
150
151			if (!is_null($relation)) {
152			$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...
153			->id;
154			} else {
155			$point = $this->findPointWithUncheckedRelation($unvisited, $visited, $startPoint);
156			}
157			};
158
159			return $paths;
160			}
161
162			/**
163			* Method generates paths for all defined points.
164			*
165			* @return Path[][] Two-dimensional array of Path objects.
166			* @throws Exception Method throws exception when generate() method throws exception.
167			*/
168			public function generateAll()
169			{
170			$generated = array();
171
172			foreach ($this->points as $index => $point) {
173			$generated[$index] = $this->generate($point);
174			}
175
176			return $generated;
177			}
178
179			/**
180			* Method try to find minimal relation to another point from given point.
181			*
182			* @param integer[] $unvisited Array of unvisited points' ids.
183			* @param Path[] $paths Array of generated Path objects.
184			* @param integer $point Point integer identifier.
185			* @return Dijkstra\Relation\|null Method returns Relation object or null when minimal relation wasn't found.
186			*/
187			private function getMinimalRelation($unvisited, $paths, $point)
188			{
189			$minimalValue = INF;
190			$minimalIndex = -1;
191
192			foreach ($this->points[$point]->relations as $index => $relation) {
193			if (($minimalValue > ($relation->distance + $paths[$point]->distance)) && isset($unvisited[$relation->to->id])) {
194			$minimalIndex = $index;
195			$minimalValue = $relation->distance + $paths[$point]->distance;
196			}
197			}
198
199			if ($minimalIndex != -1) {
200			return $this->points[$point]
201			->relations[$minimalIndex];
202			} else {
203			return null;
204			}
205			}
206
207			/**
208			* Method gets from Point object identifier or checks given value. If this value not exists in $points object property then throws exception.
209			*
210			* @param mixed $point Value to check.
211			* @return integer Point identifier.
212			* @throws Exception Method throws exception when given value not exists in $points array.
213			*/
214			private function getPointID($point)
215			{
216			if ($point instanceof Point) {
217			$point = $point->id;
218			}
219
220			if (!isset($this->points[$point])) {
221			throw new Exception("Point with id {$point} not exists");
222			}
223
224			return $point;
225			}
226
227			/**
228			* Method updates existing Path object or create new if it's possible.
229			*
230			* @param Path[] &$paths Array of generated Path[] objects. Given by reference.
231			* @param integer $point Integer point identifier.
232			*/
233			public function updatePaths(&$paths, $point)
234			{
235			foreach ($this->points[$point]->relations as $relation) {
236			if (isset($paths[$relation->to->id])) {
237			if ($paths[$relation->to->id]->distance > ($paths[$point]->distance + $relation->distance)) {
238			$paths[$relation->to->id]->copy($paths[$point])
239			->addNode($relation->to->id, $relation->distance);
240			}
241			} else {
242			$paths[$relation->to->id] = (new Path())->copy($paths[$point])
243			->addNode($relation->to->id, $relation->distance);
244			}
245			}
246			}
247			}
248

PHPAlgorithms / Dijkstra-s-algorithm

Push — master ( 2cae32...d86569 )

Dijkstra::generate() B

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like