Mouf\Database\SchemaAnalyzer\MultiDijkstra::findShortestPaths()

Complexity

Conditions	16
Paths	26

Size

Total Lines

111

Duplication

Lines	0
Ratio	0 %

Importance

Changes

0

<?php
    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) {

The variable $currentCost does not seem to be defined for all execution paths leading up to this point.

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