freecodecamp-pythonv9/adjancyListToMatrix.py at main · Definitly-Not-Me/freecodecamp-pythonv9 · GitHub

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
"""
Skip to content
Profile

    Python Certification
    Build an Adjacency List to Matrix Converter

Build an Adjacency List to Matrix Converter

In this lab, you will build a function that converts an adjacency list representation of a graph into an adjacency matrix. An adjacency list is a dictionary where each key represents a node, and the corresponding value is a list of nodes that the key node is connected to. An adjacency matrix is a 2D array where the entry at position [i][j] is 1 if there's an edge from node i to node j, and 0 otherwise.

For example, given the adjacency list:

{
    0: [1, 2],
    1: [2],
    2: [0, 3],
    3: [2]
}

The corresponding adjacency matrix would be:

[
    [0, 1, 1, 0],
    [0, 0, 1, 0],
    [1, 0, 0, 1],
    [0, 0, 1, 0]
]

Objective: Fulfill the user stories below and get all the tests to pass to complete the lab.

User Stories:

    You should define a function named adjacency_list_to_matrix to convert an adjacency list to an adjacency matrix.
    The function should take a dictionary representing the adjacency list of an unweighted (either undirected or directed) graph as its argument.
    The function should:
        Convert the adjacency list to an adjacency matrix.
        Print each row in the adjacency matrix.
        Return the adjacency matrix.

For example, adjacency_list_to_matrix({0: [2], 1: [2, 3], 2: [0, 1, 3], 3: [1, 2]}) should print:

[0, 0, 1, 0]
[0, 0, 1, 1]
[1, 1, 0, 1]
[0, 1, 1, 0]

and return [[0, 0, 1, 0], [0, 0, 1, 1], [1, 1, 0, 1], [0, 1, 1, 0]].
Tests:

    Waiting: 1. You should define a function named adjacency_list_to_matrix.
    Waiting: 2. The adjacency_list_to_matrix function should have one parameter.
    Waiting: 3. The function should correctly determine the number of nodes from the adjacency list.
    Waiting: 4. The function should correctly set matrix values to 1 for existing edges.
    Waiting: 5. The function should print each row of the matrix.
    Waiting: 6. The function should return the adjacency matrix.
    Waiting: 7. When given the adjacency list {0: [1, 2], 1: [2], 2: [0, 3], 3: [2]}, the function should return [[0, 1, 1, 0], [0, 0, 1, 0], [1, 0, 0, 1], [0, 0, 1, 0]].
    Waiting: 8. When given the adjacency list {0: [1], 1: [0]}, the function should return [[0, 1], [1, 0]].
    Waiting: 9. When given the adjacency list {0: [], 1: [], 2: []}, the function should return [[0, 0, 0], [0, 0, 0], [0, 0, 0]].


"""

def adjacency_list_to_matrix(adjList : dict) -> list[list[int]]:
    nodes_num = len(adjList)
    adjMatrix = [[0]*nodes_num for i in range(nodes_num)]
    for node, neighboors_list in adjList.items():
        row = adjMatrix[node]
        for i in neighboors_list:
            row[i] = 1

    return adjMatrix

def adjToMatrix(adjList: dict) -> list[list[int]]:
    n = len(adjList)
    adjMatrix = [[] for _ in range(n)]
    for i in range(n):
        row = adjMatrix[i]
        row = [(1 if j in adjList[i] else 0) for j in range(n)]
        print(row)
    return adjMatrix
adjToMatrix(
{
    0: [1, 2],
    1: [2],
    2: [0, 3],
    3: [2]
})