CycleDetector::isCyclic() - Code Metrics - Inspection of "Feature/reports" - phpmetrics/PhpMetrics - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Pull Request — master (#301)

by personal

created 2017-09-13 16:16 UTC

CycleDetector::isCyclic() B

↳ Parent: CycleDetector

Complexity

Conditions	4
Paths	6

Size

Total Lines	23
Code Lines	12

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
cc	4
eloc	12
c	0
b	0
f	0
nc	6
nop	1
dl	0
loc	23
rs	8.7972

<?php

/*
 * (c) Jean-François Lépine <https://twitter.com/Halleck45>
 *
 * For the full copyright and license information, please view the LICENSE
 * file that was distributed with this source code.
 */

namespace Hal\Component\Tree\Operator;

use Hal\Component\Tree\Graph;
use Hal\Component\Tree\Node;

/**
 * Class CycleDetector
 * @package Hal\Component\Tree\Util
 * @see http://www.geeksforgeeks.org/detect-cycle-in-a-graph/
 */
class CycleDetector
{
    /**
     * Check if graph contains cycle
     *
     * Each node in cycle is flagged with the "cyclic" attribute
     *
     * @param Graph $graph
     * @return bool
     */
    public function isCyclic(Graph $graph)
    {
        // prepare stack
        $recursionStack = [];
        foreach ($graph->all() as $node) {
            $recursionStack[$node->getKey()] = false;
        }

        // start analysis
        $isCyclic = false;
        foreach ($graph->getEdges() as $edge) {
            if ($r = $this->detectCycle($edge->getFrom(), $recursionStack)) {
$myVar = 'Value';
$higher = false;

if (rand(1, 6) > 3) {
    $higher = true;
} else {
    $higher = false;
}
                $edge->cyclic = true;
                $isCyclic = true;
            }

            $recursionStack[$node->getKey()] = false;
foreach ($a as $b) {
}

// $b is defined here only if $a has elements, for example if $a is array()
// then $b would not be defined here. To avoid that, we recommend to set a
// default value for $b.


// Better
$b = 0; // or whatever default makes sense in your context
foreach ($a as $b) {
}

// $b is now guaranteed to be defined here.
        }

        $graph->resetVisits();

        return $isCyclic;
    }

    /**
     * @param Node $node
     * @param $recursionStack
     * @return bool
     */
    private function detectCycle(Node $node, &$recursionStack)
    {
        if (!$node->visited) {
            // mark the current node as visited and part of recursion stack
            $recursionStack[$node->getKey()] = true;
            $node->visited = true;

            // recur for all the vertices adjacent to this vertex
            foreach ($node->getEdges() as $edge) {
                if ($edge->getTo() === $node) {
                    continue;
                }

                if (!$edge->getTo()->visited && $this->detectCycle($edge->getTo(), $recursionStack)) {
                    $edge->cyclic = $edge->getTo()->cyclic = true;
                    return true;
                } elseif ($recursionStack[$edge->getTo()->getKey()]) {
                    $edge->cyclic = $edge->getTo()->cyclic = true;
                    return true;
                }
            }
        }
        // remove the vertex from recursion stack
        $recursionStack[$node->getKey()] = false;
        return false;
    }
}


1			<?php
2
3			/*
4			* (c) Jean-François Lépine <https://twitter.com/Halleck45>
5			*
6			* For the full copyright and license information, please view the LICENSE
7			* file that was distributed with this source code.
8			*/
9
10			namespace Hal\Component\Tree\Operator;
11
12			use Hal\Component\Tree\Graph;
13			use Hal\Component\Tree\Node;
14
15			/**
16			* Class CycleDetector
17			* @package Hal\Component\Tree\Util
18			* @see http://www.geeksforgeeks.org/detect-cycle-in-a-graph/
19			*/
20			class CycleDetector
21			{
22			/**
23			* Check if graph contains cycle
24			*
25			* Each node in cycle is flagged with the "cyclic" attribute
26			*
27			* @param Graph $graph
28			* @return bool
29			*/
30			public function isCyclic(Graph $graph)
31			{
32			// prepare stack
33			$recursionStack = [];
34			foreach ($graph->all() as $node) {
35			$recursionStack[$node->getKey()] = false;
36			}
37
38			// start analysis
39			$isCyclic = false;
40			foreach ($graph->getEdges() as $edge) {
41			if ($r = $this->detectCycle($edge->getFrom(), $recursionStack)) {
			0 ignored issues – show Unused Code introduced 2017-01-30 05:20 UTC by Report Bug Copy Issue Report `$r` is not used, you could remove the assignment. This check looks for variable assignements that are either overwritten by other assignments or where the variable is not used subsequently. $myVar = 'Value'; $higher = false; if (rand(1, 6) > 3) { $higher = true; } else { $higher = false; } Both the `$myVar` assignment in line 1 and the `$higher` assignment in line 2 are dead. The first because `$myVar` is never used and the second because `$higher` is always overwritten for every possible time line. Loading history...
42			$edge->cyclic = true;
43			$isCyclic = true;
44			}
45
46			$recursionStack[$node->getKey()] = false;
			0 ignored issues – show Bug introduced 2017-01-30 05:20 UTC by Report Bug Copy Issue Report The variable `$node` seems to be defined by a `foreach` iteration on line `34`. Are you sure the iterator is never empty, otherwise this variable is not defined? It seems like you are relying on a variable being defined by an iteration: foreach ($a as $b) { } // $b is defined here only if $a has elements, for example if $a is array() // then $b would not be defined here. To avoid that, we recommend to set a // default value for $b. // Better $b = 0; // or whatever default makes sense in your context foreach ($a as $b) { } // $b is now guaranteed to be defined here. Loading history...
47			}
48
49			$graph->resetVisits();
50
51			return $isCyclic;
52			}
53
54			/**
55			* @param Node $node
56			* @param $recursionStack
57			* @return bool
58			*/
59			private function detectCycle(Node $node, &$recursionStack)
60			{
61			if (!$node->visited) {
62			// mark the current node as visited and part of recursion stack
63			$recursionStack[$node->getKey()] = true;
64			$node->visited = true;
65
66			// recur for all the vertices adjacent to this vertex
67			foreach ($node->getEdges() as $edge) {
68			if ($edge->getTo() === $node) {
69			continue;
70			}
71
72			if (!$edge->getTo()->visited && $this->detectCycle($edge->getTo(), $recursionStack)) {
73			$edge->cyclic = $edge->getTo()->cyclic = true;
74			return true;
75			} elseif ($recursionStack[$edge->getTo()->getKey()]) {
76			$edge->cyclic = $edge->getTo()->cyclic = true;
77			return true;
78			}
79			}
80			}
81			// remove the vertex from recursion stack
82			$recursionStack[$node->getKey()] = false;
83			return false;
84			}
85			}
86

phpmetrics / PhpMetrics

Pull Request — master (#301)

CycleDetector::isCyclic() B

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like