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

<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.sgi.com/tech/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&lt;T,T&gt;</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.sgi.com/tech/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&lt;G&gt;</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 &copy; 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="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>,
Indiana University (<A
HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
</TD></TR></TABLE>

</BODY>
</HTML>
Commit	Line	Data
7c673cae FG	1	<HTML>
	2	<!--
	3	Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 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>IteratorConstructibleGraph</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="concept:IteratorConstructibleGraph"></A>
	19	IteratorConstructibleGraph
	20	</H1>
	21
	22	The IteratorConstructibleGraph concept describes the interface for
	23	graph types that can be constructed using a kind of edge iterator. The
	24	edge iterator can be any <a
	25	href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>
	26	that dereferences to a pair of integers <i>(i,j)</i>, which represent
	27	an edge that should be in the graph. The two integers <i>i</i> and
	28	<i>j</i> represent vertices where <i>0 <= i < \|V\|</i> and <i>0 <= j <
	29	\|V\|</i>. The edge iterator's value type should be
	30	<tt>std::pair<T,T></tt> (or at least be a structure that has
	31	members <tt>first</tt> and <tt>second</tt>) and the value type
	32	<tt>T</tt> of the pair must be convertible to the
	33	<tt>vertices_size_type</tt> of the graph (an integer).
	34
	35	There are two valid expressions required by this concept, both of
	36	which are constructors. The first creates a graph object from a
	37	first/last iterator range. The second constructor also takes a
	38	first/last iterator range and in addition requires the number of
	39	vertices and number of edges. For some graph and edge iterator types
	40	the second constructor can be more efficient than the first.
	41
	42	<h3>Example</h3>
	43
	44	The following exampe creates two graph objects from an array of edges
	45	(vertex pairs). The type <tt>Edge*</tt> satisfies the requirements for
	46	an <a
	47	href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>
	48	and can therefore be used to construct a graph.
	49
	50	<pre>
	51	typedef ... IteratorConstructibleGraph;
	52	typedef boost::graph_traits<IteratorConstructibleGraph> Traits;
	53
	54	typedef std::pair<Traits::vertices_size_type,
	55	Traits::vertices_size_type> Edge;
	56	Edge edge_array[] =
	57	{ Edge(0,1), Edge(0,2), Edge(0,3), Edge(0,4), Edge(0,5),
	58	Edge(1, 2), Edge(1,5), Edge(1,3),
	59	Edge(2, 4), Edge(2,5),
	60	Edge(3, 2),
	61	Edge(4, 3), Edge(4,1),
	62	Edge(5, 4) };
	63	Edge* first = edge_array,
	64	last = edge_array + sizeof(edge_array)/sizeof(Edge);
65
66	IteratorConstructibleGraph G1(first, last);
67	// do something with G1 ...
68
69	Traits::vertices_size_type size_V = 6;
70	Traits::edges_size_type size_E = sizeof(edge_array)/sizeof(Edge);
71	IteratorConstructibleGraph G2(first, last, size_V, size_E);
72	// do something with G2 ...
73	</pre>
74
75	<h3>Refinement of</h3>
76
77	<a href="Graph.html">Graph</a>
78
79	<h3>Notation</h3>
80
81	<Table>
82	<tr>
83	<td><tt>G</tt></td>
84	<td>is a graph type that models IteratorConstructibleGraph.</td>
85	<tr>
86
87	<tr>
88	<td><tt>g</tt></td>
89	<td>is an object of type <tt>G</tt>.</td>
90	</tr>
91
92	<tr>
93	<td><tt>first, last</tt></td>
94	<td>are edge iterators (see above).</td>
95	</tr>
96
97	<tr>
98	<td><tt>Tr</tt></td>
99	<td>is an object of type <tt>graph_traits<G></tt>.</td>
100	</tr>
101
102	<tr>
103	<td><tt>n_vertices</tt></td>
104	<td>is an object of type <tt>Tr::vertices_size_type</tt>.</td>
105	</tr>
106
107	<tr>
108	<td><tt>n_edges</tt></td>
109	<td>is an object of type <tt>Tr::edges_size_type</tt>.</td>
110	</tr>
111
112	</Table>
113
114
115	<h3>Valid Expressions</h3>
116
117	<Table border>
118
119	<tr>
120	<td>
121	<pre>G g(first, last);</pre>
122	Construct graph object <tt>g</tt> given an edge range <tt>[first,last)</tt>.
123	</td>
124	<tr>
125
126	<tr>
127	<td>
128	<pre>G g(first, last, n_vertices, n_edges);</pre>
129	Construct graph object <tt>g</tt> given an edge range
130	<tt>[first,last)</tt>, the number of vertices, and the number of
131	edges. Sometimes this constructor is more efficient than the
132	constructor lacking the graph size information.
133	</td>
134	</tr>
135
136	</Table>
137
138
139	<!--
140	<H3>Concept Checking Class</H3>
141
142	<PRE>
143	</PRE>
144	-->
145
146	<br>
147	<HR>
148	<TABLE>
149	<TR valign=top>
150	<TD nowrap>Copyright © 2000-2001</TD><TD>
151	<A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>,
152	Indiana University (<A
153	HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br>
154	<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>
155	<A HREF="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>,
156	Indiana University (<A
157	HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
158	</TD></TR></TABLE>
159
160	</BODY>
161	</HTML>