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]
19 function [listOfPathsNodes, listOfPathsLinks] = enumeratePaths(adj,arcs,orig,dest,forbiddennodes,forward)
20  forbiddennodes(orig) = 1 ;
21  listOfPathsNodes = {} ;
22  listOfPathsLinks = {} ;
23  if (orig == dest)
24  return ;
25  endif
26  # Forward arcs
27  for arcij = adj(orig,:)
28  if (arcij != 0)
29  nodej = arcs(arcij,2) ;
30  if (forbiddennodes(nodej) == 0)
31  myforbiddennodes = forbiddennodes ;
32  [myListOfPathsNodes, myListOfPathsLinks] = enumeratePaths(adj,arcs,nodej,dest,myforbiddennodes,forward) ;
33  if isempty(myListOfPathsNodes)
34  theLink = [orig ; nodej] ;
35  listOfPathsNodes(end+1) = theLink ;
36  listOfPathsLinks(end+1) = arcij ;
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 ] ;
48  listOfPathsLinks(end+1) = [ arcij ; myListOfPathsLinks{p} ;
49  ] ;
50  endif
51  endif
52  endfor
53  endif
54  endif
55  endif
56  endfor
57  # Backward arcs
58  if (forward == 0)
59  for arcji = adj(:,orig)'
60  if (arcji != 0)
61  nodei = arcs(arcji,1) ;
62  if (forbiddennodes(nodei) == 0)
63  myforbiddennodes = forbiddennodes ;
64  [myListOfPathsNodes, myListOfPathsLinks] = enumeratePaths(adj,arcs,nodei,dest,myforbiddennodes,forward) ;
65  if isempty(myListOfPathsNodes)
66  theLink = [orig ; nodei] ;
67  listOfPathsNodes(end+1) = theLink ;
68  listOfPathsLinks(end+1) = arcji ;
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 ] ;
80  listOfPathsLinks(end+1) = [ arcji ; myListOfPathsLinks{p} ;
81  ] ;
82  endif
83  endif
84  endfor
85  endif
86  endif
87  endif
88  endfor
89  endif
90 endfunction
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