Optimization: principles and algorithms, by Michel Bierlaire
runEnumeratePaths.m
Go to the documentation of this file.
1 %> \file
2 %> Run to illustrate the path enumeration algorithm (Table 23.1)
3 %>
4 %> @note Calls \ref enumeratePaths
5 %> @note Calls \ref prepareNetwork
6 %>
7 %> @ingroup chap23
8 %> @ingroup Running
9 %> @author Michel Bierlaire
10 %> @date Thu Apr 9 17:20:47 2015
11 
12 # Arc 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
13 cost = [ 8 1 1 1 1 8 1 1 8 8 8 1 8 1 1 8 8 8 1 1 1 8 8 8]' ;
14 
15 adj = [ 0 1 0 0 2 0 0 0 0 0 0 0 0 0 0 0 ;
16  0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 ;
17  0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 ;
18  0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 ;
19  0 0 0 0 0 6 0 0 7 0 0 0 0 0 0 0 ;
20  0 8 0 0 0 0 9 0 0 0 0 0 0 0 0 0 ;
21  0 0 10 0 0 0 0 11 0 0 0 0 0 0 0 0 ;
22  0 0 0 0 0 0 0 0 0 0 0 12 0 0 0 0 ;
23  0 0 0 0 0 0 0 0 0 13 0 0 14 0 0 0 ;
24  0 0 0 0 0 15 0 0 0 0 16 0 0 0 0 0 ;
25  0 0 0 0 0 0 17 0 0 0 0 18 0 0 0 0 ;
26  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 19 ;
27  0 0 0 0 0 0 0 0 0 0 0 0 0 20 0 0 ;
28  0 0 0 0 0 0 0 0 0 21 0 0 0 0 22 0 ;
29  0 0 0 0 0 0 0 0 0 0 23 0 0 0 0 24 ;
30  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ];
31 
32 
33 addpath("../chap21") ;
34 arcs = prepareNetwork(adj) ;
35 nnodes = rows(adj) ;
36 forbiddennodes = zeros(nnodes,1) ;
37 
38 forwardOnly = 1 ;
39 o = 1 ;
40 d = 16 ;
41 [listOfPathsNodes, listOfPathsLinks] = enumeratePaths(adj,arcs,o,d,forbiddennodes,forwardOnly);
42 for i = 1:length(listOfPathsLinks)
43  printf("%d:\t",i) ;
44  cc = 0 ;
45  for j = 1:length(listOfPathsLinks{i})
46  a = listOfPathsLinks{i}(j) ;
47  cc = cc + cost(a) ;
48  endfor
49  for a = listOfPathsNodes{i}
50  printf("%d\t",a) ;
51  endfor
52  printf("\n") ;
53 endfor
function prepareNetwork(in adj)
Identifies the upstream and downstream nodes of each arc.
function enumeratePaths(in adj, in arcs, in orig, in dest, in forbiddennodes, in forward)
Enumerate all simple paths between two nodes.
Copyright 2015-2016 Michel Bierlaire