Optimization: principles and algorithms, by Michel Bierlaire
circulationDecomposition.m
Go to the documentation of this file.
1 %> \file
2 %> Algorithm 21.2: circulation decomposition. Implementation of algorithm 21.2 of \cite Bier15-book
3 %>
4 %> @note Tested with \ref runCirculationDecomposition.m
5 %> @note Calls \ref simpleCycle
6 %> @note Called by \ref flowDecomposition
7 %>
8 %> @author Michel Bierlaire
9 %> @date Sun Mar 29 17:16:14 2015
10 %> @ingroup Algorithms
11 %> @ingroup chap21
12 
13 %> Decompose a circulation into simple cycle flows
14 %> @param adj the adjacency matrix of the network. It is a \f$m \times m\f$ matrix, such that the element at row i and column j corresponds to the id of the arc (i,j). The numbering should be from 1 to n.
15 %> @param circ the circulation flow
16 %> @return simpleCycleFlows a matrix with as many columns as arcs, and as many rows as simple cycles in the decomposition
17 function simpleCycleFlows = circulationDecomposition(adj,circ)
18  simpleCycleFlows = zeros(0,0) ;
19  workingcirc = circ ;
20  while any(workingcirc)
21  theCycleFlow = simpleCycle(adj,workingcirc) ;
22  simpleCycleFlows(end+1,:) = theCycleFlow' ;
23  workingcirc -= theCycleFlow ;
24  endwhile
25 endfunction
function flowDecomposition(in adj, in flow)
Decompose a flow vector into simple path flows.
function circulationDecomposition(in adj, in circ)
Decompose a circulation into simple cycle flows.
function simpleCycle(in adj, in circ, in printlevel)
Extract a simple cycle flow from a circulation.
Copyright 2015-2016 Michel Bierlaire