[ceph.git] / ceph / src / boost / libs / graph / doc / adjacency_matrix.html

<HTML>
<!--
     Copyright (c) Jeremy Siek 2000
    
     Distributed under the Boost Software License, Version 1.0.
     (See accompanying file LICENSE_1_0.txt or copy at
     http://www.boost.org/LICENSE_1_0.txt)
  -->
<Head>
<Title>Boost Graph Library: Adjacency Matrix</Title>
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 
        ALINK="#ff0000"> 
<IMG SRC="../../../boost.png" 
     ALT="C++ Boost" width="277" height="86"> 

<BR Clear>

<H1><A NAME="sec:adjacency-matrix-class"></A>
<pre>
adjacency_matrix&lt;Directed, VertexProperty, 
                 EdgeProperty, GraphProperty,
                 Allocator&gt;
</pre>
</H1>

The <tt>adjacency_matrix</tt> class implements the BGL graph interface
using the traditional adjacency matrix storage format. For a graph
with <i>V</i> vertices, a <i>V x V</i> matrix is used, where each
element <i>a<sub>ij</sub></i> is a boolean flag that says whether
there is an edge from vertex <i>i</i> to vertex <i>j</i>. <a
href="#fig:adj-matrix-graph">Figure 1</a> shows the adjacency matrix
representation of a graph.

<P></P>
<DIV ALIGN="center"><A NAME="fig:adj-matrix-graph"></A>
<TABLE>
<CAPTION ALIGN="BOTTOM"><STRONG>Figure 1:</STRONG> Adjacency Matrix Representation of a Directed Graph.</CAPTION>
<TR><TD><IMG SRC="./figs/adj-matrix-graph3.gif" width="386" height="284"></TD>
<TD><IMG SRC="./figs/adj-matrix.gif" width="135" height="136"></TD></TR>
</TABLE>
</DIV><P></P>

The advantage of this matrix format over the adjacency list is that
edge insertion and removal is constant time.  There are several
disadvantages. The first is that the amount of memory used is
<i>O(V<sup>2</sup>)</i> instead of <i>O(V + E)</i> (where <i>E</i> is
the number of edges). The second is that operations that traverse all
the out-edges of each vertex (such as breadth-first search) run in
<i>O(V<sup>2</sup>)</i> time instead of <i>O(V + E)</i> time for the
adjacency list. In short, it is better to use the
<tt>adjacency_matrix</tt> for dense graphs (where <i>E</i> is close to
<i>V<sup>2</sup></i>) and it is better to use <a
href="adjacency_list.html"><tt>adjacency_list</tt></a> for sparse
graphs (where <i>E</i> is much smaller than <i>V<sup>2</sup></i>).

The <tt>adjacency_matrix</tt> class extends the traditional
data-structure by allowing objects to be attached to vertices and
edges using the same property template parameters supported by <a
href="adjacency_list.html"><tt>adjacency_list</tt></a>. These may be
<a href="bundles.html">bundled properties</a> or standard (backward-compatible)
<a
href="using_adjacency_list.html#sec:adjacency-list-properties">interior
properties</a>. The types of all property values must be
Copy Constructible, Assignable and Default Constructible. 

In the case of an undirected graph, the
<tt>adjacency_matrix</tt>. class does not use a full <i>V x V</i>
matrix but instead uses a lower triangle (the diagonal and below)
since the matrix for an undirected graph is symmetric. This reduces
the storage to <i>(V<sup>2</sup>)/2</i>.  <a
href="#fig:undir-adj-matrix-graph">Figure 2</a> shows an adjacency
matrix representation of an undirected graph.

<P></P>
<DIV ALIGN="center"><A NAME="fig:undir-adj-matrix-graph"></A>
<TABLE>
<CAPTION ALIGN="BOTTOM"><STRONG>Figure 2:</STRONG> Adjacency Matrix Representation of an Undirected Graph.</CAPTION>
<TR><TD><IMG SRC="./figs/undir-adj-matrix-graph3.gif" width="260" height="240"></TD>
<TD><IMG SRC="./figs/undir-adj-matrix2.gif" width="135" height="136"></TD></TR>
</TABLE>
</DIV><P></P>


<h3>Example</h3>

Creating the graph of <a href="#fig:adj-matrix-graph">Figure 1</a>. 
<pre>
  enum { A, B, C, D, E, F, N };
  const char* name = "ABCDEF";
  
  typedef boost::adjacency_matrix&lt;boost::directedS> Graph;
  Graph g(N);
  add_edge(B, C, g);
  add_edge(B, F, g);
  add_edge(C, A, g);
  add_edge(C, C, g);
  add_edge(D, E, g);
  add_edge(E, D, g);
  add_edge(F, A, g);

  std::cout &lt;&lt; "vertex set: ";
  boost::print_vertices(g, name);
  std::cout &lt;&lt; std::endl;

  std::cout &lt;&lt; "edge set: ";
  boost::print_edges(g, name);
  std::cout &lt;&lt; std::endl;

  std::cout &lt;&lt; "out-edges: " &lt;&lt; std::endl;
  boost::print_graph(g, name);
  std::cout &lt;&lt; std::endl;
</pre>
The output is:
<pre>
  vertex set: A B C D E F 

  edge set: (B,C) (B,F) (C,A) (C,C) (D,E) (E,D) (F,A) 

  out-edges: 
  A --> 
  B --> C F 
  C --> A C 
  D --> E 
  E --> D 
  F --> A 
</pre>

Creating the graph of <a href="#fig:undir-adj-matrix-graph">Figure 2</a>.
<pre>
  enum { A, B, C, D, E, F, N };
  const char* name = "ABCDEF";

  typedef boost::adjacency_matrix&lt;boost::undirectedS> UGraph;
  UGraph ug(N);
  add_edge(B, C, ug);
  add_edge(B, F, ug);
  add_edge(C, A, ug);
  add_edge(D, E, ug);
  add_edge(F, A, ug);

  std::cout &lt;&lt; "vertex set: ";
  boost::print_vertices(ug, name);
  std::cout &lt;&lt; std::endl;

  std::cout &lt;&lt; "edge set: ";
  boost::print_edges(ug, name);
  std::cout &lt;&lt; std::endl;

  std::cout &lt;&lt; "incident edges: " &lt;&lt; std::endl;
  boost::print_graph(ug, name);
  std::cout &lt;&lt; std::endl;
</pre>
The output is:
<pre>
  vertex set: A B C D E F 

  edge set: (C,A) (C,B) (E,D) (F,A) (F,B) 

  incident edges: 
  A &lt;--> C F 
  B &lt;--> C F 
  C &lt;--> A B 
  D &lt;--> E 
  E &lt;--> D 
  F &lt;--> A B 
</pre>


<h3>Where Defined</h3>

<a href="../../../boost/graph/adjacency_matrix.hpp"><tt>boost/graph/adjacency_matrix.hpp</tt></a>


<h3>Template Parameters</h3>

<p>
<table border>

<TR>
<th>Parameter</th><th>Description</th><th>Default</th>
</tr>

<tr>
  <td><tt>Directed</tt></td>
  <td>A selector to choose whether the graph is directed or undirected. The options are <tt>directedS</tt> and <tt>undirectedS</tt>.</td>
  <td><tt>directedS</tt></td>
</tr>
<tr>
  <td><tt>VertexProperty</tt></td>
  <td>for specifying internal property storage.</td>
  <td><tt>no_property</tt></td>
</tr>
<tr>
  <td><tt>EdgeProperty</tt></td>
  <td>for specifying internal property storage.</td>
  <td><tt>no_property</tt></td>
</tr>
<tr>
  <td><tt>GraphProperty</tt></td>
  <td>for specifying property storage for the graph object.</td>
  <td><tt>no_property</tt></td>
</tr>

</table>

<h3>Model Of</h3>

<a href="./VertexAndEdgeListGraph.html">VertexAndEdgeListGraph</a>, 
<a href="./IncidenceGraph.html">Incidence Graph</a>,
<a href="./BidirectionalGraph.html">Bidirectional Graph</a>,
<a
href="./AdjacencyMatrix.html">AdjacencyMatrix</a>, <a
href="./MutablePropertyGraph.html">MutablePropertyGraph</a>,
<a href="../../utility/CopyConstructible.html">CopyConstructible</a>,
and <a href="../../utility/Assignable.html">Assignable</a>.


<h3>Associated Types</h3>

<hr>

<tt>graph_traits&lt;adjacency_matrix&gt;::vertex_descriptor</tt>
<br><br>
The type for the vertex descriptors associated with the
<tt>adjacency_matrix</tt>.<br>
(Required by <a href="./Graph.html">Graph</a>.)

<hr>

<tt>graph_traits&lt;adjacency_matrix&gt;::edge_descriptor</tt>
<br><br>
The type for the edge descriptors associated with the
  <tt>adjacency_matrix</tt>.<br>
 (Required by <a href="Graph.html">Graph</a>.)

<hr>
<tt>graph_traits&lt;adjacency_matrix&gt;::vertex_iterator</tt>
<br><br>
  The type for the iterators returned by <tt>vertices()</tt>.  
  The vertex iterator models <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>. <br>
 (Required by <a href="VertexListGraph.html">VertexListGraph</a>.)

<hr>
<tt>graph_traits&lt;adjacency_matrix&gt;::edge_iterator</tt>
<br><br>
  The type for the iterators returned by <tt>edges()</tt>. This
  iterator models <a href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>.<br>
 (Required by <a href="EdgeListGraph.html">EdgeListGraph</a>.)

<hr>
<tt>graph_traits&lt;adjacency_matrix&gt;::out_edge_iterator</tt>
<br><br>
  The type for the iterators returned by <tt>out_edges()</tt>.  This
  iterator models <a href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>. <br>
  (Required by <a href="IncidenceGraph.html">IncidenceGraph</a>.)

<hr>
<tt>graph_traits&lt;adjacency_matrix&gt;::in_edge_iterator</tt>
<br><br>
  The type for the iterators returned by <tt>in_edges()</tt>.  This
  iterator models <a href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>. <br>
  (Required by <a href="BidirectionalGraph.html">BidirectionalGraph</a>.)

<hr>
<tt>graph_traits&lt;adjacency_matrix&gt;::adjacency_iterator</tt>
<br><br>
  The type for the iterators returned by <tt>adjacent_vertices()</tt>. This
  iterator models the same concept as the out-edge iterator.<br>
  (Required by <a href="AdjacencyGraph.html">AdjacencyGraph</a>.)

<hr>
<tt>graph_traits&lt;adjacency_matrix&gt;::directed_category</tt>
<br><br>
  Provides information about whether the graph is directed
  (<tt>directed_tag</tt>) or undirected (<tt>undirected_tag</tt>).<br>
  (Required by <a href="Graph.html">Graph</a>.)

<hr>
<tt>graph_traits&lt;adjacency_matrix&gt;::edge_parallel_category</tt>
<br><br>
  An adjacency matrix does not allow the insertion of
  parallel edges, so this type is always
  <tt>disallow_parallel_edge_tag</tt>. <br>
  (Required by <a href="Graph.html">Graph</a>.)

<hr>
<tt>graph_traits&lt;adjacency_matrix&gt;::vertices_size_type</tt>
<br><br>
  The type used for dealing with the number of vertices in
  the graph.<br>
  (Required by <a href="VertexListGraph.html">VertexListGraph</a>.)

<hr>
<tt>graph_traits&lt;adjacency_matrix&gt;::edges_size_type</tt>
<br><br>
  The type used for dealing with the number of edges in the graph.<br>
  (Required by <a href="EdgeListGraph.html">EdgeListGraph</a>.)

<hr>
<tt>graph_traits&lt;adjacency_matrix&gt;::degree_size_type</tt>
<br><br>
  The type used for dealing with the number of out-edges of a vertex.<br>
  (Required by <a href="IncidenceGraph.html">IncidenceGraph</a>.)

<hr>
<tt>property_map&lt;adjacency_matrix, PropertyTag&gt;::type</tt><br>
<tt>property_map&lt;adjacency_matrix, PropertyTag&gt;::const_type</tt>
<br><br>
  The map type for vertex or edge properties in the graph. The
  specific property is specified by the <tt>PropertyTag</tt> template
  argument, and must match one of the properties specified in the
  <tt>VertexProperty</tt> or <tt>EdgeProperty</tt> for the graph.<br>
  (Required by <a href="PropertyGraph.html">PropertyGraph</a>.)

<hr>

<h3>Member Functions</h3>

<hr>
<pre>
adjacency_matrix(vertices_size_type n,
                 const GraphProperty& p = GraphProperty())
</pre>
Creates a graph object with <tt>n</tt> vertices and zero edges.<br>
(Required by <a href="MutableGraph.html">MutableGraph</a>.)

<hr>
<pre>
template &lt;typename EdgeIterator&gt;
adjacency_matrix(EdgeIterator first,
                 EdgeIterator last,
                 vertices_size_type n,
                 const GraphProperty& p = GraphProperty())
</pre>
  Creates a graph object with <tt>n</tt> vertices with the edges
  specified in the edge list given by the range <tt>[first, last)</tt>.
  The value type of the <tt>EdgeIterator</tt> must be a
  <tt>std::pair</tt>, where the type in the pair is an integer type. The
  integers will correspond to vertices, and they must all fall in the
  range of
  <tt>[0, n)</tt>. <br>
  (Required by <a href="IteratorConstructibleGraph.html">IteratorConstructibleGraph</a>.)

<hr>
<pre>
template &lt;typename EdgeIterator, typename EdgePropertyIterator&gt;
adjacency_matrix(EdgeIterator first, EdgeIterator last,
                 EdgePropertyIterator ep_iter,
                 vertices_size_type n,
                 const GraphProperty& p = GraphProperty())
</pre>
  Creates a graph object with <tt>n</tt> vertices, with the edges
  specified in the edge list given by the range <tt>[first, last)</tt>.
  The value type of the <tt>EdgeIterator</tt> must be a
  <tt>std::pair</tt>, where the type in the pair is an integer type. The
  integers will correspond to vertices, and they must all fall in the
  range of <tt>[0, n)</tt>. The <tt>value_type</tt> of the
  <tt>ep_iter</tt> should be <tt>EdgeProperty</tt>.

<hr>


<h3>Non-Member Functions</h3>

<hr>
<pre>
std::pair&lt;vertex_iterator, vertex_iterator&gt;
vertices(const adjacency_matrix&amp; g)
</pre>
Returns an iterator-range providing access to the vertex set of graph <tt>g</tt>.<br>
(Required by <a href="VertexListGraph.html">VertexListGraph</a>.)

<hr>
<pre>
std::pair&lt;edge_iterator, edge_iterator&gt;
edges(const adjacency_matrix&amp; g);
</pre>
Returns an iterator-range providing access to the edge set of graph <tt>g</tt>.<br>
(Required by <a href="EdgeListGraph.html">EdgeListGraph</a>.)

<hr>
<pre>
std::pair&lt;adjacency_iterator, adjacency_iterator&gt;
adjacent_vertices(vertex_descriptor v, const adjacency_matrix&amp; g)
</pre>
Returns an iterator-range providing access to the vertices adjacent to
vertex <tt>v</tt> in graph <tt>g</tt>.<br>
(Required by <a href="AdjacencyGraph.html">AdjacencyGraph</a>.)

<hr>
<pre>
std::pair&lt;out_edge_iterator, out_edge_iterator&gt;
out_edges(vertex_descriptor v, const adjacency_matrix&amp; g)
</pre>
Returns an iterator-range providing access to the out-edges of
vertex <tt>v</tt> in graph <tt>g</tt>. If the graph is undirected,
this iterator-range provides access to all edges incident on
vertex <tt>v</tt>. <br>
(Required by <a href="IncidenceGraph.html">IncidenceGraph</a>.)

<hr>
<pre>
vertex_descriptor
source(edge_descriptor e, const adjacency_matrix&amp; g)
</pre>
Returns the source vertex of edge <tt>e</tt>.<br>
(Required by <a href="IncidenceGraph.html">IncidenceGraph</a>.)

<hr>
<pre>
vertex_descriptor
target(edge_descriptor e, const adjacency_matrix&amp; g)
</pre>
Returns the target vertex of edge <tt>e</tt>.<br>
(Required by <a href="IncidenceGraph.html">IncidenceGraph</a>.)

<hr>
<pre>
degree_size_type
out_degree(vertex_descriptor u, const adjacency_matrix&amp; g)
</pre>
Returns the number of edges leaving vertex <tt>u</tt>.<br>
(Required by <a href="IncidenceGraph.html">IncidenceGraph</a>.) 
<hr>

<hr>
<pre>
std::pair&lt;in_edge_iterator, in_edge_iterator&gt;
in_edges(vertex_descriptor v, const adjacency_matrix&amp; g)
</pre>
Returns an iterator-range providing access to the in-edges of
vertex <tt>v</tt> in graph <tt>g</tt>. If the graph is undirected,
this iterator-range provides access to all edges incident on
vertex <tt>v</tt>. <br>
(Required by <a href="BidirectionalGraph.html">BidirectionalGraph</a>.)

<hr>
<pre>
degree_size_type
in_degree(vertex_descriptor u, const adjacency_matrix&amp; g)
</pre>
Returns the number of edges entering vertex <tt>u</tt>.<br>
(Required by <a href="BidirectionalGraph.html">BidirectionalGraph</a>.) 
<hr>

<hr>
<pre>
vertices_size_type num_vertices(const adjacency_matrix&amp; g)
</pre>
Returns the number of vertices in the graph <tt>g</tt>.<br>
(Required by <a href="VertexListGraph.html">VertexListGraph</a>.)

<hr>
<pre>
edges_size_type num_edges(const adjacency_matrix&amp; g)
</pre>
Returns the number of edges in the graph <tt>g</tt>.<br>
(Required by <a href="EdgeListGraph.html">EdgeListGraph</a>.)

<hr>
<pre>
vertex_descriptor vertex(vertices_size_type n, const adjacency_matrix&amp; g)
</pre>
Returns the nth vertex in the graph's vertex list.

<hr>
<pre>
std::pair&lt;edge_descriptor, bool&gt;
edge(vertex_descriptor u, vertex_descriptor v,
     const adjacency_matrix&amp; g)
</pre>
Returns the edge connecting vertex <tt>u</tt> to vertex <tt>v</tt> in graph <tt>g</tt>.<br>
(Required by <a href="AdjacencyMatrix.html">AdjacencyMatrix</a>.)

<hr>
<pre>
std::pair&lt;edge_descriptor, bool&gt;
add_edge(vertex_descriptor u, vertex_descriptor v,
         adjacency_matrix&amp; g)
</pre>
  Adds edge <tt>(u,v)</tt> to the graph and returns the edge descriptor for
  the new edge. If the edge is already in the graph then a duplicate
  will not be added and the <tt>bool</tt> flag will be <tt>false</tt>.
  This operation does not invalidate any of the graph's iterators
  or descriptors.<br>
(Required by <a href="MutableGraph.html">MutableGraph</a>.)

<hr>
<pre>
std::pair&lt;edge_descriptor, bool&gt;
add_edge(vertex_descriptor u, vertex_descriptor v,
         const EdgeProperty& p,
         adjacency_matrix&amp; g)
</pre>
Adds edge <tt>(u,v)</tt> to the graph and attaches <tt>p</tt> as the
value of the edge's internal property storage.  Also see the previous
<tt>add_edge()</tt> member function for more details.

<hr>
<pre>
void remove_edge(vertex_descriptor u, vertex_descriptor v,
                 adjacency_matrix&amp; g)
</pre>
Removes the edge <tt>(u,v)</tt> from the graph.  <br>
(Required by <a href="MutableGraph.html">MutableGraph</a>.)

<hr>
<pre>
void remove_edge(edge_descriptor e, adjacency_matrix&amp; g)
</pre>
Removes the edge <tt>e</tt> from the graph. This is equivalent
to calling <tt>remove_edge(source(e, g), target(e, g), g)</tt>.<br>
(Required by <a href="MutableGraph.html">MutableGraph</a>.)

<hr>
<pre>
void clear_vertex(vertex_descriptor u, adjacency_matrix&amp; g)
</pre>
Removes all edges to and from vertex <tt>u</tt>. The vertex still appears
in the vertex set of the graph.<br>
(Required by <a href="MutableGraph.html">MutableGraph</a>.)

<hr>
<pre>
template &lt;typename Property&gt;
property_map&lt;adjacency_matrix, Property&gt;::type
get(Property, adjacency_matrix&amp; g)

template &lt;typename Property&gt;
property_map&lt;adjacency_matrix, Property&gt;::const_type
get(Property, const adjacency_matrix&amp; g)
</pre>
Returns the property map object for the vertex property specified by
<tt>Property</tt>. The <tt>Property</tt> must match one of the
properties specified in the graph's <tt>VertexProperty</tt> template
argument.<br>
(Required by <a href="PropertyGraph.html">PropertyGraph</a>.)

<hr>
<pre>
template &lt;typename Property, typename X&gt;
typename property_traits&lt;
  typename property_map&lt;adjacency_matrix, Property&gt;::const_type
&gt;::value_type
get(Property, const adjacency_matrix&amp; g, X x)
</pre>
This returns the property value for <tt>x</tt>, which is either
a vertex or edge descriptor.<br>
(Required by <a href="PropertyGraph.html">PropertyGraph</a>.)

<hr>
<pre>
template &lt;typename Property, typename X, typename Value&gt;
void
put(Property, const adjacency_matrix&amp; g, X x, const Value& value)
</pre>
This sets the property value for <tt>x</tt> to
<tt>value</tt>. <tt>x</tt> is either a vertex or edge descriptor.
<tt>Value</tt> must be convertible to
<tt>typename property_traits&lt;property_map&lt;adjacency_matrix, Property&gt;::type&gt;::value_type</tt>.<br>
(Required by <a href="PropertyGraph.html">PropertyGraph</a>.)

<hr>
<pre>
template &lt;typename GraphProperty, typename GraphProperty&gt;
typename property_value&lt;GraphProperty, GraphProperty&gt;::type&amp;
get_property(adjacency_matrix&amp; g, GraphProperty)
</pre>
Return the property specified by <tt>GraphProperty</tt> that is attached
to the graph object <tt>g</tt>. The <tt>property_value</tt> traits class
is defined in <tt>boost/pending/property.hpp</tt>.

<hr>
<pre>
template &lt;typename GraphProperty, typename GraphProperty&gt;
const typename property_value&lt;GraphProperty, GraphProperty&gt;::type&amp;
get_property(const adjacency_matrix&amp; g, GraphProperty)
</pre>
Return the property specified by <tt>GraphProperty</tt> that is
attached to the graph object <tt>g</tt>.  The <tt>property_value</tt>
traits class is defined in <tt>boost/pending/property.hpp</tt>.


<hr>
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>