Returns a mapping of vertices as path, if there is any from source to sink Otherwise, returns nil
(rGraph WeightedGraph, source int, sink int)
| 14 | // Returns a mapping of vertices as path, if there is any from source to sink |
| 15 | // Otherwise, returns nil |
| 16 | func FindPath(rGraph WeightedGraph, source int, sink int) map[int]int { |
| 17 | queue := make([]int, 0) |
| 18 | marked := make([]bool, len(rGraph)) |
| 19 | marked[source] = true |
| 20 | queue = append(queue, source) |
| 21 | parent := make(map[int]int) |
| 22 | |
| 23 | // BFS loop with saving the path found |
| 24 | for len(queue) > 0 { |
| 25 | v := queue[0] |
| 26 | queue = queue[1:] |
| 27 | for i := 0; i < len(rGraph[v]); i++ { |
| 28 | if !marked[i] && rGraph[v][i] > 0 { |
| 29 | parent[i] = v |
| 30 | // Terminate the BFS, if we reach to sink |
| 31 | if i == sink { |
| 32 | return parent |
| 33 | } |
| 34 | marked[i] = true |
| 35 | queue = append(queue, i) |
| 36 | } |
| 37 | } |
| 38 | } |
| 39 | // source and sink are not in the same connected component |
| 40 | return nil |
| 41 | } |
| 42 | |
| 43 | func EdmondKarp(graph WeightedGraph, source int, sink int) float64 { |
| 44 | // Check graph emptiness |