481 lines
17 KiB
HTML
481 lines
17 KiB
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 <class Edge, class Graph,
|
|
class WeightPropertyMap,
|
|
class DistancePropertyMap>
|
|
bool relax(Edge e, const Graph& g,
|
|
WeightPropertyMap weight,
|
|
DistancePropertyMap distance)
|
|
{
|
|
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
|
|
Vertex u = source(e,g), v = target(e,g);
|
|
if ( get(distance, u) + get(weight, e) < 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<Graph>::vertex_descriptor Vertex;
|
|
Vertex u = source(e,g), v = target(e,g);
|
|
typename property_traits<DistancePropertyMap>::value_type
|
|
du, dv; // local variables of the distance property type
|
|
du = get(distance, u);
|
|
dv = get(distance, v);
|
|
if (du + get(weight, e) < 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<Graph, vertex_distance_t>::type d
|
|
= get(vertex_distance, g);
|
|
|
|
property_map<Graph, edge_weight_t>::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<vecS, vecS, bidirectionalS,
|
|
no_property, property<edge_index_t, std::size_t> > 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<Graph>::edge_descriptor Edge;
|
|
typedef property_map<Graph, edge_index_t>::type EdgeID_Map;
|
|
EdgeID_Map edge_id = get(edge_index, G);
|
|
|
|
iterator_property_map
|
|
<int*, int, int&, EdgeID_Map>
|
|
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 <class T>
|
|
struct property_traits<T*> {
|
|
typedef T value_type;
|
|
typedef ptrdiff_t key_type;
|
|
typedef lvalue_property_map_tag category;
|
|
};
|
|
|
|
template <class T>
|
|
void put(T* pa, std::ptrdiff_t key, const T& value) { pa[key] = value; }
|
|
|
|
template <class T>
|
|
const T& get(const T* pa, std::ptrdiff_t key) { return pa[key]; }
|
|
|
|
template <class T>
|
|
const T& at(const T* pa, std::ptrdiff_t key) { return pa[key]; }
|
|
|
|
template <class T>
|
|
T& 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[] = { "San Jose", "San Francisco", "San Jose",
|
|
"San Francisco", "Los Angeles", "San Diego",
|
|
"Fresno", "Los Vegas", "Reno", "Sacramento",
|
|
"Salt Lake City", "Pheonix" };
|
|
|
|
// Specify all the connecting roads between cities.
|
|
typedef std::pair<int,int> E;
|
|
E edge_array[] = { E(Sacramento, Reno), ... };
|
|
|
|
// Specify the graph type.
|
|
typedef adjacency_list<vecS, vecS, undirectedS> 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 "color" the vertices.
|
|
// Here we use std::vector as exterior property storage.
|
|
std::vector<default_color_type> colors(N);
|
|
|
|
cout << "*** Depth First ***" << endl;
|
|
depth_first_search(G, city_visitor(names), colors.begin());
|
|
cout << endl;
|
|
|
|
// Get the source vertex
|
|
boost::graph_traits<Graph>::vertex_descriptor
|
|
s = vertex(SanJose, G);
|
|
|
|
cout << "*** Breadth First ***" << 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 <class Iterator, class IDMap>
|
|
class iterator_map
|
|
{
|
|
public:
|
|
typedef typename boost::property_traits<IDMap>::key_type key_type;
|
|
typedef typename std::iterator_traits<Iterator>::value_type value_type;
|
|
typedef boost::lvalue_property_map_tag category;
|
|
|
|
iterator_map(Iterator i = Iterator(),
|
|
const IDMap& 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 <class Iter, class ID>
|
|
typename std::iterator_traits<Iter>::value_type
|
|
get(const iterator_map<Iter,ID>& i,
|
|
typename boost::property_traits<ID>::key_type key)
|
|
{
|
|
return i.m_iter[i.m_id[key]];
|
|
}
|
|
template <class Iter, class ID>
|
|
void
|
|
put(const iterator_map<Iter,ID>& i,
|
|
typename boost::property_traits<ID>::key_type key,
|
|
const typename std::iterator_traits<Iter>::value_type& value)
|
|
{
|
|
i.m_iter[i.m_id[key]] = value;
|
|
}
|
|
template <class Iter, class ID>
|
|
typename std::iterator_traits<Iter>::reference
|
|
at(const iterator_map<Iter,ID>& i,
|
|
typename boost::property_traits<ID>::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 © 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>
|