18747003414

Committed 23 Oct 2025 11:33AM UTC coverage: 98.413% (-0.1%) from 98.519%

Build # 18747003414

Build Type

push

github

Committed by

web-flow

Commit Message

feat: add Graph component with directed and undirected graph support (#547)

Add comprehensive Graph component for with immutable graph data
structures and algorithms for working with directed and undirected graphs.

Features:
- DirectedGraph and UndirectedGraph classes with adjacency list representation
- Pure constructor functions: directed() and undirected()
- Weighted and unweighted edge support
- Graph operations: add_node(), add_edge(), nodes(), neighbors()
- Traversal algorithms: BFS (breadth-first search), DFS (depth-first search)
- Path algorithms: shortest_path(), shortest_path_by(), has_path()
- Topological algorithms: topological_sort(), has_cycle()

Signed-off-by: azjezz <azjezz@protonmail.com>

Run Details

275 of 286 new or added lines in 17 files covered. (96.15%)

6262 of 6363 relevant lines covered (98.41%)

48.59 hits per line

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

95.0

/src/Psl/Graph/dfs.php

<?php

declare(strict_types=1);

namespace Psl\Graph;

use Psl\DataStructure\Stack;

use function Psl\Graph\Internal\get_node_key;

/**
 * Performs depth-first search starting from a given node.
 *
 * Returns nodes in the order they are visited.
 *
 * Example:
 *
 *      $graph = Graph\directed();
 *      $graph = Graph\add_edge($graph, 'A', 'B');
 *      $graph = Graph\add_edge($graph, 'A', 'C');
 *      $graph = Graph\add_edge($graph, 'B', 'D');
 *      Graph\dfs($graph, 'A') // ['A', 'B', 'D', 'C']
 *
 * @template TNode
 * @template TWeight
 *
 * @param DirectedGraph<TNode, TWeight>|UndirectedGraph<TNode, TWeight> $graph
 * @param TNode $start
 *
 * @return list<TNode>
 *
 * @pure
 */
function dfs(DirectedGraph|UndirectedGraph $graph, mixed $start): array
{
    if (!$graph->hasNode($start)) {
        return [];
    }

    $visited = [];
    $result = [];
    /**
     * @var Stack<TNode> $stack
     * @mago-expect analysis:redundant-docblock-type
     */
    $stack = new Stack();
    $stack->push($start);

    while ($stack->count() !== 0) {
        $node = $stack->pop();
        $key = get_node_key($node);

        if (isset($visited[$key])) {
            continue;
        }

        $visited[$key] = true;
        $result[] = $node;

        // Push neighbors in reverse order to maintain left-to-right traversal
        $neighborsList = neighbors($graph, $node);
        for ($i = count($neighborsList) - 1; $i >= 0; $i--) {
            // @mago-expect analysis:mismatched-array-index - we know that $i is always an int within bounds
            $neighbor = $neighborsList[$i];
            $neighborKey = get_node_key($neighbor);
            if (!isset($visited[$neighborKey])) {
                $stack->push($neighbor);
            }
        }
    }

    return $result;
}

1	<?php
2
3	declare(strict_types=1);
4
5	namespace Psl\Graph;
6
7	use Psl\DataStructure\Stack;
8
9	use function Psl\Graph\Internal\get_node_key;
10
11	/**
12	* Performs depth-first search starting from a given node.
13	*
14	* Returns nodes in the order they are visited.
15	*
16	* Example:
17	*
18	* $graph = Graph\directed();
19	* $graph = Graph\add_edge($graph, 'A', 'B');
20	* $graph = Graph\add_edge($graph, 'A', 'C');
21	* $graph = Graph\add_edge($graph, 'B', 'D');
22	* Graph\dfs($graph, 'A') // ['A', 'B', 'D', 'C']
23	*
24	* @template TNode
25	* @template TWeight
26	*
27	* @param DirectedGraph<TNode, TWeight>\|UndirectedGraph<TNode, TWeight> $graph
28	* @param TNode $start
29	*
30	* @return list<TNode>
31	*
32	* @pure
33	*/
34	function dfs(DirectedGraph\|UndirectedGraph $graph, mixed $start): array
35	{
36	if (!$graph->hasNode($start)) {	5✔
37	return [];	1✔
38	}
39
40	$visited = [];	4✔
41	$result = [];	4✔
42	/**
43	* @var Stack<TNode> $stack
44	* @mago-expect analysis:redundant-docblock-type
45	*/
46	$stack = new Stack();	4✔
47	$stack->push($start);	4✔
48
49	while ($stack->count() !== 0) {	4✔
50	$node = $stack->pop();	4✔
51	$key = get_node_key($node);	4✔
52
53	if (isset($visited[$key])) {	4✔
NEW 54	continue;	×
55	}
56
57	$visited[$key] = true;	4✔
58	$result[] = $node;	4✔
59
60	// Push neighbors in reverse order to maintain left-to-right traversal
61	$neighborsList = neighbors($graph, $node);	4✔
62	for ($i = count($neighborsList) - 1; $i >= 0; $i--) {	4✔
63	// @mago-expect analysis:mismatched-array-index - we know that $i is always an int within bounds
64	$neighbor = $neighborsList[$i];	3✔
65	$neighborKey = get_node_key($neighbor);	3✔
66	if (!isset($visited[$neighborKey])) {	3✔
67	$stack->push($neighbor);	3✔
68	}
69	}
70	}
71
72	return $result;	4✔
73	}

azjezz / psl / 18747003414

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