Array Manipulation With Recursion

[jon_mcbee]

I have a 2D array that  is similar to an adjacency matrix.  The array holds information that I need to parse out following a set of simple rules, but I am having trouble implementing them.  Below is a simple example of the array (I would like to get the simple example working and then expand it where necessary to work with larger examples).  The array is a 6x6 array and the columns hold information about a how to transition between nodes in a map.  There is a Root column (the column we will start with) and there are Leaf columns, columns we are trying to reach by traversing through other nodes in the graph (other columns in the array).  In the example below there is only one Root and one Leaf, the Root is column zero and the Leaf is column 6 (I chose the labeling of the nodes so that column zero would be the root and column six would be the leaf but this does not have to be the case and I am trying to write the software so that it is not dependent on labeling of the map).  Aside from the 2D array input there will also be an array of column headers that maps the node label to the correct column of the array, an array of Leaves and a numeric control for the Root.  This is what I am trying to do, reference the image below.

 

I look at the Root and see that it is node 1, looking at the Column Header I see that node 1 is column zero of my Array.  I start with row 0 of column 0 (the root column) and work my way down looking for non-zero integers.  I come to row one and see the integer 2, this tells me that I need to move to column 1 of the array (because column one has the header 2) and store the integer 2.   I start with row 0 of column one and work my way down looking for non-zero integers.  I come to row 2 and see integer 3, this tells me that I need to move to column 2 of the array (because column 2 has the header 3) and store the integer 3 (So that I now have [1,2,3] as my path I am building).  I start with row 0 of column 2 and work my way down looking for non-zero integers and come to row 4 and see integer 5, this tells me I need to move to column 4 of the array (because column 4 has header 5) and store the integer so that I have [1,2,3,5] as my path.  I start with row 0 of column four and work my way down looking for a non-zero integer and come to row 5 and see integer 6, because integer 6 is my current leaf (only leaf for this example) I stop and have a path from node 1 to node 6 of [1,2,3,5,6].  I am not done yet though (and this is the part that is giving me trouble) because column 1 (node 2 from the header) had another non-zero row, row 3, which holds integer 4.  I need to repeat the process from here, giving me a second path of [1,2,4,5,6].

You can see how this will get very complex when I have multiple columns with multiple non-zero rows.  This seems to be a good case for using recursion but I am having trouble writing the code to do so.  In the end I need to find every path to get from the Root to the Leaf, as I mentioned there will be more than one Leaf in most cases.  Having multiple Leafs should not be an issue as I can repeat the same process for each Leaf.  I have attaced a VI in 8.0 that has the arrays I am working with, matching the image above.  I would appreciate any thoughts on how to get this done, as I refuse to do this by hand for large examples when I should be able to easily automate this process.

Regards

Message Edited by jmcbee on 03-30-2009 08:38 AM

Message Edited by jmcbee on 03-30-2009 08:39 AM

[altenbach]

You only have only six colums, but you are talking about seven. (column #0 to column #6). This confuses me. 😉

[jon_mcbee]

I apologize, I was trying not to do that as I don't want to add unnecessary complication.  I mean to talk about columns 0-5, which using the header array map to 1-6 (which are the names of the columns as well as the names of the nodes on my map): Column 0 has header 1, column 1 has header 2... column 5 has header 6.  Let me know if this clears it up or if you still have questions.  I appreciate the help.

Message Edited by jmcbee on 03-30-2009 08:57 AM

[nathand]

Could you re-do your example with an array of strings and use named column headers?  That might make it clearer as to what you're trying to do.  Also, can you explain the application for this?  You may want to think carefully about how to create a data structure that will make for the easiest traversal; I'm not sure your current collection of arrays is it.

Based on my understand of what you're trying to do, I think you'll find it easier to use a queue for backtracking rather than recursion.  Each time you move to a new column, save the path to the current point and the current column and row number by pushing them onto a queue.  Then, whenever you reach a leaf, pop an element off the stack, which will get you back to the previous point in the previous column, from which you can continue down looking for the next non-zero value.  If you reach the end of the column, just pop another element off the queue.  Continue until the queue is empty.

[jon_mcbee]

Thank you for the feedback, let me try again with the explanation and I will give some detail for the application (I can't give full detail as I am just trying to automate a routine my wife is using for her research, and I only understand a small bit of it.  I made the mistake of saying: I can automate that for you, it will be easy...).  This is a small part of the problem but one that seems like it can and should be automated.  We begin with a map:

 

The blue node labeled 1 is the Root, the red node labeled 6 is the Leaf.  This is a very simple map, and while there can only ever be one root there is no limit to the number of leaves.  The goal is to find all possible routes from the Root to the Leafs (Leaf in our case).  By looking at the map it is easy to see that there are two routes (we discard any loops, a loop would be Starting at node 1=>2=>3=>5=>4=>2=>3=>5=>6).  In order to get the information from the map into a useable form I used an adajacency matrix:

Looking at the adjacency matrix and the map we can see that node one is adjacent to node 2, so there is a one in  the node one column and the node two row (as well as the node one row and the node two column).  (You can see that how we decide to label the nodes of the map will change how the adjacency matrix looks, this is why I define a header array.) However this matrix is symmetric so I decided to zero out everything above the main diagonal, this prevents us from dealing with saying node one is adjacent to node two, node two is adjacent to node one and looping back and forth between the two.

 My goal is to now find all ways to get from the Root to each Leaf by using this matrix.  In the example I posted previously I replaced the ones in this array with the column header they referred to.  Let me know if you have questions on this or what I am trying to do.

With regards to nathand, I like your idea of using a queue.  I will have to try and implement it tonight.  I am finding this to be a frustrating problem because the algorithm is simple when done by hand but more complex to put into code (this is probably a reflection of the person writing the code more than anything else).  Thanks for the help!

Message Edited by jmcbee on 03-30-2009 02:04 PM

Message Edited by jmcbee on 03-30-2009 02:12 PM

[Joseph_Loo]

You have something similiar to the traveling salesman problem. The number of leafs you want to compute will require order of N! computation. Most people se the standard alpha beta algorithm but it still does not guarantee a minimal solution. You might

[jon_mcbee]

This is similar to the traveling salesman, but will not be used for large maps.  This program will only be used for 10 Leafs or so, so I am not worried about the computational time or optimization.  I am not familiar with the alpha beta algorithm but will look into it.

[nathand]

I don't really like the adjacency matrix for this problem; I think there's a better data structure.  Here's one very, very quick attempt at it (no points for style, efficiency or documentation; LabVIEW 8.5.1).  It produces the right routes for your simple test, but it reports all paths twice and has a spurious path at the end.  I don't have time to play with it further at the moment.  I've used strings rather than array indices in the hope of making it slightly easier to follow, but you could change it to array indices easily.  In a language with references to objects a map structure such as this is easier to implement, but it does make for an interesting challenge in LabVIEW.

[jon_mcbee]

Hi nathand,

I like your idea of using strings, it does make the data easier to define than using the adjacency matrix!  I am going to play around with the example you posted tonight and see what I can do, I will post my results tomorrow (assuming I have anything post worthy).  Thanks again!

[nathand · Accepted solution]

This version fixes the two problems I mentioned - one was caused by queueing the start point outside the loop (a leftover from my initial idea), the other by not dealing with the final loop iteration when there's nothing left in the queue (fixed with an additional case structure).  Do you need this to be an undirected graph (ie, have links backwards as well as forwards)?  Otherwise you could make it a bit more efficient with a directed graph, by removing the link from 2 back to 1, from 3 and 4 back to 2, etc.