Challenge 152 - Finding Adjacent Nodes

challenge_152.md

Challenge 152 - Finding Adjacent Nodes

A graph is a set of nodes and edges that connect those nodes.

There are two types of graphs; directed and undirected. In an undirected graph, the edges between nodes have no particular direction (like a two-way street) whereas in a directed graph, each edge has a direction associated with it (like a one-way street).

0 --- 1 --- 3
       \   /
        \ /
         2 

For two nodes in a graph to be considered adjacent to one another, there must be an edge between them. In the example given above, nodes 0 and 1 are adjacent, but nodes 0 and 2 are not.

We can encode graphs using an adjaceny matrix. An adjacency matrix for a graph with n nodes is an n x n matrix where the entry at row i and column j is a 0 if nodes i and j are not adjacent, and 1 if nodes i and j are adjacent.

For the example above, the adjacency matrix would be as follows:

#   0  1  2  3  Node edge goes to
[
  [ 0, 1, 0, 0 ],  # Node 0
  [ 1, 0, 1, 1 ],  # Node 1
  [ 0, 1, 0, 1 ],  # Node 2
  [ 0, 1, 1, 0 ]   # Node 3
]

A one indicates that a connection is True and a zero indicates a connection is False.

Here is how the above model might be written out:

• On the first row, node 0 does not connect to itself, but it does connect to node 1. It does not connect to node 2 or node 3. The row is written as 0, 1, 0, 0.
• On the second row, node 1 connects to node 0, node 2 and node 3, but it does not connect to itself. The row is written as 1, 0, 1, 1.
• On the third row, node 2 does not connect to node 0, but it does connect to node 1, does not connect to itself, and it does connect to node 3. The row is written as 0, 1, 0, 1.
• On the fourth row, node 3 does not connect to node 0, but it does connect to node 1 and node 2. It does not connect to itself. The row is written as 0, 1, 1, 0.

Your task is to write a function which determines if two nodes are adjacent in a graph when given the adjacency matrix and the two nodes.

Examples

Adjacency Matrix (for matrix above):

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

• Nodes 0,1 should return True.
• Nodes 0,2 should return False.

Graph Example 2

   0 --- 1
 / |     |
4  |     |
 \ |     |
   3 --- 2

[
  [ 0, 1, 0, 1, 1 ],  # Node 0
  [ 1, 0, 1, 0, 0 ],  # Node 1
  [ 0, 1, 0, 1, 0 ],  # Node 2
  [ 1, 0, 1, 0, 1 ],  # Node 3
  [ 1, 0, 0, 1, 0 ]   # Node 4
]

• Nodes 0,3 should return True.
• Nodes 1,4 should return False.

Notes

• Checkout the challenge on Edabit to see the graphs more clearly ;)

challenge_tests.py

from __future__ import annotations
import unittest


def is_adjacent(matrix: list[list[int]], node_1: int, node_2: int) -> bool:
    return False  # Put your code here!!!


class Test(unittest.TestCase):
    matrix1 = [[0, 1, 0, 0], [1, 0, 1, 1], [0, 1, 0, 1], [0, 1, 1, 0]]
    matrix2 = [[0, 1, 0, 1, 1], [1, 0, 1, 0, 0], [0, 1, 0, 1, 0], [1, 0, 1, 0, 1], [1, 0, 0, 1, 0]]

    def test_1(self):
        self.assertEqual(is_adjacent(self.matrix1, 0, 1), True)

    def test_2(self):
        self.assertEqual(is_adjacent(self.matrix1, 0, 2), False)

    def test_3(self):
        self.assertEqual(is_adjacent(self.matrix1, 2, 1), True)

    def test_4(self):
        self.assertEqual(is_adjacent(self.matrix2, 0, 3), True)

    def test_5(self):
        self.assertEqual(is_adjacent(self.matrix2, 1, 4), False)

    def test_6(self):
        self.assertEqual(is_adjacent(self.matrix2, 3, 2), True)


if __name__ == "__main__":
    unittest.main()

credits.md

Found on Edabit: Finding Adjacent Nodes