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

DepthFirstSearch.init() A
last analyzed 2017-05-26 05:56 UTC

↳ Parent: DepthFirstSearch

Complexity

Conditions

Size

Total Lines

Duplication

Lines	0
Ratio	0 %

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
cc	2
dl	0
loc	8
rs	9.4285
c	1
b	0
f	0

from abc import ABCMeta, abstractmethod

from pyalgs.data_structures.commons.queue import Queue
from pyalgs.data_structures.commons.stack import Stack
from pyalgs.data_structures.graphs.graph import EdgeWeightedGraph


class Paths(object):
    __metaclass__ = ABCMeta

    @abstractmethod
    def pathTo(self, v):
        pass

    @abstractmethod
    def hasPathTo(self, v):
        pass


class DepthFirstSearch(Paths):
    marked = None
    edgesTo = None
    s = None

    def __init__(self, G, s):
        if isinstance(G, EdgeWeightedGraph):
            G = G.to_graph()
        self.s = s
        vertex_count = G.vertex_count()
        self.marked = [False] * vertex_count
        self.edgesTo = [-1] * vertex_count
        self.dfs(G, s)

    def dfs(self, G, v):
        self.marked[v] = True
        for w in G.adj(v):
            if not self.marked[w]:
                self.edgesTo[w] = v
                self.dfs(G, w)

    def hasPathTo(self, v):
        return self.marked[v]

    def pathTo(self, v):
        x = v
        path = Stack.create()
        while x != self.s:
            path.push(x)
            x = self.edgesTo[x]
        path.push(self.s)
        return path.iterate()


class BreadthFirstSearch(Paths):

    marked = None
    s = None
    edgeTo = None

    def __init__(self, G, s):
        if isinstance(G, EdgeWeightedGraph):
            G = G.to_graph()
        self.s = s
        vertex_count = G.vertex_count()
        self.marked = [False] * vertex_count
        self.edgeTo = [-1] * vertex_count

        queue = Queue.create()

        queue.enqueue(s)
        while not queue.is_empty():
            v = queue.dequeue()
            self.marked[v] = True
            for w in G.adj(v):
                if not self.marked[w]:
                    self.edgeTo[w] = v
                    queue.enqueue(w)

    def hasPathTo(self, v):
        return self.marked[v]

    def pathTo(self, v):
        x = v
        path = Stack.create()
        while x != self.s:
            path.push(x)
            x = self.edgeTo[x]
        path.push(self.s)
        return path.iterate()

1			from abc import ABCMeta, abstractmethod
2
3			from pyalgs.data_structures.commons.queue import Queue
4			from pyalgs.data_structures.commons.stack import Stack
5			from pyalgs.data_structures.graphs.graph import EdgeWeightedGraph
6
7
8			class Paths(object):
9			__metaclass__ = ABCMeta
10
11			@abstractmethod
12			def pathTo(self, v):
13			pass
14
15			@abstractmethod
16			def hasPathTo(self, v):
17			pass
18
19
20			class DepthFirstSearch(Paths):
21			marked = None
22			edgesTo = None
23			s = None
24
25			def __init__(self, G, s):
26			if isinstance(G, EdgeWeightedGraph):
27			G = G.to_graph()
28			self.s = s
29			vertex_count = G.vertex_count()
30			self.marked = [False] * vertex_count
31			self.edgesTo = [-1] * vertex_count
32			self.dfs(G, s)
33
34			def dfs(self, G, v):
35			self.marked[v] = True
36			for w in G.adj(v):
37			if not self.marked[w]:
38			self.edgesTo[w] = v
39			self.dfs(G, w)
40
41			def hasPathTo(self, v):
42			return self.marked[v]
43
44			def pathTo(self, v):
45			x = v
46			path = Stack.create()
47			while x != self.s:
48			path.push(x)
49			x = self.edgesTo[x]
50			path.push(self.s)
51			return path.iterate()
52
53
54			class BreadthFirstSearch(Paths):
55
56			marked = None
57			s = None
58			edgeTo = None
59
60			def __init__(self, G, s):
61			if isinstance(G, EdgeWeightedGraph):
62			G = G.to_graph()
63			self.s = s
64			vertex_count = G.vertex_count()
65			self.marked = [False] * vertex_count
66			self.edgeTo = [-1] * vertex_count
67
68			queue = Queue.create()
69
70			queue.enqueue(s)
71			while not queue.is_empty():
72			v = queue.dequeue()
73			self.marked[v] = True
74			for w in G.adj(v):
75			if not self.marked[w]:
76			self.edgeTo[w] = v
77			queue.enqueue(w)
78
79			def hasPathTo(self, v):
80			return self.marked[v]
81
82			def pathTo(self, v):
83			x = v
84			path = Stack.create()
85			while x != self.s:
86			path.push(x)
87			x = self.edgeTo[x]
88			path.push(self.s)
89			return path.iterate()

chen0040 / pyalgs

DepthFirstSearch.__init__() A last analyzed 2017-05-26 05:56 UTC

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like

DepthFirstSearch.init() A
last analyzed 2017-05-26 05:56 UTC