(E) Network marketing¶

Goal: I will learn to choose a suitable STL container and to implement a recursive algorithm.

Instructions: Retrieve the code template: templates/06/network/ -> student/06/network/.

Nelly the Network Marketer has a problem (in addition to being involved in network marketing). The idea of network marketing is that every marketer has recruited more people into the network. However, there is no record of the complete structure of the network. The only thing we know is which of the marketers recruited whom. Help Nelly figure out the structure of the network by writing a program that prints the network as a tree chart. The program should be able to calculate the depth and size of subnetworks as well.

The template includes a main program that reads and analyzes the input from the user. If you change the program code of the command interpreter, please make sure it works similarly to the original one.

Your task is to choose a suitable data structure for storing the data, and to implement the commands in the following way:

• S (i.e. store) is given two strings that are the identification details (e.g. names or ID numbers) of two people as its parameters. The first string is the identification details of the recruiter, and the second is the identification details of the recruited marketer. In other words, the first person is higher in the network than the second one. Each person can have any number of recruits under themselves. In this assignment, you can assume that the IDs will not loop with each other, meaning that the ID of a marketer can never be higher than its recruiter.
• P (i.e. print) is given one ID as its parameter. The program prints the subnetwork of the person having the given ID as their identifier. The first thing to print is the ID of the person in question. Below it and after a 2-period indent, the program prints the IDs of the marketers the first person has recruited, and below that, with a larger indent (additional 2 periods), the recruits of these marketers, et cetera. The persons are printed in the same order as they have been recruited in the network. If somebody has no recruits of their own or is not enlisted at all, the program only prints their ID.
• C (i.e. count) is given one ID as its parameter. The program prints this person’s subnetwork size, that is, the number of people in the subnetwork comprised of this person’s recruits.
• D (i.e. depth) is given one ID as its parameter. The program prints the depth of this person’s subnetwork, that is, the longest recruitment chain starting from this person.

An example of how to add people and print the network:

> S Hugo Laura
> S Hugo Jasper
> S Laura Helena
> S Jasper Maria
> S Laura Elias
> S Helena Sofia
> P Hugo
Hugo
..Laura
....Helena
......Sofia
....Elias
..Jasper
....Maria
> P Laura
Laura
..Helena
....Sofia
..Elias
> Q

Below, you can see an example of how to calculate the size of a subnetwork:

> S Hugo Laura
> S Hugo Jasper
> S Laura Helena
> S Jasper Maria
> S Laura Elias
> S Helena Sofia
> C Hugo
6
> C Laura
3
> C Helena
1
> C Sofia
0
> C Jasper
1
> Q

The example below shows you how to calculate the depth of the subnetwork:

> S Hugo Laura
> S Hugo Jasper
> S Laura Helena
> S Jasper Maria
> S Laura Elias
> S Helena Sofia
> D Hugo
4
> D Laura
3
> D Helena
2
> D Sofia
1
> D Jasper
2
> Q

Tips for completing the assignment:

• The data structure does not need to be recursive even if its contents can be interpreted recursively. The simplest way to solve this assignment is to use a data structure very similar to the data structures in the assignments of the previous round.
• The algorithms that handle the data structure (the implementations of the commands P, C and D) are easiest to create recursively. In the model solution, each of the commands has less than ten lines of code. If your solutions seem to grow significantly longer than that, you should probably think of alternative solutions to the problem.