popular

Language/Type: C++ graphs collections
Author: Marty Stepp (on 2016/06/16)

Write a function named `popular` that accepts a reference to a `BasicGraph` as a parameter and returns a `Set` of pointers to all vertexes in that graph that are "popular" by the following definition. Suppose that the graph represents users on a social network such as Facebook. A vertex represents a user, and a directed edge from A to B represents the fact that user A "likes" user B, or is "friends" with B. The weight of the edge represents how much A "likes" B.

A user v is "popular" if all of the following conditions are met:

• At least 2 other users "like" v.
• More users "like" v than v "likes" other users. (More arrows are coming in than going out.)
• The combined weight of all "likes" toward v is more than the combined outbound weight of all the edges to other users that v "likes". (More total edge weight is coming in than going out.)

For example, in the graph below, vertex B is "popular" because vertexes A, C, and E "like" him with a combined weight of 3+2+4=9, while he "likes" only vertex E with a weight of 4. For this particular example graph, your function would return the set of vertexes representing `{B, F, G}`.

Constraints: You may not construct any auxiliary collections to solve this problem, other than the Set to return; but you may create as many simple variables as you like. You should not modify the state of the graph passed in. You may assume that the graph's state is valid at the start of the call.

```     3       2
A ----> B <---- C
|       ^       |
2|       |       |
|       |4      |2
V   5   V   1   V
D ----> E <---> F
|       |
1|       |4
|       |
V   3   V          2
G <---- H       I ---> J
```
Type your C++ solution code here:

This is a function problem. Write a C++ function as described. Do not write a complete program; just the function(s) above.