"""Pruebas de los programas en C: dijkstra y dv_sim.""" import os import random import re import subprocess import tempfile import unittest from netlab import HERE def tool(name, *args): return subprocess.run([os.path.join(HERE, name), *args], capture_output=True, text=True, timeout=10, cwd=HERE) def forwarding_table(output): """Convierte la tabla final de dijkstra en {destino: (costo, conjunto de next hop)}.""" table = {} for line in output.split("forwarding table")[1].splitlines()[2:]: fields = line.split() table[fields[0]] = (fields[1], set(fields[2:])) return table def rounds_of(output): return int(re.search(r"volvió a converger: (\d+)", output).group(1)) def final_costs(output, dest_names): """Lee el último renglón de dv_sim --dest: {nodo: costo}.""" lines = [line for line in output.splitlines() if "=" in line and not line.startswith("---")] return {name: re.search(rf"\b{name}=(\w+)", lines[-1]).group(1) for name in dest_names} class DijkstraTest(unittest.TestCase): def test_table_of_the_chapter(self): table = forwarding_table(tool("dijkstra", "graphs/six.txt", "a").stdout) self.assertEqual(table, { "b": ("3", {"b"}), "c": ("1", {"c"}), "d": ("5", {"b"}), "e": ("6", {"b", "c"}), "f": ("8", {"b", "c"}), }) def test_iterations_of_the_chapter(self): out = tool("dijkstra", "graphs/six.txt", "a").stdout self.assertRegex(out, r"(?m)^1\s+ac\s") self.assertRegex(out, r"(?m)^2\s+acb\s") self.assertRegex(out, r"(?m)^3\s+acbd\s.*6,cd") self.assertRegex(out, r"(?m)^4\s+acbde\s.*8,e") def test_against_exhaustive_search_on_random_graphs(self): """Compara costos y next hop contra una búsqueda de todos los caminos simples.""" rng = random.Random(5) names = list("abcdefg") for _ in range(20): links = {} for i, left in enumerate(names): for right in names[i + 1:]: if rng.random() < 0.5: links[(left, right)] = rng.randint(1, 6) links[("a", "b")] = links.get(("a", "b"), 2) def neighbors(node): for (left, right), value in links.items(): if left == node: yield right, value elif right == node: yield left, value best = {} def explore(node, cost, path): if node != "a": known = best.get(node) if known is None or cost < known[0]: best[node] = (cost, {path[1]}) elif cost == known[0]: known[1].add(path[1]) for other, value in neighbors(node): if other not in path: explore(other, cost + value, path + [other]) explore("a", 0, ["a"]) with tempfile.NamedTemporaryFile("w", suffix=".txt") as graph: graph.writelines(f"{u} {v} {c}\n" for (u, v), c in links.items()) graph.flush() table = forwarding_table(tool("dijkstra", graph.name, "a").stdout) for node, (cost, hops) in best.items(): self.assertEqual(table[node], (str(cost), hops), f"{links} hacia {node}") def test_errors_are_reported(self): self.assertNotEqual(tool("dijkstra", "graphs/six.txt", "z").returncode, 0) missing = tool("dijkstra", "graphs/no_existe.txt", "a") self.assertNotEqual(missing.returncode, 0) self.assertIn("graphs/no_existe.txt", missing.stderr) class DistanceVectorTest(unittest.TestCase): def test_worked_example_rounds(self): out = tool("dv_sim", "graphs/four.txt").stdout self.assertIn("convergió: 2 rondas", out) # Después de la primera ronda, w cree que z le cuesta 10; después de la segunda, 6. first = out.split("ronda 1")[1].split("ronda 2")[0] second = out.split("ronda 2")[1] self.assertRegex(first, r"(?m)^w\s+0\s+2/x\s+5/x\s+10/x") self.assertRegex(second, r"(?m)^w\s+0\s+2/x\s+5/x\s+6/x") self.assertRegex(second, r"(?m)^z\s+6/y\s+4/y\s+1/y\s+0") def test_converges_to_the_same_costs_as_dijkstra(self): out = tool("dv_sim", "graphs/six.txt").stdout last = out.split("ronda ")[-1] row_a = re.search(r"(?m)^a\s+(.*)$", last).group(1).split() costs = [cell.split("/")[0] for cell in row_a] self.assertEqual(costs, ["0", "3", "1", "5", "6", "8"]) def test_count_to_infinity_in_a_line(self): out = tool("dv_sim", "graphs/line.txt", "--dest", "z", "--fail", "y", "z", "--order", "x:y,y:x").stdout self.assertIn("ciclo: x > y > x", out) self.assertGreaterEqual(rounds_of(out), 10) self.assertEqual(final_costs(out, "xy"), {"x": "inf", "y": "inf"}) def test_split_horizon_and_poison_reverse_fix_the_line(self): for mode in ("split", "poison"): out = tool("dv_sim", "graphs/line.txt", "--dest", "z", "--fail", "y", "z", "--order", "x:y,y:x", "--mode", mode).stdout self.assertNotIn("ciclo", out, mode) self.assertLessEqual(rounds_of(out), 2, mode) def test_poison_reverse_does_not_fix_the_triangle(self): for mode in ("split", "poison"): out = tool("dv_sim", "graphs/tail.txt", "--dest", "d", "--fail", "c", "d", "--mode", mode).stdout self.assertGreaterEqual(rounds_of(out), 10, mode) self.assertEqual(final_costs(out, "abc"), {"a": "inf", "b": "inf", "c": "inf"}, mode) def test_loop_of_three_survives_poison_reverse(self): out = tool("dv_sim", "graphs/tail.txt", "--dest", "d", "--fail", "c", "d", "--mode", "poison", "--order", "c:a,b:a,a:c,c:b").stdout self.assertIn("ciclo: a > b > c > a", out) def test_good_news_fast_bad_news_slow(self): good = tool("dv_sim", "graphs/triangle.txt", "--dest", "p", "--inf", "100", "--set", "p", "q", "1").stdout bad = tool("dv_sim", "graphs/triangle.txt", "--dest", "p", "--inf", "100", "--set", "p", "q", "20").stdout self.assertLessEqual(rounds_of(good), 2) self.assertGreaterEqual(rounds_of(bad), 8) self.assertEqual(final_costs(bad, "qr"), {"q": "20", "r": "21"}) def test_lie_pulls_traffic_toward_the_liar(self): out = tool("dv_sim", "graphs/six.txt", "--dest", "a", "--lie", "e", "a", "0").stdout self.assertRegex(out.splitlines()[-2], r"d=1/e\s+e=0\s+f=2/e") def test_errors_are_reported(self): self.assertNotEqual(tool("dv_sim", "graphs/no_existe.txt").returncode, 0) self.assertNotEqual(tool("dv_sim", "graphs/line.txt", "--mode", "x").returncode, 0) self.assertNotEqual(tool("dv_sim", "graphs/line.txt", "--fail", "y", "w").returncode, 0) if __name__ == "__main__": unittest.main()