ceph/src/boost/libs/graph/doc/grid_graph.html

   1 <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN">
   2 <!--
   3    Copyright &copy; 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> &lt;<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>&gt;
  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>&lt;...&gt;(<span class="name">boost</span>:<span class="type">array</span>&lt;<span class="name">VertexIndex</span>, <span class="name">Dimensions</span>&gt; 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>&lt;...&gt;(<span class="name">boost</span>:<span class="type">array</span>&lt;<span class="name">VertexIndex</span>, <span class="name">Dimensions</span>&gt; 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>&lt;...&gt;(<span class="name">boost</span>:<span class="type">array</span>&lt;<span class="name">VertexIndex</span>, <span class="name">Dimensions</span>&gt; dimension_lengths,
 108                 <span class="name">boost</span>:<span class="type">array</span>&lt;<span class="keyword">bool</span>, <span class="name">Dimensions</span>&gt; 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>&lt;<span class="keyword">int</span>, <span class="literal">2</span>&gt; 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>&lt;<span class="literal">2</span>&gt; 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>&lt;<span class="literal">2</span>&gt; 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>&lt;...&gt; <span class="name">Graph</span>;
 145 <span class="keyword">typedef</span> <span class="type">graph_traits</span>&lt;<span class="name">Graph</span>&gt; <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&amp;</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&amp;</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&amp;</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&amp;</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&amp;</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&amp;</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>&lt;2&gt; <span class="name">Graph</span>;
 185 <span class="keyword">typedef</span> <span class="type">graph_traits</span>&lt;<span class="name">Graph</span>&gt; <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>&lt;<span class="keyword">int</span>, <span class="literal">2</span>&gt; 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 &lt; 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 &lt;&lt; <span class="literal">&quot;Index of vertex &quot;</span> &lt;&lt; v_index &lt;&lt; <span class="literal">&quot; is &quot;</span> &lt;&lt;
 197     get(<span class="name">boost</span>::vertex_index, graph, vertex(v_index, graph)) &lt;&lt; <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 &lt; 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 &lt;&lt; <span class="literal">&quot;Index of edge &quot;</span> &lt;&lt; e_index &lt;&lt; <span class="literal">&quot; is &quot;</span> &lt;&lt;
 207     get(<span class="name">boost</span>::edge_index, graph, edge_at(e_index, graph)) &lt;&lt; <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>&lt;...&gt; <span class="name">Graph</span>;
 225 <span class="keyword">typedef</span> <span class="type">graph_traits</span>&lt;<span class="name">Graph</span>&gt; <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 &quot;next&quot; 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 &quot;previous&quot; 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>&lt;<span class="literal">3</span>&gt; <span class="name">Graph</span>;
 252 <span class="keyword">typedef</span> <span class="type">graph_traits</span>&lt;<span class="name">Graph</span>&gt; <span class="name">Traits</span>;
 253
 254 <span class="comment">// Define a 3x5x7 grid_graph where the second dimension doesn&apos;t wrap</span>
 255 <span class="name">boost</span>::<span class="type">array</span>&lt;<span class="name">std</span>::<span class="type">size_t</span>, <span class="literal">3</span>&gt; 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>&lt;<span class="keyword">bool</span>, <span class="literal">3</span>&gt; 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 &lt;&lt; graph.dimensions() &lt;&lt; <span class="name">std</span>::endl; <span class="comment">// prints &quot;3&quot;</span>
 261
 262 <span class="comment">// Print dimension lengths (same order as in the lengths array)</span>
 263 <span class="name">std</span>::cout &lt;&lt; graph.length(<span class="literal">0</span>) &lt;&lt; <span class="literal">&quot;x&quot;</span> &lt;&lt; graph.length(<span class="literal">1</span>) <<
 264   <span class="literal">&quot;x&quot;</span> &lt;&lt; graph.length(<span class="literal">2</span>) &lt;&lt; <span class="name">std</span>::endl; <span class="comment">// prints &quot;3x5x7&quot;</span>
 265
 266 <span class="comment">// Print dimension wrapping (W = wrapped, U = unwrapped)</span>
 267 <span class="name">std</span>::cout &lt;&lt; graph.wrapped(<span class="literal">0</span>) ? <span class="literal">&quot;W&quot;</span> : <span class="literal">&quot;U&quot;</span> &lt;&lt; <span class="literal">&quot;, &quot;</span> <<
 268   graph.wrapped(<span class="literal">1</span>) ? <span class="literal">&quot;W&quot;</span> : <span class="literal">&quot;U&quot;</span> &lt;&lt; <span class="literal">&quot;, &quot;</span> <<
 269   graph.wrapped(<span class="literal">2</span>) ? <span class="literal">&quot;W&quot;</span> : <span class="literal">&quot;U&quot;</span> &lt;&lt; <span class="name">std</span>::endl; <span class="comment">// prints &quot;W, U, W&quot;</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 &lt;&lt; <span class="literal">&quot;(&quot;</span> &lt;&lt; vertex_to_print[<span class="literal">0</span>] &lt;&lt; <span class="literal">&quot;, &quot;</span> &lt;&lt; vertex_to_print[<span class="literal">1</span>] <<
 274     <span class="literal">&quot;, &quot;</span> &lt;&lt; vertex_to_print[<span class="literal">2</span>] &lt;&lt; <span class="literal">&quot;)&quot;</span> &lt;&lt; <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 &quot;(0, 0, 0)&quot;</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 &quot;(1, 0, 0)&quot;</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 &quot;(0, 1, 0)&quot;</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 &quot;(0, 0, 5)&quot;</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 &quot;(2, 0, 0)&quot;</span>
 292
 293 <span class="comment">// Print the previous vertex in dimension 1 (doesn&apos;t wrap, so it&apos;s the same)</span>
 294 print_vertex(graph.previous(first_vertex, <span class="literal">1</span>)); <span class="comment">// prints &quot;(0, 0, 0)&quot;</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 &quot;(0, 0, 1)&quot;</span>
 298     </pre>
 299
 300     <hr />
 301     Copyright &copy; 2009 Trustees of Indiana University
 302
 303   </body>
 304 </html>