0

I have N number of nodes at start and end where they can be paired as N number of sets (1 to 1, .., n to n, .., N to N). However, I have M stages (can be assumed as parallel stages) in between the start and end, and each stage has R number of nodes where R>=N.

If I consider start n node to end n node (i.e., n to n pair), I have to pass (M+1) hops to reach end node, and there are R^M possible paths. Thus, all possible paths for all pairs are N*R^M.

I weight each link as : the link between node i at stage m and node j at stage m+1 as w_{i,j}^{m,m+1}.

I want to write a MATLAB code to generate all possible paths each pair, i.e., N number of pairs. Can someone please help me?

I tried it only using exhaustive search just for 2 start and end nodes with 2 stages that have 3 nodes. But I don't know how to write this for a general network with effective way. Please help me !!!

Added: For example: N = M = 2, R = 3 I have R^M=2^3=9 possible paths for each pair. For both pairs, I have 18. For 1 to 1 pair, possible paths set is: 

{1-1-1-1, 1-1-2-1,1-1-3-1
1-2-1-1, 1-2-2-1,1-2-3-1
1-3-1-1, 1-3-2-1,1-3-3-1}

and corresponding weights set is (0 represents start) :

{w_{1,1}^{0,1}-w_{1,1}^{1,2}-w_{1,1}^{2,3}; w_{1,1}^{0,1}-w_{1,2}^{1,2}-w_{2,1}^{2,3}; w_{1,1}^{0,1}-w_{1,3}^{1,2}-w_{3,1}^{2,3}, ........., w_{1,3}^{0,1}-w_{3,3}^{1,2}-w_{3,1}^{2,3}}

Same follows for the 2 to 2 pair.

Actually, my exhaustive search I generate each hop as matrix with randomly generated weights. From start to 1st hop: A=rand(2,3), then 1st hop to 2nd hop: B=rand(3,3), and 2nd to end: C=rand(3,2)

Frey
  • 315
  • 4
  • 11
  • It's not really clear to me precisely what the scenario is. You mention some edge weights here, but they don't seem to have anything to do with the problem of enumerating paths. Also, the choice of starting and ending nodes doesn't seem to matter, as you don't indicate any constraints on which nodes can be connected to which. Could you perhaps indicate the desired output for, say, N = M = 2, R = 3? – Daniel McLaury Sep 27 '16 at 06:40
  • Thanks @Daniel McLaury, I want to write both 1) the possible paths and 2) corresponding weights.You are right that enough to know one set, but I am worrying about the corresponding weight set as well. As you comments, I update the problems using example N = M = 2, R = 3. – Frey Sep 27 '16 at 07:07
  • Maybe this can help you - http://stackoverflow.com/questions/9535819/find-all-paths-between-two-graph-nodes – StefanM Sep 27 '16 at 07:40

1 Answers1

0

Okay, so per your update you just want to generate the Cartesian product

{i} X {1, 2, ..., R}^M X {j}

A quick-and-dirty approach would be to do something like this:

paths = zeros(R ^ M, M + 2); # initialize array
paths(:, 1) = i;              # start all paths at node i
paths(:, M+2) = j;            # end all paths at node j

for c = 1:M
  for r = 1:(R ^ M)
    paths(r, c+1) = mod(idivide(r-1, R ^ (c-1)), R)+1 ;
  end
end

You could then loop through paths and calculate the weights.

Daniel McLaury
  • 4,047
  • 1
  • 15
  • 37
  • I did not get the meaning of `{i} X {1, 2, ..., R}^M X {j}` and `**`. – Frey Sep 27 '16 at 09:09
  • Well, look at the way you enumerated the paths. In the first column we want the pattern 1-2-3-1-2-3-1-2-3-..., in the second column we want the pattern 1-1-1-2-2-2-3-3-3-1-1-1-..., and so forth. So the things we're going to produce are basically going to be the ternary (or more generally the base-R) expansions of the numbers from 1 to R^M, modulo that we want 3's instead of 0's. So we can just write a loop and extract these. – Daniel McLaury Sep 27 '16 at 09:24
  • If we want to get the hundreds' digit of, say, 41235, we can divide by 100 and throw away the remainder (`idivide`), giving 412, and then take the remainder upon dividing by 10 (`mod`), giving 2. And of course the same idea works in arbitrary bases, not just base ten. – Daniel McLaury Sep 27 '16 at 09:26
  • From where `i` and `j` come? Further, for given `i,j,R,M` I run code, then I get `Error using idivide>idivide_check At least one argument must belong to an integer class.` It is great if you can give code which works for one given set of `R,N,M`. – Frey Sep 27 '16 at 09:36
  • Oh, perhaps you need to change the `**` to `^`. I have Octave instead of MATLAB on this machine and they're not 100% compatible. Try the updated version in my answer. – Daniel McLaury Sep 27 '16 at 09:45
  • what the purpose of `{i} X {1, 2, ..., R}^M X {j}`, and how do you generate it to relate this code? – Frey Sep 27 '16 at 15:31
  • It's a Cartesian product. For instance {1, 2}^2 = {(1, 1), (1, 2), (2, 1), (2, 2)} and {3} X {1, 2, 3} = {(3, 1), (3, 2), (3, 3)}. – Daniel McLaury Sep 27 '16 at 18:49