Optimization: principles and algorithms, by Michel Bierlaire
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
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
 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
 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.
 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
Copyright 2015-2016 Michel Bierlaire