Optimization: principles and algorithms, by Michel Bierlaire
enumeratePaths.m
Go to the documentation of this file.
1 %> \file
2 %> Enumerate all simple paths between two nodes
3 %>
4 %> @note Tested with runEnumeratePaths.m
5 %>
6 %> @author Michel Bierlaire
7 %> @date Sat Apr 11 11:08:57 2015
8 %> @ingroup Algorithms
9 %> @ingroup chap23
10
11 %> Enumerate all simple paths between two nodes
12 %> @param adj adjacency matrix of the network. Each nonzero entry corresponds to an arc. The value of the entry is the ID of the arc.
13 %> @param arcs 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. Can be generated from the adjacency matrix by \ref prepareNetwork
14 %> @param orig the origin node
15 %> @param dest the destination node
16 %> @param forbiddennodes nodes that cannot be included anymore, in order to generate simple paths.
17 %> @param forward if 0, arcs can be used in any direction. If not 0, arcs can only be used in the forward direction
18 %> @return paths [cell array containing paths as list of nodes, cell array containing paths as list of links]
20  forbiddennodes(orig) = 1 ;
21  listOfPathsNodes = {} ;
23  if (orig == dest)
24  return ;
25  endif
26  # Forward arcs
28  if (arcij != 0)
29  nodej = arcs(arcij,2) ;
30  if (forbiddennodes(nodej) == 0)
31  myforbiddennodes = forbiddennodes ;
33  if isempty(myListOfPathsNodes)
34  theLink = [orig ; nodej] ;
37  else
38  for p = 1:length(myListOfPathsNodes)
39  thePathNode = myListOfPathsNodes{p} ;
40  % To avoid cycles, if the orig has
41  % already been included in the
42  % downstream path, it is not included
43  % again
44  idx = find(thePathNode == orig) ;
45  if (length(idx) == 0)
46  if (thePathNode(end) == dest)
47  listOfPathsNodes(end+1) = [ orig ; thePathNode ] ;
49  ] ;
50  endif
51  endif
52  endfor
53  endif
54  endif
55  endif
56  endfor
57  # Backward arcs
58  if (forward == 0)
60  if (arcji != 0)
61  nodei = arcs(arcji,1) ;
62  if (forbiddennodes(nodei) == 0)
63  myforbiddennodes = forbiddennodes ;
65  if isempty(myListOfPathsNodes)
66  theLink = [orig ; nodei] ;
69  else
70  for p = 1:length(myListOfPathsNodes)
71  thePathNode = myListOfPathsNodes{p} ;
72  % To avoid cycles, if the orig has
73  % already been included in the
74  % downstream path, it is not included
75  % again
76  idx = find(thePathNode == orig) ;
77  if (length(idx) == 0)
78  if (thePathNode(end) == dest)
79  listOfPathsNodes(end+1) = [ orig ; thePathNode ] ;
81  ] ;
82  endif
83  endif
84  endfor
85  endif
86  endif
87  endif
88  endfor
89  endif
90 endfunction