Created
October 1, 2022 15:35
-
-
Save tonicanada/11a669b7a314de0f154c3cfea2fa3b33 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Ford-Fulkerson algorithm implementation to solve Max Network Flow | |
// capacitiesGraph graph network | |
// https://graphonline.ru/en/?graph=lfhEQWkIEqiJCKvH | |
const capacitiesGraph = [ | |
[0, 18, 0, 15, 0, 0], | |
[0, 0, 9, 2, 10, 0], | |
[0, 0, 0, 0, 0, 13], | |
[0, 0, 0, 0, 3, 0], | |
[0, 0, 5, 0, 0, 12], | |
[0, 0, 0, 0, 0, 0], | |
] | |
// Function that finds possible path from node to other node using DFS traversal | |
const findPossiblePath = (adjMatrix, startVertex, endVertex) => { | |
const visited = new Array(adjMatrix.length).fill(false) | |
visited[startVertex] = true | |
const foundPathsArray = [] | |
const currentPath = [] | |
const visitedPaths = {} | |
const dfs = (adjMatrix, currentVertex, visited, visitedPaths, foundPathsArray, currentPath) => { | |
// Recursion stops if one path is found | |
if (foundPathsArray.length > 0) { | |
return | |
} | |
currentPath.push(currentVertex) | |
// If startVertex is equal to endVertex (and they are not the same), means path is found, then we add it to the array | |
if (currentPath.length > 1) { | |
if (currentPath[currentPath.length - 1] === endVertex) { | |
foundPathsArray.push([...currentPath]) | |
} | |
} | |
// Add currentPath to the visitedPaths | |
for (let i = 0; i < adjMatrix.length; i++) { | |
if (adjMatrix[currentVertex][i] > 0) { | |
if (!visited[i] && !visitedPaths[currentPath.join("-")]) { | |
visited[i] = true | |
dfs(adjMatrix, i, [...visited], visitedPaths, foundPathsArray, currentPath) | |
visitedPaths[currentPath.join("-")] = true | |
currentPath.pop() | |
visited[currentPath.length - 1] = false | |
} | |
} | |
} | |
} | |
dfs(adjMatrix, startVertex, visited, visitedPaths, foundPathsArray, currentPath) | |
return foundPathsArray[0] | |
} | |
const getBottleneck = (path, residualNetwork) => { | |
const capacitiesArray = [] | |
for (let i = 0; i < path.length - 1; i++) { | |
let start = path[i] | |
let next = path[i + 1] | |
capacitiesArray.push(residualNetwork[start][next]) | |
} | |
const bottleneck = Math.min(...capacitiesArray) | |
return bottleneck | |
} | |
const updateFlowNetwork = (path, bottleneck, flowNetwork, capacitiesGraph) => { | |
for (let i = 0; i < path.length - 1; i++) { | |
let start = path[i] | |
let end = path[i + 1] | |
if (capacitiesGraph[start][end] > 0) { | |
flowNetwork[start][end] += bottleneck | |
} else { | |
flowNetwork[end][start] -= bottleneck | |
} | |
} | |
} | |
const updateResidualNetwork = (residualNetwork, flowNetwork, capacitiesGraph) => { | |
const n = residualNetwork.length | |
for (let i = 0; i < n; i++) { | |
for (let j = 0; j < n; j++) { | |
residualNetwork[i][j] = flowNetwork[j][i] | |
if (residualNetwork[i][j] === 0) { | |
residualNetwork[i][j] = capacitiesGraph[i][j] - flowNetwork[i][j] | |
} | |
} | |
} | |
} | |
const getMaxFlowNetwork = (capacitiesGraph) => { | |
const n = capacitiesGraph.length | |
let flowNetwork = Array(n).fill().map(() => Array(n).fill(0)); | |
let residualNetwork = Array(n).fill().map(() => Array(n).fill(0)); | |
for (let i = 0; i < n; i++) { | |
for (let j = 0; j < n; j++) { | |
residualNetwork[i][j] = capacitiesGraph[i][j] | |
} | |
} | |
let path = findPossiblePath(residualNetwork, 0, n - 1) | |
let i = 0 | |
console.log("i", i) | |
console.log("FLOWNETWORK", flowNetwork) | |
console.log("RESIDUAL", residualNetwork) | |
console.log("PATH", path) | |
while (path) { | |
i++ | |
let bottleneck = getBottleneck(path, residualNetwork) | |
console.log("bottleneck", bottleneck) | |
updateFlowNetwork(path, bottleneck, flowNetwork, capacitiesGraph) | |
updateResidualNetwork(residualNetwork, flowNetwork, capacitiesGraph) | |
path = findPossiblePath(residualNetwork, 0, n - 1) | |
console.log("i", i) | |
console.log("FLOWNETWORK", flowNetwork) | |
console.log("RESIDUAL", residualNetwork) | |
console.log("PATH", path) | |
} | |
let solution = 0 | |
for (let i = 0; i < n; i++) { | |
solution += flowNetwork[0][i] | |
} | |
return solution | |
} | |
const maxFlow = getMaxFlowNetwork(capacitiesGraph) | |
console.log(maxFlow) | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment