[ceph.git] / ceph / src / boost / libs / graph / doc / Graph.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>Graph</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>

<H2><A NAME="concept:Graph"></A>
Graph
</H2>

<P>
The Graph concept contains a few requirements that are common to all
the graph concepts. These include some associated types for
<tt>vertex_descriptor</tt>, <tt>edge_descriptor</tt>, etc. One should
note that a model of Graph is <B>not</B> required to be a model of <a
href="http://www.sgi.com/tech/stl/Assignable.html">Assignable</a>,
so algorithms should pass graph objects by reference.

<P>

<h3>Notation</h3>

<Table>
<TR>
<TD><tt>G</tt></TD>
<TD>A type that is a model of Graph.</TD>
</TR>

<TR>
<TD><tt>g</tt></TD>
<TD>An object of type <tt>G</tt>.</TD>
</TR>
</table>

<H3>Associated Types</H3>

<table border>
<tr>
<td><pre>boost::graph_traits&lt;G&gt;::vertex_descriptor</pre>
A vertex descriptor corresponds to a unique vertex in an abstract
graph instance. A vertex descriptor must be
<a
href="http://www.sgi.com/tech/stl/DefaultConstructible.html">Default Constructible</a>,
<a href="http://www.sgi.com/tech/stl/Assignable.html">Assignable</a>, and
<a href="http://www.sgi.com/tech/stl/EqualityComparable.html">Equality Comparable</a>.
</td>
</tr>

<tr>
<td><pre>boost::graph_traits&lt;G&gt;::edge_descriptor</pre>
An edge descriptor corresponds to a unique edge <i>(u,v)</i> in a
graph.  An edge descriptor must be <a
href="http://www.sgi.com/tech/stl/DefaultConstructible.html">Default Constructible</I>,
<a href="http://www.sgi.com/tech/stl/Assignable.html">Assignable</a>, and
<a href="http://www.sgi.com/tech/stl/EqualityComparable.html">Equality Comparable</a>.
</td>
</tr>

<tr>
<td><pre>boost::graph_traits&lt;G&gt;::directed_category</pre>
This type shall be convertible to <TT>directed_tag</TT> or <TT>undirected_tag</TT>.
</td>
</tr>

<tr>
<td><pre>boost::graph_traits&lt;G&gt;::edge_parallel_category</pre>
This describes whether the graph class allows the insertion of
parallel edges (edges with the same source and target). The two tags
are <TT>allow_parallel_edge_tag</TT> and <TT>disallow_parallel_edge_tag</TT>.
</td>
</tr>

<tr>
<td><pre>boost::graph_traits&lt;G&gt;::traversal_category</pre>
This describes the ways in which the vertices and edges of the
graph can be visited. The choices are <TT>incidence_graph_tag</TT>,
<TT>adjacency_graph_tag</TT>, <TT>bidirectional_graph_tag</TT>, 
<TT>vertex_list_graph_tag</TT>, <TT>edge_list_graph_tag</TT>, and 
<TT>adjacency_matrix_tag</TT>.
</td>
</tr>

</table>

<H3>Valid Expressions</H3>

<table border>

<tr>
<td><pre>boost::graph_traits&lt;G&gt;::null_vertex()</pre></td></TD>
<td>
Returns a special <tt>boost::graph_traits&lt;G&gt;::vertex_descriptor</tt> object which does not refer to
any vertex of graph object which type is <tt>G</tt>.
<td>
</tr>
</table>


<H3>Concept Checking Class</H3>

<PRE>
  template &lt;class G&gt;
  struct GraphConcept
  {
    typedef typename boost::graph_traits&lt;G&gt;::vertex_descriptor vertex_descriptor;
    typedef typename boost::graph_traits&lt;G&gt;::edge_descriptor edge_descriptor;
    typedef typename boost::graph_traits&lt;G&gt;::directed_category directed_category;
    typedef typename boost::graph_traits&lt;G&gt;::edge_parallel_category edge_parallel_category;
    typedef typename boost::graph_traits&lt;G&gt;::traversal_category traversal_category;

    void constraints() {
      BOOST_CONCEPT_ASSERT(( DefaultConstructibleConcept&lt;vertex_descriptor&gt; ));
      BOOST_CONCEPT_ASSERT(( EqualityComparableConcept&lt;vertex_descriptor&gt; ));
      BOOST_CONCEPT_ASSERT(( AssignableConcept&lt;vertex_descriptor&gt; ));
      BOOST_CONCEPT_ASSERT(( DefaultConstructibleConcept&lt;edge_descriptor&gt; ));
      BOOST_CONCEPT_ASSERT(( EqualityComparableConcept&lt;edge_descriptor&gt; ));
      BOOST_CONCEPT_ASSERT(( AssignableConcept&lt;edge_descriptor&gt; ));
    }
    G g;
  };
</PRE>

<H3>See Also</H3>

<a href="./graph_concepts.html">Graph concepts</a>

<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>)
</TD></TR></TABLE>

</BODY>
</HTML>
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>Graph</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	<H2><A NAME="concept:Graph"></A>
	19	Graph
	20	</H2>
	21
	22	<P>
	23	The Graph concept contains a few requirements that are common to all
	24	the graph concepts. These include some associated types for
	25	<tt>vertex_descriptor</tt>, <tt>edge_descriptor</tt>, etc. One should
	26	note that a model of Graph is <B>not</B> required to be a model of <a
	27	href="http://www.sgi.com/tech/stl/Assignable.html">Assignable</a>,
	28	so algorithms should pass graph objects by reference.
	29
	30	<P>
	31
	32	<h3>Notation</h3>
	33
	34	<Table>
	35	<TR>
	36	<TD><tt>G</tt></TD>
	37	<TD>A type that is a model of Graph.</TD>
	38	</TR>
	39
	40	<TR>
	41	<TD><tt>g</tt></TD>
	42	<TD>An object of type <tt>G</tt>.</TD>
	43	</TR>
	44	</table>
	45
	46	<H3>Associated Types</H3>
	47
	48	<table border>
	49	<tr>
	50	<td><pre>boost::graph_traits<G>::vertex_descriptor</pre>
	51	A vertex descriptor corresponds to a unique vertex in an abstract
	52	graph instance. A vertex descriptor must be
	53	<a
	54	href="http://www.sgi.com/tech/stl/DefaultConstructible.html">Default Constructible</a>,
	55	<a href="http://www.sgi.com/tech/stl/Assignable.html">Assignable</a>, and
	56	<a href="http://www.sgi.com/tech/stl/EqualityComparable.html">Equality Comparable</a>.
	57	</td>
	58	</tr>
	59
	60	<tr>
	61	<td><pre>boost::graph_traits<G>::edge_descriptor</pre>
	62	An edge descriptor corresponds to a unique edge <i>(u,v)</i> in a
	63	graph. An edge descriptor must be <a
	64	href="http://www.sgi.com/tech/stl/DefaultConstructible.html">Default Constructible</I>,
65	<a href="http://www.sgi.com/tech/stl/Assignable.html">Assignable</a>, and
66	<a href="http://www.sgi.com/tech/stl/EqualityComparable.html">Equality Comparable</a>.
67	</td>
68	</tr>
69
70	<tr>
71	<td><pre>boost::graph_traits<G>::directed_category</pre>
72	This type shall be convertible to <TT>directed_tag</TT> or <TT>undirected_tag</TT>.
73	</td>
74	</tr>
75
76	<tr>
77	<td><pre>boost::graph_traits<G>::edge_parallel_category</pre>
78	This describes whether the graph class allows the insertion of
79	parallel edges (edges with the same source and target). The two tags
80	are <TT>allow_parallel_edge_tag</TT> and <TT>disallow_parallel_edge_tag</TT>.
81	</td>
82	</tr>
83
84	<tr>
85	<td><pre>boost::graph_traits<G>::traversal_category</pre>
86	This describes the ways in which the vertices and edges of the
87	graph can be visited. The choices are <TT>incidence_graph_tag</TT>,
88	<TT>adjacency_graph_tag</TT>, <TT>bidirectional_graph_tag</TT>,
89	<TT>vertex_list_graph_tag</TT>, <TT>edge_list_graph_tag</TT>, and
90	<TT>adjacency_matrix_tag</TT>.
91	</td>
92	</tr>
93
94	</table>
95
96	<H3>Valid Expressions</H3>
97
98	<table border>
99
100	<tr>
101	<td><pre>boost::graph_traits<G>::null_vertex()</pre></td></TD>
102	<td>
103	Returns a special <tt>boost::graph_traits<G>::vertex_descriptor</tt> object which does not refer to
104	any vertex of graph object which type is <tt>G</tt>.
105	<td>
106	</tr>
107	</table>
108
109
110
111	<H3>Concept Checking Class</H3>
112
113	<PRE>
114	template <class G>
115	struct GraphConcept
116	{
117	typedef typename boost::graph_traits<G>::vertex_descriptor vertex_descriptor;
118	typedef typename boost::graph_traits<G>::edge_descriptor edge_descriptor;
119	typedef typename boost::graph_traits<G>::directed_category directed_category;
120	typedef typename boost::graph_traits<G>::edge_parallel_category edge_parallel_category;
121	typedef typename boost::graph_traits<G>::traversal_category traversal_category;
122
123	void constraints() {
124	BOOST_CONCEPT_ASSERT(( DefaultConstructibleConcept<vertex_descriptor> ));
125	BOOST_CONCEPT_ASSERT(( EqualityComparableConcept<vertex_descriptor> ));
126	BOOST_CONCEPT_ASSERT(( AssignableConcept<vertex_descriptor> ));
127	BOOST_CONCEPT_ASSERT(( DefaultConstructibleConcept<edge_descriptor> ));
128	BOOST_CONCEPT_ASSERT(( EqualityComparableConcept<edge_descriptor> ));
129	BOOST_CONCEPT_ASSERT(( AssignableConcept<edge_descriptor> ));
130	}
131	G g;
132	};
133	</PRE>
134
135	<H3>See Also</H3>
136
137	<a href="./graph_concepts.html">Graph concepts</a>
138
139	<br>
140	<HR>
141	<TABLE>
142	<TR valign=top>
143	<TD nowrap>Copyright © 2000-2001</TD><TD>
144	<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>)
145	</TD></TR></TABLE>
146
147	</BODY>
148	</HTML>