path: root/users/wpcarro/scratch/data_structures_and_algorithms/mesh-message.py

import unittest
from collections import deque


################################################################################
# Solution
################################################################################
# get_path :: G(V, E) -> V -> V -> Maybe([V])
def get_path(g, src, dst):
    q = deque()
    result = None
    seen = set()
    q.append(([], src))

    if src not in g or dst not in g:
        raise Exception

    while q:
        p, node = q.popleft()

        seen.add(node)

        if node == dst:
            if not result:
                result = p + [node]
            elif len(p + [node]) < len(result):
                result = p + [node]
        else:
            if node not in g:
                raise Exception
            for x in g.get(node):
                if not x in seen:
                    q.append((p + [node], x))

    return result


################################################################################
# Tests
################################################################################
class Test(unittest.TestCase):
    def setUp(self):
        self.graph = {
            'a': ['b', 'c', 'd'],
            'b': ['a', 'd'],
            'c': ['a', 'e'],
            'd': ['a', 'b'],
            'e': ['c'],
            'f': ['g'],
            'g': ['f'],
        }

    def test_two_hop_path_1(self):
        actual = get_path(self.graph, 'a', 'e')
        expected = ['a', 'c', 'e']
        self.assertEqual(actual, expected)

    def test_two_hop_path_2(self):
        actual = get_path(self.graph, 'd', 'c')
        expected = ['d', 'a', 'c']
        self.assertEqual(actual, expected)

    def test_one_hop_path_1(self):
        actual = get_path(self.graph, 'a', 'c')
        expected = ['a', 'c']
        self.assertEqual(actual, expected)

    def test_one_hop_path_2(self):
        actual = get_path(self.graph, 'f', 'g')
        expected = ['f', 'g']
        self.assertEqual(actual, expected)

    def test_one_hop_path_3(self):
        actual = get_path(self.graph, 'g', 'f')
        expected = ['g', 'f']
        self.assertEqual(actual, expected)

    def test_zero_hop_path(self):
        actual = get_path(self.graph, 'a', 'a')
        expected = ['a']
        self.assertEqual(actual, expected)

    def test_no_path(self):
        actual = get_path(self.graph, 'a', 'f')
        expected = None
        self.assertEqual(actual, expected)

    def test_start_node_not_present(self):
        with self.assertRaises(Exception):
            get_path(self.graph, 'h', 'a')

    def test_end_node_not_present(self):
        with self.assertRaises(Exception):
            get_path(self.graph, 'a', 'h')


unittest.main(verbosity=2)