123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161 |
- <HTML>
- <!--
- Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 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>IteratorConstructibleGraph</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="concept:IteratorConstructibleGraph"></A>
- IteratorConstructibleGraph
- </H1>
- The IteratorConstructibleGraph concept describes the interface for
- graph types that can be constructed using a kind of edge iterator. The
- edge iterator can be any <a
- href="http://www.boost.org/sgi/stl/InputIterator.html">InputIterator</a>
- that dereferences to a pair of integers <i>(i,j)</i>, which represent
- an edge that should be in the graph. The two integers <i>i</i> and
- <i>j</i> represent vertices where <i>0 <= i < |V|</i> and <i>0 <= j <
- |V|</i>. The edge iterator's value type should be
- <tt>std::pair<T,T></tt> (or at least be a structure that has
- members <tt>first</tt> and <tt>second</tt>) and the value type
- <tt>T</tt> of the pair must be convertible to the
- <tt>vertices_size_type</tt> of the graph (an integer).
- There are two valid expressions required by this concept, both of
- which are constructors. The first creates a graph object from a
- first/last iterator range. The second constructor also takes a
- first/last iterator range and in addition requires the number of
- vertices and number of edges. For some graph and edge iterator types
- the second constructor can be more efficient than the first.
- <h3>Example</h3>
- The following exampe creates two graph objects from an array of edges
- (vertex pairs). The type <tt>Edge*</tt> satisfies the requirements for
- an <a
- href="http://www.boost.org/sgi/stl/InputIterator.html">InputIterator</a>
- and can therefore be used to construct a graph.
- <pre>
- typedef ... IteratorConstructibleGraph;
- typedef boost::graph_traits<IteratorConstructibleGraph> Traits;
- typedef std::pair<Traits::vertices_size_type,
- Traits::vertices_size_type> Edge;
- Edge edge_array[] =
- { Edge(0,1), Edge(0,2), Edge(0,3), Edge(0,4), Edge(0,5),
- Edge(1, 2), Edge(1,5), Edge(1,3),
- Edge(2, 4), Edge(2,5),
- Edge(3, 2),
- Edge(4, 3), Edge(4,1),
- Edge(5, 4) };
- Edge* first = edge_array,
- last = edge_array + sizeof(edge_array)/sizeof(Edge);
- IteratorConstructibleGraph G1(first, last);
- // do something with G1 ...
-
- Traits::vertices_size_type size_V = 6;
- Traits::edges_size_type size_E = sizeof(edge_array)/sizeof(Edge);
- IteratorConstructibleGraph G2(first, last, size_V, size_E);
- // do something with G2 ...
- </pre>
- <h3>Refinement of</h3>
- <a href="Graph.html">Graph</a>
- <h3>Notation</h3>
- <Table>
- <tr>
- <td><tt>G</tt></td>
- <td>is a graph type that models IteratorConstructibleGraph.</td>
- <tr>
- <tr>
- <td><tt>g</tt></td>
- <td>is an object of type <tt>G</tt>.</td>
- </tr>
- <tr>
- <td><tt>first, last</tt></td>
- <td>are edge iterators (see above).</td>
- </tr>
- <tr>
- <td><tt>Tr</tt></td>
- <td>is an object of type <tt>graph_traits<G></tt>.</td>
- </tr>
- <tr>
- <td><tt>n_vertices</tt></td>
- <td>is an object of type <tt>Tr::vertices_size_type</tt>.</td>
- </tr>
- <tr>
- <td><tt>n_edges</tt></td>
- <td>is an object of type <tt>Tr::edges_size_type</tt>.</td>
- </tr>
- </Table>
- <h3>Valid Expressions</h3>
- <Table border>
- <tr>
- <td>
- <pre>G g(first, last);</pre>
- Construct graph object <tt>g</tt> given an edge range <tt>[first,last)</tt>.
- </td>
- <tr>
- <tr>
- <td>
- <pre>G g(first, last, n_vertices, n_edges);</pre>
- Construct graph object <tt>g</tt> given an edge range
- <tt>[first,last)</tt>, the number of vertices, and the number of
- edges. Sometimes this constructor is more efficient than the
- constructor lacking the graph size information.
- </td>
- </tr>
- </Table>
- <!--
- <H3>Concept Checking Class</H3>
- <PRE>
- </PRE>
- -->
- <br>
- <HR>
- <TABLE>
- <TR valign=top>
- <TD nowrap>Copyright © 2000-2001</TD><TD>
- <A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>,
- Indiana University (<A
- HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br>
- <A HREF="http://www.boost.org/people/liequan_lee.htm">Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@cs.indiana.edu">llee@cs.indiana.edu</A>)<br>
- <A HREF="https://homes.cs.washington.edu/~al75">Andrew Lumsdaine</A>,
- Indiana University (<A
- HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
- </TD></TR></TABLE>
- </BODY>
- </HTML>
|