maxflowproblem_ford_fulkerson.js

// 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)