15537876122

Committed 09 Jun 2025 03:10PM UTC coverage: 99.639%. Remained the same

Build # 15537876122

Build Type

push

github

Committed by

homersimpsons

Commit Message

:memo: Update README.md to target ^2.0 install

Run Details

276 of 277 relevant lines covered (99.64%)

40.9 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

100.0

/src/MultiDijkstra.php

<?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) {
                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
22	*/
23	public static function findShortestPaths(Vertex $startVertex, Vertex $endVertex)
24	{
25	$totalCostOfCheapestPathTo = [];	85✔
26	// start node distance
27	$totalCostOfCheapestPathTo[$startVertex->getId()] = 0;	85✔
28
29	$endVertexId = $endVertex->getId();	85✔
30
31	// just to get the cheapest vertex in the correct order
32	$cheapestVertex = new SplPriorityQueue();	85✔
33	$cheapestVertex->setExtractFlags(SplPriorityQueue::EXTR_BOTH);	85✔
34	$cheapestVertex->insert($startVertex, 0);	85✔
35
36	// predecessors
37	$predecesEdgeOfCheapestPathTo = [];	85✔
38
39	// mark vertices when their cheapest path has been found
40	$usedVertices = [$startVertex->getId() => true];	85✔
41
42	$isFirst = true;	85✔
43
44	// Repeat until all vertices have been marked
45	$totalCountOfVertices = count($startVertex->getGraph()->getVertices());	85✔
46	for ($i = 0; $i < $totalCountOfVertices; ++$i) {	85✔
47	$currentVertex = null;	85✔
48	$currentVertexId = null;	85✔
49	$isEmpty = false;	85✔
50	if ($isFirst) {	85✔
51	$currentVertex = $startVertex;	85✔
52	$currentCost = 0;	85✔
53	$currentVertexId = $currentVertex->getId();	85✔
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()) {	80✔
58	$isEmpty = true;	5✔
59	break;	5✔
60	}
61	// Get cheapest unmarked vertex
62	$cheapestResult = $cheapestVertex->extract();	80✔
63	$currentVertex = $cheapestResult['data'];	80✔
64	$currentCost = $cheapestResult['priority'];	80✔
65	$currentVertexId = $currentVertex->getId();	80✔
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]));	80✔
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) {	85✔
77	break;	5✔
78	}
79
80	if ($isFirst) {	85✔
81	$isFirst = false;	85✔
82	}
83
84	// mark this vertex
85	$usedVertices[$currentVertexId] = true;	85✔
86
87	if (isset($usedVertices[$endVertexId]) && $totalCostOfCheapestPathTo[$endVertexId] < -$currentCost) {	85✔
88	break;	25✔
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) {	85✔
93	$weight = $edge->getWeight();	85✔
94	if ($weight < 0) {	85✔
95	throw new UnexpectedValueException('Dijkstra not supported for negative weights - Consider using MooreBellmanFord');	5✔
96	}
97
98	$targetVertex = $edge->getVertexToFrom($currentVertex);	80✔
99	$targetVertexId = $targetVertex->getId();	80✔
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])) {	80✔
103	// calculate new cost to vertex
104	$newCostsToTargetVertex = $totalCostOfCheapestPathTo[$currentVertexId] + $weight;	80✔
105
106	if ((!isset($predecesEdgeOfCheapestPathTo[$targetVertexId]))	80✔
107	// is the new path cheaper?
108	\|\| $totalCostOfCheapestPathTo[$targetVertexId] > $newCostsToTargetVertex) {	80✔
109
110	// Not an update, just a new insert with lower cost
111	$cheapestVertex->insert($targetVertex, -$newCostsToTargetVertex);	80✔
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;	80✔
117	// update/set predecessor vertex from the new connection
118	$predecesEdgeOfCheapestPathTo[$targetVertexId] = [$edge];	80✔
119	} elseif ($totalCostOfCheapestPathTo[$targetVertexId] == $newCostsToTargetVertex) {	70✔
120	// Same length paths. We need to add the predecessor to the list of possible predecessors.
121	$predecesEdgeOfCheapestPathTo[$targetVertexId][] = $edge;	25✔
122	}
123	}
124	}
125	}
126
127	if (!isset($totalCostOfCheapestPathTo[$endVertexId])) {	80✔
128	throw new MultiDijkstraNoPathException("No path found between vertex '".$startVertex->getId()."' and vertex '".$endVertex->getId()."'");	5✔
129	}
130
131	// algorithm is done, return resulting edges
132	return $predecesEdgeOfCheapestPathTo;	75✔
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 = [];	65✔
143	$currentVertex = $endVertex;	65✔
144	while ($currentVertex !== $startVertex) {	65✔
145	$predecessorEdges = $predecesEdgesArray[$currentVertex->getId()];	65✔
146	if (count($predecessorEdges) > 1) {	65✔
147	throw new MultiDijkstraAmbiguityException("There are many possible shortest paths to link vertex '".$startVertex->getId()."' to '".$endVertex->getId()."'");	15✔
148	}
149	/** @var $edge \Fhaculty\Graph\Edge\Base */
150	$edge = $predecessorEdges[0];	50✔
151	$edges[] = $edge;	50✔
152	if ($currentVertex === $edge->getVerticesStart()->getVertexFirst()) {	50✔
153	$currentVertex = $edge->getVerticesTarget()->getVertexFirst();	25✔
154	} else {
155	$currentVertex = $edge->getVerticesStart()->getVertexFirst();	45✔
156	}
157	}
158
159	return array_reverse($edges);	50✔
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 = [];	20✔
172
173	if ($startVertex === $endVertex) {	20✔
174	return [];	20✔
175	}
176
177	$predecessorEdges = $predecesEdgesArray[$endVertex->getId()];	20✔
178
179	foreach ($predecessorEdges as $edge) {	20✔
180	if ($endVertex === $edge->getVerticesStart()->getVertexFirst()) {	20✔
181	$nextVertex = $edge->getVerticesTarget()->getVertexFirst();	15✔
182	} else {
183	$nextVertex = $edge->getVerticesStart()->getVertexFirst();	20✔
184	}
185
186	$edgesPaths2 = self::getAllPossiblePathsFromPredecesArray($startVertex, $nextVertex, $predecesEdgesArray);	20✔
187	if ($edgesPaths2) {	20✔
188	foreach ($edgesPaths2 as &$edges2) {	10✔
189	$edges2[] = $edge;	10✔
190	}
191	} else {
192	$edgesPaths2 = [[$edge]];	20✔
193	}
194
195	$edgesPaths = array_merge($edgesPaths, $edgesPaths2);	20✔
196	}
197
198	return $edgesPaths;	20✔
199	}
200	}

thecodingmachine / schema-analyzer / 15537876122

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous