algorithms-python/algorithms/graph/maximum_flow_dfs.py at master · ivan1911/algorithms-python · GitHub

History

88 lines (67 loc) · 1.99 KB

Raw

"""

Given a n*n adjacency array.

it will give you a maximum flow.

This version use DFS to search path.

Assume the first is the source and the last is the sink.

Time complexity - O(Ef)

example

graph = [[0, 16, 13, 0, 0, 0],

[0, 0, 10, 12, 0, 0],

[0, 4, 0, 0, 14, 0],

[0, 0, 9, 0, 0, 20],

[0, 0, 0, 7, 0, 4],

[0, 0, 0, 0, 0, 0]]

answer should be

"""

import copy

import math

def maximum_flow_dfs(adjacency_matrix):

"""

Get the maximum flow through a graph using a depth first search

"""

#initial setting

new_array = copy.deepcopy(adjacency_matrix)

total = 0

while True:

#setting min to max_value

min = math.inf

#save visited nodes

visited = [0]*len(new_array)

#save parent nodes

path = [0]*len(new_array)

#initialize stack for DFS

stack = []

#initial setting

visited[0] = 1

stack.append(0)

#DFS to find path

while len(stack) > 0:

#pop from queue

src = stack.pop()

for k in range(len(new_array)):

#checking capacity and visit

if new_array[src][k] > 0 and visited[k] == 0:

#if not, put into queue and chage to visit and save path

visited[k] = 1

stack.append(k)

path[k] = src

#if there is no path from src to sink

if visited[len(new_array) - 1] == 0:

break

#initial setting

tmp = len(new_array) - 1

#Get minimum flow

while tmp != 0:

#find minimum flow

if min > new_array[path[tmp]][tmp]:

min = new_array[path[tmp]][tmp]

tmp = path[tmp]

#initial setting

tmp = len(new_array) - 1

#reduce capacity

while tmp != 0:

new_array[path[tmp]][tmp] = new_array[path[tmp]][tmp] - min

tmp = path[tmp]

total = total + min

return total

algorithms-python/algorithms/graph/maximum_flow_dfs.py at master · ivan1911/algorithms-python · GitHub

Expand file tree

Breadcrumbs

maximum_flow_dfs.py

Latest commit

History

Breadcrumbs

maximum_flow_dfs.py

File metadata and controls