MultiDijkstra::getCheapestPathFromPredecesArray() - Code Metrics - thecodingmachine/schema-analyzer - Measure and Improve Code Quality continuously with Scrutinizer

MultiDijkstra::getCheapestPathFromPredecesArray() A
last analyzed 2020-08-01 21:35 UTC

↳ Parent: MultiDijkstra

Complexity

Conditions	4
Paths	4

Size

Total Lines

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
dl	0
loc	21
rs	9.584
c	0
b	0
f	0
cc	4
nc	4
nop	3

<?php

namespace Mouf\Database\SchemaAnalyzer;

use Fhaculty\Graph\Edge;
use Fhaculty\Graph\Exception\UnexpectedValueException;
use Fhaculty\Graph\Vertex;
use SplPriorityQueue;

/**
 * Dijkstra's shortest path algorithm modified to measure all possible shortest paths.
 */
class MultiDijkstra
{
    /**
     * Get all edges on shortest path for this vertex.
     *
     * @throws UnexpectedValueException     when encountering an Edge with negative weight
     * @throws MultiDijkstraNoPathException
     *
     * @return array<string, Vertex[]> where key is the destination vertex name and value is an array of possible origin vertex

     */
    public static function findShortestPaths(Vertex $startVertex, Vertex $endVertex)
    {
        $totalCostOfCheapestPathTo = [];
        // start node distance
        $totalCostOfCheapestPathTo[$startVertex->getId()] = 0;

        $endVertexId = $endVertex->getId();

        // just to get the cheapest vertex in the correct order
        $cheapestVertex = new SplPriorityQueue();
        $cheapestVertex->setExtractFlags(SplPriorityQueue::EXTR_BOTH);
        $cheapestVertex->insert($startVertex, 0);

        // predecessors
        $predecesEdgeOfCheapestPathTo = [];

        // mark vertices when their cheapest path has been found
        $usedVertices = [$startVertex->getId() => true];

        $isFirst = true;

        // Repeat until all vertices have been marked
        $totalCountOfVertices = count($startVertex->getGraph()->getVertices());
        for ($i = 0; $i < $totalCountOfVertices; ++$i) {
            $currentVertex = null;
            $currentVertexId = null;
            $isEmpty = false;
            if ($isFirst) {
                $currentVertex = $startVertex;
                $currentCost = 0;
                $currentVertexId = $currentVertex->getId();
            } else {
                do {
                    // if the priority queue is empty there are isolated vertices, but the algorithm visited all other vertices
                    if ($cheapestVertex->isEmpty()) {
                        $isEmpty = true;
                        break;
                    }
                    // Get cheapest unmarked vertex
                    $cheapestResult = $cheapestVertex->extract();
                    $currentVertex = $cheapestResult['data'];
                    $currentCost = $cheapestResult['priority'];
                    $currentVertexId = $currentVertex->getId();
                // Vertices can be in the priority queue multiple times, with different path costs (if vertex is already marked, this is an old unvalid entry)
                } while (isset($usedVertices[$currentVertexId]));
            }

            // Check premature end condition
            // If the end vertex is marked as done and the next lowest possible weight is bigger than end vertix,
            // we are done processing.


            // catch "algorithm ends" condition
            if ($isEmpty) {
                break;
            }

            if ($isFirst) {
                $isFirst = false;
            }

            // mark this vertex
            $usedVertices[$currentVertexId] = true;

            if (isset($usedVertices[$endVertexId]) && $totalCostOfCheapestPathTo[$endVertexId] < -$currentCost) {
function myFunction($a) {
    switch ($a) {
        case 'foo':
            $x = 1;
            break;

        case 'bar':
            $x = 2;
            break;
    }

    // $x is potentially undefined here.
    echo $x;
}
                break;
            }

            // check for all edges of current vertex if there is a cheaper path (or IN OTHER WORDS: Add reachable nodes from currently added node and refresh the current possible distances)
            foreach ($currentVertex->getEdgesOut() as $edge) {
                $weight = $edge->getWeight();
                if ($weight < 0) {
                    throw new UnexpectedValueException('Dijkstra not supported for negative weights - Consider using MooreBellmanFord');
                }

                $targetVertex = $edge->getVertexToFrom($currentVertex);
                $targetVertexId = $targetVertex->getId();

                // if the targetVertex is marked, the cheapest path for this vertex has already been found (no negative edges) {
                if (!isset($usedVertices[$targetVertexId])) {
                    // calculate new cost to vertex
                    $newCostsToTargetVertex = $totalCostOfCheapestPathTo[$currentVertexId] + $weight;

                    if ((!isset($predecesEdgeOfCheapestPathTo[$targetVertexId]))
                           // is the new path cheaper?
                           || $totalCostOfCheapestPathTo[$targetVertexId] > $newCostsToTargetVertex) {

                        // Not an update, just a new insert with lower cost
                        $cheapestVertex->insert($targetVertex, -$newCostsToTargetVertex);
                        // so the lowest cost will be extracted first
                        // and higher cost will be skipped during extraction

                        // update/set costs found with the new connection
                        $totalCostOfCheapestPathTo[$targetVertexId] = $newCostsToTargetVertex;
                        // update/set predecessor vertex from the new connection
                        $predecesEdgeOfCheapestPathTo[$targetVertexId] = [$edge];
                    } elseif ($totalCostOfCheapestPathTo[$targetVertexId] == $newCostsToTargetVertex) {
                        // Same length paths. We need to add the predecessor to the list of possible predecessors.
                        $predecesEdgeOfCheapestPathTo[$targetVertexId][] = $edge;
                    }
                }
            }
        }

        if (!isset($totalCostOfCheapestPathTo[$endVertexId])) {
            throw new MultiDijkstraNoPathException("No path found between vertex '".$startVertex->getId()."' and vertex '".$endVertex->getId()."'");
        }

        // algorithm is done, return resulting edges
        return $predecesEdgeOfCheapestPathTo;
    }

    /**
     * @param array<string, Vertex[]> $predecesEdgesArray key is the destination vertex name and value is an array of possible origin vertex
     *
     * @return Edge\Base[]
     */
    public static function getCheapestPathFromPredecesArray(Vertex $startVertex, Vertex $endVertex, array $predecesEdgesArray)
    {
        $edges = [];
        $currentVertex = $endVertex;
        while ($currentVertex !== $startVertex) {
            $predecessorEdges = $predecesEdgesArray[$currentVertex->getId()];
            if (count($predecessorEdges) > 1) {
                throw new MultiDijkstraAmbiguityException("There are many possible shortest paths to link vertex '".$startVertex->getId()."' to '".$endVertex->getId()."'");
            }
            /* @var $edge \Fhaculty\Graph\Edge\Base */
            $edge = $predecessorEdges[0];
            $edges[] = $edge;
            if ($currentVertex === $edge->getVerticesStart()->getVertexFirst()) {
                $currentVertex = $edge->getVerticesTarget()->getVertexFirst();
            } else {
                $currentVertex = $edge->getVerticesStart()->getVertexFirst();
            }
        }

        return array_reverse($edges);
    }

    /**
     * @param Vertex $startVertex
     * @param Vertex $endVertex
     * @param array  $predecesEdgesArray
     *
     * @return Edge\Base[][]
     */
    public static function getAllPossiblePathsFromPredecesArray(Vertex $startVertex, Vertex $endVertex, array $predecesEdgesArray)
    {
        $edgesPaths = [];

        if ($startVertex === $endVertex) {
            return [];
        }

        $predecessorEdges = $predecesEdgesArray[$endVertex->getId()];

        foreach ($predecessorEdges as $edge) {
            if ($endVertex === $edge->getVerticesStart()->getVertexFirst()) {
                $nextVertex = $edge->getVerticesTarget()->getVertexFirst();
            } else {
                $nextVertex = $edge->getVerticesStart()->getVertexFirst();
            }

            $edgesPaths2 = self::getAllPossiblePathsFromPredecesArray($startVertex, $nextVertex, $predecesEdgesArray);
            if ($edgesPaths2) {
                foreach ($edgesPaths2 as &$edges2) {
                    $edges2[] = $edge;
                }
            } else {
                $edgesPaths2 = [[$edge]];
            }

            $edgesPaths = array_merge($edgesPaths, $edgesPaths2);
        }

        return $edgesPaths;
    }
}


1			<?php
2
3			namespace Mouf\Database\SchemaAnalyzer;
4
5			use Fhaculty\Graph\Edge;
6			use Fhaculty\Graph\Exception\UnexpectedValueException;
7			use Fhaculty\Graph\Vertex;
8			use SplPriorityQueue;
9
10			/**
11			* Dijkstra's shortest path algorithm modified to measure all possible shortest paths.
12			*/
13			class MultiDijkstra
14			{
15			/**
16			* Get all edges on shortest path for this vertex.
17			*
18			* @throws UnexpectedValueException when encountering an Edge with negative weight
19			* @throws MultiDijkstraNoPathException
20			*
21			* @return array<string, Vertex[]> where key is the destination vertex name and value is an array of possible origin vertex
			0 ignored issues – show Documentation introduced 2016-03-04 16:39 UTC by Report Bug Copy Issue Report The doc-type `array<string,` could not be parsed: Expected ">" at position 5, but found "end of type". (view supported doc-types) This check marks PHPDoc comments that could not be parsed by our parser. To see which comment annotations we can parse, please refer to our documentation on supported doc-types. Loading history...
22			*/
23			public static function findShortestPaths(Vertex $startVertex, Vertex $endVertex)
24			{
25			$totalCostOfCheapestPathTo = [];
26			// start node distance
27			$totalCostOfCheapestPathTo[$startVertex->getId()] = 0;
28
29			$endVertexId = $endVertex->getId();
30
31			// just to get the cheapest vertex in the correct order
32			$cheapestVertex = new SplPriorityQueue();
33			$cheapestVertex->setExtractFlags(SplPriorityQueue::EXTR_BOTH);
34			$cheapestVertex->insert($startVertex, 0);
35
36			// predecessors
37			$predecesEdgeOfCheapestPathTo = [];
38
39			// mark vertices when their cheapest path has been found
40			$usedVertices = [$startVertex->getId() => true];
41
42			$isFirst = true;
43
44			// Repeat until all vertices have been marked
45			$totalCountOfVertices = count($startVertex->getGraph()->getVertices());
46			for ($i = 0; $i < $totalCountOfVertices; ++$i) {
47			$currentVertex = null;
48			$currentVertexId = null;
49			$isEmpty = false;
50			if ($isFirst) {
51			$currentVertex = $startVertex;
52			$currentCost = 0;
53			$currentVertexId = $currentVertex->getId();
54			} else {
55			do {
56			// if the priority queue is empty there are isolated vertices, but the algorithm visited all other vertices
57			if ($cheapestVertex->isEmpty()) {
58			$isEmpty = true;
59			break;
60			}
61			// Get cheapest unmarked vertex
62			$cheapestResult = $cheapestVertex->extract();
63			$currentVertex = $cheapestResult['data'];
64			$currentCost = $cheapestResult['priority'];
65			$currentVertexId = $currentVertex->getId();
66			// Vertices can be in the priority queue multiple times, with different path costs (if vertex is already marked, this is an old unvalid entry)
67			} while (isset($usedVertices[$currentVertexId]));
68			}
69
70			// Check premature end condition
71			// If the end vertex is marked as done and the next lowest possible weight is bigger than end vertix,
72			// we are done processing.
73
74
75			// catch "algorithm ends" condition
76			if ($isEmpty) {
77			break;
78			}
79
80			if ($isFirst) {
81			$isFirst = false;
82			}
83
84			// mark this vertex
85			$usedVertices[$currentVertexId] = true;
86
87			if (isset($usedVertices[$endVertexId]) && $totalCostOfCheapestPathTo[$endVertexId] < -$currentCost) {
			0 ignored issues – show Bug introduced 2016-03-04 16:39 UTC by Report Bug Copy Issue Report The variable `$currentCost` does not seem to be defined for all execution paths leading up to this point. If you define a variable conditionally, it can happen that it is not defined for all execution paths. Let’s take a look at an example: function myFunction($a) { switch ($a) { case 'foo': $x = 1; break; case 'bar': $x = 2; break; } // $x is potentially undefined here. echo $x; } In the above example, the variable `$x` is defined if you pass “foo” or “bar” as argument for `$a`. However, since the `switch` statement has no default case statement, if you pass any other value, the variable `$x` would be undefined. Available Fixes Check for existence of the variable explicitly: function myFunction($a) { switch ($a) { case 'foo': $x = 1; break; case 'bar': $x = 2; break; } if (isset($x)) { // Make sure it's always set. echo $x; } } Define a default value for the variable: function myFunction($a) { $x = ''; // Set a default which gets overridden for certain paths. switch ($a) { case 'foo': $x = 1; break; case 'bar': $x = 2; break; } echo $x; } Add a value for the missing path: function myFunction($a) { switch ($a) { case 'foo': $x = 1; break; case 'bar': $x = 2; break; // We add support for the missing case. default: $x = ''; break; } echo $x; } Loading history...
88			break;
89			}
90
91			// check for all edges of current vertex if there is a cheaper path (or IN OTHER WORDS: Add reachable nodes from currently added node and refresh the current possible distances)
92			foreach ($currentVertex->getEdgesOut() as $edge) {
93			$weight = $edge->getWeight();
94			if ($weight < 0) {
95			throw new UnexpectedValueException('Dijkstra not supported for negative weights - Consider using MooreBellmanFord');
96			}
97
98			$targetVertex = $edge->getVertexToFrom($currentVertex);
99			$targetVertexId = $targetVertex->getId();
100
101			// if the targetVertex is marked, the cheapest path for this vertex has already been found (no negative edges) {
102			if (!isset($usedVertices[$targetVertexId])) {
103			// calculate new cost to vertex
104			$newCostsToTargetVertex = $totalCostOfCheapestPathTo[$currentVertexId] + $weight;
105
106			if ((!isset($predecesEdgeOfCheapestPathTo[$targetVertexId]))
107			// is the new path cheaper?
108			\|\| $totalCostOfCheapestPathTo[$targetVertexId] > $newCostsToTargetVertex) {
109
110			// Not an update, just a new insert with lower cost
111			$cheapestVertex->insert($targetVertex, -$newCostsToTargetVertex);
112			// so the lowest cost will be extracted first
113			// and higher cost will be skipped during extraction
114
115			// update/set costs found with the new connection
116			$totalCostOfCheapestPathTo[$targetVertexId] = $newCostsToTargetVertex;
117			// update/set predecessor vertex from the new connection
118			$predecesEdgeOfCheapestPathTo[$targetVertexId] = [$edge];
119			} elseif ($totalCostOfCheapestPathTo[$targetVertexId] == $newCostsToTargetVertex) {
120			// Same length paths. We need to add the predecessor to the list of possible predecessors.
121			$predecesEdgeOfCheapestPathTo[$targetVertexId][] = $edge;
122			}
123			}
124			}
125			}
126
127			if (!isset($totalCostOfCheapestPathTo[$endVertexId])) {
128			throw new MultiDijkstraNoPathException("No path found between vertex '".$startVertex->getId()."' and vertex '".$endVertex->getId()."'");
129			}
130
131			// algorithm is done, return resulting edges
132			return $predecesEdgeOfCheapestPathTo;
133			}
134
135			/**
136			* @param array<string, Vertex[]> $predecesEdgesArray key is the destination vertex name and value is an array of possible origin vertex
137			*
138			* @return Edge\Base[]
139			*/
140			public static function getCheapestPathFromPredecesArray(Vertex $startVertex, Vertex $endVertex, array $predecesEdgesArray)
141			{
142			$edges = [];
143			$currentVertex = $endVertex;
144			while ($currentVertex !== $startVertex) {
145			$predecessorEdges = $predecesEdgesArray[$currentVertex->getId()];
146			if (count($predecessorEdges) > 1) {
147			throw new MultiDijkstraAmbiguityException("There are many possible shortest paths to link vertex '".$startVertex->getId()."' to '".$endVertex->getId()."'");
148			}
149			/* @var $edge \Fhaculty\Graph\Edge\Base */
150			$edge = $predecessorEdges[0];
151			$edges[] = $edge;
152			if ($currentVertex === $edge->getVerticesStart()->getVertexFirst()) {
153			$currentVertex = $edge->getVerticesTarget()->getVertexFirst();
154			} else {
155			$currentVertex = $edge->getVerticesStart()->getVertexFirst();
156			}
157			}
158
159			return array_reverse($edges);
160			}
161
162			/**
163			* @param Vertex $startVertex
164			* @param Vertex $endVertex
165			* @param array $predecesEdgesArray
166			*
167			* @return Edge\Base[][]
168			*/
169			public static function getAllPossiblePathsFromPredecesArray(Vertex $startVertex, Vertex $endVertex, array $predecesEdgesArray)
170			{
171			$edgesPaths = [];
172
173			if ($startVertex === $endVertex) {
174			return [];
175			}
176
177			$predecessorEdges = $predecesEdgesArray[$endVertex->getId()];
178
179			foreach ($predecessorEdges as $edge) {
180			if ($endVertex === $edge->getVerticesStart()->getVertexFirst()) {
181			$nextVertex = $edge->getVerticesTarget()->getVertexFirst();
182			} else {
183			$nextVertex = $edge->getVerticesStart()->getVertexFirst();
184			}
185
186			$edgesPaths2 = self::getAllPossiblePathsFromPredecesArray($startVertex, $nextVertex, $predecesEdgesArray);
187			if ($edgesPaths2) {
188			foreach ($edgesPaths2 as &$edges2) {
189			$edges2[] = $edge;
190			}
191			} else {
192			$edgesPaths2 = [[$edge]];
193			}
194
195			$edgesPaths = array_merge($edgesPaths, $edgesPaths2);
196			}
197
198			return $edgesPaths;
199			}
200			}
201

thecodingmachine / schema-analyzer

MultiDijkstra::getCheapestPathFromPredecesArray() A last analyzed 2020-08-01 21:35 UTC

Complexity

Size

Duplication

Importance

Available Fixes

Duplication Side-by-Side

Filter issues like

MultiDijkstra::getCheapestPathFromPredecesArray() A
last analyzed 2020-08-01 21:35 UTC