unsaturatedPath.m File Reference

Algorithm 24.1: unsaturated path. More...

Go to the source code of this file.

Functions
function	unsaturatedPath (in adj, in orig, in dest, in lb, in ub, in flow, in printlevel)
	Find an unsaturated path from o to d. More...
function	buildPathBackward (in layer, in dest, in arcs)
	Build the path by traversing the layers backward. More...
function	printLayers (in layer, in arcs)
	Print the layers. More...

Detailed Description

Algorithm 24.1: unsaturated path.

Implementation of algorithm 24.1 of [1]

Note

Tested with runUnsaturatedPath.m

Called by fordFulkerson

Calls prepareNetwork

Author

Michel Bierlaire

Date

Thu Apr 9 18:08:09 2015

Definition in file unsaturatedPath.m.

Function Documentation

buildPathBackward()

function buildPathBackward	(	in	layer,
		in	dest,
		in	arcs
	)

Build the path by traversing the layers backward.

Note

Called by unsaturatedPath

Parameters

layer	list of layers. Each layer contains an array of nodes, arcs and directions.
dest	destination node to reach
arcs	A matrix containing the upstream and downstream nodes of each arc. Each row corresponds to an arc. Column 1 contains the upstream node and column 2 the downstream. Output of prepareNetwork.

Returns

path.arcs: sequence of arcs on the path

path.dir: +1 if forward, -1 if backward

printLayers()

function printLayers	(	in	layer,
		in	arcs
	)

Print the layers.

Note

Called by unsaturatedPath

Parameters

layer	list of layers. Each layer contains an array of nodes, arcs and directions.
arcs	A matrix containing the upstream and downstream nodes of each arc. Each row corresponds to an arc. Column 1 contains the upstream node and column 2 the downstream. Output of prepareNetwork.

unsaturatedPath()

function unsaturatedPath	(	in	adj,
		in	orig,
		in	dest,
		in	lb,
		in	ub,
		in	flow,
		in	printlevel
	)

Find an unsaturated path from o to d.

Note

Calls buildPathBackward

Calls printLayers

Parameters

adj	adjacency matrix of the network. Each nonzero entry corresponds to an arc. The value of the entry is the ID of the arc.
orig	the origin node
dest	the destination node
lb	the lower bound on the flow
ub	the upper bound on the flow
flow	the current flow vector
printlevel	If different from 0, the layers are printed. (Default: 0)

Returns

path.arcs: sequence of arcs on the path

path.dir: +1 if forward, -1 if backward

cut: array of nodes defining the cut