Optimization: principles and algorithms, by Michel Bierlaire
Functions
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

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

Build the path by traversing the layers backward.

Note
Called by unsaturatedPath
Parameters
layerlist of layers. Each layer contains an array of nodes, arcs and directions.
destdestination node to reach
arcsA 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
function printLayers ( in  layer,
in  arcs 
)

Print the layers.

Note
Called by unsaturatedPath
Parameters
layerlist of layers. Each layer contains an array of nodes, arcs and directions.
arcsA 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.
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
adjadjacency matrix of the network. Each nonzero entry corresponds to an arc. The value of the entry is the ID of the arc.
origthe origin node
destthe destination node
lbthe lower bound on the flow
ubthe upper bound on the flow
flowthe current flow vector
printlevelIf 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
Copyright 2015-2016 Michel Bierlaire