Dijkstra::getDestinationVertexes() - Code Metrics - Inspection of "use "Dijkstra" instead of basic "breadth first"" - mikekamornikov/UpgradeSpec - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( 8a3ba8...53d1ed )

by Mike

created 2017-02-09 14:52 UTC

Dijkstra::getDestinationVertexes() A

↳ Parent: Dijkstra

Complexity

Conditions	1
Paths	1

Size

Total Lines	6
Code Lines	3

Duplication

Lines	0
Ratio	0 %

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
cc	1
eloc	3
c	1
b	0
f	0
nc	1
nop	1
dl	0
loc	6
rs	9.4285

<?php

namespace Sugarcrm\UpgradeSpec\Version\Graph;

use Sugarcrm\UpgradeSpec\Version\Version;

class Dijkstra
{
    /**
     * @var array
     */
    private $graph;

    /**
     * Graph constructor.
     *
     * @param AdjacencyList $adj
     */
    public function __construct(AdjacencyList $adj)
    {
        foreach ($adj as $vertex => $list) {
            $list = array_map(function (Version $version) use ($vertex) {
                return [(string) $version => (new Version($vertex))->isChildOf($version) ? 0 : 1];
            }, iterator_to_array($list));

            $this->graph[(string) $vertex] = $list ? call_user_func_array('array_merge', $list) : [];
        }
    }

    /**
     * @param Version $from
     * @param Version $to
     *
     * @return array
     */
    public function getPath(Version $from, Version $to)
    {
        $destinations = $this->getDestinationVertexes($to);
        foreach ($this->getOriginVertexes($from) as $origin) {
            foreach ($destinations as $destination) {
                if ($path = $this->getShortestPath((string) $origin, (string) $destination)) {
                    return $this->getRealHops($path);
                }
            }
        }

        return [];
    }

    /**
     * @param $path
     *
     * @return array
     */
    private function getRealHops($path)
    {
        $pairs = [];

        $first = new Version($path[0]);
        foreach (range(1, count($path) - 1) as $index) {
            $second = new Version($path[$index]);
            if ($first->isChildOf($second)) {
                $first = $second;
                continue;
            }

            $pairs[] = [$first, $second];

            $first = $second;
        }

        return $pairs;
    }

    private function getShortestPath($source, $target)
    {
        // array of the best estimates of shortest path to each vertex
        $bestEstimates = [];
        // array of predecessors for each vertex
        $predecessors = [];
        // queue of all unoptimized vertices
        $queue = new \SplPriorityQueue();

        foreach ($this->graph as $vertex => $list) {
            $bestEstimates[$vertex] = \INF; // set initial distance to "infinity"
            $predecessors[$vertex] = null; // no known predecessors yet
            foreach ($list as $w => $cost) {
                // use the edge cost as the priority
                $queue->insert($w, $cost);
            }
        }

        // initial distance at source is 0
        $bestEstimates[$source] = 0;

        while (!$queue->isEmpty()) {
            // extract min cost
            $u = $queue->extract();
            if (!empty($this->graph[$u])) {
                // "relax" each adjacent vertex
                foreach ($this->graph[$u] as $vertex => $cost) {
                    // alternate route length to adjacent neighbor
                    $alt = $bestEstimates[$u] + $cost;
                    /**
                     * if alternate route is shorter:
                     * - update minimum length to vertex
                     * - add neighbor to predecessors for vertex
                     */
                    if ($alt < $bestEstimates[$vertex]) {
                        $bestEstimates[$vertex] = $alt;
                        $predecessors[$vertex] = $u;

                        $queue->insert($vertex, $cost);
                    }
                }
            }
        }

        // we can now find the shortest path using reverse iteration
        $path = [];
        $u = $target;
        while (isset($predecessors[$u]) && $predecessors[$u]) {
            $path[] = $u;
            $u = $predecessors[$u];
        }

        if (!$path) {

            return [];
        }

        return array_reverse(array_merge($path, [$source]));
    }

    /**
     * @param Version $from
     *
     * @return OrderedList

     */
    private function getOriginVertexes(Version $from)
    {
        $aliases = $from->getAliases();
        while ($from->isMinor()) {
            $from = $from->getParent();

            $aliases = $aliases->merge($from->getAliases());
        }

        return $aliases->filter(function (Version $version) {
            return isset($this->graph[(string) $version]);
        });
    }

    /**
     * @param Version $to
     *
     * @return OrderedList

     */
    private function getDestinationVertexes(Version $to)
    {
        return $to->getAliases()->filter(function (Version $version) {
            return isset($this->graph[(string) $version]);
        });
    }
}


1			<?php
2
3			namespace Sugarcrm\UpgradeSpec\Version\Graph;
4
5			use Sugarcrm\UpgradeSpec\Version\Version;
6
7			class Dijkstra
8			{
9			/**
10			* @var array
11			*/
12			private $graph;
13
14			/**
15			* Graph constructor.
16			*
17			* @param AdjacencyList $adj
18			*/
19			public function __construct(AdjacencyList $adj)
20			{
21			foreach ($adj as $vertex => $list) {
22			$list = array_map(function (Version $version) use ($vertex) {
23			return [(string) $version => (new Version($vertex))->isChildOf($version) ? 0 : 1];
24			}, iterator_to_array($list));
25
26			$this->graph[(string) $vertex] = $list ? call_user_func_array('array_merge', $list) : [];
27			}
28			}
29
30			/**
31			* @param Version $from
32			* @param Version $to
33			*
34			* @return array
35			*/
36			public function getPath(Version $from, Version $to)
37			{
38			$destinations = $this->getDestinationVertexes($to);
39			foreach ($this->getOriginVertexes($from) as $origin) {
40			foreach ($destinations as $destination) {
41			if ($path = $this->getShortestPath((string) $origin, (string) $destination)) {
42			return $this->getRealHops($path);
43			}
44			}
45			}
46
47			return [];
48			}
49
50			/**
51			* @param $path
52			*
53			* @return array
54			*/
55			private function getRealHops($path)
56			{
57			$pairs = [];
58
59			$first = new Version($path[0]);
60			foreach (range(1, count($path) - 1) as $index) {
61			$second = new Version($path[$index]);
62			if ($first->isChildOf($second)) {
63			$first = $second;
64			continue;
65			}
66
67			$pairs[] = [$first, $second];
68
69			$first = $second;
70			}
71
72			return $pairs;
73			}
74
75			private function getShortestPath($source, $target)
76			{
77			// array of the best estimates of shortest path to each vertex
78			$bestEstimates = [];
79			// array of predecessors for each vertex
80			$predecessors = [];
81			// queue of all unoptimized vertices
82			$queue = new \SplPriorityQueue();
83
84			foreach ($this->graph as $vertex => $list) {
85			$bestEstimates[$vertex] = \INF; // set initial distance to "infinity"
86			$predecessors[$vertex] = null; // no known predecessors yet
87			foreach ($list as $w => $cost) {
88			// use the edge cost as the priority
89			$queue->insert($w, $cost);
90			}
91			}
92
93			// initial distance at source is 0
94			$bestEstimates[$source] = 0;
95
96			while (!$queue->isEmpty()) {
97			// extract min cost
98			$u = $queue->extract();
99			if (!empty($this->graph[$u])) {
100			// "relax" each adjacent vertex
101			foreach ($this->graph[$u] as $vertex => $cost) {
102			// alternate route length to adjacent neighbor
103			$alt = $bestEstimates[$u] + $cost;
104			/**
105			* if alternate route is shorter:
106			* - update minimum length to vertex
107			* - add neighbor to predecessors for vertex
108			*/
109			if ($alt < $bestEstimates[$vertex]) {
110			$bestEstimates[$vertex] = $alt;
111			$predecessors[$vertex] = $u;
112
113			$queue->insert($vertex, $cost);
114			}
115			}
116			}
117			}
118
119			// we can now find the shortest path using reverse iteration
120			$path = [];
121			$u = $target;
122			while (isset($predecessors[$u]) && $predecessors[$u]) {
123			$path[] = $u;
124			$u = $predecessors[$u];
125			}
126
127			if (!$path) {
			0 ignored issues – show Bug Best Practice introduced 2017-02-09 14:56 UTC by Report Bug Copy Issue Report The expression `$path` of type `array` is implicitly converted to a boolean; are you sure this is intended? If so, consider using `empty($expr)` instead to make it clear that you intend to check for an array without elements. This check marks implicit conversions of arrays to boolean values in a comparison. While in PHP an empty array is considered to be equal (but not identical) to false, this is not always apparent. Consider making the comparison explicit by using `empty(..)` or `! empty(...)` instead. Loading history...
128			return [];
129			}
130
131			return array_reverse(array_merge($path, [$source]));
132			}
133
134			/**
135			* @param Version $from
136			*
137			* @return OrderedList
			0 ignored issues – show Documentation introduced 2017-02-09 14:56 UTC by Report Bug Copy Issue Report Should the return type not be `\Sugarcrm\UpgradeSpec\Version\OrderedList`? This check compares the return type specified in the `@return` annotation of a function or method doc comment with the types returned by the function and raises an issue if they mismatch. Loading history...
138			*/
139			private function getOriginVertexes(Version $from)
140			{
141			$aliases = $from->getAliases();
142			while ($from->isMinor()) {
143			$from = $from->getParent();
			0 ignored issues – show Coding Style introduced 2017-02-09 14:56 UTC by Report Bug Copy Issue Report Consider using a different name than the parameter `$from`. This often makes code more readable. Loading history...
144			$aliases = $aliases->merge($from->getAliases());
145			}
146
147			return $aliases->filter(function (Version $version) {
148			return isset($this->graph[(string) $version]);
149			});
150			}
151
152			/**
153			* @param Version $to
154			*
155			* @return OrderedList
			0 ignored issues – show Documentation introduced 2017-02-09 14:56 UTC by Report Bug Copy Issue Report Should the return type not be `\Sugarcrm\UpgradeSpec\Version\OrderedList`? This check compares the return type specified in the `@return` annotation of a function or method doc comment with the types returned by the function and raises an issue if they mismatch. Loading history...
156			*/
157			private function getDestinationVertexes(Version $to)
158			{
159			return $to->getAliases()->filter(function (Version $version) {
160			return isset($this->graph[(string) $version]);
161			});
162			}
163			}
164

mikekamornikov / UpgradeSpec

Push — master ( 8a3ba8...53d1ed )

Dijkstra::getDestinationVertexes() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like