Week 05 Lab Solution

Graphs and Social Networks

Sample Solutions

Note: Answers for complexity analysis will vary depending on your implementation.

Note: Complexity analysis of complex data structures such as graphs often involves multiple variables to produce a more fine-grained analysis, for example, \(V\) for the number of vertices, \(E\) for the number of edges, \(d(v)\) for the degree of vertex \(v\) and so on. We only required you to analyse time complexity in terms of \(n\), where \(n\) is the number of people, so it is fine to take the worst case as the case where each person has the greatest possible number of friends, for example.

FbFriend
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
static struct adjNode *adjListInsert(struct adjNode *l, int v);

bool FbFriend(Fb fb, char *name1, char *name2) {
    int id1 = nameToId(fb, name1);
    int id2 = nameToId(fb, name2);
    assert(id1 != id2);

    if (!inAdjList(fb->adj[id1], id2)) {
        fb->adj[id1] = adjListInsert(fb->adj[id1], id2);
        fb->adj[id2] = adjListInsert(fb->adj[id2], id1);
        return true;
    } else {
        return false;
    }
}

static struct adjNode *adjListInsert(struct adjNode *l, int v) {
    if (l == NULL || v < l->v) {
        struct adjNode *new = newAdjNode(v);
        new->next = l;
        return new;
    } else if (v == l->v) {
        return l;
    } else {
        l->next = adjListInsert(l->next, v);
        return l;
    }
}

Worst case time complexity: \(O(n)\)

Explanation: The solution calls nameToId twice, checks if the two given people are friends, and then inserts each person into the other's adjacency list. nameToId is \(O(\log n)\), checking if two people are friends using inAdjList is \(O(n)\) in the worst case (if the length of the adjacency list is \(O(n)\)) and inserting into an adjacency list is also \(O(n)\) in the worst case. Thus, the worst-case time complexity is \(O(n)\).

FbNumFriends
1
2
3
4
5
6
7
8
9
int FbNumFriends(Fb fb, char *name) {
    int id = nameToId(fb, name);
    
    int numFriends = 0;
    for (struct adjNode *curr = fb->adj[id]; curr != NULL; curr = curr->next) {
        numFriends++;
    }
    return numFriends;
}

Worst case time complexity: \(O(n)\)

Explanation: The solution calls nameToId and iterates through the given person's adjacency list. nameToId is \(O(\log n)\), since it only calls MapContains and MapGet once each, and it is given that these functions are \(O(\log n)\). The length of the adjacency list is at most \(n - 1\) (if the person is friends with everyone else), so the time complexity of the loop is at worst \(O(n)\). Hence, the worst-case time complexity is \(O(n)\).

FbMutualFriends
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
List FbMutualFriends(Fb fb, char *name1, char *name2) {
    int id1 = nameToId(fb, name1);
    int id2 = nameToId(fb, name2);
    
    List l = ListNew();
    struct adjNode *curr1 = fb->adj[id1];
    struct adjNode *curr2 = fb->adj[id2];
    
    // takes advantage of the adjacency lists being in order
    while (curr1 != NULL && curr2 != NULL) {
        if (curr1->v == curr2->v) {
            ListAppend(l, fb->names[curr1->v]);
            curr1 = curr1->next;
            curr2 = curr2->next;
        } else if (curr1->v < curr2->v) {
            curr1 = curr1->next;
        } else {
            curr2 = curr2->next;
        }
    }
    return l;
}

Worst case time complexity: \(O(n)\)

Explanation: The solution calls nameToId twice, and then uses a single while loop to iterate through both people's adjacency lists, calling ListAppend for each mutual friend. Since the length of each adjacency list is at most \(n - 1\) and at least one list pointer is advanced every iteration, there are guaranteed to be fewer than \(2n\) iterations of the loop. It is given that ListAppend is \(O(1)\), so the time complexity of the loop is \(O(n)\). Thus, the worst-case time complexity is \(O(n)\).

FbUnfriend
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
static struct adjNode *adjListDelete(struct adjNode *l, int v);

bool FbUnfriend(Fb fb, char *name1, char *name2) {
    int id1 = nameToId(fb, name1);
    int id2 = nameToId(fb, name2);
    assert(id1 != id2);

    if (inAdjList(fb->adj[id1], id2)) {
        fb->adj[id1] = adjListDelete(fb->adj[id1], id2);
        fb->adj[id2] = adjListDelete(fb->adj[id2], id1);
        return true;
    } else {
        return false;
    }
}

// Recursive list delete
static struct adjNode *adjListDelete(struct adjNode *l, int v) {
    if (l == NULL || v < l->v) {
        return l;
    } else if (v == l->v) {
        struct adjNode *newHead = l->next;
        free(l);
        return newHead;
    } else {
        l->next = adjListDelete(l->next, v);
        return l;
    }
}
Note: Time complexity was not required for this task.

Worst case time complexity: \(O(n)\)

Explanation: The solution calls nameToId twice, checks if the two given people are friends, and then deletes each person from the other's adjacency list. nameToId is \(O(\log n)\), checking if two people are friends using inAdjList is \(O(n)\) in the worst case (if the length of the adjacency list is \(O(n)\)) and deleting from an adjacency list is also \(O(n)\) in the worst case. Thus, the worst-case time complexity is \(O(n)\).

FbFriendRecs1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int FbFriendRecs1(Fb fb, char *name, struct recommendation recs[]) {
    int id = nameToId(fb, name);

    // Collect mutual friend counts
    int *counts = calloc(fb->numPeople, sizeof(int));
    assert(counts != NULL); // lazy error checking

    struct adjNode *curr1 = fb->adj[id];
    for (; curr1 != NULL; curr1 = curr1->next) {
        struct adjNode *curr2 = fb->adj[curr1->v];
        for (; curr2 != NULL; curr2 = curr2->next) {
            counts[curr2->v]++;
        }
    }

    // Remove counts of friends
    counts[id] = 0;
    for (curr1 = fb->adj[id]; curr1 != NULL; curr1 = curr1->next) {
        counts[curr1->v] = 0;
    }

    // Add friend recommendations to array
    int numRecs = 0;
    for (int i = fb->numPeople - 2; i > 0; i--) {
        for (id = 0; id < fb->numPeople; id++) {
            if (counts[id] == i) {
                strcpy(recs[numRecs].name, fb->names[id]);
                recs[numRecs].numMutualFriends = i;
                numRecs++;
            }
        }
    }

    free(counts);
    return numRecs;
}

Worst case time complexity: \(O(n^2)\)

Explanation: Each part of the solution has at most two nested loops, each of which have at most \(n\) iterations. Thus, the worst-case time complexity is \(O(n^2)\).