Looping, cross-product, transitive closure

[SJM]

Hi,

I am trying to represent a dependency relation between events. I have a table called 'Events', and a join table between Events and itself. The join table is called 'Prereqs' and has two columns, 'earlier' and 'later'. The values in these columns are primary keys for Events (this is what I mean by saying it is a join table between Events and itself). So if one row of Prereqs is the pair then the event whose primary key is 'a' is earlier than the event whose primary key is 'b'.

I have a table 'Extended_Prereqs' and I want to populate it with the transitive closure of the Prereqs table. So, if is in Prereqs and is in Prereqs, then

I have an algorithm called Warshall's that shows how to compute this. My problem is that I don't know how to translate this into FileMaker script steps. The algorithm is basically this:

1.

Copy all the rows from Prereqs to Extended_Prereqs.

2. (this is a triple-nested loop but the indentation doesn't show up in forum)

For every i in Events:

For every j in Events:

For every k in Events:

if is in Extended_Prereqs and is in Extended_Prereqs then put in Extended_Prereqs.

So what's the problem? Well, for one thing I don't know how to loop over a found set and have the current value bound to something (i, j, or k) that I can refer to later. Also, if I'm using Go To Record/Request/Page, I need three independent series of steps through the array, but I feel like in FileMaker I can only have one found set to step through, and so the nested loops will be stepping all over each other and it won't work.

To get around this last problem, I thought to create a triple cross-product of Events x Events x Events and then step once through that. But I'm not sure how to do such a thing, and I still have the problem of stepping through, testing for membership (i.e., querying for a record with the two columns equal to the two members of the pair, and testing if the found set is empty or not), and then writing a new row with the new pair when appropriate.

Finally, I'm well aware that the complexity of this is on the order of the cube of the number of Events - we're willing to entertain that for now. We suppose we'll have less than 100 events, and so we won't exceed one million items. Also, if we can get this done, we expect mainly to update the dependencies between events on-the-fly, each time an event or a dependency is created.

So, if anyone can provide some insight and/or instruction on some of these more basic issues, I'd certainly appreciate it!

Thanks

[comment]

Is this really for version 6? You seem to be using version 7 vocabulary, and it is easier to do in 7.

[SJM]

No, I'm sorry, I forgot to update my profile. I am using FileMaker Pro 8 Advanced. I had originally posted in the FMP8 forum but I guess it was moved to Relationships.

So I'm using 8...

Hello.

[comment]

Ah, good. See if the attached file gets you in the right direction. Note that it doesn't use the algorithm you mentioned. Instead, it utilises relationships - something Filemaker does much better than raw computing.

In the same vein, I don't know what is your ultimate purpose here, but I cannot help wondering:

If you count, for each event, the number of records in Prereqs where this event is 'later', then sort the Events table by the result - I believe you would end up with a chronological order of Events.

TransitiveClosure.fp7.zip