1"""Provides factory methods for building well-known, predefined graphs."""
2
3from .classes import UndirectedGraph
4from .helpers import create_graph_from_adjacency_matrix
5
6def build_cycle_graph(num_nodes):
7    """Builds a cycle graph with the specified number of nodes.
8       Ref: http://mathworld.wolfram.com/CycleGraph.html"""
9    graph = UndirectedGraph()
10
11    if num_nodes > 0:
12        first_node = graph.new_node()
13        if num_nodes > 1:
14            previous_node = first_node
15            for _ in range(num_nodes - 1):
16                new_node = graph.new_node()
17                graph.new_edge(previous_node, new_node)
18                previous_node = new_node
19            graph.new_edge(previous_node, first_node)
20
21    return graph
22
23
24def build_wheel_graph(num_nodes):
25    """Builds a wheel graph with the specified number of nodes.
26       Ref: http://mathworld.wolfram.com/WheelGraph.html"""
27    # The easiest way to build a wheel graph is to build
28    # C_n-1 and then add a hub node and spoke edges
29    graph = build_cycle_graph(num_nodes - 1)
30
31    cycle_graph_vertices = graph.get_all_node_ids()
32
33    node_id = graph.new_node()
34    for cycle_node in cycle_graph_vertices:
35        graph.new_edge(node_id, cycle_node)
36
37    return graph
38
39def build_triangle_graph():
40    """Builds a triangle graph, C3.
41       Ref: http://mathworld.wolfram.com/CycleGraph.html"""
42    graph = build_cycle_graph(3)
43
44    return graph
45
46
47def build_square_graph():
48    """Builds a square graph, C4.
49       Ref: http://mathworld.wolfram.com/CycleGraph.html"""
50    graph = build_cycle_graph(4)
51
52    return graph
53
54
55def build_diamond_graph():
56    """Builds a diamond graph.
57       Ref: http://mathworld.wolfram.com/DiamondGraph.html"""
58    graph = build_square_graph()
59
60    graph.new_edge(2, 4)
61
62    return graph
63
64
65def build_tetrahedral_graph():
66    """Builds a tetrahedral graph, K4 (also, W4).
67       Ref: http://mathworld.wolfram.com/TetrahedralGraph.html"""
68    graph = build_wheel_graph(4)
69
70    return graph
71
72
73def build_5_cycle_graph():
74    """Builds a 5-cycle graph, C5.
75       Ref: http://mathworld.wolfram.com/CycleGraph.html"""
76    graph = build_cycle_graph(5)
77
78    return graph
79
80
81def build_gem_graph():
82    """Builds a gem graph, F4,1.
83       Ref: http://mathworld.wolfram.com/GemGraph.html"""
84    graph = build_5_cycle_graph()
85
86    graph.new_edge(1, 3)
87    graph.new_edge(1, 4)
88
89    return graph
90
91
92def build_k5_graph():
93    """Makes a new K5 graph.
94       Ref: http://mathworld.wolfram.com/Pentatope.html"""
95    graph = UndirectedGraph()
96
97    # K5 has 5 nodes
98    for _ in range(5):
99        graph.new_node()
100
101    # K5 has 10 edges
102    # --Edge: a
103    graph.new_edge(1, 2)
104    # --Edge: b
105    graph.new_edge(2, 3)
106    # --Edge: c
107    graph.new_edge(3, 4)
108    # --Edge: d
109    graph.new_edge(4, 5)
110    # --Edge: e
111    graph.new_edge(5, 1)
112    # --Edge: f
113    graph.new_edge(1, 3)
114    # --Edge: g
115    graph.new_edge(1, 4)
116    # --Edge: h
117    graph.new_edge(2, 4)
118    # --Edge: i
119    graph.new_edge(2, 5)
120    # --Edge: j
121    graph.new_edge(3, 5)
122
123    return graph
124
125
126def build_k33_graph():
127    """Makes a new K3,3 graph.
128       Ref: http://mathworld.wolfram.com/UtilityGraph.html"""
129    graph = UndirectedGraph()
130
131    # K3,3 has 6 nodes
132    for _ in range(1, 7):
133        graph.new_node()
134
135    # K3,3 has 9 edges
136    # --Edge: a
137    graph.new_edge(1, 4)
138    # --Edge: b
139    graph.new_edge(1, 5)
140    # --Edge: c
141    graph.new_edge(1, 6)
142    # --Edge: d
143    graph.new_edge(2, 4)
144    # --Edge: e
145    graph.new_edge(2, 5)
146    # --Edge: f
147    graph.new_edge(2, 6)
148    # --Edge: g
149    graph.new_edge(3, 4)
150    # --Edge: h
151    graph.new_edge(3, 5)
152    # --Edge: i
153    graph.new_edge(3, 6)
154
155    return graph
156
157def build_groetzch_graph():
158    """Makes a new Groetzsch graph.
159       Ref: http://mathworld.wolfram.com/GroetzschGraph.html"""
160    # Because the graph is so complicated, we want to
161    # build it via adjacency matrix specification
162
163    # -- Initialize the matrix to all zeros
164    adj = [[0 for _ in range(11)] for _ in range(11)]
165
166    # -- Add individual edge connections
167    row_connections = []
168
169    row_connections.append( (1,2,7,10) )
170    row_connections.append( (0,3,6,9) )
171    row_connections.append( (0,4,6,8) )
172    row_connections.append( (1,4,8,10) )
173    row_connections.append( (2,3,7,9) )
174    row_connections.append( (6,7,8,9,10) )
175    row_connections.append( (1,2,5) )
176    row_connections.append( (0,4,5) )
177    row_connections.append( (2,3,5) )
178    row_connections.append( (1,4,5) )
179    row_connections.append( (0,3,5) )
180
181    for j, tpl in enumerate(row_connections):
182        for i in tpl:
183            adj[j][i] = 1
184            adj[i][j] = 1
185
186    # Debug print the adjacency matrix
187    #for row in adj:
188    #    print row
189
190    graph, _ = create_graph_from_adjacency_matrix(adj)
191
192    return graph
193
194
195def build_franklin_graph():
196    """Makes a new Franklin graph.
197       Ref: http://mathworld.wolfram.com/FranklinGraph.html"""
198    # The easiest way to build the Franklin graph is to start
199    # with C12 and add the additional 6 edges
200    graph = build_cycle_graph(12)
201
202    edge_tpls = [
203        (1,8),
204        (2,7),
205        (3,10),
206        (4,9),
207        (5,12),
208        (6,11)
209    ]
210
211    for i, j in edge_tpls:
212        graph.new_edge(i, j)
213
214    return graph
215
216
217def build_chvatal_graph():
218    """Makes a new Chvatal graph.
219       Ref: http://mathworld.wolfram.com/ChvatalGraph.html"""
220    # The easiest way to build the Chvatal graph is to start
221    # with C12 and add the additional 12 edges
222    graph = build_cycle_graph(12)
223
224    edge_tpls = [
225        (1,7), (1,9), (2,5), (2,11),
226        (3,7), (3,9), (4,10), (4,12),
227        (5,8), (6,10), (6,12), (8,11),
228    ]
229
230    for i, j in edge_tpls:
231        graph.new_edge(i, j)
232
233    return graph
234
235