20 Chapter 20 Solutions

Solution to Challenge 1

This solution uses the AdjacencyList API you built in this chapter. You can use any non-null weight, but a good default is 1.

final graph = AdjacencyList<String>();

final megan = graph.createVertex('Megan');
final sandra = graph.createVertex('Sandra');
final pablo = graph.createVertex('Pablo');
final edith = graph.createVertex('Edith');
final ray = graph.createVertex('Ray');
final luke = graph.createVertex('Luke');
final manda = graph.createVertex('Manda');
final vicki = graph.createVertex('Vicki');

graph.addEdge(megan, sandra, weight: 1);
graph.addEdge(megan, pablo, weight: 1);
graph.addEdge(megan, edith, weight: 1);
graph.addEdge(pablo, ray, weight: 1);
graph.addEdge(pablo, luke, weight: 1);
graph.addEdge(edith, manda, weight: 1);
graph.addEdge(edith, vicki, weight: 1);
graph.addEdge(manda, pablo, weight: 1);
graph.addEdge(manda, megan, weight: 1);

print(graph);

You can simply look at the graph to find the common friend:

Megan --> Sandra, Pablo, Edith, Manda
Sandra --> Megan
Pablo --> Megan, Ray, Luke, Manda
Edith --> Megan, Manda, Vicki
Ray --> Pablo
Luke --> Pablo
Manda --> Edith, Pablo, Megan
Vicki --> Edith

Turns out to be Manda, which was stated pretty directly in the question. :]

If you want to solve it programmatically, you can find the intersection of the set of Megan’s friends with the set of Pablo’s friends.

final megansFriends = Set.of(
  graph.edges(megan).map((edge) {
    return edge.destination.data;
  }),
);

final pablosFriends = Set.of(
  graph.edges(pablo).map((edge) {
    return edge.destination.data;
  }),
);

final mutualFriends = megansFriends.intersection(pablosFriends);