samples/2022/03/algorithms/maxflow_push_relabel.js

"use strict";

const fs = require('fs');
const {EOL} = require('os');
const eps = 1e-6;

function chooseActiveNodeForRelabel(c, e, h) {
	let n = h.length;
	for (let i = 0; i < n; i++) {
		if (e[i] <= 0) {
			continue;
		}

		for (let j = 0; j < n; j++) {
			if (c[i][j] <= 0) {
				// in edge E_f
				continue;
			}

			if (h[i] > h[j]) {
				break;
			}
		}

		return i;
	}

	return -1;
}

function chooseActiveNodeForPush(c, e, h) {
	let n = h.length;
	for (let i = 0; i < n; i++) { // what about replacing it with priority queues
		if (e[i] <= 0) {
			continue;
		}

		// we are looking for nodes if excess

		for (let j = 0; j < n; j++) { // what about replacing it with priority queues
			if (c[i][j] <= 0 || h[i] != h[j] + 1) {
				continue;
			}

			// c[i][j] > 0 && h[i] == h[j] + 1
			return [i, j];
		}
	}

	return [-1, -1];
}

function findMaximumFlow(graph) {
	let nodes = [];
	let m = {};
	for (let el of graph.nodes) {
		nodes.push(el);
	}

	for (let i = 0; i < nodes.length; i++) {
		m[nodes[i]] = i;
	}

	const n = nodes.length;
	let c = new Array(n);
	let oc = new Array(n);
	let f = new Array(n);
	let h = new Array(n);
	let e = new Array(n); // excess flow
	for (let i = 0; i < n; i++) {
		c[i]  = new Array(n); // residual capacity
		oc[i] = new Array(n); // residual capacity
		f[i]  = new Array(n); // flow
		h[i]  = 0; // node height
		e[i]  = 0; // node flow excess
	}

	h[m[graph.source]] = n;

	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
			f[i][j]  = 0;
			c[i][j]  = 0;
			oc[i][j] = 0;
		}
	}

	// init capacity

	for (let v in graph.edges) {
		for (let {node, weight} of graph.edges[v]) {
			c[m[v]][m[node]]  = weight;
			oc[m[v]][m[node]] = weight;
		}
	}

	for (let {node, weight} of graph.edges[graph.source]) {
		f[m[graph.source]][m[node]] = weight;
		e[m[node]] = weight;
		e[m[graph.source]] -= weight;
	}

	console.log('Capacity', c);
	console.log('Flow', f);
	console.log('Height', h);
	console.log('Excess', e);

	// try push
	// if not relabel
	// and repeat till it's possible

	// quite naive way to choose active node for push
	do {
		// push
		let [ci, cj] = chooseActiveNodeForPush(c, e, h);
		if (ci >= 0 && cj >= 0) {
			console.log(`Pushing (${ci},${cj})`);
			let flow = Math.min(e[ci], c[ci][cj]);
			if (oc[ci][cj] > 0) { // if ci, cj exists in e edges
				f[ci][cj] += flow;
			} else {
				f[cj][ci] -= flow;
			}

			e[ci] -= flow;
			e[cj] += flow;
		} else {
			// relabel
			let ri = chooseActiveNodeForRelabel(c, e, h);
			if (ri >= 0) {
				console.log(`Relabeling (${ri})`);
				let hMax = -Infinity;
				for (let i = 0; i < n; i++) {
					if (c[ri][i] <= 0) {
						continue;
					}
					hMax = Math.max(hMax, h[i]);
				}
				if (hMax <= 0) {
					continue;
				}
				h[ri] = hMax + 1;
				console.log(`Setting height ${h[ri]} for ${ri}`);
			} else {
				console.log('Maximal flow...');
				break; // we have maximal flow
			}
		}
	} while (true);

	let flow = 0;
	for (let j = 0; j < n; j++) {
		flow += f[m[graph.source]][j];
	}
	return flow;
}

function sourceCmdLine(ctx, cmdLine) {
	ctx.source = cmdLine.slice(
		'source'.length,
		cmdLine.indexOf(';')
	).trim();
}

function targetCmdLine(ctx, cmdLine) {
	ctx.target = cmdLine.slice(
		'target'.length,
		cmdLine.indexOf(';')
	).trim();
}

function edgeCmdLine(ctx, cmdLine) {
	let edgeLine = cmdLine.slice(
		'edge'.length,
		cmdLine.indexOf(';')
	).trim();
	console.log(`Edge line ${edgeLine}`);

	const matches = edgeLine.match(/^([a-zA-Z]*) -> ([a-zA-Z]*): ([0-9.]*)$/);
	// console.log('Matches', matches);
	const v = matches[1];
	const z = matches[2];
	const weight = Number.parseFloat(matches[3]);

	console.log(`Parsed ${v} ->  ${z} : ${weight}`);

	ctx.nodes.add(v);
	ctx.nodes.add(z);
	let targetEdges = ctx.edges[v] || [];
	targetEdges.push({node: z, weight});
	ctx.edges[v] = targetEdges;

}

function processCmdLine(ctx, cmdLine) {
	console.log(`Processing command line ${cmdLine}`);
	if (cmdLine.startsWith('source')) {
		sourceCmdLine(ctx, cmdLine);
	} else if (cmdLine.startsWith('target')) {
		targetCmdLine(ctx, cmdLine);
	} else if (cmdLine.startsWith('edge')) {
		edgeCmdLine(ctx, cmdLine);
	}
}

console.log(`Process argv: ${process.argv}`);

const inputPath  = process.argv.length > 2 ? process.argv[2] : '-';
const outputPath = process.argv.length > 3 ? process.argv[3] : '-';

console.log(`Input path ${inputPath}, output path: ${outputPath}`);

const inputStream = inputPath === '-' 
	? process.stdin
	: fs.createReadStream(inputPath);

// const outputStream = outputPath === '-' 
// 	? process.stdout
//	: fs.createWriteStream(outputStream);

let inputBuffer = "";
let ctx = {
	source: '',
	target: '',
	edges: {},
	nodes: new Set()
};

function processChunk(chunk) {
	inputBuffer += chunk;
	console.log(`Chunk: ${chunk}`);
	let eolIdx;
	do {
		eolIdx = inputBuffer.indexOf(EOL);
		if (eolIdx < 0 && !chunk) {
			eolIdx = inputBuffer.length;
		}

		let cmdLine = null;
		if (eolIdx >= 0) {
			console.log(`We got new line ${eolIdx}`);
			cmdLine = inputBuffer.slice(0, eolIdx);
			processCmdLine(ctx, cmdLine);
			inputBuffer = inputBuffer.slice(eolIdx+EOL.length);
		}
	} while (eolIdx >= 0 && inputBuffer.length);
}

inputStream.on('data', (chunk) => {
	processChunk(chunk);
});

inputStream.on('end', (chunk) => {
	console.log(`end chunk ${chunk}`);
	processChunk(chunk);
	console.log('Got following graph', ctx);

	for (let v in ctx.edges) {
		for (let {node, weight} of ctx.edges[v]) {
			console.log(`${v} ${node} : ${weight}`);
		}
	}

	let mflow = findMaximumFlow(ctx);

	console.log(`Maximum flow is ${mflow}`);

});