-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathtest_main.py
170 lines (149 loc) · 7.47 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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
import networkx as nx
import pytest
from main import CopsAndRobbersGame, GameState, find_optimal_starting_vertices, find_damage_number
# 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),
# Graph where the cop starting on the centre allows the robber to damage more vertices than the damage number.
(
[
(2, 1),
(1, 10),
(10, 6),
(6, 8),
(8, 7),
(7, 3),
(3, 10),
(10, 9),
(9, 4),
(4, 3),
(4, 7),
(4, 5),
(5, 8),
(5, 6),
(5, 9),
],
10,
5,
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,
)
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}"
def test_find_optimal_starting_vertices_for_path():
graph = nx.Graph()
graph.add_edges_from([(0, 1), (1, 2), (2, 3), (3, 4), (4, 5)])
for node in graph.nodes:
graph.add_edge(node, node)
result = find_optimal_starting_vertices(graph)
assert result == [2, 3]
def test_find_optimal_starting_vertices_for_cycle():
graph = nx.Graph()
graph.add_edges_from([(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)])
for node in graph.nodes:
graph.add_edge(node, node)
result = find_optimal_starting_vertices(graph)
assert result == [0, 1, 2, 3, 4]
def test_find_damage_number_for_path():
graph = nx.Graph()
graph.add_edges_from([(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)])
for node in graph.nodes:
graph.add_edge(node, node)
result = find_damage_number(graph)
assert result == 2
def test_find_damage_number_for_cycle():
graph = nx.Graph()
graph.add_edges_from([(0, 1), (1, 2), (2, 3), (3, 0)])
for node in graph.nodes:
graph.add_edge(node, node)
result = find_damage_number(graph)
assert result == 1