Optimization: principles and algorithms, by Michel Bierlaire
prepareNetwork.m
Go to the documentation of this file.
1 %> \file
2 %> Prepares the network for efficient access to the data
3 %>
4 %> @note Tested with runPrepareNetwork.m
5 %> @note Called by \ref simpleCycle
6 %> @note Called by \ref shortestPath
7 %> @note Called by \ref dijkstra
8 %> @note Called by \ref incidenceMatrix
9 %> @note Called by \ref transhipmentTransform
10 %> @note Called by \ref run2120.m
11 %> @note Called by \ref runEnumeratePaths.m
12 %>
13 %> @author Michel Bierlaire
14 %> @date Fri Mar 27 17:52:24 2015
15 %> @ingroup Algorithms
16 %> @ingroup chap21
17 
18 %> Identifies the upstream and downstream nodes of each arc
19 %> @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.
20 %> @return 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.
21 
22 function arcs = prepareNetwork(adj)
23  nnodes = rows(adj) ;
24  if (columns(adj) != nnodes)
25  error("Adjacency matrix must be square") ;
26  endif
27  narcs = max(max(adj)) ;
28  arcs = zeros(narcs,2) ;
29  for i = 1:nnodes
30  for j = 1:nnodes
31  if (adj(i,j) != 0)
32  arcs(adj(i,j),1) = i ;
33  arcs(adj(i,j),2) = j ;
34  endif
35  endfor
36  endfor
37 
38 endfunction
function simpleCycle(in adj, in circ, in printlevel)
Extract a simple cycle flow from a circulation.
function shortestPath(in adj, in cost, in orig)
Calculate the shortest paths from one origin to all nodes.
function incidenceMatrix(in adj)
Provide the incidence matrix a a network.
function prepareNetwork(in adj)
Identifies the upstream and downstream nodes of each arc.
function transhipmentTransform(in adj, in cost, in lb, in ub, in supply)
Transform a transhipment problem with m nodes and n arcs into a problem in standard form...
function dijkstra(in adj, in cost, in orig, in printlevel)
Calculate the shortest paths from one origin to all nodes using Dijkstra's algorithm.
Copyright 2015-2016 Michel Bierlaire