[ceph.git] / ceph / src / boost / libs / graph / doc / using_property_maps.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>Boost Graph Library: Using Property Maps</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:property-maps"></A>
Property Maps
</H1>

<P>
The main link between the abstract mathematical nature of graphs and
the concrete problems they are used to solve is the properties that
are attached to the vertices and edges of a graph, things like
distance, capacity, weight, color, etc. There are many ways to attach
properties to graph in terms of data-structure implementation, but
graph algorithms should not have to deal with the implementation
details of the properties. The <I>property map</I> interface
defined in Section <A
HREF="../../property_map/doc/property_map.html">Property
Map Concepts</A> provides a generic method for accessing
properties from graphs. This is the interface used in the BGL
algorithms to access properties.

<P>

<H2>Property Map Interface</H2>

<P>
The property map interface specifies that each property is
accessed using a separate property map object. In the following
example we show an implementation of the <TT>relax()</TT> function used
inside of Dijkstra's shortest paths algorithm.  In this function, we
need to access the weight property of an edge, and the distance
property of a vertex. We write <TT>relax()</TT> as a template function
so that it can be used in many difference situations. Two of the
arguments to the function, <TT>weight</TT> and <TT>distance</TT>, are the
property map objects. In general, BGL algorithms explicitly pass
property map objects for every property that a function will
need. The property map interface defines several functions, two
of which we use here: <TT>get()</TT> and <TT>put()</TT>. The <TT>get()</TT>
function takes a property map object, such as <TT>distance</TT> and
a <I>key</I> object. In the case of the distance property we are using
the vertex objects <TT>u</TT> and <TT>v</TT> as keys. The <TT>get()</TT>
function then returns the property value for the vertex.

<P>
<PRE>
  template &lt;class Edge, class Graph,
            class WeightPropertyMap, 
            class DistancePropertyMap&gt;
  bool relax(Edge e, const Graph&amp; g, 
             WeightPropertyMap weight, 
             DistancePropertyMap distance)
  {
    typedef typename graph_traits&lt;Graph&gt;::vertex_descriptor Vertex;
    Vertex u = source(e,g), v = target(e,g);
    if ( get(distance, u) + get(weight, e) &lt; get(distance, v)) {
      put(distance, v, get(distance, u) + get(weight, e));
      return true;
    } else
      return false;
  }
</PRE>

The function <TT>get()</TT> returns a copy of the property value.  There
is a third function in the property map interface, <TT>at()</TT>,
that returns a reference to the property value (a const reference if
the map is not mutable).

<P>
Similar to the <TT>iterator_traits</TT> class of the STL, there is a
<TT>property_traits</TT> class that can be used to deduce the types
associated with a property map type: the key and value types, and
the property map category (which is used to tell whether the
map is readable, writeable, or both). In the <TT>relax()</TT>
function we could have used <TT>property_traits</TT> to declare local
variables of the distance property type.

<P>
<PRE>
  {
    typedef typename graph_traits&lt;Graph&gt;::vertex_descriptor Vertex;
    Vertex u = source(e,g), v = target(e,g);
    typename property_traits&lt;DistancePropertyMap&gt;::value_type
      du, dv; // local variables of the distance property type
    du = get(distance, u);
    dv = get(distance, v);
    if (du + get(weight, e) &lt; dv) {
      put(distance, v, du + get(weight, e));
      return true;
    } else
      return false;
  }
</PRE>

<P>
There are two kinds of graph properties: interior and exterior. 

<P>
<DL>
<DT><STRONG>Interior Properties</STRONG></DT>
<DD>are stored ``inside'' the graph object
in some way, and the lifetime of the property value objects is the
same as that of the graph object. 

<P>
</DD>
<DT><STRONG>Exterior Properties</STRONG></DT>
<DD>are stored ``outside'' of the graph
object and the lifetime of the property value objects is independent
of the graph. This is useful for properties that are only needed
temporarily, perhaps for the duration of a particular algorithm such
as the color property used in <TT>breadth_first_search()</TT>.  When
using exterior properties with a BGL algorithm a property map
object for the exterior property must be passed as an argument to the
algorithm.
</DD>
</DL>

<P>

<H2><A NAME="sec:interior-properties"></A>
Interior Properties
</H2>

<P>
A graph type that supports interior property storage (such as
<TT>adjacency_list</TT>) provides access to its property map
objects through the interface defined in <a
href="./PropertyGraph.html">PropertyGraph</a>.  There is a function
<TT>get(Property, g)</TT> that get property map objects from a
graph. The first argument is the property type to specify which
property you want to access and the second argument is the graph
object. A graph type must document which properties (and therefore
tags) it provides access to.  The type of the property map depends on
the type of graph and the property being mapped. A trait class is
defined that provides a generic way to deduce the property map type:
<TT>property_map</TT>. The following code shows how one can obtain the
property map for the distance and weight properties of some graph
type.

<P>
<PRE>
  property_map&lt;Graph, vertex_distance_t&gt;::type d
    = get(vertex_distance, g);

  property_map&lt;Graph, edge_weight_t&gt;::type w
    = get(edge_weight, g);
</PRE>

<P>
In general, the BGL algorithms require all property maps needed
by the algorithm to be explicitly passed to the algorithm. For
example, the BGL Dijkstra's shortest paths algorithm requires four
property maps: distance, weight, color, and vertex ID.

<P>
Often times some or all of the properties will be interior to the
graph, so one would call Dijkstra's algorithm in the following way
(given some graph <TT>g</TT> and source vertex <TT>src</TT>).

<P>
<PRE>
  dijkstra_shortest_paths(g, src,  
    distance_map(get(vertex_distance, g)).
    weight_map(get(edge_weight, g)).
    color_map(get(vertex_color, g)).
    vertex_index_map(get(vertex_index, g)));
</PRE>

<P>
Since it is somewhat cumbersome to specify all of the property maps,
BGL provides defaults that assume some of the properties are interior
and can be accessed via <TT>get(Property, g)</TT> from the graph, or
if the property map is only used internally, then the algorithm will
create a property map for itself out of an array and using the graph's
vertex index map as the offset into the array. Below we show a call to
<TT>dijkstra_shortest_paths</TT> algorithm using all defaults for the
named parameters. This call is equivalent to the previous call to
Dijkstra's algorithm.

<P>
<PRE>
  dijkstra_shortest_paths(g, src);
</PRE>

<P>
The next question is: how do interior properties become attached to a
graph object in the first place? This depends on the graph class that
you are using. The <TT>adjacency_list</TT> graph class of BGL uses a
property mechanism (see Section <A
HREF="using_adjacency_list.html#sec:adjacency-list-properties">Internal
Properties</A>) to allow an arbitrary number of properties to be
stored on the edges and vertices of the graph.

<P>

<H2><A NAME="sec:exterior-properties"></A>
Exterior Properties
</H2>

<P>
In this section we will describe two methods for constructing exterior
property maps, however there is an unlimited number of ways that
one could create exterior properties for a graph.

<P>
The first method uses the adaptor class
<TT>iterator_property_map</TT>. This
class wraps a random access iterator, creating a property map out
of it. The random access iterator must point to the beginning of a
range of property values, and the length of the range must be the
number of vertices or edges in the graph (depending on whether it is a
vertex or edge property map). The adaptor must also be supplied
with an ID property map, which will be used to map the vertex or
edge descriptor to the offset of the property value (offset from the
random access iterator). The ID property map will typically be an
interior property map of the graph.  The following example shows
how the <TT>iterator_property_map</TT>
can be used to create exterior property maps for the capacity and flow properties, which are stored in arrays. The arrays are
indexed by edge ID. The edge ID is added to the graph using a property,
and the values of the ID's are given when each edge is added to the
graph. The complete source code for this example is in
<TT>example/exterior_edge_properties.cpp</TT>. The
<TT>print_network()</TT> function prints out the graph with
the flow and capacity values.

<P>
<PRE>
  typedef adjacency_list&lt;vecS, vecS, bidirectionalS, 
    no_property, property&lt;edge_index_t, std::size_t&gt; &gt; Graph;

  const int num_vertices = 9;
  Graph G(num_vertices);

  int capacity_array[] = { 10, 20, 20, 20, 40, 40, 20, 20, 20, 10 };
  int flow_array[] = { 8, 12, 12, 12, 12, 12, 16, 16, 16, 8 };

  // Add edges to the graph, and assign each edge an ID number.
  add_edge(0, 1, 0, G);
  // ...

  typedef graph_traits&lt;Graph&gt;::edge_descriptor Edge;
  typedef property_map&lt;Graph, edge_index_t&gt;::type EdgeID_Map;
  EdgeID_Map edge_id = get(edge_index, G);

  iterator_property_map
    &lt;int*, int, int&amp;, EdgeID_Map&gt; 
      capacity(capacity_array, edge_id), 
      flow(flow_array, edge_id);

  print_network(G, capacity, flow);
</PRE>

<P>
The second method uses a pointer type (a pointer to an array of
property values) as a property map. This requires the key type to
be an integer so that it can be used as an offset to the pointer. The
<TT>adjacency_list</TT> class with template parameter
<TT>VertexList=vecS</TT> uses integers for vertex descriptors (indexed
from zero to the number of vertices in the graph), so they are
suitable as the key type for a pointer property map. When the
<TT>VertexList</TT> is not <TT>vecS</TT>, then the vertex descriptor is
not an integer, and cannot be used with a pointer property map.
Instead the method described above of using a
<TT>iterator_property_map</TT> with an ID
property must be used. The <TT>edge_list</TT> class may also use an
integer type for the vertex descriptor, depending on how the adapted
edge iterator is defined. The example in
<TT>example/bellman_ford.cpp</TT> shows <TT>edge_list</TT> being used
with pointers as vertex property maps.

<P>
The reason that pointers can be used as property maps is that
there are several overloaded functions and a specialization of
<TT>property_traits</TT> in the header <a
href="../../../boost/property_map/property_map.hpp"><TT>boost/property_map/property_map.hpp</TT></a>
that implement the property map interface in terms of
pointers. The definition of those functions is listed here.

<P>
<PRE>
namespace boost {
  template &lt;class T&gt;
  struct property_traits&lt;T*&gt; {
    typedef T value_type;
    typedef ptrdiff_t key_type;
    typedef lvalue_property_map_tag category;
  };

  template &lt;class T&gt;
  void put(T* pa, std::ptrdiff_t key, const T&amp; value) { pa[key] = value;  }

  template &lt;class T&gt;
  const T&amp; get(const T* pa, std::ptrdiff_t key) { return pa[key]; }

  template &lt;class T&gt;
  const T&amp; at(const T* pa, std::ptrdiff_t key) { return pa[key]; }

  template &lt;class T&gt;
  T&amp; at(T* pa, std::ptrdiff_t key) { return pa[key]; }
}
</PRE>

<P>
In the following example, we use an array to store names of cities for
each vertex in the graph, and a <TT>std::vector</TT> to store vertex
colors which will be needed in a call to
<TT>breadth_first_search()</TT>. Since the iterator of a
<TT>std::vector</TT> (obtained with a call to <TT>begin()</TT>) is a
pointer, the pointer property map method also works for
<TT>std::vector::iterator</TT>. The complete source code for this
example is in <a
href="../example/city_visitor.cpp"><TT>example/city_visitor.cpp</TT></a>.

<P>
<PRE>
// Definition of city_visitor omitted...

int main(int,char*[])
{
  enum { SanJose, SanFran, LA, SanDiego, Fresno, LosVegas, Reno,
         Sacramento, SaltLake, Pheonix, N };

  // An array of vertex name properties
  std::string names[] = { &quot;San Jose&quot;, &quot;San Francisco&quot;,  &quot;San Jose&quot;,
                          &quot;San Francisco&quot;, &quot;Los Angeles&quot;, &quot;San Diego&quot;, 
                          &quot;Fresno&quot;, &quot;Los Vegas&quot;, &quot;Reno&quot;, &quot;Sacramento&quot;,
                          &quot;Salt Lake City&quot;, &quot;Pheonix&quot; };

  // Specify all the connecting roads between cities.
  typedef std::pair&lt;int,int&gt; E;
  E edge_array[] = { E(Sacramento, Reno), ... };

  // Specify the graph type.
  typedef adjacency_list&lt;vecS, vecS, undirectedS&gt; Graph;
  // Create the graph object, based on the edges in edge_array.
  Graph G(N, edge_array, edge_array + sizeof(edge_array)/sizeof(E));

  // DFS and BFS need to &quot;color&quot; the vertices.
  // Here we use std::vector as exterior property storage.
  std::vector&lt;default_color_type&gt; colors(N);

  cout &lt;&lt; &quot;*** Depth First ***&quot; &lt;&lt; endl;
  depth_first_search(G, city_visitor(names), colors.begin());
  cout &lt;&lt; endl;

  // Get the source vertex
  boost::graph_traits&lt;Graph&gt;::vertex_descriptor 
    s = vertex(SanJose, G);

  cout &lt;&lt; &quot;*** Breadth First ***&quot; &lt;&lt; endl;
  breadth_first_search(G, s, city_visitor(names), colors.begin());

  return 0;
}
</PRE>

<P>

<H2><A NAME="sec:custom-exterior-property-maps"></A>
Constructing an Exterior Property Map
</H2>

<P>
Implementing your own exterior property maps is not very
difficult. You simply need to overload the functions required by the
<a href="property_map.html">property map concept</a>
that you want your class to model. At most, this means overloading the
<TT>put()</TT> and <TT>get()</TT> functions and implementing
<TT>operator[]</TT>. Also, your property map class will need to have
nested typedefs for all the types defined in <TT>property_traits</TT>,
or you can create a specialization of <TT>property_traits</TT> for
your new property map type.

<P>
The implementation of the
<TT>iterator_property_map</TT> class
serves as a good example for how to build and exterior property
map. Here we present a simplified implementation of the
<TT>iterator_property_map</TT> class
which we will name <TT>iterator_pa</TT>.

<P>
We start with the definition of the <TT>iterator_map</TT> class
itself. This adaptor class is templated on the adapted <TT>Iterator</TT>
type and the ID property map. The job of the ID property map
is to map the key object (which will typically be a vertex or edge
descriptor) to an integer offset. The <TT>iterator_map</TT> class will
need the three necessary typedefs for a property map:
<TT>key_type</TT>, <TT>value_type</TT>, and <TT>category</TT>. We can use
<TT>property_traits</TT> to find the key type of <TT>IDMap</TT>, and
we can use <TT>iterator_traits</TT> to determine the value type of
<TT>Iterator</TT>.  We choose
<TT>boost::lvalue_property_map_tag</TT> for the category
since we plan on implementing the <TT>at()</TT> function.

<P>
<PRE>
  template &lt;class Iterator, class IDMap&gt;
  class iterator_map
  {
  public:
    typedef typename boost::property_traits&lt;IDMap&gt;::key_type key_type; 
    typedef typename std::iterator_traits&lt;Iterator&gt;::value_type value_type;
    typedef boost::lvalue_property_map_tag category;

    iterator_map(Iterator i = Iterator(), 
                const IDMap&amp; id = IDMap()) 
      : m_iter(i), m_id(id) { }
    Iterator m_iter;
    IDMap m_id;
  };
</PRE>

<P>
Next we implement the three property map functions, <TT>get()</TT>,
<TT>put()</TT>, and <TT>at()</TT>. In each of the functions, the
<TT>key</TT> object is converted to an integer offset using the
<TT>m_id</TT> property map, and then that is used as an offset
to the random access iterator <TT>m_iter</TT>.

<P>
<PRE>
  template &lt;class Iter, class ID&gt;
  typename std::iterator_traits&lt;Iter&gt;::value_type
  get(const iterator_map&lt;Iter,ID&gt;&amp; i,
      typename boost::property_traits&lt;ID&gt;::key_type key)
  {
    return i.m_iter[i.m_id[key]];
  }
  template &lt;class Iter, class ID&gt;
  void
  put(const iterator_map&lt;Iter,ID&gt;&amp; i,
      typename boost::property_traits&lt;ID&gt;::key_type key,
      const typename std::iterator_traits&lt;Iter&gt;::value_type&amp; value)
  {
    i.m_iter[i.m_id[key]] = value;
  }
  template &lt;class Iter, class ID&gt;
  typename std::iterator_traits&lt;Iter&gt;::reference
  at(const iterator_map&lt;Iter,ID&gt;&amp; i,
      typename boost::property_traits&lt;ID&gt;::key_type key)
  {
    return i.m_iter[i.m_id[key]];
  }
</PRE>

<P>
That is it. The <TT>iterator_map</TT> class is complete and could be
used just like the
<TT>iterator_property_map</TT> in the
previous section.

<P>


<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>Boost Graph Library: Using Property Maps</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
	19	<H1><A NAME="sec:property-maps"></A>
	20	Property Maps
	21	</H1>
	22
	23	<P>
	24	The main link between the abstract mathematical nature of graphs and
	25	the concrete problems they are used to solve is the properties that
	26	are attached to the vertices and edges of a graph, things like
	27	distance, capacity, weight, color, etc. There are many ways to attach
	28	properties to graph in terms of data-structure implementation, but
	29	graph algorithms should not have to deal with the implementation
	30	details of the properties. The <I>property map</I> interface
	31	defined in Section <A
	32	HREF="../../property_map/doc/property_map.html">Property
	33	Map Concepts</A> provides a generic method for accessing
	34	properties from graphs. This is the interface used in the BGL
	35	algorithms to access properties.
	36
	37	<P>
	38
	39	<H2>Property Map Interface</H2>
	40
	41	<P>
	42	The property map interface specifies that each property is
	43	accessed using a separate property map object. In the following
	44	example we show an implementation of the <TT>relax()</TT> function used
	45	inside of Dijkstra's shortest paths algorithm. In this function, we
	46	need to access the weight property of an edge, and the distance
	47	property of a vertex. We write <TT>relax()</TT> as a template function
	48	so that it can be used in many difference situations. Two of the
	49	arguments to the function, <TT>weight</TT> and <TT>distance</TT>, are the
	50	property map objects. In general, BGL algorithms explicitly pass
	51	property map objects for every property that a function will
	52	need. The property map interface defines several functions, two
	53	of which we use here: <TT>get()</TT> and <TT>put()</TT>. The <TT>get()</TT>
	54	function takes a property map object, such as <TT>distance</TT> and
	55	a <I>key</I> object. In the case of the distance property we are using
	56	the vertex objects <TT>u</TT> and <TT>v</TT> as keys. The <TT>get()</TT>
	57	function then returns the property value for the vertex.
	58
	59	<P>
	60	<PRE>
	61	template <class Edge, class Graph,
	62	class WeightPropertyMap,
	63	class DistancePropertyMap>
	64	bool relax(Edge e, const Graph& g,
65	WeightPropertyMap weight,
66	DistancePropertyMap distance)
67	{
68	typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
69	Vertex u = source(e,g), v = target(e,g);
70	if ( get(distance, u) + get(weight, e) < get(distance, v)) {
71	put(distance, v, get(distance, u) + get(weight, e));
72	return true;
73	} else
74	return false;
75	}
76	</PRE>
77
78	The function <TT>get()</TT> returns a copy of the property value. There
79	is a third function in the property map interface, <TT>at()</TT>,
80	that returns a reference to the property value (a const reference if
81	the map is not mutable).
82
83	<P>
84	Similar to the <TT>iterator_traits</TT> class of the STL, there is a
85	<TT>property_traits</TT> class that can be used to deduce the types
86	associated with a property map type: the key and value types, and
87	the property map category (which is used to tell whether the
88	map is readable, writeable, or both). In the <TT>relax()</TT>
89	function we could have used <TT>property_traits</TT> to declare local
90	variables of the distance property type.
91
92	<P>
93	<PRE>
94	{
95	typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
96	Vertex u = source(e,g), v = target(e,g);
97	typename property_traits<DistancePropertyMap>::value_type
98	du, dv; // local variables of the distance property type
99	du = get(distance, u);
100	dv = get(distance, v);
101	if (du + get(weight, e) < dv) {
102	put(distance, v, du + get(weight, e));
103	return true;
104	} else
105	return false;
106	}
107	</PRE>
108
109	<P>
110	There are two kinds of graph properties: interior and exterior.
111
112	<P>
113	<DL>
114	<DT><STRONG>Interior Properties</STRONG></DT>
115	<DD>are stored ``inside'' the graph object
116	in some way, and the lifetime of the property value objects is the
117	same as that of the graph object.
118
119	<P>
120	</DD>
121	<DT><STRONG>Exterior Properties</STRONG></DT>
122	<DD>are stored ``outside'' of the graph
123	object and the lifetime of the property value objects is independent
124	of the graph. This is useful for properties that are only needed
125	temporarily, perhaps for the duration of a particular algorithm such
126	as the color property used in <TT>breadth_first_search()</TT>. When
127	using exterior properties with a BGL algorithm a property map
128	object for the exterior property must be passed as an argument to the
129	algorithm.
130	</DD>
131	</DL>
132
133	<P>
134
135	<H2><A NAME="sec:interior-properties"></A>
136	Interior Properties
137	</H2>
138
139	<P>
140	A graph type that supports interior property storage (such as
141	<TT>adjacency_list</TT>) provides access to its property map
142	objects through the interface defined in <a
143	href="./PropertyGraph.html">PropertyGraph</a>. There is a function
144	<TT>get(Property, g)</TT> that get property map objects from a
145	graph. The first argument is the property type to specify which
146	property you want to access and the second argument is the graph
147	object. A graph type must document which properties (and therefore
148	tags) it provides access to. The type of the property map depends on
149	the type of graph and the property being mapped. A trait class is
150	defined that provides a generic way to deduce the property map type:
151	<TT>property_map</TT>. The following code shows how one can obtain the
152	property map for the distance and weight properties of some graph
153	type.
154
155	<P>
156	<PRE>
157	property_map<Graph, vertex_distance_t>::type d
158	= get(vertex_distance, g);
159
160	property_map<Graph, edge_weight_t>::type w
161	= get(edge_weight, g);
162	</PRE>
163
164	<P>
165	In general, the BGL algorithms require all property maps needed
166	by the algorithm to be explicitly passed to the algorithm. For
167	example, the BGL Dijkstra's shortest paths algorithm requires four
168	property maps: distance, weight, color, and vertex ID.
169
170	<P>
171	Often times some or all of the properties will be interior to the
172	graph, so one would call Dijkstra's algorithm in the following way
173	(given some graph <TT>g</TT> and source vertex <TT>src</TT>).
174
175	<P>
176	<PRE>
177	dijkstra_shortest_paths(g, src,
178	distance_map(get(vertex_distance, g)).
179	weight_map(get(edge_weight, g)).
180	color_map(get(vertex_color, g)).
181	vertex_index_map(get(vertex_index, g)));
182	</PRE>
183
184	<P>
185	Since it is somewhat cumbersome to specify all of the property maps,
186	BGL provides defaults that assume some of the properties are interior
187	and can be accessed via <TT>get(Property, g)</TT> from the graph, or
188	if the property map is only used internally, then the algorithm will
189	create a property map for itself out of an array and using the graph's
190	vertex index map as the offset into the array. Below we show a call to
191	<TT>dijkstra_shortest_paths</TT> algorithm using all defaults for the
192	named parameters. This call is equivalent to the previous call to
193	Dijkstra's algorithm.
194
195	<P>
196	<PRE>
197	dijkstra_shortest_paths(g, src);
198	</PRE>
199
200	<P>
201	The next question is: how do interior properties become attached to a
202	graph object in the first place? This depends on the graph class that
203	you are using. The <TT>adjacency_list</TT> graph class of BGL uses a
204	property mechanism (see Section <A
205	HREF="using_adjacency_list.html#sec:adjacency-list-properties">Internal
206	Properties</A>) to allow an arbitrary number of properties to be
207	stored on the edges and vertices of the graph.
208
209	<P>
210
211	<H2><A NAME="sec:exterior-properties"></A>
212	Exterior Properties
213	</H2>
214
215	<P>
216	In this section we will describe two methods for constructing exterior
217	property maps, however there is an unlimited number of ways that
218	one could create exterior properties for a graph.
219
220	<P>
221	The first method uses the adaptor class
222	<TT>iterator_property_map</TT>. This
223	class wraps a random access iterator, creating a property map out
224	of it. The random access iterator must point to the beginning of a
225	range of property values, and the length of the range must be the
226	number of vertices or edges in the graph (depending on whether it is a
227	vertex or edge property map). The adaptor must also be supplied
228	with an ID property map, which will be used to map the vertex or
229	edge descriptor to the offset of the property value (offset from the
230	random access iterator). The ID property map will typically be an
231	interior property map of the graph. The following example shows
232	how the <TT>iterator_property_map</TT>
233	can be used to create exterior property maps for the capacity and flow properties, which are stored in arrays. The arrays are
234	indexed by edge ID. The edge ID is added to the graph using a property,
235	and the values of the ID's are given when each edge is added to the
236	graph. The complete source code for this example is in
237	<TT>example/exterior_edge_properties.cpp</TT>. The
238	<TT>print_network()</TT> function prints out the graph with
239	the flow and capacity values.
240
241	<P>
242	<PRE>
243	typedef adjacency_list<vecS, vecS, bidirectionalS,
244	no_property, property<edge_index_t, std::size_t> > Graph;
245
246	const int num_vertices = 9;
247	Graph G(num_vertices);
248
249	int capacity_array[] = { 10, 20, 20, 20, 40, 40, 20, 20, 20, 10 };
250	int flow_array[] = { 8, 12, 12, 12, 12, 12, 16, 16, 16, 8 };
251
252	// Add edges to the graph, and assign each edge an ID number.
253	add_edge(0, 1, 0, G);
254	// ...
255
256	typedef graph_traits<Graph>::edge_descriptor Edge;
257	typedef property_map<Graph, edge_index_t>::type EdgeID_Map;
258	EdgeID_Map edge_id = get(edge_index, G);
259
260	iterator_property_map
261	<int*, int, int&, EdgeID_Map>
262	capacity(capacity_array, edge_id),
263	flow(flow_array, edge_id);
264
265	print_network(G, capacity, flow);
266	</PRE>
267
268	<P>
269	The second method uses a pointer type (a pointer to an array of
270	property values) as a property map. This requires the key type to
271	be an integer so that it can be used as an offset to the pointer. The
272	<TT>adjacency_list</TT> class with template parameter
273	<TT>VertexList=vecS</TT> uses integers for vertex descriptors (indexed
274	from zero to the number of vertices in the graph), so they are
275	suitable as the key type for a pointer property map. When the
276	<TT>VertexList</TT> is not <TT>vecS</TT>, then the vertex descriptor is
277	not an integer, and cannot be used with a pointer property map.
278	Instead the method described above of using a
279	<TT>iterator_property_map</TT> with an ID
280	property must be used. The <TT>edge_list</TT> class may also use an
281	integer type for the vertex descriptor, depending on how the adapted
282	edge iterator is defined. The example in
283	<TT>example/bellman_ford.cpp</TT> shows <TT>edge_list</TT> being used
284	with pointers as vertex property maps.
285
286	<P>
287	The reason that pointers can be used as property maps is that
288	there are several overloaded functions and a specialization of
289	<TT>property_traits</TT> in the header <a
290	href="../../../boost/property_map/property_map.hpp"><TT>boost/property_map/property_map.hpp</TT></a>
291	that implement the property map interface in terms of
292	pointers. The definition of those functions is listed here.
293
294	<P>
295	<PRE>
296	namespace boost {
297	template <class T>
298	struct property_traits<T*> {
299	typedef T value_type;
300	typedef ptrdiff_t key_type;
301	typedef lvalue_property_map_tag category;
302	};
303
304	template <class T>
305	void put(T* pa, std::ptrdiff_t key, const T& value) { pa[key] = value; }
306
307	template <class T>
308	const T& get(const T* pa, std::ptrdiff_t key) { return pa[key]; }
309
310	template <class T>
311	const T& at(const T* pa, std::ptrdiff_t key) { return pa[key]; }
312
313	template <class T>
314	T& at(T* pa, std::ptrdiff_t key) { return pa[key]; }
315	}
316	</PRE>
317
318	<P>
319	In the following example, we use an array to store names of cities for
320	each vertex in the graph, and a <TT>std::vector</TT> to store vertex
321	colors which will be needed in a call to
322	<TT>breadth_first_search()</TT>. Since the iterator of a
323	<TT>std::vector</TT> (obtained with a call to <TT>begin()</TT>) is a
324	pointer, the pointer property map method also works for
325	<TT>std::vector::iterator</TT>. The complete source code for this
326	example is in <a
327	href="../example/city_visitor.cpp"><TT>example/city_visitor.cpp</TT></a>.
328
329	<P>
330	<PRE>
331	// Definition of city_visitor omitted...
332
333	int main(int,char*[])
334	{
335	enum { SanJose, SanFran, LA, SanDiego, Fresno, LosVegas, Reno,
336	Sacramento, SaltLake, Pheonix, N };
337
338	// An array of vertex name properties
339	std::string names[] = { "San Jose", "San Francisco", "San Jose",
340	"San Francisco", "Los Angeles", "San Diego",
341	"Fresno", "Los Vegas", "Reno", "Sacramento",
342	"Salt Lake City", "Pheonix" };
343
344	// Specify all the connecting roads between cities.
345	typedef std::pair<int,int> E;
346	E edge_array[] = { E(Sacramento, Reno), ... };
347
348	// Specify the graph type.
349	typedef adjacency_list<vecS, vecS, undirectedS> Graph;
350	// Create the graph object, based on the edges in edge_array.
351	Graph G(N, edge_array, edge_array + sizeof(edge_array)/sizeof(E));
352
353	// DFS and BFS need to "color" the vertices.
354	// Here we use std::vector as exterior property storage.
355	std::vector<default_color_type> colors(N);
356
357	cout << "* Depth First *" << endl;
358	depth_first_search(G, city_visitor(names), colors.begin());
359	cout << endl;
360
361	// Get the source vertex
362	boost::graph_traits<Graph>::vertex_descriptor
363	s = vertex(SanJose, G);
364
365	cout << "* Breadth First *" << endl;
366	breadth_first_search(G, s, city_visitor(names), colors.begin());
367
368	return 0;
369	}
370	</PRE>
371
372	<P>
373
374	<H2><A NAME="sec:custom-exterior-property-maps"></A>
375	Constructing an Exterior Property Map
376	</H2>
377
378	<P>
379	Implementing your own exterior property maps is not very
380	difficult. You simply need to overload the functions required by the
381	<a href="property_map.html">property map concept</a>
382	that you want your class to model. At most, this means overloading the
383	<TT>put()</TT> and <TT>get()</TT> functions and implementing
384	<TT>operator[]</TT>. Also, your property map class will need to have
385	nested typedefs for all the types defined in <TT>property_traits</TT>,
386	or you can create a specialization of <TT>property_traits</TT> for
387	your new property map type.
388
389	<P>
390	The implementation of the
391	<TT>iterator_property_map</TT> class
392	serves as a good example for how to build and exterior property
393	map. Here we present a simplified implementation of the
394	<TT>iterator_property_map</TT> class
395	which we will name <TT>iterator_pa</TT>.
396
397	<P>
398	We start with the definition of the <TT>iterator_map</TT> class
399	itself. This adaptor class is templated on the adapted <TT>Iterator</TT>
400	type and the ID property map. The job of the ID property map
401	is to map the key object (which will typically be a vertex or edge
402	descriptor) to an integer offset. The <TT>iterator_map</TT> class will
403	need the three necessary typedefs for a property map:
404	<TT>key_type</TT>, <TT>value_type</TT>, and <TT>category</TT>. We can use
405	<TT>property_traits</TT> to find the key type of <TT>IDMap</TT>, and
406	we can use <TT>iterator_traits</TT> to determine the value type of
407	<TT>Iterator</TT>. We choose
408	<TT>boost::lvalue_property_map_tag</TT> for the category
409	since we plan on implementing the <TT>at()</TT> function.
410
411	<P>
412	<PRE>
413	template <class Iterator, class IDMap>
414	class iterator_map
415	{
416	public:
417	typedef typename boost::property_traits<IDMap>::key_type key_type;
418	typedef typename std::iterator_traits<Iterator>::value_type value_type;
419	typedef boost::lvalue_property_map_tag category;
420
421	iterator_map(Iterator i = Iterator(),
422	const IDMap& id = IDMap())
423	: m_iter(i), m_id(id) { }
424	Iterator m_iter;
425	IDMap m_id;
426	};
427	</PRE>
428
429	<P>
430	Next we implement the three property map functions, <TT>get()</TT>,
431	<TT>put()</TT>, and <TT>at()</TT>. In each of the functions, the
432	<TT>key</TT> object is converted to an integer offset using the
433	<TT>m_id</TT> property map, and then that is used as an offset
434	to the random access iterator <TT>m_iter</TT>.
435
436	<P>
437	<PRE>
438	template <class Iter, class ID>
439	typename std::iterator_traits<Iter>::value_type
440	get(const iterator_map<Iter,ID>& i,
441	typename boost::property_traits<ID>::key_type key)
442	{
443	return i.m_iter[i.m_id[key]];
444	}
445	template <class Iter, class ID>
446	void
447	put(const iterator_map<Iter,ID>& i,
448	typename boost::property_traits<ID>::key_type key,
449	const typename std::iterator_traits<Iter>::value_type& value)
450	{
451	i.m_iter[i.m_id[key]] = value;
452	}
453	template <class Iter, class ID>
454	typename std::iterator_traits<Iter>::reference
455	at(const iterator_map<Iter,ID>& i,
456	typename boost::property_traits<ID>::key_type key)
457	{
458	return i.m_iter[i.m_id[key]];
459	}
460	</PRE>
461
462	<P>
463	That is it. The <TT>iterator_map</TT> class is complete and could be
464	used just like the
465	<TT>iterator_property_map</TT> in the
466	previous section.
467
468	<P>
469
470
471	<br>
472	<HR>
473	<TABLE>
474	<TR valign=top>
475	<TD nowrap>Copyright © 2000-2001</TD><TD>
476	<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>)
477	</TD></TR></TABLE>
478
479	</BODY>
480	</HTML>