-
Notifications
You must be signed in to change notification settings - Fork 0
/
test_main.py
105 lines (100 loc) · 5.93 KB
/
test_main.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
import networkx as nx
import pytest
from main import CopsAndRobbersGame, GameState
# Test cases defined as tuples of graph edges, cop position, robber position, and expected damage number.
test_cases = [
# Path graph with 3 vertices where cop and robber start on opposite ends.
([(0, 1), (1, 2)], 0, 2, 1),
# Path graph with 3 vertices where cop and robber start adjacent to each other.
([(0, 1), (1, 2)], 0, 1, 0),
# Path graph with 4 vertices where robber starts distance zero from cop.
([(0, 1), (1, 2), (2, 3)], 2, 2, 0),
# Path graph with 4 vertices where robber starts distance one from cop.
([(0, 1), (1, 2), (2, 3)], 1, 2, 0),
# Path graph with 4 vertices where robber starts distance two from cop.
([(0, 1), (1, 2), (2, 3)], 0, 2, 2),
# Path graph with 4 vertices where robber starts distance three from cop.
([(0, 1), (1, 2), (2, 3)], 0, 3, 1),
# Path graph with 5 vertices where cop and robber start on opposite ends.
([(0, 1), (1, 2), (2, 3), (3, 4)], 0, 4, 2),
# Path graph with 5 vertices where robber starts distance two from cop.
([(0, 1), (1, 2), (2, 3), (3, 4)], 0, 2, 3),
# Path graph with 5 vertices where robber starts distance two from cop.
([(0, 1), (1, 2), (2, 3), (3, 4)], 2, 4, 1),
# Path graph with 6 vertices.
([(0, 1), (1, 2), (2, 3), (3, 4), (4, 5)], 2, 4, 2),
# Path graph with 6 vertices where cop starts on a leaf and robber can damage vertices 2, 3, 4, and 5.
([(0, 1), (1, 2), (2, 3), (3, 4), (4, 5)], 0, 2, 4),
# 3-cycle.
([(0, 1), (1, 2), (2, 0)], 0, 1, 0),
# 4-cycle where cop and robber start adjacent.
([(0, 1), (1, 2), (2, 3), (3, 0)], 0, 1, 0),
# 4-cycle where cop and robber start opposite.
([(0, 1), (1, 2), (2, 3), (3, 0)], 1, 3, 1),
# 5-cycle where cop and robber start adjacent.
([(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)], 0, 1, 0),
# 5-cycle where cop and robber start distance 2 away.
([(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)], 0, 2, 2),
# 6-cycle where cop and robber start adjacent.
([(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 0)], 0, 1, 0),
# 6-cycle where cop and robber start distance 2 away.
([(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 0)], 0, 2, 2),
# 6-cycle where cop and robber start distance 3 away.
([(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 0)], 0, 3, 2),
# 7-cycle where cop and robber start distance 2 away.
([(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 0)], 0, 2, 3),
# 7-cycle where cop and robber start distance 3 away.
([(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 0)], 0, 3, 3),
# Star graph S_5 where the cop starts on the central vertex.
([(0, 1), (0, 2), (0, 3), (0, 4)], 0, 1, 0),
# Star graph S_5 where neither player starts on the central vertex.
([(0, 1), (0, 2), (0, 3), (0, 4)], 1, 2, 1),
# Complete graph K_4.
([(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)], 0, 1, 0),
# Balanced binary tree with 7 nodes (cop at root, robber at leaf).
([(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)], 0, 3, 1),
# Balanced binary tree with 7 nodes (cop and robber at leaf vertices within the same branch).
([(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)], 3, 4, 1),
# Balanced binary tree with 7 nodes (cop at leaf, robber at root).
([(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)], 3, 0, 3),
# Complete bipartite graph K_{3,3} where cop and robber start on different partitions.
([(0, 3), (0, 4), (0, 5), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5)], 0, 5, 0),
# Complete bipartite graph K_{3,3} where cop and robber start on the same partition.
([(0, 3), (0, 4), (0, 5), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5)], 0, 1, 1),
# Wheel graph W_6 where cop starts at 0 (central vertex) and robber starts at 3
([(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 2), (2, 3), (3, 4), (4, 5), (5, 1)], 0, 3, 0),
# A 3-barbell graph where cop and robber start distance 2 away from each other.
([(0, 1), (0, 2), (1, 2), (3, 4), (3, 5), (4, 5), (2, 3)], 2, 5, 1),
# A 3-barbell graph where cop and robber start distance 3 away from each other.
([(0, 1), (0, 2), (1, 2), (3, 4), (3, 5), (4, 5), (2, 3)], 0, 5, 2),
# A (4,3)-lollipop graph where the cop starts on the cut vertex of the clique.
([(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3), (3, 4), (4, 5), (5, 6)], 3, 5, 2),
# 3x3 Grid graph where cop starts in the centre and robber starts on a corner.
([(0, 1), (1, 2), (0, 3), (1, 4), (2, 5), (3, 4), (4, 5), (3, 6), (4, 7), (5, 8), (6, 7), (7, 8)], 4, 8, 1),
# Möbius ladder M4.
([(0, 1), (1, 2), (2, 3), (3, 0), (0, 2), (1, 3)], 0, 2, 0),
# Möbius ladder M6 where robber starts distance 2 away from the cop.
([(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 0), (0, 3), (1, 4), (2, 5)], 0, 4, 1),
# Möbius ladder M8 where cop starts at vertex 0 and robber starts at vertex 3.
([(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 0), (0, 4), (1, 5), (2, 6), (3, 7)], 0, 3, 4),
# Cubical graph where cop and robber start on opposite ends.
([(0, 1), (1, 2), (2, 3), (3, 0), (4, 5), (5, 6), (6, 7), (7, 4), (0, 4), (1, 5), (2, 6), (3, 7)], 0, 2, 2),
# 8-cycle where cop and robber start distance 2 away.
([(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 0)], 0, 2, 3),
]
@pytest.mark.parametrize("edges, cop_position, robber_position, expected_damage", test_cases)
def test_minimax(edges, cop_position, robber_position, expected_damage):
graph = nx.Graph()
graph.add_edges_from(edges)
for node in graph.nodes:
graph.add_edge(node, node)
initial_state = GameState(
cop_position=cop_position,
robber_position=robber_position,
damaged_vertices=frozenset(),
is_cop_turn=True,
)
visited = set()
game = CopsAndRobbersGame(graph, cop_position)
result = game.minimax(initial_state, visited)
assert result == expected_damage, f"Expected dmg(G) = {expected_damage} but got {result}"