Dijkstra::getShortestPath() - Code Metrics - mikekamornikov/UpgradeSpec - Measure and Improve Code Quality continuously with Scrutinizer

Dijkstra::getShortestPath() C
last analyzed 2017-02-09 15:23 UTC

↳ Parent: Dijkstra

Complexity

Conditions	10
Paths	60

Size

Total Lines	62
Code Lines	28

Duplication

Lines	0
Ratio	0 %

Importance

Changes	2
Bugs	0	Features	0

Metric	Value
cc	10
eloc	28
c	2
b	0
f	0
nc	60
nop	2
dl	0
loc	62
rs	6.4192

How to fix Long Method Complexity

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

    /**
     * Dijkstra "the shortest path" algorithm
     *
     * @param $source
     * @param $target
     *
     * @return array
     */
    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
        $stack = new \SplStack();
        $u = $target;
        while (isset($predecessors[$u]) && $predecessors[$u]) {
            $stack->push($u);
            $u = $predecessors[$u];
        }

        // there is no route back
        if ($stack->isEmpty()) {
            return [];
        }

        // add the source node
        $stack->push($source);

        return iterator_to_array($stack, false);
    }

    /**
     * @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			/**
76			* Dijkstra "the shortest path" algorithm
77			*
78			* @param $source
79			* @param $target
80			*
81			* @return array
82			*/
83			private function getShortestPath($source, $target)
84			{
85			// array of the best estimates of shortest path to each vertex
86			$bestEstimates = [];
87			// array of predecessors for each vertex
88			$predecessors = [];
89			// queue of all unoptimized vertices
90			$queue = new \SplPriorityQueue();
91
92			foreach ($this->graph as $vertex => $list) {
93			$bestEstimates[$vertex] = \INF; // set initial distance to "infinity"
94			$predecessors[$vertex] = null; // no known predecessors yet
95			foreach ($list as $w => $cost) {
96			// use the edge cost as the priority
97			$queue->insert($w, $cost);
98			}
99			}
100
101			// initial distance at source is 0
102			$bestEstimates[$source] = 0;
103
104			while (!$queue->isEmpty()) {
105			// extract min cost
106			$u = $queue->extract();
107			if (!empty($this->graph[$u])) {
108			// "relax" each adjacent vertex
109			foreach ($this->graph[$u] as $vertex => $cost) {
110			// alternate route length to adjacent neighbor
111			$alt = $bestEstimates[$u] + $cost;
112			/**
113			* if alternate route is shorter:
114			* - update minimum length to vertex
115			* - add neighbor to predecessors for vertex
116			*/
117			if ($alt < $bestEstimates[$vertex]) {
118			$bestEstimates[$vertex] = $alt;
119			$predecessors[$vertex] = $u;
120
121			$queue->insert($vertex, $cost);
122			}
123			}
124			}
125			}
126
127			// we can now find the shortest path using reverse iteration
128			$stack = new \SplStack();
129			$u = $target;
130			while (isset($predecessors[$u]) && $predecessors[$u]) {
131			$stack->push($u);
132			$u = $predecessors[$u];
133			}
134
135			// there is no route back
136			if ($stack->isEmpty()) {
137			return [];
138			}
139
140			// add the source node
141			$stack->push($source);
142
143			return iterator_to_array($stack, false);
144			}
145
146			/**
147			* @param Version $from
148			*
149			* @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...
150			*/
151			private function getOriginVertexes(Version $from)
152			{
153			$aliases = $from->getAliases();
154			while ($from->isMinor()) {
155			$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...
156			$aliases = $aliases->merge($from->getAliases());
157			}
158
159			return $aliases->filter(function (Version $version) {
160			return isset($this->graph[(string) $version]);
161			});
162			}
163
164			/**
165			* @param Version $to
166			*
167			* @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...
168			*/
169			private function getDestinationVertexes(Version $to)
170			{
171			return $to->getAliases()->filter(function (Version $version) {
172			return isset($this->graph[(string) $version]);
173			});
174			}
175			}
176

mikekamornikov / UpgradeSpec

Dijkstra::getShortestPath() C last analyzed 2017-02-09 15:23 UTC

Complexity

Size

Duplication

Importance

How to fix Long Method Complexity

Long Method

Duplication Side-by-Side

Filter issues like

Dijkstra::getShortestPath() C
last analyzed 2017-02-09 15:23 UTC