# File: test_dijkstra_spt.py

from unittest import TestCase, main
from dijkstra import dijkstra_spt, WeightedGraph


biggie: WeightedGraph = {
    'A': {('B', 4), ('E', 8)},
    'B': {('A', 4), ('E', 11), ('C', 8)},
    'C': {('B', 8), ('I', 2), ('G', 4), ('D', 7)},
    'D': {('C', 7), ('G', 14), ('H', 9)},
    'E': {('A', 8), ('B', 11), ('I', 7), ('F', 1)},
    'F': {('E', 1), ('I', 6), ('G', 2)},
    'G': {('F', 2), ('C', 4), ('D', 14), ('H', 10)},
    'H': {('D', 9), ('G', 10)},
    'I': {('C', 2), ('E', 7), ('F', 6)},
}


class Testdijkstra_spt(TestCase):

    def test_dijkstra_spt_1(self):
        self.assertEqual(
            ({'A': 0, 'B': 1},
             {'A': {('B', 1)},
              'B': {('A', 1)}}),
            dijkstra_spt('A', {
                'A': {('B', 1)},
                'B': {('A', 1)}
            }))

    def test_dijkstra_spt_2(self):
        self.assertEqual(
            ({'A': 0, 'B': 1, 'C': 1},
             {'A': {('B', 1), ('C', 1)},
              'B': {('A', 1)},
              'C': {('A', 1)}}),
            dijkstra_spt('A', {
                'A': {('B', 1), ('C', 1)},
                'B': {('A', 1), ('C', 2)},
                'C': {('A', 1), ('B', 2)},
            }))

    def test_dijkstra_spt_3(self):
        self.assertEqual(
            ({'A': 1, 'B': 1, 'C': 1, 'D': 1, 'E': 0},
             {'A': {('E', 1)},
              'B': {('E', 1)},
              'C': {('E', 1)},
              'D': {('E', 1)},
              'E': {('A', 1), ('B', 1), ('C', 1), ('D', 1)}}),
            dijkstra_spt('E', {
                'A': {('B', 1), ('C', 1), ('D', 1), ('E', 1)},
                'B': {('A', 1), ('C', 1), ('D', 1), ('E', 1)},
                'C': {('A', 1), ('B', 1), ('D', 1), ('E', 1)},
                'D': {('A', 1), ('B', 1), ('C', 1), ('E', 1)},
                'E': {('A', 1), ('B', 1), ('C', 1), ('D', 1)}
            }))

    def test_dijkstra_spt_4(self):
        self.assertEqual(
            ({'A': 0, 'B': 1, 'C': 3, 'D': 6, 'E': 10},
             {'A': {('B', 1)},
              'B': {('A', 1), ('C', 2)},
              'C': {('B', 2), ('D', 3)},
              'D': {('C', 3), ('E', 4)},
              'E': {('D', 4)}}),
            dijkstra_spt('A', {
                'A': {('B', 1)},
                'B': {('A', 1), ('C', 2)},
                'C': {('B', 2), ('D', 3)},
                'D': {('C', 3), ('E', 4)},
                'E': {('D', 4)}
            }))

    def test_dijkstra_spt_5(self):
        self.assertEqual(
            ({'A': 6, 'B': 4, 'C': 5, 'D': 1, 'E': 0},
             {'A': {('B', 2)},
              'B': {('A', 2), ('D', 3)},
              'C': {('E', 5)},
              'D': {('B', 3), ('E', 1)},
              'E': {('C', 5), ('D', 1)}}),
            dijkstra_spt('E', {
                'A': {('B', 2), ('C', 4)},
                'B': {('A', 2), ('D', 3)},
                'C': {('A', 4), ('E', 5)},
                'D': {('B', 3), ('E', 1)},
                'E': {('C', 5), ('D', 1)}
            }))

    def test_dijkstra_spt_6(self):
        self.assertEqual(
            ({'A': 0, 'B': 5, 'C': 8, 'D': 7, 'E': 6},
             {'A': {('B', 5), ('E', 6)},
              'B': {('A', 5), ('D', 2)},
              'C': {('D', 1)},
              'D': {('B', 2), ('C', 1)},
              'E': {('A', 6)}}),
            dijkstra_spt('A', {
                'A': {('B', 5), ('C', 10), ('E', 6)},
                'B': {('A', 5), ('D', 2)},
                'C': {('A', 10), ('D', 1), ('E', 3)},
                'D': {('B', 2), ('C', 1), ('E', 4)},
                'E': {('A', 6), ('C', 3), ('D', 4)},
            }))

    def test_dijkstra_spt_7(self):
        self.assertEqual(
            ({'A': 0, 'B': 4, 'C': 12, 'D': 19, 'E': 8, 'F': 9,
              'G': 11, 'H': 21, 'I': 14},
             {'A': {('B', 4), ('E', 8)},
              'B': {('A', 4), ('C', 8)},
              'C': {('B', 8), ('D', 7), ('I', 2)},
              'D': {('C', 7)},
              'E': {('A', 8), ('F', 1)},
              'F': {('E', 1), ('G', 2)},
              'G': {('F', 2), ('H', 10)},
              'H': {('G', 10)},
              'I': {('C', 2)}}),
            dijkstra_spt('A', biggie))

    def test_dijkstra_spt_8(self):
        self.assertEqual(
            ({'A': 19, 'B': 15, 'C': 7, 'D': 0, 'E': 14, 'F': 13,
              'G': 11, 'H': 9, 'I': 9},
             {'A': {('B', 4)},
              'B': {('A', 4), ('C', 8)},
              'C': {('B', 8), ('D', 7), ('G', 4), ('I', 2)},
              'D': {('C', 7), ('H', 9)},
              'E': {('F', 1)},
              'F': {('E', 1), ('G', 2)},
              'G': {('C', 4), ('F', 2)},
              'H': {('D', 9)},
              'I': {('C', 2)}}),
            dijkstra_spt('D', biggie))

    def test_dijkstra_spt_9(self):
        self.assertEqual(
            ({'A': 21, 'B': 22, 'C': 14, 'D': 9, 'E': 13, 'F': 12,
              'G': 10, 'H': 0, 'I': 16},
             {'A': {('E', 8)},
              'B': {('C', 8)},
              'C': {('G', 4), ('B', 8), ('I', 2)},
              'D': {('H', 9)},
              'E': {('F', 1), ('A', 8)},
              'F': {('E', 1), ('G', 2)},
              'G': {('C', 4), ('H', 10), ('F', 2)},
              'H': {('D', 9), ('G', 10)},
              'I': {('C', 2)}}),
            dijkstra_spt('H', biggie))

    def test_dijkstra_spt_10(self):
        self.assertEqual(
            ({'A': 14, 'B': 10, 'C': 2, 'D': 9, 'E': 7, 'F': 6,
              'G': 6, 'H': 16, 'I': 0},
             {'A': {('B', 4)},
              'B': {('A', 4), ('C', 8)},
              'C': {('B', 8), ('D', 7), ('G', 4), ('I', 2)},
              'D': {('C', 7)},
              'E': {('I', 7)},
              'F': {('I', 6)},
              'G': {('C', 4), ('H', 10)},
              'H': {('G', 10)},
              'I': {('C', 2), ('E', 7), ('F', 6)}}),
            dijkstra_spt('I', biggie))


if __name__ == '__main__':
    main()