Planet

navi

home

PPS

about

screenshots

download

development

forum

Context Navigation

source: downloads/boost_1_34_1/libs/graph/doc/adjacency_matrix.html @ 30

Last change on this file since 30 was 29, checked in by landauf, 17 years ago
updated boost from 1_33_1 to 1_34_1
File size: 19.0 KB

Line
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><A NAME="1509"></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><A NAME="1509"></A>
76	<TABLE>
77	<CAPTION ALIGN="BOTTOM"><STRONG>Figure 1:</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>Associates 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>

Note: See TracBrowser for help on using the repository browser.

Download in other formats: