Farmer needs algorithm for looping through self-referencing animal table

Question

The problem: There's a ton of animals on a farm. Every animal can have any number of animal friends, except for the anti-social animals--they don't have friends that belong to them, but they belong to other normal animals as friends. Each animal is exactly as happy as it's least happiest animal friend, except for the anti-social animals of course. The anti-social animals happiness' levels can be anything.

One morning all the animals wake up and find some of the anti-social animals mood's have changed. How does the farmer figure out the happiness of each animal?

Here's as far as the ranch hands got (they didn't go to farmer school):

DataTable animals = Select_All_Animals();
foreach (DataRow animal in animals.Rows)
{
    int worstMood = 10; //Super Happy!
    DataTable friendRecords = Select_Comp_Animal_AnimalFriend((int)animal["AnimalID"]);
    foreach (DataRow friend in friendRecords.Rows)
    {
        DataTable animalFriends = Select_AnimalFriend((int)friend["AnimalID_Friend"]);
        foreach (DataRow animalFriend in animalFriends.Rows)
        {
            int animalMood = Get_Animal_Mood((int)animalFriend["Mood"]);
            if (animalMood < worstMood)
            {
                worstMood = animalMood;
            }
        }
    }
}

But this will not work because the animal table does not sequentially follow the animal friend hierarchies that have formed. Animals can make friends with each other at any time! So Animal(1) might have Animal(4000) as a friend. Animal(1) will not show an accurate mood because it will check Animal(4000)'s mood before Animal(4000)'s mood has been updated itself. And new animals are being dropped off everyday. I figure the solution might a common algorithm design, but I haven't been able to find it. I don't believe I have the correct terminology to accurately search for it.

Thanks a bunch and sorry if this has already been answered!

Added:

Here's a ghetto Paint chart of possible relationships:

The anti-social animals are at the bottom level and have no friends belonging to them. The normal animals are everywhere else above. There is no exact structure to the normal animal friendships, except (as Sebastian pointed out) there can't be a closed loop (if designed correctly).

There will be hundred's of thousands of animals added weekly and processing speed is a critical element.

Answer 1

Start by grabbing all the antisocial animals and ordering them from least happy to most happy. Initialise the happiness of all the social animals to the maximum (this makes everything easier since you don't have to detect when a previously unhappy animal gets happier). Then just iterate over the list and propagate the happiness levels up the friendship chains:

void UpdateFarm()
{
    // Start with a list of antisocial animals from least to most happy.
    var antisocialAnimals = GetAntisocialAnimals().OrderBy(x => x.Happiness);

    // Initialise the social animals to the global maximum. Note the
    // global maximum is the happiest antisocial animal. This is done to
    // avoid the case where an antisocial animal's happiness has increased,
    // so some of the social animals are too unhappy.
    var maxHappiness = antisocialAnimals.Last().Happiness;
    var socialAnimals = GetSocialAnimals();
    foreach (var socialAnimal in socialAnimals)
        socialAnimal.Happiness = maxHappiness;

    // Now iterate from least to most happy, propagating up the friend chain.
    foreach (var antisocialAnimal in antisocialAnimals)
        UpdateFriends(antisocialAnimal);
}

// To propagate a happiness change, we just find all friends with a higher
// happiness and then lower them, then find their friends and so on.
void UpdateFriends(Animal animal)
{
    var friends = GetFriends(animal); // Friends with this animal, not friends of.

    foreach (var friend in friends.Where(x => x.Happiness > animal.Happiness))
    {
        friend.Happiness = animal.Happiness;

        // Since this friend's happiness has changed, we now need to update
        // its friends too.
        UpdateFriends(friend);
    }
}

Answer 2

Nice question. So, if i understand correctly you basically have directed graph with cycles. You can think of every animal as a node (vertex) that has outgoing edge to animal on which it mood depends, and incoming edges from animals which mood it influences. Obviously anti-social animals will have incoming edges only.

If you think about it this way you will notice two things

1) You can devise a iterative algorithm that will sweep trough all animals, checking for each animal if it has any outgoing edges only to anit-social or already processed animal, if yes, we compute mood of the animal, and mark it as processed. If not, we just skip it for this iteration.

2) Because you can have cycles in your graph, this algorithm will not always finish. That is you may have Animal A depending on B, B depending on C and C depending on A. If you have simple logic, as in your case, that the lowest mood wins, you could probably detect and resolve those cycles by assigning to all animals in the cycle - in this case A,B,C lowest common mood.

Hope it helps!

Answer 3

Interesting problem. If I understand it correctly, each animal's happiness is the MIN of the happiness of all if it's one-way friends (inbound).

If that's so, then the challenge is that each of the animal's friends' happiness is subject to THEIR friends and so on so where to start.

Here's what I think at first glance...

Since new animals show up every day, you need to start fresh every day and you need to start with the animal(s) with the lowest starting happiness. It's easy enough to find those and then propogate that happiness out to all the animals they are friends to, adjusting those levels of happiness down accordingly. Then take all the adjusted animals and repeat until no more animals are adjusted. Once that happiness level is fully propogated, move to the next-highest happiness level and repeat until the highest remaining level of happiness is handled.

One interesting point to this is that it doesn't matter which animals, if any, are anti-social. They are just animals with no influencing inputs and therefore won't be adjusted by this process.

I think that will get you where you want to be and it shouldn't be difficult at all to code.

Hope it helps.