Traverse::createContextCollection() - Code Metrics - Inspection of "refactor" - Smoren/graph-tools-php - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — master ( 73c04c...2087f9 )

by Smoren

created 2022-09-01 16:31 UTC

Traverse::createContextCollection() A

↳ Parent: Traverse

Complexity

Conditions	2
Paths	2

Size

Total Lines	11
Code Lines	5

Duplication

Lines	0
Ratio	0 %

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
eloc	5
c	1
b	0
f	0
dl	0
loc	11
rs	10
cc	2
nc	2
nop	2

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

/**
 * Class for non-directional graph traversing
 * @author <[email protected]> Smoren
 */
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();
            $currentEdge = $currentContext->getEdge();

            if($filter->matchesHandleCondition($currentContext)) {
                $cmd = (yield $currentEdge => $currentContext);
                switch($cmd) {
                    case static::STOP_BRANCH:
                        yield $currentEdge => $currentContext;
                        continue 2;
                    case static::STOP_ALL:
                        return;
                }
            }

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

            $nextVertexes = $this->getNextVertexes($currentVertex, $filter->getPassCondition($currentContext));
            $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, $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
22			/**
23			* Class for non-directional graph traversing
24			* @author <[email protected]> Smoren
25			*/
26			class Traverse implements TraverseInterface
27			{
28			/**
29			* Stop branch command
30			*/
31			public const STOP_BRANCH = 1;
32			/**
33			* Stop all branches command
34			*/
35			public const STOP_ALL = 2;
36
37			/**
38			* Wide traverse mode
39			*/
40			public const MODE_WIDE = 1;
41			/**
42			* Deep traverse mode
43			*/
44			public const MODE_DEEP = 2;
45
46			/**
47			* @var GraphRepositoryInterface
48			*/
49			protected GraphRepositoryInterface $repository;
50
51			/**
52			* @param GraphRepositoryInterface $repository
53			*/
54			public function __construct(GraphRepositoryInterface $repository)
55			{
56			$this->repository = $repository;
57			}
58
59			/**
60			* @inheritDoc
61			* @return Generator<TraverseContextInterface>
62			*/
63			public function generate(
64			VertexInterface $start,
65			TraverseFilterInterface $filter,
66			int $traverseMode = self::MODE_WIDE
67			): Generator {
68			$branchContext = $this->createBranchContext(0, null, $start);
69			$globalPassedVertexesMap = [];
70			$context = $this->createContext($start, null, $branchContext, [], $globalPassedVertexesMap);
71			yield from $this->traverse($context, $filter, $traverseMode);
72			}
73
74			/**
75			* Graph traverse generator
76			* @param TraverseContextInterface $startContext traverse context of the first vertex
77			* @param TraverseFilterInterface $filter traverse filter
78			* @param int $traverseMode traverse mode (wide or deep)
79			* @return Generator<TraverseContextInterface>
80			*/
81			protected function traverse(
82			TraverseContextInterface $startContext,
83			TraverseFilterInterface $filter,
84			int $traverseMode
85			): Generator {
86			$lastBranchIndex = $startContext->getBranchContext()->getIndex();
87			$globalPassedVertexesMap = $startContext->getGlobalPassedVertexesMap();
88			$contexts = $this->createContextCollection($traverseMode, $startContext);
89
90			while(count($contexts)) {
91			/** @var TraverseContextInterface $currentContext */
92			$currentContext = $contexts->pop();
93			$currentVertex = $currentContext->getVertex();
94			$currentEdge = $currentContext->getEdge();
95
96			if($filter->matchesHandleCondition($currentContext)) {
97			$cmd = (yield $currentEdge => $currentContext);
98			switch($cmd) {
99			case static::STOP_BRANCH:
100			yield $currentEdge => $currentContext;
101			continue 2;
102			case static::STOP_ALL:
103			return;
104			}
105			}
106
107			$passedVertexesMap = $currentContext->getPassedVertexesMap();
108			$passedVertexesMap[$currentVertex->getId()] = $currentVertex;
109			$globalPassedVertexesMap[$currentVertex->getId()] = $currentVertex;
110
111			$nextVertexes = $this->getNextVertexes($currentVertex, $filter->getPassCondition($currentContext));
112			$i = 0;
113			foreach($nextVertexes as $edge => $vertex) {
114			$currentBranchContext = $currentContext->getBranchContext();
115			if(count($nextVertexes) > 1 && $i > 0) {
116			$nextBranchContext = $this->createBranchContext(
117			++$lastBranchIndex,
118			$currentBranchContext->getIndex(),
119			$currentVertex
120			);
121			} else {
122			$nextBranchContext = $currentBranchContext;
123			}
124
125			$contexts->push($this->createContext(
126			$vertex,
127			$edge,
128			$nextBranchContext,
129			$passedVertexesMap,
130			$globalPassedVertexesMap
131			));
132
133			++$i;
134			}
135			}
136			}
137
138			/**
139			* Returns traverse iterator for the next step of traversing
140			* @param VertexInterface $vertex vertex to traverse from
141			* @param FilterConditionInterface $condition pass condition
142			* @return TraverseStepIteratorInterface next vertexes iterator
143			*/
144			protected function getNextVertexes(
145			VertexInterface $vertex,
146			FilterConditionInterface $condition
147			): TraverseStepIteratorInterface {
148			return TraverseStepIterator::combine(
149			$this->repository->getNextVertexes($vertex, $condition),
150			$this->repository->getPrevVertexes($vertex, $condition)
151			);
152			}
153
154			/**
155			* Creates context collection
156			* @param int $traverseMode traverse mode
157			* @param TraverseContextInterface $startContext start context
158			* @return Queue<TraverseContextInterface>\|Stack<TraverseContextInterface>
159			*/
160			protected function createContextCollection(
161			int $traverseMode,
162			TraverseContextInterface $startContext
163			): Collection {
164			if($traverseMode === self::MODE_WIDE) {
165			$contexts = new Queue([$startContext]);
166			} else {
167			$contexts = new Stack([$startContext]);
168			}
169
170			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...
171			}
172
173			/**
174			* Creates new traverse context instance
175			* @param VertexInterface $vertex current vertex
176			* @param EdgeInterface\|null $edge current edge leading to current vertex
177			* @param TraverseBranchContextInterface $branchContext branch context
178			* @param array<VertexInterface> $passedVertexesMap map of passed vertexes in current branch
179			* @param array<VertexInterface> $globalPassedVertexesMap map of all the passed vertexes
180			* @return TraverseContextInterface traverse context
181			*/
182			protected function createContext(
183			VertexInterface $vertex,
184			?EdgeInterface $edge,
185			TraverseBranchContextInterface $branchContext,
186			array $passedVertexesMap,
187			array &$globalPassedVertexesMap
188			): TraverseContextInterface {
189			return new TraverseContext($vertex, $edge, $branchContext, $passedVertexesMap, $globalPassedVertexesMap);
190			}
191
192			/**
193			* Creates new branch context instance
194			* @param int $index branch index
195			* @param int\|null $parentIndex parent branch index
196			* @param VertexInterface $start vertex which started this branch
197			* @return TraverseBranchContextInterface new branch context
198			*/
199			protected function createBranchContext(
200			int $index,
201			?int $parentIndex,
202			VertexInterface $start
203			): TraverseBranchContextInterface {
204			return new TraverseBranchContext($index, $parentIndex, $start);
205			}
206			}
207

Smoren / graph-tools-php

Push — master ( 73c04c...2087f9 )

Traverse::createContextCollection() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like