2 %> Enumerate all simple paths between two nodes
4 %> @note Tested with runEnumeratePaths.m
6 %> @author Michel Bierlaire
7 %> @date Sat Apr 11 11:08:57 2015
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 = {} ;
27 for arcij = adj(orig,:)
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 ;
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
44 idx = find(thePathNode == orig) ;
46 if (thePathNode(end) == dest)
47 listOfPathsNodes(end+1) = [ orig ; thePathNode ] ;
48 listOfPathsLinks(end+1) = [ arcij ; myListOfPathsLinks{p} ;
59 for arcji = adj(:,orig)
' 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 ; 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 76 idx = find(thePathNode == orig) ; 78 if (thePathNode(end) == dest) 79 listOfPathsNodes(end+1) = [ orig ; thePathNode ] ; 80 listOfPathsLinks(end+1) = [ arcji ; myListOfPathsLinks{p} ; 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.