123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584 |
- <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 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<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.boost.org/sgi/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>
|