| <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<Directed, VertexProperty, |
| EdgeProperty, GraphProperty, |
| Allocator> |
| </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 1:</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<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 << "vertex set: "; |
| boost::print_vertices(g, name); |
| std::cout << std::endl; |
| |
| std::cout << "edge set: "; |
| boost::print_edges(g, name); |
| std::cout << std::endl; |
| |
| std::cout << "out-edges: " << std::endl; |
| boost::print_graph(g, name); |
| std::cout << 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<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 << "vertex set: "; |
| boost::print_vertices(ug, name); |
| std::cout << std::endl; |
| |
| std::cout << "edge set: "; |
| boost::print_edges(ug, name); |
| std::cout << std::endl; |
| |
| std::cout << "incident edges: " << std::endl; |
| boost::print_graph(ug, name); |
| std::cout << 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 <--> C F |
| B <--> C F |
| C <--> A B |
| D <--> E |
| E <--> D |
| F <--> 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<adjacency_matrix>::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<adjacency_matrix>::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<adjacency_matrix>::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<adjacency_matrix>::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<adjacency_matrix>::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<adjacency_matrix>::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<adjacency_matrix>::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<adjacency_matrix>::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<adjacency_matrix>::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<adjacency_matrix>::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<adjacency_matrix>::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<adjacency_matrix>::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<adjacency_matrix, PropertyTag>::type</tt><br> |
| <tt>property_map<adjacency_matrix, PropertyTag>::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 <typename EdgeIterator> |
| 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 <typename EdgeIterator, typename EdgePropertyIterator> |
| 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<vertex_iterator, vertex_iterator> |
| vertices(const adjacency_matrix& 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<edge_iterator, edge_iterator> |
| edges(const adjacency_matrix& 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<adjacency_iterator, adjacency_iterator> |
| adjacent_vertices(vertex_descriptor v, const adjacency_matrix& 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<out_edge_iterator, out_edge_iterator> |
| out_edges(vertex_descriptor v, const adjacency_matrix& 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& 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& 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& 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<in_edge_iterator, in_edge_iterator> |
| in_edges(vertex_descriptor v, const adjacency_matrix& 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& 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& 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& 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& g) |
| </pre> |
| Returns the nth vertex in the graph's vertex list. |
| |
| <hr> |
| <pre> |
| std::pair<edge_descriptor, bool> |
| edge(vertex_descriptor u, vertex_descriptor v, |
| const adjacency_matrix& 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<edge_descriptor, bool> |
| add_edge(vertex_descriptor u, vertex_descriptor v, |
| adjacency_matrix& 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<edge_descriptor, bool> |
| add_edge(vertex_descriptor u, vertex_descriptor v, |
| const EdgeProperty& p, |
| adjacency_matrix& 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& 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& 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& 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 <typename Property> |
| property_map<adjacency_matrix, Property>::type |
| get(Property, adjacency_matrix& g) |
| |
| template <typename Property> |
| property_map<adjacency_matrix, Property>::const_type |
| get(Property, const adjacency_matrix& 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 <typename Property, typename X> |
| typename property_traits< |
| typename property_map<adjacency_matrix, Property>::const_type |
| >::value_type |
| get(Property, const adjacency_matrix& 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 <typename Property, typename X, typename Value> |
| void |
| put(Property, const adjacency_matrix& 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<property_map<adjacency_matrix, Property>::type>::value_type</tt>.<br> |
| (Required by <a href="PropertyGraph.html">PropertyGraph</a>.) |
| |
| <hr> |
| <pre> |
| template <typename GraphProperty, typename GraphProperty> |
| typename property_value<GraphProperty, GraphProperty>::type& |
| get_property(adjacency_matrix& 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 <typename GraphProperty, typename GraphProperty> |
| const typename property_value<GraphProperty, GraphProperty>::type& |
| get_property(const adjacency_matrix& 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> |