BreadthFirstSearch.hasPathTo() - Code Metrics - Inspection of "Update docs for the breadth first graph search alg..." - chen0040/pyalgs - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( 72947f...dc545e )

by Xianshun

created 2017-04-26 10:53 UTC

BreadthFirstSearch.hasPathTo() A

↳ Parent: BreadthFirstSearch

Complexity

Conditions

Size

Total Lines

Duplication

Lines	0
Ratio	0 %

Importance

Changes	1
Bugs	0	Features	0

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

from abc import ABCMeta, abstractmethod

from pyalgs.data_structures.commons.queue import Queue
from pyalgs.data_structures.commons.stack import Stack


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

chen0040 / pyalgs

Push — master ( 72947f...dc545e )

BreadthFirstSearch.hasPathTo() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like