import sys, os, math, unittest
sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
from bellman_ford import bellman_ford, reconstruct_path


class TestBellmanFord(unittest.TestCase):
    def test_simple(self):
        edges = [(0,1,4),(0,2,1),(2,1,2),(1,3,1),(2,3,5)]
        dist, parent, neg = bellman_ford(edges, 4, 0)
        self.assertFalse(neg)
        self.assertEqual(dist[0], 0)
        self.assertEqual(dist[2], 1)
        self.assertEqual(dist[1], 3)
        self.assertEqual(dist[3], 4)

    def test_negative_edges(self):
        edges = [(0,1,4),(0,2,5),(1,2,-3),(2,3,4),(1,3,6)]
        dist, parent, neg = bellman_ford(edges, 4, 0)
        self.assertFalse(neg)
        self.assertEqual(dist[2], 1)  # 0->1->2 = 4-3=1
        self.assertEqual(dist[3], 5)  # 0->1->2->3 = 1+4=5

    def test_negative_cycle(self):
        edges = [(0,1,1),(1,2,-1),(2,0,-1)]  # cycle sum -1
        dist, parent, neg = bellman_ford(edges, 3, 0)
        self.assertTrue(neg)

    def test_no_negative_cycle_unreachable(self):
        edges = [(0,1,2),(2,3,-5),(3,2,1)]  # cycle in comp 2 not reachable
        dist, parent, neg = bellman_ford(edges, 4, 0)
        self.assertFalse(neg)
        self.assertEqual(dist[2], float("inf"))

    def test_path_reconstruct(self):
        edges = [(0,1,4),(0,2,1),(2,1,2)]
        dist, parent, neg = bellman_ford(edges, 3, 0)
        self.assertEqual(reconstruct_path(parent, 0, 1), [0,2,1])

    def test_single_vertex(self):
        dist, parent, neg = bellman_ford([], 1, 0)
        self.assertFalse(neg)
        self.assertEqual(dist[0], 0)

    def test_unreachable(self):
        edges = [(0,1,5)]
        dist, parent, neg = bellman_ford(edges, 3, 0)
        self.assertEqual(dist[2], float("inf"))

    def test_zero_weight(self):
        edges = [(0,1,0),(1,2,0)]
        dist, parent, neg = bellman_ford(edges, 3, 0)
        self.assertEqual(dist[2], 0)
        self.assertFalse(neg)


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