A Family Tree

Section 18.13 A Family Tree

As a more in depth example of using aggregation, let us model a family tree. The basis of our program will be a Person class. Every Person has a name. They may have a mother that we know about and they may also have a number of children we need to represent. (For brevity, we will skip representing fathers... the logic would be the same as for mothers.) A Person will thus need a Person* to store the mother, it will start out as a nullptr. It will also need a vector<Person*> to store any children. An empty vector will indicate no children, so we don’t need to explicitly add any nullptrs to it.

🔗

The implementation for this is shown below. Much of this code is similar to the Person class we used on the previous page, here are the key new features:

getMother and getChild both return Person*s as we want to return the memory address to the appropriate object instead of a copy of the object. If getMother looked like Person getMother() const it would return a copy of the object that m_mother points at.
🔗

🔗
getChild takes a parameter to specify which child to retrieve. The parameter is a size_t (not an int) as we will use it to specify a location in the vector.
🔗

🔗
setMother is similar to the marry function from our spouse sample. When we set a Person’s mother, we also make sure that the mother object has the child Person in their list of children. mother->m_children.push_back(this) tells the mother object to add the current object to its list of children.
🔗

🔗
print checks the Person being printed to see if they have a mother and/or children. If so, it prints out the names of those objects.
🔗

🔗

Other than noting those features, don’t worry about reading the code too closely.

🔗

Listing 18.13.1. Person.cxx

🔗

module;

#include <iostream>
#include <string>
#include <vector>

export module Person;

using namespace std;

export class Person {
private:
    string m_name;
    Person* m_mother;
    vector<Person*> m_children;

public:
    Person(const string& name);
    void setName(const string& name);

    Person* getMother() const;
    void setMother(Person* mother);

    bool hasChildren() const;
    Person* getChild(size_t childNum) const;

    void print() const;
};

Person::Person(const string& name) : m_name(name) {
    // m_name = name;
    m_mother = nullptr;
    // vector starts empty by default
}

void Person::setName(const string& name) {
    m_name = name;
}

Person* Person::getMother() const {
  return m_mother;
}

void Person::setMother(Person* mother) {
  m_mother = mother;
  mother->m_children.push_back(this);
}

bool Person::hasChildren() const {
  return m_children.size() > 0;
}

Person* Person::getChild(size_t childNum) const {
    // The vector will throw an exception if the index is out of bounds
    return m_children.at(childNum);
}

void Person::print() const {
    cout << "Person: " << m_name;
    if (m_mother) {
        cout << " Mother is: " << m_mother->m_name;
    }
    if (hasChildren()) {
        cout << ", Children: ";
        for (Person* child : m_children) {
            cout << child->m_name << " ";
        }
    }
    cout << endl;
}

To work with this class, we will need to set up some Persons and establish links between them. The figure below shows the relations we will set up. Each person has an arrow pointing at their mother, which corresponds to the `m_mother. (This is not a true memory diagram - it does not visualize the pointers that point back at the children from the mother.)

🔗

Henry and George have Fay as mother. Fay has Erin as Mother. Erin has Diana as mother. Diana, Carl and Bob have Anna as mother.

        stateDiagram-v2
          direction BT
          Anna: Anna (p0)
          Bob: Bob (p1)
          Carl: Carl (p2)
          Diana: Diana (p3)
          Erin: Erin (p4)
          Fay: Fay (p5)
          George: George (p6)
          Henry: Henry (p7)
          Bob --> Anna
          Carl --> Anna
          Diana --> Anna
          Erin --> Diana
          Fay --> Erin
          George --> Fay
          Henry --> Fay

Figure 18.13.2. The family relations set up in the programs below.

🔗

The first program sets up this family tree in lines 9-25. It then prints out some of the Persons, changes one of their names, and prints again.

🔗

Listing 18.13.3.

🔗

Notice that because we are using aggregation, when we change Fay’s name to Fiona (line 32), the Henry object “sees” the change. On line 35, as we print out Henry, we see

🔗

Note 18.13.1.

Recall that this is the key distinction of storing a Person* as the m_mother instead of a Person object. Because we are using Person*s, objects “see” changes that are made to the object that was set as their m_mother. If the Henry object stored a Person, it would make a copy of the Fay object when their relationship was set up. In that case, the Henry object would never “see” future changes to the Fay object.

🔗

Now let’s get trickier. We are going to try to navigating all the way from Henry up to the top of the family tree (a person with no known mother).

🔗

To do this, we need a way to track “the current person”. However, we need to be careful about how we do this. If we use a Person object to store “the current person”, we will be making a copy of whatever Person we assign to it. But we do not want to make a copies of any Person once the family is set up. There should only ever be one “Henry” (the variable named p7) in the program.We need currentPerson to be an alias for one of the existing Person objects, and not a new Person. Thus we will make Person* currentPerson. Using that, we can point at p7 and have access to the Henry object without copying it.

🔗

This program starts with the same family set up code. Skip past it and examine lines 28+. They set up some pointers to point to Henry and his ancestors.

🔗

Listing 18.13.4.

🔗

Rather than write out each next step in accessing Henry’s ancestors by hand, we could use a loop to “walk up” the family tree. The next program does exactly that. It reuse the currentPerson pointer to always store the person we are currently at. To “step up” the tree, we can change the currentPerson to be the mother of the old currentPerson. Once the currentPerson is null, we know we have run out of family members!

🔗

Listing 18.13.5.

🔗

#include <iostream>
#include <iostream>

import Person;

using namespace std;

int main() {
    Person p0("Anna");
    Person p1("Bob");
    Person p2("Carl");
    Person p3("Diana");
    Person p4("Erin");
    Person p5("Fay");
    Person p6("George");
    Person p7("Henry");

// Set up family relationships
    p1.setMother(&p0);
    p2.setMother(&p0);
    p3.setMother(&p0);
    p4.setMother(&p3);
    p5.setMother(&p4);
    p6.setMother(&p5);
    p7.setMother(&p5);

// Print some Person objects
    Person* currentPerson = &p7;

while (currentPerson != nullptr) {
        //Print the current person's information
        cout << "-------------------------" << endl;
        cout << "Current Person address is " << currentPerson << endl;
        cout << "They are: ";
        currentPerson->print();
        // Get the mother of the current person
        Person* currentMother = currentPerson->getMother();
        cout << "Their mother's address is " << currentMother << endl;
        // Change the current person pointer to point to the mother
        currentPerson = currentMother;
    }
    cout << "Reached the top of the family tree." << endl;
}

The tricky bit is the last line of the loop (40). We change the memory address stored in currentPerson to be a copy of the address stored in currentMother. This updates the currentPerson pointer to point at the mother of the old currentPerson. Then, we bounce up to the start of the loop to check if we have reached an unknown mother (nullptr) - that will be our sign that we have reached the top of the tree and it is time to stop.

🔗

Checkpoint 18.13.1.

Construct a Person function getSiblings that returns a vector containing all of the siblings of the current Person. If the current Person’s mother is unknown, we will return an empty vector.

🔗

vector<Person*> Person::getSiblings() const {
---
    vector<Person*> sibs;
---
    if (m_mother) {
---
        for (Person* kid : m_mother->m_children) {
---
            if (kid != this) {
---
                sibs.push_back(kid);
---
            }
        }
    }
---
    return sibs;
---
}

🔗

You have attempted of activities on this page.

🔗

Prev Top Next