DirectedCycle.dfs() - Code Metrics - chen0040/pyalgs - Measure and Improve Code Quality continuously with Scrutinizer

DirectedCycle.dfs() B
last analyzed 2017-05-26 05:56 UTC

↳ Parent: DirectedCycle

Complexity

Conditions

Size

Total Lines

Duplication

Lines	0
Ratio	0 %

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
cc	6
c	1
b	0
f	0
dl	0
loc	21
rs	7.8867

from pyalgs.data_structures.commons.stack import Stack
from pyalgs.data_structures.graphs.graph import DirectedEdgeWeightedGraph, Digraph


class DirectedCycle(object):

    marked = None
    onStack = None
    cycle = None
    edgeTo = None

    def __init__(self, G):
        if isinstance(G, DirectedEdgeWeightedGraph):
            G = G.to_digraph()

        if not isinstance(G, Digraph):
            raise ValueError('Graph must be unweighted digraph')

        vertex_count = G.vertex_count()
        self.marked = [False] * vertex_count
        self.onStack = [False] * vertex_count
        self.edgeTo = [-1] * vertex_count

        for v in range(vertex_count):
            if not self.marked[v]:
                self.dfs(G, v)

    def dfs(self, G, v):
        self.marked[v] = True
        self.onStack[v] = True

        for w in G.adj(v):
            if not self.marked[w]:
                self.edgeTo[w] = v
                self.dfs(G, w)
            elif self.cycle is not None:
                break
            elif self.onStack[w]:
                self.cycle = Stack.create()
                x = v
                while x != w:
                    self.cycle.push(x)
                    x = self.edgeTo[x]
                self.cycle.push(w)
                self.cycle.push(v)
                break

        self.onStack[v] = False

    def hasCycle(self):
        return self.cycle is not None

    def get_cycle(self):
        return self.cycle.iterate()


1			from pyalgs.data_structures.commons.stack import Stack
2			from pyalgs.data_structures.graphs.graph import DirectedEdgeWeightedGraph, Digraph
3
4
5			class DirectedCycle(object):
6
7			marked = None
8			onStack = None
9			cycle = None
10			edgeTo = None
11
12			def __init__(self, G):
13			if isinstance(G, DirectedEdgeWeightedGraph):
14			G = G.to_digraph()
15
16			if not isinstance(G, Digraph):
17			raise ValueError('Graph must be unweighted digraph')
18
19			vertex_count = G.vertex_count()
20			self.marked = [False] * vertex_count
21			self.onStack = [False] * vertex_count
22			self.edgeTo = [-1] * vertex_count
23
24			for v in range(vertex_count):
25			if not self.marked[v]:
26			self.dfs(G, v)
27
28			def dfs(self, G, v):
29			self.marked[v] = True
30			self.onStack[v] = True
31
32			for w in G.adj(v):
33			if not self.marked[w]:
34			self.edgeTo[w] = v
35			self.dfs(G, w)
36			elif self.cycle is not None:
37			break
38			elif self.onStack[w]:
39			self.cycle = Stack.create()
40			x = v
41			while x != w:
42			self.cycle.push(x)
43			x = self.edgeTo[x]
44			self.cycle.push(w)
45			self.cycle.push(v)
46			break
47
48			self.onStack[v] = False
49
50			def hasCycle(self):
51			return self.cycle is not None
52
53			def get_cycle(self):
54			return self.cycle.iterate()
55

chen0040 / pyalgs

DirectedCycle.dfs() B last analyzed 2017-05-26 05:56 UTC

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like

DirectedCycle.dfs() B
last analyzed 2017-05-26 05:56 UTC