Optimization: principles and algorithms, by Michel Bierlaire
flowDecomposition.m
Go to the documentation of this file.
1 %> \file
2 %> Algorithm 21.3: flow decomposition. Implementation of algorithm 21.3 of \cite Bier15-book
3 %>
4 %> @note Tested with \ref runFlowDecomposition.m
5 %> @note Calls \ref nodeDivergence
6 %> @note Calls \ref circulationDecomposition
7 %>
8 %> @author Michel Bierlaire
9 %> @date Sun Mar 29 17:26:50 2015
10 %> @ingroup Algorithms
11 %> @ingroup chap21
12 
13 %> Decompose a flow vector into simple path 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 flow the flow vector
16 %> @return simplePathFlows a matrix with as many columns as arcs, and as many rows as simple paths in the decomposition
17 function simplePathFlows = flowDecomposition(adj,flow)
18  nnodes = rows(adj) ;
19  narcs = max(max(adj)) ;
20 
21  y = nodeDivergence(adj,flow) ;
22 
23  modAdj = [ adj zeros(nnodes,1) ; zeros(1,nnodes+1)] ;
24  arcNumber = narcs ;
25  modFlow = flow ;
26  for i=1:length(y)
27  if (y(i) != 0)
28  arcNumber += 1 ;
29  modAdj(nnodes + 1,i) = arcNumber ;
30  modFlow(end+1) = y(i) ;
31  endif
32  endfor
33  theSimpleCycleFlow = circulationDecomposition(modAdj,modFlow);
34  simplePathFlows = theSimpleCycleFlow(:,1:narcs);
35 endfunction
function nodeDivergence(in adj, in flow)
Compute the divergence of a flow vector.
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.
Copyright 2015-2016 Michel Bierlaire