]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | <HTML> |
2 | <!-- | |
3 | Copyright (c) Jeremy Siek 2000 | |
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 | <Head> | |
10 | <Title>Boost Graph Library: Adjacency Matrix</Title> | |
11 | <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" | |
12 | ALINK="#ff0000"> | |
13 | <IMG SRC="../../../boost.png" | |
14 | ALT="C++ Boost" width="277" height="86"> | |
15 | ||
16 | <BR Clear> | |
17 | ||
18 | <H1><A NAME="sec:adjacency-matrix-class"></A> | |
19 | <pre> | |
20 | adjacency_matrix<Directed, VertexProperty, | |
21 | EdgeProperty, GraphProperty, | |
22 | Allocator> | |
23 | </pre> | |
24 | </H1> | |
25 | ||
26 | The <tt>adjacency_matrix</tt> class implements the BGL graph interface | |
27 | using the traditional adjacency matrix storage format. For a graph | |
28 | with <i>V</i> vertices, a <i>V x V</i> matrix is used, where each | |
29 | element <i>a<sub>ij</sub></i> is a boolean flag that says whether | |
30 | there is an edge from vertex <i>i</i> to vertex <i>j</i>. <a | |
31 | href="#fig:adj-matrix-graph">Figure 1</a> shows the adjacency matrix | |
32 | representation of a graph. | |
33 | ||
34 | <P></P> | |
35 | <DIV ALIGN="center"><A NAME="fig:adj-matrix-graph"></A> | |
36 | <TABLE> | |
37 | <CAPTION ALIGN="BOTTOM"><STRONG>Figure 1:</STRONG> Adjacency Matrix Representation of a Directed Graph.</CAPTION> | |
38 | <TR><TD><IMG SRC="./figs/adj-matrix-graph3.gif" width="386" height="284"></TD> | |
39 | <TD><IMG SRC="./figs/adj-matrix.gif" width="135" height="136"></TD></TR> | |
40 | </TABLE> | |
41 | </DIV><P></P> | |
42 | ||
43 | The advantage of this matrix format over the adjacency list is that | |
44 | edge insertion and removal is constant time. There are several | |
45 | disadvantages. The first is that the amount of memory used is | |
46 | <i>O(V<sup>2</sup>)</i> instead of <i>O(V + E)</i> (where <i>E</i> is | |
47 | the number of edges). The second is that operations that traverse all | |
48 | the out-edges of each vertex (such as breadth-first search) run in | |
49 | <i>O(V<sup>2</sup>)</i> time instead of <i>O(V + E)</i> time for the | |
50 | adjacency list. In short, it is better to use the | |
51 | <tt>adjacency_matrix</tt> for dense graphs (where <i>E</i> is close to | |
52 | <i>V<sup>2</sup></i>) and it is better to use <a | |
53 | href="adjacency_list.html"><tt>adjacency_list</tt></a> for sparse | |
54 | graphs (where <i>E</i> is much smaller than <i>V<sup>2</sup></i>). | |
55 | ||
56 | The <tt>adjacency_matrix</tt> class extends the traditional | |
57 | data-structure by allowing objects to be attached to vertices and | |
58 | edges using the same property template parameters supported by <a | |
59 | href="adjacency_list.html"><tt>adjacency_list</tt></a>. These may be | |
60 | <a href="bundles.html">bundled properties</a> or standard (backward-compatible) | |
61 | <a | |
62 | href="using_adjacency_list.html#sec:adjacency-list-properties">interior | |
63 | properties</a>. The types of all property values must be | |
64 | Copy Constructible, Assignable and Default Constructible. | |
65 | ||
66 | In the case of an undirected graph, the | |
67 | <tt>adjacency_matrix</tt>. class does not use a full <i>V x V</i> | |
68 | matrix but instead uses a lower triangle (the diagonal and below) | |
69 | since the matrix for an undirected graph is symmetric. This reduces | |
70 | the storage to <i>(V<sup>2</sup>)/2</i>. <a | |
71 | href="#fig:undir-adj-matrix-graph">Figure 2</a> shows an adjacency | |
72 | matrix representation of an undirected graph. | |
73 | ||
74 | <P></P> | |
75 | <DIV ALIGN="center"><A NAME="fig:undir-adj-matrix-graph"></A> | |
76 | <TABLE> | |
77 | <CAPTION ALIGN="BOTTOM"><STRONG>Figure 2:</STRONG> Adjacency Matrix Representation of an Undirected Graph.</CAPTION> | |
78 | <TR><TD><IMG SRC="./figs/undir-adj-matrix-graph3.gif" width="260" height="240"></TD> | |
79 | <TD><IMG SRC="./figs/undir-adj-matrix2.gif" width="135" height="136"></TD></TR> | |
80 | </TABLE> | |
81 | </DIV><P></P> | |
82 | ||
83 | ||
84 | <h3>Example</h3> | |
85 | ||
86 | Creating the graph of <a href="#fig:adj-matrix-graph">Figure 1</a>. | |
87 | <pre> | |
88 | enum { A, B, C, D, E, F, N }; | |
89 | const char* name = "ABCDEF"; | |
90 | ||
91 | typedef boost::adjacency_matrix<boost::directedS> Graph; | |
92 | Graph g(N); | |
93 | add_edge(B, C, g); | |
94 | add_edge(B, F, g); | |
95 | add_edge(C, A, g); | |
96 | add_edge(C, C, g); | |
97 | add_edge(D, E, g); | |
98 | add_edge(E, D, g); | |
99 | add_edge(F, A, g); | |
100 | ||
101 | std::cout << "vertex set: "; | |
102 | boost::print_vertices(g, name); | |
103 | std::cout << std::endl; | |
104 | ||
105 | std::cout << "edge set: "; | |
106 | boost::print_edges(g, name); | |
107 | std::cout << std::endl; | |
108 | ||
109 | std::cout << "out-edges: " << std::endl; | |
110 | boost::print_graph(g, name); | |
111 | std::cout << std::endl; | |
112 | </pre> | |
113 | The output is: | |
114 | <pre> | |
115 | vertex set: A B C D E F | |
116 | ||
117 | edge set: (B,C) (B,F) (C,A) (C,C) (D,E) (E,D) (F,A) | |
118 | ||
119 | out-edges: | |
120 | A --> | |
121 | B --> C F | |
122 | C --> A C | |
123 | D --> E | |
124 | E --> D | |
125 | F --> A | |
126 | </pre> | |
127 | ||
128 | Creating the graph of <a href="#fig:undir-adj-matrix-graph">Figure 2</a>. | |
129 | <pre> | |
130 | enum { A, B, C, D, E, F, N }; | |
131 | const char* name = "ABCDEF"; | |
132 | ||
133 | typedef boost::adjacency_matrix<boost::undirectedS> UGraph; | |
134 | UGraph ug(N); | |
135 | add_edge(B, C, ug); | |
136 | add_edge(B, F, ug); | |
137 | add_edge(C, A, ug); | |
138 | add_edge(D, E, ug); | |
139 | add_edge(F, A, ug); | |
140 | ||
141 | std::cout << "vertex set: "; | |
142 | boost::print_vertices(ug, name); | |
143 | std::cout << std::endl; | |
144 | ||
145 | std::cout << "edge set: "; | |
146 | boost::print_edges(ug, name); | |
147 | std::cout << std::endl; | |
148 | ||
149 | std::cout << "incident edges: " << std::endl; | |
150 | boost::print_graph(ug, name); | |
151 | std::cout << std::endl; | |
152 | </pre> | |
153 | The output is: | |
154 | <pre> | |
155 | vertex set: A B C D E F | |
156 | ||
157 | edge set: (C,A) (C,B) (E,D) (F,A) (F,B) | |
158 | ||
159 | incident edges: | |
160 | A <--> C F | |
161 | B <--> C F | |
162 | C <--> A B | |
163 | D <--> E | |
164 | E <--> D | |
165 | F <--> A B | |
166 | </pre> | |
167 | ||
168 | ||
169 | <h3>Where Defined</h3> | |
170 | ||
171 | <a href="../../../boost/graph/adjacency_matrix.hpp"><tt>boost/graph/adjacency_matrix.hpp</tt></a> | |
172 | ||
173 | ||
174 | <h3>Template Parameters</h3> | |
175 | ||
176 | <p> | |
177 | <table border> | |
178 | ||
179 | <TR> | |
180 | <th>Parameter</th><th>Description</th><th>Default</th> | |
181 | </tr> | |
182 | ||
183 | <tr> | |
184 | <td><tt>Directed</tt></td> | |
185 | <td>A selector to choose whether the graph is directed or undirected. The options are <tt>directedS</tt> and <tt>undirectedS</tt>.</td> | |
186 | <td><tt>directedS</tt></td> | |
187 | </tr> | |
188 | <tr> | |
189 | <td><tt>VertexProperty</tt></td> | |
190 | <td>for specifying internal property storage.</td> | |
191 | <td><tt>no_property</tt></td> | |
192 | </tr> | |
193 | <tr> | |
194 | <td><tt>EdgeProperty</tt></td> | |
195 | <td>for specifying internal property storage.</td> | |
196 | <td><tt>no_property</tt></td> | |
197 | </tr> | |
198 | <tr> | |
199 | <td><tt>GraphProperty</tt></td> | |
200 | <td>for specifying property storage for the graph object.</td> | |
201 | <td><tt>no_property</tt></td> | |
202 | </tr> | |
203 | ||
204 | </table> | |
205 | ||
206 | <h3>Model Of</h3> | |
207 | ||
208 | <a href="./VertexAndEdgeListGraph.html">VertexAndEdgeListGraph</a>, | |
209 | <a href="./IncidenceGraph.html">Incidence Graph</a>, | |
210 | <a href="./BidirectionalGraph.html">Bidirectional Graph</a>, | |
211 | <a | |
212 | href="./AdjacencyMatrix.html">AdjacencyMatrix</a>, <a | |
213 | href="./MutablePropertyGraph.html">MutablePropertyGraph</a>, | |
214 | <a href="../../utility/CopyConstructible.html">CopyConstructible</a>, | |
215 | and <a href="../../utility/Assignable.html">Assignable</a>. | |
216 | ||
217 | ||
218 | <h3>Associated Types</h3> | |
219 | ||
220 | <hr> | |
221 | ||
222 | <tt>graph_traits<adjacency_matrix>::vertex_descriptor</tt> | |
223 | <br><br> | |
224 | The type for the vertex descriptors associated with the | |
225 | <tt>adjacency_matrix</tt>.<br> | |
226 | (Required by <a href="./Graph.html">Graph</a>.) | |
227 | ||
228 | <hr> | |
229 | ||
230 | <tt>graph_traits<adjacency_matrix>::edge_descriptor</tt> | |
231 | <br><br> | |
232 | The type for the edge descriptors associated with the | |
233 | <tt>adjacency_matrix</tt>.<br> | |
234 | (Required by <a href="Graph.html">Graph</a>.) | |
235 | ||
236 | <hr> | |
237 | <tt>graph_traits<adjacency_matrix>::vertex_iterator</tt> | |
238 | <br><br> | |
239 | The type for the iterators returned by <tt>vertices()</tt>. | |
240 | The vertex iterator models <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>. <br> | |
241 | (Required by <a href="VertexListGraph.html">VertexListGraph</a>.) | |
242 | ||
243 | <hr> | |
244 | <tt>graph_traits<adjacency_matrix>::edge_iterator</tt> | |
245 | <br><br> | |
246 | The type for the iterators returned by <tt>edges()</tt>. This | |
247 | iterator models <a href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>.<br> | |
248 | (Required by <a href="EdgeListGraph.html">EdgeListGraph</a>.) | |
249 | ||
250 | <hr> | |
251 | <tt>graph_traits<adjacency_matrix>::out_edge_iterator</tt> | |
252 | <br><br> | |
253 | The type for the iterators returned by <tt>out_edges()</tt>. This | |
254 | iterator models <a href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>. <br> | |
255 | (Required by <a href="IncidenceGraph.html">IncidenceGraph</a>.) | |
256 | ||
257 | <hr> | |
258 | <tt>graph_traits<adjacency_matrix>::in_edge_iterator</tt> | |
259 | <br><br> | |
260 | The type for the iterators returned by <tt>in_edges()</tt>. This | |
261 | iterator models <a href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>. <br> | |
262 | (Required by <a href="BidirectionalGraph.html">BidirectionalGraph</a>.) | |
263 | ||
264 | <hr> | |
265 | <tt>graph_traits<adjacency_matrix>::adjacency_iterator</tt> | |
266 | <br><br> | |
267 | The type for the iterators returned by <tt>adjacent_vertices()</tt>. This | |
268 | iterator models the same concept as the out-edge iterator.<br> | |
269 | (Required by <a href="AdjacencyGraph.html">AdjacencyGraph</a>.) | |
270 | ||
271 | <hr> | |
272 | <tt>graph_traits<adjacency_matrix>::directed_category</tt> | |
273 | <br><br> | |
274 | Provides information about whether the graph is directed | |
275 | (<tt>directed_tag</tt>) or undirected (<tt>undirected_tag</tt>).<br> | |
276 | (Required by <a href="Graph.html">Graph</a>.) | |
277 | ||
278 | <hr> | |
279 | <tt>graph_traits<adjacency_matrix>::edge_parallel_category</tt> | |
280 | <br><br> | |
281 | An adjacency matrix does not allow the insertion of | |
282 | parallel edges, so this type is always | |
283 | <tt>disallow_parallel_edge_tag</tt>. <br> | |
284 | (Required by <a href="Graph.html">Graph</a>.) | |
285 | ||
286 | <hr> | |
287 | <tt>graph_traits<adjacency_matrix>::vertices_size_type</tt> | |
288 | <br><br> | |
289 | The type used for dealing with the number of vertices in | |
290 | the graph.<br> | |
291 | (Required by <a href="VertexListGraph.html">VertexListGraph</a>.) | |
292 | ||
293 | <hr> | |
294 | <tt>graph_traits<adjacency_matrix>::edges_size_type</tt> | |
295 | <br><br> | |
296 | The type used for dealing with the number of edges in the graph.<br> | |
297 | (Required by <a href="EdgeListGraph.html">EdgeListGraph</a>.) | |
298 | ||
299 | <hr> | |
300 | <tt>graph_traits<adjacency_matrix>::degree_size_type</tt> | |
301 | <br><br> | |
302 | The type used for dealing with the number of out-edges of a vertex.<br> | |
303 | (Required by <a href="IncidenceGraph.html">IncidenceGraph</a>.) | |
304 | ||
305 | <hr> | |
306 | <tt>property_map<adjacency_matrix, PropertyTag>::type</tt><br> | |
307 | <tt>property_map<adjacency_matrix, PropertyTag>::const_type</tt> | |
308 | <br><br> | |
309 | The map type for vertex or edge properties in the graph. The | |
310 | specific property is specified by the <tt>PropertyTag</tt> template | |
311 | argument, and must match one of the properties specified in the | |
312 | <tt>VertexProperty</tt> or <tt>EdgeProperty</tt> for the graph.<br> | |
313 | (Required by <a href="PropertyGraph.html">PropertyGraph</a>.) | |
314 | ||
315 | <hr> | |
316 | ||
317 | <h3>Member Functions</h3> | |
318 | ||
319 | <hr> | |
320 | <pre> | |
321 | adjacency_matrix(vertices_size_type n, | |
322 | const GraphProperty& p = GraphProperty()) | |
323 | </pre> | |
324 | Creates a graph object with <tt>n</tt> vertices and zero edges.<br> | |
325 | (Required by <a href="MutableGraph.html">MutableGraph</a>.) | |
326 | ||
327 | <hr> | |
328 | <pre> | |
329 | template <typename EdgeIterator> | |
330 | adjacency_matrix(EdgeIterator first, | |
331 | EdgeIterator last, | |
332 | vertices_size_type n, | |
333 | const GraphProperty& p = GraphProperty()) | |
334 | </pre> | |
335 | Creates a graph object with <tt>n</tt> vertices with the edges | |
336 | specified in the edge list given by the range <tt>[first, last)</tt>. | |
337 | The value type of the <tt>EdgeIterator</tt> must be a | |
338 | <tt>std::pair</tt>, where the type in the pair is an integer type. The | |
339 | integers will correspond to vertices, and they must all fall in the | |
340 | range of | |
341 | <tt>[0, n)</tt>. <br> | |
342 | (Required by <a href="IteratorConstructibleGraph.html">IteratorConstructibleGraph</a>.) | |
343 | ||
344 | <hr> | |
345 | <pre> | |
346 | template <typename EdgeIterator, typename EdgePropertyIterator> | |
347 | adjacency_matrix(EdgeIterator first, EdgeIterator last, | |
348 | EdgePropertyIterator ep_iter, | |
349 | vertices_size_type n, | |
350 | const GraphProperty& p = GraphProperty()) | |
351 | </pre> | |
352 | Creates a graph object with <tt>n</tt> vertices, with the edges | |
353 | specified in the edge list given by the range <tt>[first, last)</tt>. | |
354 | The value type of the <tt>EdgeIterator</tt> must be a | |
355 | <tt>std::pair</tt>, where the type in the pair is an integer type. The | |
356 | integers will correspond to vertices, and they must all fall in the | |
357 | range of <tt>[0, n)</tt>. The <tt>value_type</tt> of the | |
358 | <tt>ep_iter</tt> should be <tt>EdgeProperty</tt>. | |
359 | ||
360 | <hr> | |
361 | ||
362 | ||
363 | <h3>Non-Member Functions</h3> | |
364 | ||
365 | <hr> | |
366 | <pre> | |
367 | std::pair<vertex_iterator, vertex_iterator> | |
368 | vertices(const adjacency_matrix& g) | |
369 | </pre> | |
370 | Returns an iterator-range providing access to the vertex set of graph <tt>g</tt>.<br> | |
371 | (Required by <a href="VertexListGraph.html">VertexListGraph</a>.) | |
372 | ||
373 | <hr> | |
374 | <pre> | |
375 | std::pair<edge_iterator, edge_iterator> | |
376 | edges(const adjacency_matrix& g); | |
377 | </pre> | |
378 | Returns an iterator-range providing access to the edge set of graph <tt>g</tt>.<br> | |
379 | (Required by <a href="EdgeListGraph.html">EdgeListGraph</a>.) | |
380 | ||
381 | <hr> | |
382 | <pre> | |
383 | std::pair<adjacency_iterator, adjacency_iterator> | |
384 | adjacent_vertices(vertex_descriptor v, const adjacency_matrix& g) | |
385 | </pre> | |
386 | Returns an iterator-range providing access to the vertices adjacent to | |
387 | vertex <tt>v</tt> in graph <tt>g</tt>.<br> | |
388 | (Required by <a href="AdjacencyGraph.html">AdjacencyGraph</a>.) | |
389 | ||
390 | <hr> | |
391 | <pre> | |
392 | std::pair<out_edge_iterator, out_edge_iterator> | |
393 | out_edges(vertex_descriptor v, const adjacency_matrix& g) | |
394 | </pre> | |
395 | Returns an iterator-range providing access to the out-edges of | |
396 | vertex <tt>v</tt> in graph <tt>g</tt>. If the graph is undirected, | |
397 | this iterator-range provides access to all edges incident on | |
398 | vertex <tt>v</tt>. <br> | |
399 | (Required by <a href="IncidenceGraph.html">IncidenceGraph</a>.) | |
400 | ||
401 | <hr> | |
402 | <pre> | |
403 | vertex_descriptor | |
404 | source(edge_descriptor e, const adjacency_matrix& g) | |
405 | </pre> | |
406 | Returns the source vertex of edge <tt>e</tt>.<br> | |
407 | (Required by <a href="IncidenceGraph.html">IncidenceGraph</a>.) | |
408 | ||
409 | <hr> | |
410 | <pre> | |
411 | vertex_descriptor | |
412 | target(edge_descriptor e, const adjacency_matrix& g) | |
413 | </pre> | |
414 | Returns the target vertex of edge <tt>e</tt>.<br> | |
415 | (Required by <a href="IncidenceGraph.html">IncidenceGraph</a>.) | |
416 | ||
417 | <hr> | |
418 | <pre> | |
419 | degree_size_type | |
420 | out_degree(vertex_descriptor u, const adjacency_matrix& g) | |
421 | </pre> | |
422 | Returns the number of edges leaving vertex <tt>u</tt>.<br> | |
423 | (Required by <a href="IncidenceGraph.html">IncidenceGraph</a>.) | |
424 | <hr> | |
425 | ||
426 | <hr> | |
427 | <pre> | |
428 | std::pair<in_edge_iterator, in_edge_iterator> | |
429 | in_edges(vertex_descriptor v, const adjacency_matrix& g) | |
430 | </pre> | |
431 | Returns an iterator-range providing access to the in-edges of | |
432 | vertex <tt>v</tt> in graph <tt>g</tt>. If the graph is undirected, | |
433 | this iterator-range provides access to all edges incident on | |
434 | vertex <tt>v</tt>. <br> | |
435 | (Required by <a href="BidirectionalGraph.html">BidirectionalGraph</a>.) | |
436 | ||
437 | <hr> | |
438 | <pre> | |
439 | degree_size_type | |
440 | in_degree(vertex_descriptor u, const adjacency_matrix& g) | |
441 | </pre> | |
442 | Returns the number of edges entering vertex <tt>u</tt>.<br> | |
443 | (Required by <a href="BidirectionalGraph.html">BidirectionalGraph</a>.) | |
444 | <hr> | |
445 | ||
446 | <hr> | |
447 | <pre> | |
448 | vertices_size_type num_vertices(const adjacency_matrix& g) | |
449 | </pre> | |
450 | Returns the number of vertices in the graph <tt>g</tt>.<br> | |
451 | (Required by <a href="VertexListGraph.html">VertexListGraph</a>.) | |
452 | ||
453 | <hr> | |
454 | <pre> | |
455 | edges_size_type num_edges(const adjacency_matrix& g) | |
456 | </pre> | |
457 | Returns the number of edges in the graph <tt>g</tt>.<br> | |
458 | (Required by <a href="EdgeListGraph.html">EdgeListGraph</a>.) | |
459 | ||
460 | <hr> | |
461 | <pre> | |
462 | vertex_descriptor vertex(vertices_size_type n, const adjacency_matrix& g) | |
463 | </pre> | |
464 | Returns the nth vertex in the graph's vertex list. | |
465 | ||
466 | <hr> | |
467 | <pre> | |
468 | std::pair<edge_descriptor, bool> | |
469 | edge(vertex_descriptor u, vertex_descriptor v, | |
470 | const adjacency_matrix& g) | |
471 | </pre> | |
472 | Returns the edge connecting vertex <tt>u</tt> to vertex <tt>v</tt> in graph <tt>g</tt>.<br> | |
473 | (Required by <a href="AdjacencyMatrix.html">AdjacencyMatrix</a>.) | |
474 | ||
475 | <hr> | |
476 | <pre> | |
477 | std::pair<edge_descriptor, bool> | |
478 | add_edge(vertex_descriptor u, vertex_descriptor v, | |
479 | adjacency_matrix& g) | |
480 | </pre> | |
481 | Adds edge <tt>(u,v)</tt> to the graph and returns the edge descriptor for | |
482 | the new edge. If the edge is already in the graph then a duplicate | |
483 | will not be added and the <tt>bool</tt> flag will be <tt>false</tt>. | |
484 | This operation does not invalidate any of the graph's iterators | |
485 | or descriptors.<br> | |
486 | (Required by <a href="MutableGraph.html">MutableGraph</a>.) | |
487 | ||
488 | <hr> | |
489 | <pre> | |
490 | std::pair<edge_descriptor, bool> | |
491 | add_edge(vertex_descriptor u, vertex_descriptor v, | |
492 | const EdgeProperty& p, | |
493 | adjacency_matrix& g) | |
494 | </pre> | |
495 | Adds edge <tt>(u,v)</tt> to the graph and attaches <tt>p</tt> as the | |
496 | value of the edge's internal property storage. Also see the previous | |
497 | <tt>add_edge()</tt> member function for more details. | |
498 | ||
499 | <hr> | |
500 | <pre> | |
501 | void remove_edge(vertex_descriptor u, vertex_descriptor v, | |
502 | adjacency_matrix& g) | |
503 | </pre> | |
504 | Removes the edge <tt>(u,v)</tt> from the graph. <br> | |
505 | (Required by <a href="MutableGraph.html">MutableGraph</a>.) | |
506 | ||
507 | <hr> | |
508 | <pre> | |
509 | void remove_edge(edge_descriptor e, adjacency_matrix& g) | |
510 | </pre> | |
511 | Removes the edge <tt>e</tt> from the graph. This is equivalent | |
512 | to calling <tt>remove_edge(source(e, g), target(e, g), g)</tt>.<br> | |
513 | (Required by <a href="MutableGraph.html">MutableGraph</a>.) | |
514 | ||
515 | <hr> | |
516 | <pre> | |
517 | void clear_vertex(vertex_descriptor u, adjacency_matrix& g) | |
518 | </pre> | |
519 | Removes all edges to and from vertex <tt>u</tt>. The vertex still appears | |
520 | in the vertex set of the graph.<br> | |
521 | (Required by <a href="MutableGraph.html">MutableGraph</a>.) | |
522 | ||
523 | <hr> | |
524 | <pre> | |
525 | template <typename Property> | |
526 | property_map<adjacency_matrix, Property>::type | |
527 | get(Property, adjacency_matrix& g) | |
528 | ||
529 | template <typename Property> | |
530 | property_map<adjacency_matrix, Property>::const_type | |
531 | get(Property, const adjacency_matrix& g) | |
532 | </pre> | |
533 | Returns the property map object for the vertex property specified by | |
534 | <tt>Property</tt>. The <tt>Property</tt> must match one of the | |
535 | properties specified in the graph's <tt>VertexProperty</tt> template | |
536 | argument.<br> | |
537 | (Required by <a href="PropertyGraph.html">PropertyGraph</a>.) | |
538 | ||
539 | <hr> | |
540 | <pre> | |
541 | template <typename Property, typename X> | |
542 | typename property_traits< | |
543 | typename property_map<adjacency_matrix, Property>::const_type | |
544 | >::value_type | |
545 | get(Property, const adjacency_matrix& g, X x) | |
546 | </pre> | |
547 | This returns the property value for <tt>x</tt>, which is either | |
548 | a vertex or edge descriptor.<br> | |
549 | (Required by <a href="PropertyGraph.html">PropertyGraph</a>.) | |
550 | ||
551 | <hr> | |
552 | <pre> | |
553 | template <typename Property, typename X, typename Value> | |
554 | void | |
555 | put(Property, const adjacency_matrix& g, X x, const Value& value) | |
556 | </pre> | |
557 | This sets the property value for <tt>x</tt> to | |
558 | <tt>value</tt>. <tt>x</tt> is either a vertex or edge descriptor. | |
559 | <tt>Value</tt> must be convertible to | |
560 | <tt>typename property_traits<property_map<adjacency_matrix, Property>::type>::value_type</tt>.<br> | |
561 | (Required by <a href="PropertyGraph.html">PropertyGraph</a>.) | |
562 | ||
563 | <hr> | |
564 | <pre> | |
565 | template <typename GraphProperty, typename GraphProperty> | |
566 | typename property_value<GraphProperty, GraphProperty>::type& | |
567 | get_property(adjacency_matrix& g, GraphProperty) | |
568 | </pre> | |
569 | Return the property specified by <tt>GraphProperty</tt> that is attached | |
570 | to the graph object <tt>g</tt>. The <tt>property_value</tt> traits class | |
571 | is defined in <tt>boost/pending/property.hpp</tt>. | |
572 | ||
573 | <hr> | |
574 | <pre> | |
575 | template <typename GraphProperty, typename GraphProperty> | |
576 | const typename property_value<GraphProperty, GraphProperty>::type& | |
577 | get_property(const adjacency_matrix& g, GraphProperty) | |
578 | </pre> | |
579 | Return the property specified by <tt>GraphProperty</tt> that is | |
580 | attached to the graph object <tt>g</tt>. The <tt>property_value</tt> | |
581 | traits class is defined in <tt>boost/pending/property.hpp</tt>. | |
582 | ||
583 | ||
584 | <hr> |