Traverse::generate() - Code Metrics - Smoren/graph-tools-php - Measure and Improve Code Quality continuously with Scrutinizer

Traverse::generate() A
last analyzed 2023-08-25 10:12 UTC

↳ Parent: Traverse

Complexity

Conditions	1
Paths	1

Size

Total Lines	9
Code Lines	4

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
eloc	4
dl	0
loc	9
rs	10
c	0
b	0
f	0
cc	1
nc	1
nop	3

<?php

namespace Smoren\GraphTools\Traverse;

use Ds\Collection;
use Ds\Queue;
use Ds\Stack;
use Generator;
use Smoren\GraphTools\Traverse\Interfaces\TraverseInterface;
use Smoren\GraphTools\Conditions\Interfaces\FilterConditionInterface;
use Smoren\GraphTools\Filters\Interfaces\TraverseFilterInterface;
use Smoren\GraphTools\Models\Interfaces\EdgeInterface;
use Smoren\GraphTools\Models\Interfaces\VertexInterface;
use Smoren\GraphTools\Store\Interfaces\GraphRepositoryInterface;
use Smoren\GraphTools\Structs\Interfaces\TraverseBranchContextInterface;
use Smoren\GraphTools\Structs\Interfaces\TraverseContextInterface;
use Smoren\GraphTools\Structs\Interfaces\TraverseStepIteratorInterface;
use Smoren\GraphTools\Structs\TraverseBranchContext;
use Smoren\GraphTools\Structs\TraverseContext;
use Smoren\GraphTools\Structs\TraverseStepIterator;
use Smoren\GraphTools\Structs\TraverseStepItem;

/**
 * Class for non-directional graph traversing
 * @author Smoren <[email protected]>
 */
class Traverse implements TraverseInterface
{
    /**
     * Stop branch command
     */
    public const STOP_BRANCH = 1;
    /**
     * Stop all branches command
     */
    public const STOP_ALL = 2;

    /**
     * Wide traverse mode
     */
    public const MODE_WIDE = 1;
    /**
     * Deep traverse mode
     */
    public const MODE_DEEP = 2;

    /**
     * @var GraphRepositoryInterface
     */
    protected GraphRepositoryInterface $repository;

    /**
     * @param GraphRepositoryInterface $repository
     */
    public function __construct(GraphRepositoryInterface $repository)
    {
        $this->repository = $repository;
    }

    /**
     * @inheritDoc
     * @return Generator<TraverseContextInterface>
     */
    public function generate(
        VertexInterface $start,
        TraverseFilterInterface $filter,
        int $traverseMode = self::MODE_WIDE
    ): Generator {
        $branchContext = $this->createBranchContext(0, null, $start);
        $globalPassedVertexesMap = [];
        $context = $this->createContext($start, null, $branchContext, [], $globalPassedVertexesMap);
        yield from $this->traverse($context, $filter, $traverseMode);
    }

    /**
     * Graph traverse generator
     * @param TraverseContextInterface $startContext traverse context of the first vertex
     * @param TraverseFilterInterface $filter traverse filter
     * @param int $traverseMode traverse mode (wide or deep)
     * @return Generator<TraverseContextInterface>
     */
    protected function traverse(
        TraverseContextInterface $startContext,
        TraverseFilterInterface $filter,
        int $traverseMode
    ): Generator {
        $lastBranchIndex = $startContext->getBranchContext()->getIndex();
        $globalPassedVertexesMap = $startContext->getGlobalPassedVertexesMap();
        $contexts = $this->createContextCollection($traverseMode, $startContext);

        while(count($contexts)) {
            /** @var TraverseContextInterface $currentContext */
            $currentContext = $contexts->pop();
            $currentVertex = $currentContext->getVertex();

            $customPassCondition = null;
            $nextVertex = null;
            if($filter->matchesHandleCondition($currentContext)) {
                $cmd = (yield $currentContext);

                if($cmd instanceof FilterConditionInterface) {
                    $customPassCondition = $cmd;
                    yield $currentContext;
                } elseif($cmd instanceof VertexInterface) {
                    $nextVertex = $cmd;
                    yield $currentContext;
                } else {
                    switch($cmd) {
                        case static::STOP_BRANCH:
                            yield $currentContext;
                            continue 2;
                        case static::STOP_ALL:
                            return;
                    }
                }
            }

            $passedVertexesMap = $currentContext->getPassedVertexesMap();
            $passedVertexesMap[$currentVertex->getId()] = $currentVertex;
            $globalPassedVertexesMap[$currentVertex->getId()] = $currentVertex;

            if ($nextVertex !== null) {
                $nextVertexes = new TraverseStepIterator([new TraverseStepItem(null, $nextVertex)]);
            } else {
                $customPassCondition = $customPassCondition ?? $filter->getPassCondition($currentContext);
                $nextVertexes = $this->getNextVertexes($currentVertex, $customPassCondition);
            }

            $i = 0;
            foreach($nextVertexes as $edge => $vertex) {
                $currentBranchContext = $currentContext->getBranchContext();
                if(count($nextVertexes) > 1 && $i > 0) {
                    $nextBranchContext = $this->createBranchContext(
                        ++$lastBranchIndex,
                        $currentBranchContext->getIndex(),
                        $currentVertex
                    );
                } else {
                    $nextBranchContext = $currentBranchContext;
                }

                $contexts->push($this->createContext(
                    $vertex,
                    $edge,
                    $nextBranchContext,
                    $passedVertexesMap,
                    $globalPassedVertexesMap
                ));

                ++$i;
            }
        }
    }

    /**
     * Returns traverse iterator for the next step of traversing
     * @param VertexInterface $vertex vertex to traverse from
     * @param FilterConditionInterface $condition pass condition
     * @return TraverseStepIteratorInterface next vertexes iterator
     */
    protected function getNextVertexes(
        VertexInterface $vertex,
        FilterConditionInterface $condition
    ): TraverseStepIteratorInterface {
        return TraverseStepIterator::combine(
            $this->repository->getNextVertexes($vertex, $condition),
            $this->repository->getPrevVertexes($vertex, $condition)
        );
    }

    /**
     * Creates context collection
     * @param int $traverseMode traverse mode
     * @param TraverseContextInterface $startContext start context
     * @return Queue<TraverseContextInterface>|Stack<TraverseContextInterface>
     */
    protected function createContextCollection(
        int $traverseMode,
        TraverseContextInterface $startContext
    ): Collection {
        if($traverseMode === self::MODE_WIDE) {
            $contexts = new Queue([$startContext]);
        } else {
            $contexts = new Stack([$startContext]);
        }

        return $contexts;

    }

    /**
     * Creates new traverse context instance
     * @param VertexInterface $vertex current vertex
     * @param EdgeInterface|null $edge current edge leading to current vertex
     * @param TraverseBranchContextInterface $branchContext branch context
     * @param array<VertexInterface> $passedVertexesMap map of passed vertexes in current branch
     * @param array<VertexInterface> $globalPassedVertexesMap map of all the passed vertexes
     * @return TraverseContextInterface traverse context
     */
    protected function createContext(
        VertexInterface $vertex,
        ?EdgeInterface $edge,
        TraverseBranchContextInterface $branchContext,
        array $passedVertexesMap,
        array &$globalPassedVertexesMap
    ): TraverseContextInterface {
        return new TraverseContext(
            $vertex,
            $edge,
            $this->repository,
            $branchContext,
            $passedVertexesMap,
            $globalPassedVertexesMap
        );
    }

    /**
     * Creates new branch context instance
     * @param int $index branch index
     * @param int|null $parentIndex parent branch index
     * @param VertexInterface $start vertex which started this branch
     * @return TraverseBranchContextInterface new branch context
     */
    protected function createBranchContext(
        int $index,
        ?int $parentIndex,
        VertexInterface $start
    ): TraverseBranchContextInterface {
        return new TraverseBranchContext($index, $parentIndex, $start);
    }
}


1			<?php
2
3			namespace Smoren\GraphTools\Traverse;
4
5			use Ds\Collection;
6			use Ds\Queue;
7			use Ds\Stack;
8			use Generator;
9			use Smoren\GraphTools\Traverse\Interfaces\TraverseInterface;
10			use Smoren\GraphTools\Conditions\Interfaces\FilterConditionInterface;
11			use Smoren\GraphTools\Filters\Interfaces\TraverseFilterInterface;
12			use Smoren\GraphTools\Models\Interfaces\EdgeInterface;
13			use Smoren\GraphTools\Models\Interfaces\VertexInterface;
14			use Smoren\GraphTools\Store\Interfaces\GraphRepositoryInterface;
15			use Smoren\GraphTools\Structs\Interfaces\TraverseBranchContextInterface;
16			use Smoren\GraphTools\Structs\Interfaces\TraverseContextInterface;
17			use Smoren\GraphTools\Structs\Interfaces\TraverseStepIteratorInterface;
18			use Smoren\GraphTools\Structs\TraverseBranchContext;
19			use Smoren\GraphTools\Structs\TraverseContext;
20			use Smoren\GraphTools\Structs\TraverseStepIterator;
21			use Smoren\GraphTools\Structs\TraverseStepItem;
22
23			/**
24			* Class for non-directional graph traversing
25			* @author Smoren <[email protected]>
26			*/
27			class Traverse implements TraverseInterface
28			{
29			/**
30			* Stop branch command
31			*/
32			public const STOP_BRANCH = 1;
33			/**
34			* Stop all branches command
35			*/
36			public const STOP_ALL = 2;
37
38			/**
39			* Wide traverse mode
40			*/
41			public const MODE_WIDE = 1;
42			/**
43			* Deep traverse mode
44			*/
45			public const MODE_DEEP = 2;
46
47			/**
48			* @var GraphRepositoryInterface
49			*/
50			protected GraphRepositoryInterface $repository;
51
52			/**
53			* @param GraphRepositoryInterface $repository
54			*/
55			public function __construct(GraphRepositoryInterface $repository)
56			{
57			$this->repository = $repository;
58			}
59
60			/**
61			* @inheritDoc
62			* @return Generator<TraverseContextInterface>
63			*/
64			public function generate(
65			VertexInterface $start,
66			TraverseFilterInterface $filter,
67			int $traverseMode = self::MODE_WIDE
68			): Generator {
69			$branchContext = $this->createBranchContext(0, null, $start);
70			$globalPassedVertexesMap = [];
71			$context = $this->createContext($start, null, $branchContext, [], $globalPassedVertexesMap);
72			yield from $this->traverse($context, $filter, $traverseMode);
73			}
74
75			/**
76			* Graph traverse generator
77			* @param TraverseContextInterface $startContext traverse context of the first vertex
78			* @param TraverseFilterInterface $filter traverse filter
79			* @param int $traverseMode traverse mode (wide or deep)
80			* @return Generator<TraverseContextInterface>
81			*/
82			protected function traverse(
83			TraverseContextInterface $startContext,
84			TraverseFilterInterface $filter,
85			int $traverseMode
86			): Generator {
87			$lastBranchIndex = $startContext->getBranchContext()->getIndex();
88			$globalPassedVertexesMap = $startContext->getGlobalPassedVertexesMap();
89			$contexts = $this->createContextCollection($traverseMode, $startContext);
90
91			while(count($contexts)) {
92			/** @var TraverseContextInterface $currentContext */
93			$currentContext = $contexts->pop();
94			$currentVertex = $currentContext->getVertex();
95
96			$customPassCondition = null;
97			$nextVertex = null;
98			if($filter->matchesHandleCondition($currentContext)) {
99			$cmd = (yield $currentContext);
100
101			if($cmd instanceof FilterConditionInterface) {
102			$customPassCondition = $cmd;
103			yield $currentContext;
104			} elseif($cmd instanceof VertexInterface) {
105			$nextVertex = $cmd;
106			yield $currentContext;
107			} else {
108			switch($cmd) {
109			case static::STOP_BRANCH:
110			yield $currentContext;
111			continue 2;
112			case static::STOP_ALL:
113			return;
114			}
115			}
116			}
117
118			$passedVertexesMap = $currentContext->getPassedVertexesMap();
119			$passedVertexesMap[$currentVertex->getId()] = $currentVertex;
120			$globalPassedVertexesMap[$currentVertex->getId()] = $currentVertex;
121
122			if ($nextVertex !== null) {
123			$nextVertexes = new TraverseStepIterator([new TraverseStepItem(null, $nextVertex)]);
124			} else {
125			$customPassCondition = $customPassCondition ?? $filter->getPassCondition($currentContext);
126			$nextVertexes = $this->getNextVertexes($currentVertex, $customPassCondition);
127			}
128
129			$i = 0;
130			foreach($nextVertexes as $edge => $vertex) {
131			$currentBranchContext = $currentContext->getBranchContext();
132			if(count($nextVertexes) > 1 && $i > 0) {
133			$nextBranchContext = $this->createBranchContext(
134			++$lastBranchIndex,
135			$currentBranchContext->getIndex(),
136			$currentVertex
137			);
138			} else {
139			$nextBranchContext = $currentBranchContext;
140			}
141
142			$contexts->push($this->createContext(
143			$vertex,
144			$edge,
145			$nextBranchContext,
146			$passedVertexesMap,
147			$globalPassedVertexesMap
148			));
149
150			++$i;
151			}
152			}
153			}
154
155			/**
156			* Returns traverse iterator for the next step of traversing
157			* @param VertexInterface $vertex vertex to traverse from
158			* @param FilterConditionInterface $condition pass condition
159			* @return TraverseStepIteratorInterface next vertexes iterator
160			*/
161			protected function getNextVertexes(
162			VertexInterface $vertex,
163			FilterConditionInterface $condition
164			): TraverseStepIteratorInterface {
165			return TraverseStepIterator::combine(
166			$this->repository->getNextVertexes($vertex, $condition),
167			$this->repository->getPrevVertexes($vertex, $condition)
168			);
169			}
170
171			/**
172			* Creates context collection
173			* @param int $traverseMode traverse mode
174			* @param TraverseContextInterface $startContext start context
175			* @return Queue<TraverseContextInterface>\|Stack<TraverseContextInterface>
176			*/
177			protected function createContextCollection(
178			int $traverseMode,
179			TraverseContextInterface $startContext
180			): Collection {
181			if($traverseMode === self::MODE_WIDE) {
182			$contexts = new Queue([$startContext]);
183			} else {
184			$contexts = new Stack([$startContext]);
185			}
186
187			return $contexts;
			0 ignored issues – show Bug Best Practice introduced 2022-09-01 16:33 UTC by Report Bug Copy Issue Report The expression `return $contexts` also could return the type `Ds\Stack` which is incompatible with the documented return type `Ds\Queue`. Loading history...
188			}
189
190			/**
191			* Creates new traverse context instance
192			* @param VertexInterface $vertex current vertex
193			* @param EdgeInterface\|null $edge current edge leading to current vertex
194			* @param TraverseBranchContextInterface $branchContext branch context
195			* @param array<VertexInterface> $passedVertexesMap map of passed vertexes in current branch
196			* @param array<VertexInterface> $globalPassedVertexesMap map of all the passed vertexes
197			* @return TraverseContextInterface traverse context
198			*/
199			protected function createContext(
200			VertexInterface $vertex,
201			?EdgeInterface $edge,
202			TraverseBranchContextInterface $branchContext,
203			array $passedVertexesMap,
204			array &$globalPassedVertexesMap
205			): TraverseContextInterface {
206			return new TraverseContext(
207			$vertex,
208			$edge,
209			$this->repository,
210			$branchContext,
211			$passedVertexesMap,
212			$globalPassedVertexesMap
213			);
214			}
215
216			/**
217			* Creates new branch context instance
218			* @param int $index branch index
219			* @param int\|null $parentIndex parent branch index
220			* @param VertexInterface $start vertex which started this branch
221			* @return TraverseBranchContextInterface new branch context
222			*/
223			protected function createBranchContext(
224			int $index,
225			?int $parentIndex,
226			VertexInterface $start
227			): TraverseBranchContextInterface {
228			return new TraverseBranchContext($index, $parentIndex, $start);
229			}
230			}
231

Smoren / graph-tools-php

Traverse::generate() A last analyzed 2023-08-25 10:12 UTC

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like

Traverse::generate() A
last analyzed 2023-08-25 10:12 UTC