Skip to content

Instantly share code, notes, and snippets.

@tonicanada
Created October 1, 2022 15:35
Show Gist options
  • Save tonicanada/11a669b7a314de0f154c3cfea2fa3b33 to your computer and use it in GitHub Desktop.
Save tonicanada/11a669b7a314de0f154c3cfea2fa3b33 to your computer and use it in GitHub Desktop.
// 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