Hi Malte. Hope I'm not too late to the party :-)
Here's some sample code that appears to work on my small sample data.
It's not easy to come up with good test data here - nothing obvious
could generate realistic test data by program.
Summary is
1. deal with all equality cases first. For every set of equal-age names,
we use the same name (first one alphabetically) for the 'younger'
relationship table.
2. normalize the realtionships (always younger, replace by same-age
equivalent
3. for each name, keep two lists - those older and still to be handled,
and those older but already dealt with
4. repeatedly, take a name from the first list and try to move it to the
second. If this name itself has nothing left on its 'still-to-do' list
then we have completely moved this name - remove it from the still-to-do
list.
This should be reasonably efficient, though there are possible
optimizations by keeping back-pointers - so let me know if this is too
slow when you start using thousands of names,
-- Alex.
global gSameAge -- array of those who are the same age
global gRelate -- array of direct (i.e. defined) relationships
global gOlder -- array containing (one per line) all those who are
known older than the key
global gOlderStillToDo
on c
put URL "file:~/data.txt" into tData
put empty into gSameAge
put empty into gOlder
put empty into gOlderStillToDo
-- deal with all the equal age info
-- for each group of same-age people, we will use the first
alphabetically
-- step 1. normalize each individual equality to be alphabetocal
-- step 2. sort the set of equality facts to be alphabetical
-- step 3. for each subsequent name, store the earliest equal one
repeat for each line L in tData
if word 2 of L = "=" then
if word 1 of L < word 3 of L then
put word 1 of L && word 3 of L & CR after tEqual
else
put word 3 of L && word 1 of L & CR after tEqual
end if
end if
end repeat
-- sort these to handle cases like a=b and b=d
sort lines of tEqual
repeat for each line L in tEqual
if gSameAge[word 1 of L] is not empty then
put gSameAge[word 1 of L] into gSameAge[word 2 of L]
else
put word 1 of L into gSameAge[word 2 of L]
end if
end repeat
-- now normalize the direct relationships
put empty into gRelate
repeat for each line L in tData
if word 2 of L = "<" then
put sample(word 1 of L) into t1
put sample(word 3 of L) into t2
put t1 && t2 & CR after tUnequal
end if
end repeat
-- first the direct relationships
repeat for each line L in tUnequal
put word 2 of L & CR after gOlderStillToDo[word 1 of L]
end repeat
repeat 10000 timeS -- forever, but avoid infinite loops
put 0 into tNeedToDoAgain
put the keys of gOlderStillToDo into tKeys
-- for each one that still has something to do
repeat for each line K in tKeys
put empty into tNewlyFound
put empty into tStillToDo
repeat for each line L in gOlderStillToDo[K]
if L is not among the keys of gOlderStillToDo then
-- add this older one, *and* all names known to be
older than it
put L & CR after gOlder[K]
put gOlder[L] & CR after tNewlyFound
else -- this one hasn't yet been done, so we may need
another iteration
put L & CR after tStillToDo
add 1 to tNeedToDoAgain
end if
end repeat
if tStillToDo is empty then
delete variable gOlderStillToDo[K]
else
put tStillToDo into gOlderStillToDo[K]
end if
repeat for each line L in tNewlyFound
if L = K then -- there is a loop in age info - i.e. bad
input !!
ask "loop" && L && K
exit to top
end if
if L is not among the lines gOlder[K] and L is not among
the lines of gOlderStillToDo[K] then
put L & CR after gOlderStillToDo[K]
add 1 to tNeedToDoAgain
end if
end repeat
end repeat
if tNeedToDoAgain = 0 then exit repeat
end repeat
repeat for each key K in gOlder
put K & "--->" & CR after field "F"
put gOlder[K] after field "F"
end repeat
end c
function sample pA
if gSameAge[pA] is not empty then
return gSameAge[pA]
else
return pA
end if
end sample
On 08/03/2011 18:49, Malte Brill wrote:
Thanks for the head ups folks,
Björnke and Mark: I do not have the exact ages to sort by. All I do have is
relations:
Malte is older than Björnke
Mark is older than Malte
And now I need to compute if it is valid to say:
- Björnke is older than Mark (obviously not)
- Björnke is the same age as Mark (obviously not)
- Björnke is younger than Mark. (That´s the one)
What comes easy to the human brain in fact appears to be a lot more difficult
when having to be tackled computationaly.
Chris: Yes, I want such a list in the end. But in order to finally get this I
will need to tell the machine which relations are legal first (the user tells
which relations there are) and ideally filter out the data for relations that
make no sense. Now I wish it was easy to tell the machine to just use logic and
make sense itself :D This comparison has to be done for thousands of entities
(children in this case).
Cheers,
Malte
_______________________________________________
use-livecode mailing list
use-livecode@lists.runrev.com
Please visit this url to subscribe, unsubscribe and manage your subscription
preferences:
http://lists.runrev.com/mailman/listinfo/use-livecode
_______________________________________________
use-livecode mailing list
use-livecode@lists.runrev.com
Please visit this url to subscribe, unsubscribe and manage your subscription
preferences:
http://lists.runrev.com/mailman/listinfo/use-livecode
