1"""Provides utility functions for unit testing."""
2
3from ..pygraph import (DirectedGraph, UndirectedGraph,
4                     build_triangle_graph, build_k5_graph, build_k33_graph, build_5_cycle_graph,
5                     merge_graphs)
6
7
8def build_simple_test_graph(directed=False):
9    """Builds a simple undirected graph that gets used for testing."""
10    if directed:
11        graph = DirectedGraph()
12    else:
13        graph = UndirectedGraph()
14
15    # There are 7 vertices in the test graph
16    for _ in range(7):
17        graph.new_node()
18
19    # There are 4 edges in the test graph
20    # --Edge: a
21    graph.new_edge(1, 2)
22    # --Edge: b
23    graph.new_edge(1, 4)
24    # --Edge: c
25    graph.new_edge(2, 5)
26    # --Edge: d
27    graph.new_edge(6, 7)
28
29    return graph
30
31
32def build_single_node_graph(directed=False):
33    """Builds a graph with a single node for testing."""
34    if directed:
35        graph = DirectedGraph()
36    else:
37        graph = UndirectedGraph()
38    graph.new_node()
39
40    return graph
41
42
43def build_2_node_graph(directed=False):
44    """Builds a 2-node connected graph for testing."""
45    if directed:
46        graph = DirectedGraph()
47    else:
48        graph = UndirectedGraph()
49
50    graph.new_node()
51    graph.new_node()
52    graph.new_edge(1, 2)
53
54    return graph
55
56
57def build_3_node_line_graph(directed=False):
58    """Builds a 3-node, 2-edge connected line graph for testing."""
59    if directed:
60        graph = DirectedGraph()
61    else:
62        graph = UndirectedGraph()
63
64    graph.new_node()
65    graph.new_node()
66    graph.new_node()
67
68    graph.new_edge(1, 2)
69    graph.new_edge(2, 3)
70
71    return graph
72
73
74def build_3_node_line_root_articulation_graph(directed=False):
75    """Builds a 3-node, 2-edge connected line graph for testing, where the root node is the articulation vertex."""
76    if directed:
77        graph = DirectedGraph()
78    else:
79        graph = UndirectedGraph()
80
81    graph.new_node()
82    graph.new_node()
83    graph.new_node()
84
85    graph.new_edge(1, 2)
86    graph.new_edge(1, 3)
87
88    return graph
89
90
91def build_biconnected_test_graph(directed=False):
92    """Builds a graph with multiple biconnected components that gets used for testing."""
93    if directed:
94        graph = DirectedGraph()
95    else:
96        graph = UndirectedGraph()
97
98    # There are 12 vertices in the test graph
99    for _ in range(12):
100        graph.new_node()
101
102    # Nodes 1,2,3 form the first component
103    graph.new_edge(1, 2)
104    graph.new_edge(1, 3)
105    graph.new_edge(2, 3)
106
107    # Nodes 4,5,6,7 form the second component
108    graph.new_edge(4, 5)
109    graph.new_edge(4, 6)
110    graph.new_edge(5, 6)
111    graph.new_edge(5, 7)
112    graph.new_edge(6, 7)
113
114    # Nodes 8,9,10,11,12 form the third component
115    graph.new_edge(8, 9)
116    graph.new_edge(8, 10)
117    graph.new_edge(8, 11)
118    graph.new_edge(8, 12)
119    graph.new_edge(9, 10)
120    graph.new_edge(10, 11)
121    graph.new_edge(10, 12)
122    graph.new_edge(11, 12)
123
124    # Nodes 2 and 5 connect the first and second components
125    graph.new_edge(2, 5)
126
127    # Nodes 7 and 8 connect the second and third components
128    graph.new_edge(7, 8)
129
130    return graph
131
132
133def build_fully_biconnected_test_graph():
134    """Builds a graph with only one biconnected component that gets used for testing."""
135    graph = build_biconnected_test_graph()
136
137    # Connect the first and third components to create a ring, converting everything into a single biconnected component
138    graph.new_edge(1, 12)
139
140    return graph
141
142
143def build_disconnected_test_graph():
144    """Builds a graph with three disconnected components that gets used for testing."""
145    graph = build_triangle_graph()
146    g2 = build_triangle_graph()
147    g3 = build_triangle_graph()
148
149    merge_graphs(graph, g2)
150    merge_graphs(graph, g3)
151
152    return graph
153
154
155def build_triangle_graph_with_costs(directed=False):
156    """Builds a triangle graph with costs for testing."""
157    if directed:
158        graph = DirectedGraph()
159    else:
160        graph = UndirectedGraph()
161
162    graph.new_node()
163    graph.new_node()
164    graph.new_node()
165
166    graph.new_edge(1, 2, 1)
167    graph.new_edge(2, 3, 2)
168    graph.new_edge(3, 1, 10)
169
170    return graph
171
172
173def build_square_test_graph_with_costs(directed=False):
174    """Builds a square graph with costs for testing."""
175    if directed:
176        graph = DirectedGraph()
177    else:
178        graph = UndirectedGraph()
179
180    graph.new_node()
181    graph.new_node()
182    graph.new_node()
183    graph.new_node()
184    graph.new_edge(1, 2, 2)
185    graph.new_edge(1, 4, 10)
186    graph.new_edge(2, 3, 3)
187    graph.new_edge(3, 4, 1)
188
189    return graph
190
191
192def build_complicated_test_graph_with_one_mst(directed=False):
193    """Builds a test graph that has a unique minimum spanning tree."""
194    if directed:
195        graph = DirectedGraph()
196    else:
197        graph = UndirectedGraph()
198
199    for _ in range(7):
200        graph.new_node()
201
202    graph.new_edge(1, 2, 2)  # 1
203    graph.new_edge(1, 3, 4)  # 2
204    graph.new_edge(1, 4, 1)  # 3
205    graph.new_edge(2, 4, 3)  # 4
206    graph.new_edge(2, 5, 10)  # 5
207    graph.new_edge(3, 4, 2)  # 6
208    graph.new_edge(3, 6, 5)  # 7
209    graph.new_edge(4, 5, 7)  # 8
210    graph.new_edge(4, 6, 8)  # 9
211    graph.new_edge(4, 7, 4)  # 10
212    graph.new_edge(5, 7, 6)  # 11
213    graph.new_edge(6, 7, 1)  # 12
214
215    return graph
216
217
218def build_non_planar_test_graph_with_k5_subgraph():
219    """Builds a test graph that contains K5 as a subgraph, and is thus non-planar."""
220    graph = build_triangle_graph()
221    addition_graph = build_k5_graph()
222
223    merge_graphs(graph, addition_graph)
224
225    return graph
226
227
228def build_non_planar_test_graph_with_k33_subgraph():
229    """Builds a test graph that contains K3,3 as a subgraph, and is thus non-planar."""
230    graph = build_triangle_graph()
231    addition_graph = build_k33_graph()
232
233    merge_graphs(graph, addition_graph)
234
235    return graph
236
237
238def build_non_planar_disconnected_test_graph_with_k5_subgraph():
239    """Builds a disconnected test graph that contains K5 as a subgraph, and is thus non-planar."""
240    graph = build_triangle_graph()
241    addition_graph = build_k5_graph()
242    addition_graph2 = build_k5_graph()
243
244    merge_graphs(graph, addition_graph)
245    merge_graphs(graph, addition_graph2)
246
247    return graph
248
249
250def build_petersons_graph():
251    """Builds a non-planar test graph that does not contain K5 or K3,3 as a subgraph (Peterson's Graph).
252       Ref: http://mathworld.wolfram.com/PetersenGraph.html"""
253    graph = build_5_cycle_graph()
254
255    # --Build a 5-pointed star
256    for _ in range(5):
257        graph.new_node()
258    graph.new_edge(6, 8)
259    graph.new_edge(6, 9)
260    graph.new_edge(7, 9)
261    graph.new_edge(7, 10)
262    graph.new_edge(8, 10)
263
264    # --Connect it to the outside 5-cycle graph
265    graph.new_edge(1, 6)
266    graph.new_edge(2, 7)
267    graph.new_edge(3, 8)
268    graph.new_edge(4, 9)
269    graph.new_edge(5, 10)
270
271    return graph
272