]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN"> |
2 | <!-- | |
3 | Copyright © 2009 Trustees of Indiana University | |
4 | ||
5 | Distributed under the Boost Software License, Version 1.0. | |
6 | (See accompanying file LICENSE_1_0.txt or copy at | |
7 | http://www.boost.org/LICENSE_1_0.txt) | |
8 | --> | |
9 | <html> | |
10 | <head> | |
11 | <title>Boost Graph Library: Grid Graph</title> | |
12 | <style type="text/css"> | |
13 | <!-- | |
14 | body { | |
15 | color: black; | |
16 | background-color: white; | |
17 | } | |
18 | ||
19 | a { | |
20 | color: blue; | |
21 | } | |
22 | ||
23 | a:visited { | |
24 | color: #551A8B; | |
25 | } | |
26 | ||
27 | .code | |
28 | { | |
29 | border-left-style: groove; | |
30 | border-left-width: 1px; | |
31 | padding-left: 2em; | |
32 | } | |
33 | ||
34 | --> | |
35 | </style> | |
36 | </head> | |
37 | <body> | |
38 | <img src="../../../boost.png" alt="C++ Boost" width="277" height="86" /> | |
39 | <br /> | |
40 | <h1> | |
41 | <tt>grid_graph</tt> | |
42 | </h1> | |
43 | ||
44 | <ul> | |
45 | <li><a href="#overview">Overview</a></li> | |
46 | <li><a href="#creating">Creating a Grid Graph</a></li> | |
47 | <li><a href="#indexing">Indexing</a></li> | |
48 | <li><a href="#member">Grid Graph Member Functions</a></li> | |
49 | </ul> | |
50 | ||
51 | <h3 id="overview">Overview</h3> | |
52 | <p> | |
53 | A <tt>grid_graph</tt> represents a multi-dimensional, | |
54 | rectangular grid of vertices with user-defined dimension lengths | |
55 | and wrapping. | |
56 | ||
57 | </p> | |
58 | <p> | |
59 | <tt>grid_graph</tt> models: | |
60 | <ul> | |
61 | <li><a href="IncidenceGraph.html">Incidence Graph</a></li> | |
62 | <li><a href="AdjacencyGraph.html">Adjacency Graph</a></li> | |
63 | <li><a href="VertexListGraph.html">Vertex List Graph</a></li> | |
64 | <li><a href="EdgeListGraph.html">Edge List Graph</a></li> | |
65 | <li><a href="BidirectionalGraph.html">Bidirectional Graph</a></li> | |
66 | <li><a href="AdjacencyMatrix.html">Adjacency Matrix</a></li> | |
67 | </ul> | |
68 | </p> | |
69 | <p> | |
70 | Defined in | |
71 | <a href="../../../boost/graph/grid_graph.hpp"><tt>boost/graph/grid_graph.hpp</tt></a> | |
72 | with all functions in the <tt>boost</tt> namespace. A simple examples of creating and iterating over a grid_graph is available here <a href="../../../libs/graph/example/grid_graph_example.cpp"><tt>libs/graph/example/grid_graph_example.cpp</tt></a>. An example of adding properties to a grid_graph is also available <a href="../../../libs/graph/example/grid_graph_example.cpp"><tt>libs/graph/example/grid_graph_properties.cpp</tt></a> | |
73 | </p> | |
74 | ||
75 | <h4>Template Parameters</h4> | |
76 | <pre class="code"> | |
77 | <span class="keyword">template</span> <<span class="name">std</span>::<span class="type">size_t</span> <span class="name">Dimensions</span>, | |
78 | <span class="keyword">typename</span> <span class="name">VertexIndex</span> = <span class="name">std</span>::<span class="type">size_t</span>, | |
79 | <span class="keyword">typename</span> <span class="name">EdgeIndex</span> = <span class="name">VertexIndex</span>> | |
80 | <span class="keyword">class</span> grid_graph; | |
81 | </pre> | |
82 | <ul> | |
83 | <li> | |
84 | <tt>Dimensions</tt> - Number of dimensions in the graph | |
85 | </li> | |
86 | <li> | |
87 | <tt>VertexIndex</tt> - Type used for vertex indices, defaults to <tt>std::size_t</tt> | |
88 | </li> | |
89 | <li> | |
90 | <tt>EdgeIndex</tt> - Type used for edge indices, defaults to the same type as <tt>VertexIndex</tt> | |
91 | </li> | |
92 | </ul> | |
93 | ||
94 | <h3 id="creating">Creating a Grid Graph</h3> | |
95 | <p> | |
96 | The constructor to <tt>grid_graph</tt> has several overloads to aid in configuring each dimension: | |
97 | </p> | |
98 | <pre class="code"> | |
99 | <span class="comment">// Defines a grid_graph that does not wrap.</span> | |
100 | <span class="type">grid_graph</span><...>(<span class="name">boost</span>:<span class="type">array</span><<span class="name">VertexIndex</span>, <span class="name">Dimensions</span>> dimension_lengths); | |
101 | ||
102 | <span class="comment">// Defines a grid_graph where all dimensions are either wrapped or unwrapped.</span> | |
103 | <span class="type">grid_graph</span><...>(<span class="name">boost</span>:<span class="type">array</span><<span class="name">VertexIndex</span>, <span class="name">Dimensions</span>> dimension_lengths, | |
104 | <span class="keyword">bool</span> wrap_all_dimensions); | |
105 | ||
106 | <span class="comment">// Defines a grid_graph where the wrapping for each dimension is specified individually.</span> | |
107 | <span class="type">grid_graph</span><...>(<span class="name">boost</span>:<span class="type">array</span><<span class="name">VertexIndex</span>, <span class="name">Dimensions</span>> dimension_lengths, | |
108 | <span class="name">boost</span>:<span class="type">array</span><<span class="keyword">bool</span>, <span class="name">Dimensions</span>> wrap_dimension); | |
109 | </pre> | |
110 | ||
111 | <h4>Example</h4> | |
112 | <pre class="code"> | |
113 | <span class="comment">// Define dimension lengths, a 3x3 in this case</span> | |
114 | <span class="name">boost</span>::<span class="type">array</span><<span class="keyword">int</span>, <span class="literal">2</span>> lengths = { { <span class="literal">3</span>, <span class="literal">3</span> } }; | |
115 | ||
116 | <span class="comment">// Create a 3x3 two-dimensional, unwrapped grid graph (Figure 1)</span> | |
117 | <span class="type">grid_graph</span><<span class="literal">2</span>> graph(lengths); | |
118 | ||
119 | <span class="comment">// Create a 3x3 two-dimensional, wrapped grid graph (Figure 2)</span> | |
120 | <span class="type">grid_graph</span><<span class="literal">2</span>> graph(lengths, <span class="keyword">true</span>); | |
121 | ||
122 | </pre> | |
123 | <p style="margin-left: 10px;"> | |
124 | <img src="figs/grid_graph_unwrapped.png" /> | |
125 | <br /> | |
126 | <em style="font-size: 0.8em"><b>Figure 1:</b> A 3x3 two-dimensional, unwrapped grid graph</em> | |
127 | </p> | |
128 | <br /> | |
129 | <p style="margin-left: 10px;"> | |
130 | <img src="figs/grid_graph_wrapped.png" /> | |
131 | <br /> | |
132 | <em style="font-size: 0.8em"><b>Figure 2:</b> A 3x3 two-dimensional, wrapped grid graph</em> | |
133 | </p> | |
134 | <br /> | |
135 | ||
136 | <h3 id="indexing">Indexing</h3> | |
137 | <p> | |
138 | The <tt>grid_graph</tt> supports addressing vertices and edges | |
139 | by index. The following functions allow you to convert between | |
140 | vertices, edges, and their associated indices: | |
141 | </p> | |
142 | ||
143 | <pre class="code"> | |
144 | <span class="keyword">typedef</span> <span class="type">grid_graph</span><...> <span class="name">Graph</span>; | |
145 | <span class="keyword">typedef</span> <span class="type">graph_traits</span><<span class="name">Graph</span>> <span class="name">Traits</span>; | |
146 | ||
147 | <span class="comment">// Get the vertex associated with vertex_index</span> | |
148 | <span class="name">Traits</span>::<span class="type">vertex_descriptor</span> | |
149 | vertex(<span class="name">Traits</span>::<span class="type">vertices_size_type</span> vertex_index, | |
150 | <span class="keyword">const</span> <span class="name">Graph&</span> graph); | |
151 | ||
152 | <span class="comment">// Get the index associated with vertex</span> | |
153 | <span class="name">Traits</span>::<span class="type">vertices_size_type</span> | |
154 | get(<span class="name">boost</span>::<span class="type">vertex_index_t</span>, | |
155 | <span class="keyword">const</span> <span class="name">Graph&</span> graph, | |
156 | <span class="name">Traits</span>::<span class="type">vertex_descriptor</span> vertex); | |
157 | ||
158 | <span class="comment">// Get the edge associated with edge_index</span> | |
159 | <span class="name">Traits</span>::<span class="type">edge_descriptor</span> | |
160 | edge_at(<span class="name">Traits</span>::<span class="type">edges_size_type</span> edge_index, | |
161 | <span class="keyword">const</span> <span class="name">Graph&</span> graph); | |
162 | ||
163 | <span class="comment">// Get the index associated with edge</span> | |
164 | <span class="name">Traits</span>::<span class="type">edges_size_type</span> | |
165 | get(<span class="name">boost</span>::<span class="type">edge_index_t</span>, | |
166 | <span class="keyword">const</span> <span class="name">Graph&</span> graph, | |
167 | <span class="name">Traits</span>::<span class="type">edge_descriptor</span> edge); | |
168 | ||
169 | <span class="comment">// Get the out-edge associated with vertex and out_edge_index</span> | |
170 | <span class="name">Traits</span>::<span class="type">edge_descriptor</span> | |
171 | out_edge_at(<span class="name">Traits</span>::<span class="type">vertex_descriptor</span> vertex, | |
172 | <span class="name">Traits</span>::<span class="type">degree_size_type</span> out_edge_index, | |
173 | <span class="keyword">const</span> <span class="name">Graph&</span> graph); | |
174 | ||
175 | <span class="comment">// Get the out-edge associated with vertex and in_edge_index</span> | |
176 | <span class="name">Traits</span>::<span class="type">edge_descriptor</span> | |
177 | in_edge_at(<span class="name">Traits</span>::<span class="type">vertex_descriptor</span> vertex, | |
178 | <span class="name">Traits</span>::<span class="type">degree_size_type</span> in_edge_index, | |
179 | <span class="keyword">const</span> <span class="name">Graph&</span> graph); | |
180 | </pre> | |
181 | ||
182 | <h4>Example</h4> | |
183 | <pre class="code"> | |
184 | <span class="keyword">typedef</span> <span class="type">grid_graph</span><2> <span class="name">Graph</span>; | |
185 | <span class="keyword">typedef</span> <span class="type">graph_traits</span><<span class="name">Graph</span>> <span class="name">Traits</span>; | |
186 | ||
187 | <span class="comment">// Create a 3x3, unwrapped grid_graph (Figure 3)</span> | |
188 | <span class="name">boost</span>::<span class="type">array</span><<span class="keyword">int</span>, <span class="literal">2</span>> lengths = { { <span class="literal">3</span>, <span class="literal">3</span> } }; | |
189 | <span class="name">Graph</span> graph(lengths); | |
190 | ||
191 | <span class="comment">// Do a round-trip test of the vertex index functions</span> | |
192 | <span class="keyword">for</span> (<span class="name">Traits</span>::<span class="type">vertices_size_type</span> v_index = <span class="literal">0</span>; | |
193 | v_index < num_vertices(graph); ++v_index) { | |
194 | ||
195 | <span class="comment">// The two indices should always be equal</span> | |
196 | <span class="name">std</span>::cout << <span class="literal">"Index of vertex "</span> << v_index << <span class="literal">" is "</span> << | |
197 | get(<span class="name">boost</span>::vertex_index, graph, vertex(v_index, graph)) << <span class="name">std</span>::endl; | |
198 | ||
199 | } | |
200 | ||
201 | <span class="comment">// Do a round-trip test of the edge index functions</span> | |
202 | <span class="keyword">for</span> (<span class="name">Traits</span>::<span class="type">edges_size_type</span> e_index = <span class="literal">0</span>; | |
203 | e_index < num_edges(graph); ++e_index) { | |
204 | ||
205 | <span class="comment">// The two indices should always be equal</span> | |
206 | <span class="name">std</span>::cout << <span class="literal">"Index of edge "</span> << e_index << <span class="literal">" is "</span> << | |
207 | get(<span class="name">boost</span>::edge_index, graph, edge_at(e_index, graph)) << <span class="name">std</span>::endl; | |
208 | ||
209 | } | |
210 | </pre> | |
211 | ||
212 | <p style="margin-left: 10px;"> | |
213 | <img src="figs/grid_graph_indexed.png" /> | |
214 | <br /> | |
215 | <em style="font-size: 0.8em"><b>Figure 3:</b> 3x3 unwrapped grid_graph with vertex and edge indices shown.</em> | |
216 | </p> | |
217 | <br /> | |
218 | ||
219 | <h3 id="member">Member Functions</h3> | |
220 | <p> | |
221 | There are several <tt>grid_graph</tt> specific member functions available: | |
222 | </p> | |
223 | <pre class="code"> | |
224 | <span class="keyword">typedef</span> <span class="type">grid_graph</span><...> <span class="name">Graph</span>; | |
225 | <span class="keyword">typedef</span> <span class="type">graph_traits</span><<span class="name">Graph</span>> <span class="name">Traits</span>; | |
226 | ||
227 | <span class="comment">// Returns the number of dimensions</span> | |
228 | <span class="name">std</span>::<span class="type">size_t</span> dimensions(); | |
229 | ||
230 | <span class="comment">// Returns the length of a dimension</span> | |
231 | <span class="name">Traits</span>::<span class="type">vertices_size_type</span> length(<span class="name">std</span>::<span class="type">size_t</span> dimension); | |
232 | ||
233 | <span class="comment">// Returns true if the dimension wraps, false if not</span> | |
234 | <span class="keyword">bool</span> wrapped(<span class="name">std</span>::<span class="type">size_t</span> dimension); | |
235 | ||
236 | <span class="comment">// Returns the "next" vertex in a dimension at a given distance. If the dimension | |
237 | // is unwrapped, next will stop at the last vertex in the dimension. | |
238 | </span><span class="name">Traits</span>::<span class="type">vertex_descriptor</span> next(<span class="name">Traits</span>::<span class="type">vertex_descriptor</span> vertex, | |
239 | <span class="name">std</span>::<span class="type">size_t</span> dimension, | |
240 | <span class="name">Traits</span>::<span class="type">vertices_size_type</span> distance = <span class="literal">1</span>); | |
241 | ||
242 | <span class="comment">// Returns the "previous" vertex in a dimension at a given distance. If the | |
243 | // dimension is unwrapped, previous will stop at the beginning vertex in the dimension. | |
244 | </span><span class="name">Traits</span>::<span class="type">vertex_descriptor</span> previous(<span class="name">Traits</span>::<span class="type">vertex_descriptor</span> vertex, | |
245 | <span class="name">std</span>::<span class="type">size_t</span> dimension, | |
246 | <span class="name">Traits</span>::<span class="type">vertices_size_type</span> distance = <span class="literal">1</span>); | |
247 | </pre> | |
248 | ||
249 | <h4>Example</h4> | |
250 | <pre class="code"> | |
251 | <span class="keyword">typedef</span> <span class="type">grid_graph</span><<span class="literal">3</span>> <span class="name">Graph</span>; | |
252 | <span class="keyword">typedef</span> <span class="type">graph_traits</span><<span class="name">Graph</span>> <span class="name">Traits</span>; | |
253 | ||
254 | <span class="comment">// Define a 3x5x7 grid_graph where the second dimension doesn't wrap</span> | |
255 | <span class="name">boost</span>::<span class="type">array</span><<span class="name">std</span>::<span class="type">size_t</span>, <span class="literal">3</span>> lengths = { { <span class="literal">3</span>, <span class="literal">5</span>, <span class="literal">7</span> } }; | |
256 | <span class="name">boost</span>::<span class="type">array</span><<span class="keyword">bool</span>, <span class="literal">3</span>> wrapped = { { <span class="keyword">true</span>, <span class="keyword">false</span>, <span class="keyword">true</span> } }; | |
257 | <span class="name">Graph</span> graph(lengths, wrapped); | |
258 | ||
259 | <span class="comment">// Print number of dimensions</span> | |
260 | <span class="name">std</span>::cout << graph.dimensions() << <span class="name">std</span>::endl; <span class="comment">// prints "3"</span> | |
261 | ||
262 | <span class="comment">// Print dimension lengths (same order as in the lengths array)</span> | |
263 | <span class="name">std</span>::cout << graph.length(<span class="literal">0</span>) << <span class="literal">"x"</span> << graph.length(<span class="literal">1</span>) << | |
264 | <span class="literal">"x"</span> << graph.length(<span class="literal">2</span>) << <span class="name">std</span>::endl; <span class="comment">// prints "3x5x7"</span> | |
265 | ||
266 | <span class="comment">// Print dimension wrapping (W = wrapped, U = unwrapped)</span> | |
267 | <span class="name">std</span>::cout << graph.wrapped(<span class="literal">0</span>) ? <span class="literal">"W"</span> : <span class="literal">"U"</span> << <span class="literal">", "</span> << | |
268 | graph.wrapped(<span class="literal">1</span>) ? <span class="literal">"W"</span> : <span class="literal">"U"</span> << <span class="literal">", "</span> << | |
269 | graph.wrapped(<span class="literal">2</span>) ? <span class="literal">"W"</span> : <span class="literal">"U"</span> << <span class="name">std</span>::endl; <span class="comment">// prints "W, U, W"</span> | |
270 | ||
271 | <span class="comment">// Define a simple function to print vertices</span> | |
272 | <span class="keyword">void</span> print_vertex(<span class="name">Traits</span>::<span class="type">vertex_descriptor</span> vertex_to_print) { | |
273 | <span class="name">std</span>::cout << <span class="literal">"("</span> << vertex_to_print[<span class="literal">0</span>] << <span class="literal">", "</span> << vertex_to_print[<span class="literal">1</span>] << | |
274 | <span class="literal">", "</span> << vertex_to_print[<span class="literal">2</span>] << <span class="literal">")"</span> << <span class="name">std</span>::endl; | |
275 | } | |
276 | ||
277 | <span class="comment">// Start with the first vertex in the graph</span> | |
278 | <span class="name">Traits</span>::<span class="type">vertex_descriptor</span> first_vertex = vertex(<span class="literal">0</span>, graph); | |
279 | print_vertex(first_vertex); <span class="comment">// prints "(0, 0, 0)"</span> | |
280 | ||
281 | <span class="comment">// Print the next vertex in dimension 0</span> | |
282 | print_vertex(graph.next(first_vertex, <span class="literal">0</span>)); <span class="comment">// prints "(1, 0, 0)"</span> | |
283 | ||
284 | <span class="comment">// Print the next vertex in dimension 1</span> | |
285 | print_vertex(graph.next(first_vertex, <span class="literal">1</span>)); <span class="comment">// prints "(0, 1, 0)"</span> | |
286 | ||
287 | <span class="comment">// Print the 5th next vertex in dimension 2</span> | |
288 | print_vertex(graph.next(first_vertex, <span class="literal">2</span>, <span class="literal">5</span>)); <span class="comment">// prints "(0, 0, 5)"</span> | |
289 | ||
290 | <span class="comment">// Print the previous vertex in dimension 0 (wraps)</span> | |
291 | print_vertex(graph.previous(first_vertex, <span class="literal">0</span>)); <span class="comment">// prints "(2, 0, 0)"</span> | |
292 | ||
293 | <span class="comment">// Print the previous vertex in dimension 1 (doesn't wrap, so it's the same)</span> | |
294 | print_vertex(graph.previous(first_vertex, <span class="literal">1</span>)); <span class="comment">// prints "(0, 0, 0)"</span> | |
295 | ||
296 | <span class="comment">// Print the 20th previous vertex in dimension 2 (wraps around twice)</span> | |
297 | print_vertex(graph.previous(first_vertex, <span class="literal">2</span>, <span class="literal">20</span>)); <span class="comment">// prints "(0, 0, 1)"</span> | |
298 | </pre> | |
299 | ||
300 | <hr /> | |
301 | Copyright © 2009 Trustees of Indiana University | |
302 | ||
303 | </body> | |
304 | </html> |