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

Passed

Push — master ( 7d597c...1de5f6 )

by Smoren

created 2022-09-01 10:49 UTC

Traverse::traverse() B

↳ Parent: Traverse

Complexity

Conditions	9
Paths	18

Size

Total Lines	57
Code Lines	39

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
eloc	39
dl	0
loc	57
rs	7.7404
c	0
b	0
f	0
cc	9
nc	18
nop	3

How to fix Long Method

<?php

namespace Smoren\GraphTools\Traverse;

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();

        if($traverseMode === self::MODE_WIDE) {
            $contexts = new Queue([$startContext]);
        } else {
            $contexts = new Stack([$startContext]);
        }
        while(count($contexts)) {
            /** @var TraverseContextInterface $currentContext */
            $currentContext = $contexts->pop();
            $currentVertex = $currentContext->getVertex();
            $currentEdge = $currentContext->getEdge();

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

Smoren / graph-tools-php

Push — master ( 7d597c...1de5f6 )

Traverse::traverse() B

Complexity

Size

Duplication

Importance

How to fix Long Method

Long Method

Duplication Side-by-Side

Filter issues like