Write a function named popular that accepts a reference to a BasicGraph as a parameter and returns a Set of strings representing the names of 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 {"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
