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

FordFulkersonMaxFlow.has_augmenting_path() B
last analyzed 2017-05-26 05:56 UTC

↳ Parent: FordFulkersonMaxFlow

Complexity

Conditions

Size

Total Lines

Duplication

Lines	0
Ratio	0 %

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
cc	5
c	1
b	0
f	0
dl	0
loc	21
rs	8.439

from pyalgs.data_structures.commons.queue import Queue


class FordFulkersonMaxFlow(object):
    edgeTo = None
    marked = None
    s = None
    t = None
    value = 0.0
    network = None

    def __init__(self, network, s, t):
        self.s = s
        self.t = t
        self.network = network
        self.value = 0.0
        while self.has_augmenting_path():
            x = self.t
            bottle = float('inf')
            while x != self.s:
                bottle = min(bottle, self.edgeTo[x].residual_capacity_to(x))
                x = self.edgeTo[x].other(x)

            x = self.t
            while x != self.s:
                self.edgeTo[x].add_residual_flow_to(x, bottle)
                x = self.edgeTo[x].other(x)

            self.value += bottle

    def has_augmenting_path(self):
        vertex_count = self.network.vertex_count()
        self.edgeTo = [None] * vertex_count
        self.marked = [False] * vertex_count

        queue = Queue.create()

        queue.enqueue(self.s)
        self.marked[self.s] = True

        while not queue.is_empty():
            x = queue.dequeue()
            for e in self.network.adj(x):
                w = e.other(x)
                if e.residual_capacity_to(w) > 0:
                    if not self.marked[w]:
                        self.marked[w] = True
                        self.edgeTo[w] = e
                        queue.enqueue(w)

        return self.marked[self.t]

    def max_flow_value(self):
        return self.value

    def min_cut(self):
        queue = Queue.create()
        for edge in self.network.edges():
            if edge.residual_capacity_to(edge.end()) == 0:
                queue.enqueue(edge)

        return queue.iterate()



1			from pyalgs.data_structures.commons.queue import Queue
2
3
4			class FordFulkersonMaxFlow(object):
5			edgeTo = None
6			marked = None
7			s = None
8			t = None
9			value = 0.0
10			network = None
11
12			def __init__(self, network, s, t):
13			self.s = s
14			self.t = t
15			self.network = network
16			self.value = 0.0
17			while self.has_augmenting_path():
18			x = self.t
19			bottle = float('inf')
20			while x != self.s:
21			bottle = min(bottle, self.edgeTo[x].residual_capacity_to(x))
22			x = self.edgeTo[x].other(x)
23
24			x = self.t
25			while x != self.s:
26			self.edgeTo[x].add_residual_flow_to(x, bottle)
27			x = self.edgeTo[x].other(x)
28
29			self.value += bottle
30
31			def has_augmenting_path(self):
32			vertex_count = self.network.vertex_count()
33			self.edgeTo = [None] * vertex_count
34			self.marked = [False] * vertex_count
35
36			queue = Queue.create()
37
38			queue.enqueue(self.s)
39			self.marked[self.s] = True
40
41			while not queue.is_empty():
42			x = queue.dequeue()
43			for e in self.network.adj(x):
44			w = e.other(x)
45			if e.residual_capacity_to(w) > 0:
46			if not self.marked[w]:
47			self.marked[w] = True
48			self.edgeTo[w] = e
49			queue.enqueue(w)
50
51			return self.marked[self.t]
52
53			def max_flow_value(self):
54			return self.value
55
56			def min_cut(self):
57			queue = Queue.create()
58			for edge in self.network.edges():
59			if edge.residual_capacity_to(edge.end()) == 0:
60			queue.enqueue(edge)
61
62			return queue.iterate()
63
64

chen0040 / pyalgs

FordFulkersonMaxFlow.has_augmenting_path() B last analyzed 2017-05-26 05:56 UTC

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like

FordFulkersonMaxFlow.has_augmenting_path() B
last analyzed 2017-05-26 05:56 UTC