FilesExpand file tree

 master

/

maximum_flow_dfs.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

84 lines (64 loc) · 1.95 KB

 master

/

maximum_flow_dfs.py

Copy path

Top

File metadata and controls

• Code
• Blame

84 lines (64 loc) · 1.95 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

"""

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

23

"""

import copy

import math

def maximum_flow_dfs(adjacency_matrix):

#initial setting

new_array = copy.deepcopy(adjacency_matrix)

total = 0

while(1):

#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