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="name">std</span>::<span class="type">size_t</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> 149vertex(<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> 154get(<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> 160edge_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> 165get(<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> 171out_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> 177in_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="name">std</span>::<span class="type">size_t</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); 279print_vertex(first_vertex); <span class="comment">// prints "(0, 0, 0)"</span> 280 281<span class="comment">// Print the next vertex in dimension 0</span> 282print_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> 285print_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> 288print_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> 291print_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> 294print_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> 297print_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> 305
