123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787 |
- <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>Using the Boost Graph Library</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="SECTION00830000000000000000"></A>
- <A NAME="sec:using-adjacency-list"></A>
- <BR>
- Using <TT>adjacency_list</TT>
- </H1>
- This section describes the details of how use the
- <tt>adjacency_list</tt> class. The presentation is divided into the
- following topics:
- <OL>
- <li><A href="#sec:choosing-graph-type">Choosing the <TT>Edgelist</TT> and <TT>VertexList</TT></A>
- <li><a href="#sec:directed-and-undirected">Directed and Undirected
- Adjacency Lists</a>
- <li><A href="#sec:adjacency-list-properties">Internal Properties</A>
- <li><A href="#sec:custom-storage">Customizing the Adjacency List Storage</A>
- </ol>
- <P>
- <H2><A NAME="SECTION00831000000000000000"></A>
- <A NAME="sec:choosing-graph-type"></A>
- <BR>
- Choosing the <TT>Edgelist</TT> and <TT>VertexList</TT>
- </H2>
- <P>
- This section focuses on how to decide which version of the <a
- href="./adjacency_list.html"><TT>adjacency_list</TT></a> class to use
- in different situations. The <TT>adjacency_list</TT> is like a
- swiss-army knife in that it can be configured in many ways. The
- parameters that we will focus on in this section are <TT>OutEdgeList</TT>
- and <TT>VertexList</TT>, which control the underlying data structures
- that will be used to represent the graph. The choice of
- <TT>OutEdgeList</TT> and <TT>VertexList</TT> affects the time complexity
- of many of the graph operations and the space complexity of the graph
- object.
- <P>
- BGL uses containers from the STL such as
- <a href="http://www.boost.org/sgi/stl/Vector.html"><TT>std::vector</TT></a>,
- <a href="http://www.boost.org/sgi/stl/List.html"><TT>std::list</TT></a>,
- and <a href="http://www.boost.org/sgi/stl/set.html"><TT>std::set</TT></a>
- to represent the set of vertices and the adjacency structure
- (out-edges and in-edges) of the graph. There are several selector
- types that are used to specify the choice of container for
- <TT>OutEdgeList</TT> and <TT>VertexList</TT>.
- <P>
- <UL>
- <LI><TT>vecS</TT> selects <TT>std::vector</TT>.</LI>
- <LI><TT>listS</TT> selects <TT>std::list</TT>.</LI>
- <LI><TT>slistS</TT> selects <TT>std::slist</TT>.</LI>
- <LI><TT>setS</TT> selects <TT>std::set</TT>.</LI>
- <LI><TT>multisetS</TT> selects <TT>std::multiset</TT>.</LI>
- <LI><TT>hash_setS</TT> selects <TT>boost::unordered_set</TT>.</LI>
- </UL>
- <P>
- <H3>Choosing the <TT>VertexList</TT> type</A></H3>
- <P>
- The <TT>VertexList</TT> parameter determines what kind of container
- will be used to represent the vertex set, or two-dimensional structure
- of the graph. The container must model <a
- href="http://www.boost.org/sgi/stl/Sequence.html">Sequence</a> or
- <a
- href="http://www.boost.org/sgi/stl/RandomAccessContainer.html">RandomAccessContainer</a>. In
- general, <TT>listS</TT> is a good choice if you need to add and remove
- vertices quickly. The price for this is extra space overhead compared
- to choosing <TT>vecS</TT>.
- <P>
- <H4>Space Complexity</H4>
- <P>
- The <TT>std::list</TT> has a higher per-vertex space overhead than the
- <TT>std::vector</TT>, storing three extra pointers per vertex.
- <P>
- <H4>Time Complexity</H4>
- <P>
- The choice of <TT>VertexList</TT> affects the time complexity of the
- following operations.
- <ul>
- <li>
- <pre>
- add_vertex()
- </PRE>
- This operation is amortized constant time for both <TT>vecS</TT> and
- <TT>listS</TT> (implemented with <TT>push_back()</TT>). However, when
- the <TT>VertexList</TT> type is <TT>vecS</TT> the time for this
- operation is occasionally large because the vector will be
- reallocated and the whole graph copied.
- <P></p>
- <li>
- <PRE>
- remove_vertex()
- </PRE>
- This operation is constant time for <TT>listS</TT> and <i>O(V + E)</i> for
- <TT>vecS</TT>. The large time complexity for <TT>vecS</TT> is because
- the vertex descriptors (which in this case are indices that correspond
- to the vertices' place in the vertex list) must be adjusted in the
- out-edges for the whole graph.
- <P></P>
- <li>
- <PRE>
- vertex()
- </PRE>
- This operation is constant time for <TT>vecS</TT> and for
- <TT>listS</TT>.
- </ul>
-
- <P>
- <H3><A NAME="SECTION00831200000000000000">
- Choosing the <TT>OutEdgeList</TT> type</A>
- </H3>
- <P>
- The <TT>OutEdgeList</TT> parameter determines what kind of container will
- be used to store the out-edges (and possibly in-edges) for each vertex
- in the graph. The containers used for edge lists must either satisfy
- the requirements for <a
- href="http://www.boost.org/sgi/stl/Sequence.html">Sequence</a> or for
- <a
- href="http://www.boost.org/sgi/stl/AssociativeContainer.html">AssociativeContainer</a>.
- <P>
- One of the first things to consider when choosing the
- <TT>OutEdgeList</TT> is whether you want <TT>adjacency_list</TT> to
- enforce the absence of parallel edges in the graph (that is, enforce
- that the graph not become a multi-graph). If you want this enforced
- then use the <TT>setS</TT> or <TT>hash_setS</TT> selectors. If you
- want to represent a multi-graph, or know that you will not be
- inserting parallel edges into the graph, then choose one of the <a
- href="http://www.boost.org/sgi/stl/Sequence.html">Sequence</a>
- types: <TT>vecS</TT>, <TT>listS</TT>, or <TT>slistS</TT>.
- You will also want to take into account the differences in time and space
- complexity for the various graph operations. Below we use <i>V</i> for
- the total number of vertices in the graph and <i>E</i> for the total
- number of edges. Operations not discussed here are constant time.
- <P>
- <H4>Space Complexity</H4>
- <P>
- The selection of the <TT>OutEdgeList</TT> affects the amount of space
- overhead per edge in the graph object. In the order of least space to
- most space, the selectors are <TT>vecS</TT>, <TT>slistS</TT>,
- <TT>listS</TT>, and <TT>setS</TT>.
- <P>
- <H4>Time Complexity</H4>
- <P>
- In the following description of the time complexity for various
- operations, we use <i>E/V</i> inside of the ``big-O'' notation to
- express the length of an out-edge list. Strictly speaking this is not
- accurate because <i>E/V</i> merely gives the average number of edges
- per vertex in a random graph. The worst-case number of out-edges for a
- vertex is <i>V</i> (unless it is a multi-graph). For sparse graphs
- <i>E/V</i> is typically much smaller than <i>V</i> and can be
- considered a constant.
- <P>
-
- <P> <P>
- <UL>
- <LI>
- <PRE>
- add_edge()
- </PRE>
- When the <TT>OutEdgeList</TT> is a <a
- href="http://www.boost.org/sgi/stl/UniqueAssociativeContainer.html">UniqueAssociativeContainer</a>
- like <TT>std::set</TT> the absence of parallel edges is enforced when
- an edge is added. The extra lookup involved has time complexity
- <i>O(log(E/V))</i>. The <TT>OutEdgeList</TT> types that model <a
- href="http://www.boost.org/sgi/stl/Sequence.html">Sequence</a> do
- not perform this check and therefore <TT>add_edge()</TT> is amortized
- constant time. This means that it if you don't care whether the graph
- has parallel edges, or know that the input to the graph does not
- contain them, then it is better to use the sequence-based
- <TT>OutEdgeList</TT>. The <TT>add_edge()</TT> for the sequence-based
- <TT>OutEdgeList</TT> is implemented with <TT>push_front()</TT> or
- <TT>push_back()</TT>. However, for <TT>std::list</TT> and
- <TT>std::slist</TT> this operation will typically be faster than with
- <TT>std::vector</TT> which occasionally reallocates and copies all
- elements.
- <p></p>
- <li>
- <PRE>
- remove_edge()
- </PRE>
- For sequence-based <TT>OutEdgeList</TT> types this operation is
- implemented with <TT>std::remove_if()</TT> which means the average
- time is <i>E/V</i>. For set-based <TT>OutEdgeList</TT> types this is
- implemented with the <TT>erase()</TT> member function, which has
- average time <i>log(E/V)</i>.
- <p></p>
- <li>
- <PRE>
- edge()
- </PRE>
- The time complexity for this operation is <i>O(E/V)</i> when the
- <TT>OutEdgeList</TT> type is a <a
- href="http://www.boost.org/sgi/stl/Sequence.html">Sequence</a> and it
- is <i>O(log(E/V))</i> when the <TT>OutEdgeList</TT> type is an <a
- href="http://www.boost.org/sgi/stl/AssociativeContainer.html">AssociativeContainer</a>.
- <p></p>
- <li>
- <PRE>
- clear_vertex()
- </PRE>
- For directed graphs with sequence-based <TT>OutEdgeList</TT> types the time
- complexity is <i>O(V + E)</i>, while for associative container based
- <TT>OutEdgeList</TT> types the operation is faster, with time complexity
- <i>O(V log(E/V))</i>. For undirected graphs this operation is
- <i>O(E<sup>2</sup>/V<sup>2</sup>)</i> or <i>O(E/V log(E/V))</i>.
- <p></p>
- <li>
- <PRE>
- remove_vertex()
- </PRE>
- The time complexity for this operation is <i>O(V + E)</i> regardless of the
- <TT>OutEdgeList</TT> type.
- <p></p>
- <li>
- <PRE>
- out_edge_iterator::operator++()
- </PRE>
- This operation is constant time for all the <TT>OneD</TT> types.
- However, there is a significant constant factor time difference
- between the various types, which is important since this operation is
- the work-horse of most graph algorithms. The speed of
- this operation in order of fastest to slowest is
- <TT>vecS</TT>, <TT>slistS</TT>, <TT>listS</TT>, <TT>setS</TT>,
- <TT>hash_setS</TT>.
- <p></p>
- <li>
- <PRE>
- in_edge_iterator::operator++()
- </PRE>
- This operation is constant time and exhibits a similar speed
- ordering as the <TT>out_edge_iterator</TT> with respect to
- the <TT>OutEdgeList</TT> selection.
- <p></p>
- <li>
- <PRE>
- vertex_iterator::operator++()
- </PRE>
- This operation is constant time and fast (same speed as incrementing a
- pointer). The selection of <TT>OneD</TT> does not affect the speed of
- this operation.
- <p></p>
- <li>
- <PRE>
- edge_iterator::operator++()
- </PRE>
- This operation is constant time and exhibits a similar speed ordering
- as the <TT>out_edge_iterator</TT> with respect to the <TT>OutEdgeList</TT>
- selection. Traversing through the whole edge set is <i>O(V + E)</i>.
- <p></p>
- <li>
- <PRE>
- adjacency_iterator::operator++()
- </PRE>
- This operation is constant time and exhibits a similar speed
- ordering as the <TT>out_edge_iterator</TT> with respect to
- the <TT>OutEdgeList</TT> selection.
- <p></p>
- </ul>
- <P>
-
- <P>
- <H2><a name="sec:directed-and-undirected">Directed and Undirected Adjacency Lists</H2>
- <P>
- The <TT>adjacency_list</TT> class can be used to represent both
- directed and undirected graphs, depending on the argument passed to
- the <TT>Directed</TT> template parameter. Selecting <TT>directedS</TT>
- or <TT>bidirectionalS</TT> choose a directed graph, whereas
- <TT>undirectedS</TT> selects the representation for an undirected
- graph. See Section <A
- HREF="graph_concepts.html#sec:undirected-graphs">Undirected Graphs</A>
- for a description of the difference between directed and undirected
- graphs in BGL. The <TT>bidirectionalS</TT> selector specifies that the
- graph will provide the <TT>in_edges()</TT> function as well as the
- <TT>out_edges()</TT> function. This imposes twice as much space
- overhead per edge, which is why <TT>in_edges()</TT> is optional.
- <P>
- <H2><A NAME="sec:adjacency-list-properties"></A>
- Internal Properties
- </H2>
- <P>
- Properties can be attached to the vertices or edges of an
- <TT>adjacency_list</TT> graph via the property interface. The template
- parameters <TT>VertexProperty</TT> and <TT>EdgeProperty</TT> of the
- <TT>adjacency_list</TT> class are meant to be filled by these interior
- properties.
- <p><b>NOTE</b>: The Boost Graph Library supports two interchangeable methods for
- specifying interior properties: <a href="bundles.html">bundled properties</a>
- and property lists. The former is easier to use and requires less effort,
- whereas the latter is compatible with older, broken compilers and is
- backward-compatible with Boost versions prior to 1.32.0. If you absolutely
- require these compatibility features, read on to learn about property lists.
- Otherwise, we strongly suggest that you read about the <a href="bundles.html">bundled
- properties</a> mechanism.
- <p>One may specify internal properties via property lists, which are build from instances of the
- property class declared as follows.
- <P>
- <PRE>
- template <class PropertyTag, class T, class NextProperty = no_property>
- struct property;
- </PRE>
- <P>
- The <a href="./PropertyTag.html"><TT>PropertyTag</TT></a> template
- parameter is a tag class that simply identifies or gives a unique name
- to the property. There are several predefined tags, and it is easy to
- add more.
- <P>
- <PRE>
- struct vertex_index_t { };
- struct vertex_index1_t { };
- struct vertex_index2_t { };
- struct edge_index_t { };
- struct graph_name_t { };
- struct vertex_name_t { };
- struct edge_name_t { };
- struct edge_weight_t { };
- struct edge_weight2_t { };
- struct edge_capacity_t { };
- struct edge_residual_capacity_t { };
- struct edge_reverse_t { };
- struct vertex_distance_t { };
- struct vertex_root_t { };
- struct vertex_all_t { };
- struct edge_all_t { };
- struct graph_all_t { };
- struct vertex_color_t { };
- struct vertex_rank_t { };
- struct vertex_predecessor_t { };
- struct vertex_isomorphism_t { };
- struct vertex_invariant_t { };
- struct vertex_invariant1_t { };
- struct vertex_invariant2_t { };
- struct vertex_degree_t { };
- struct vertex_out_degree_t { };
- struct vertex_in_degree_t { };
- struct vertex_discover_time_t { };
- struct vertex_finish_time_t { };
- </PRE>
- <P>
- The <b><TT>T</TT></b> template parameter of <TT>property</TT>
- specifies the type of the property values. The type <tt>T</tt> must be
- <a
- href="http://www.boost.org/sgi/stl/DefaultConstructible.html">Default
- Constructible</a>, <a
- href="../../utility/Assignable.html">Assignable</a>, and <a
- href="../../utility/CopyConstructible.html">Copy Constructible</a>.
- Like the containers of the C++ Standard Library, the property objects
- of type <tt>T</tt> are held by-value inside of the graph.
- <p>
- The <b><TT>NextProperty</TT></b> parameter allows <TT>property</TT>
- types to be nested, so that an arbitrary number of properties can be
- attached to the same graph.
- <P>
- The following code shows how a vertex and edge property type can be
- assembled and used to create a graph type. We have attached a distance
- property with values of type <TT>float</TT> and a name property with
- values of type <TT>std::string</TT> to the vertices of the graph. We
- have attached a weight property with values of type <TT>float</TT> to
- the edges of the graph.
- <P>
- <PRE>
- typedef property<vertex_distance_t, float,
- property<vertex_name_t, std::string> > VertexProperty;
- typedef property<edge_weight_t, float> EdgeProperty;
- typedef adjacency_list<mapS, vecS, undirectedS,
- VertexProperty, EdgeProperty> Graph;
- Graph g(num_vertices); // construct a graph object
- </PRE>
- <P>
- The property values are then read from and written to using property
- maps. See Section <A HREF="using_property_maps.html#sec:interior-properties">Interior
- Properties</A> for a description of how to obtain property maps
- from a graph, and read Section <A
- HREF="./using_property_maps.html">Property Maps</A> for how
- to use property maps.
- <P>
- <H3><A NAME="sec:custom-edge-properties"></A>
- Custom Edge Properties
- </H3>
- <P>
- Creating your own property types and properties is easy; just define
- a tag class for your new property. The property tag class will need to
- define <tt>num</tt> with a unique integer ID, and <tt>kind</tt> which
- should be either <tt>edge_property_tag</tt>,
- <tt>vertex_property_tag</tt>, or <tt>graph_property_tag</tt>.
- <P>
- <PRE>
- struct flow_t {
- typedef edge_property_tag kind;
- };
- struct capacity_t {
- typedef edge_property_tag kind;
- };
- </PRE>
- <p>
- You can also use enum's instead of struct's to create tag types. Create an enum
- type for each property inside the boost namespace. The first part of the name of
- the enum type must be <tt>edge</tt>, <tt>vertex</tt>, or <tt>graph</tt> followed
- by an underscore, the new property name, and a <tt>_t</tt> at the end. Inside
- the enum, define a value with the same name minus the <tt>_t</tt>. Then invoke
- the <tt>BOOST_INSTALL_PROPERTY</tt> macro.
- <pre>
- namespace boost {
- enum edge_flow_t { edge_flow };
- enum edge_capacity_t { edge_capacity };
- BOOST_INSTALL_PROPERTY(edge, flow);
- BOOST_INSTALL_PROPERTY(edge, capacity);
- }
- </pre>
- <P>
- Now you can use your new property tag in the definition of properties just as
- you would one of the builtin tags.
- <P>
- <PRE>
- typedef property<capacity_t, int> Cap;
- typedef property<flow_t, int, Cap> EdgeProperty;
- typedef adjacency_list<vecS, vecS, no_property, EdgeProperty> Graph;
- </PRE>
- <P>
- Just as before, the property maps for these properties can be
- obtained from the graph via the
- <TT>get(Property, g)</TT> function.
- <P>
- <PRE>
- property_map<Graph, capacity_t>::type capacity
- = get(capacity_t(), G);
- property_map<Graph, flow_t>::type flow
- = get(flow_t(), G);
- </PRE>
- <P>
- The file <TT>edge_property.cpp</TT> shows the complete source
- code for this example.
- <P>
- <H3><A NAME="SECTION00833200000000000000"></A>
- <A NAME="sec:custom-vertex-properties"></A>
- <BR>
- Custom Vertex Properties
- </H3>
- <P>
- Creating your own properties to attach to vertices is just as easy as
- for edges. Here we want to attach people's first names to the vertices
- in the graph.
- <P>
- <PRE>
- struct first_name_t {
- typedef vertex_property_tag kind;
- };
- </PRE>
- <P>
- Now we can use the new tag in the <TT>property</TT> class and use that in
- the assembly of a graph type. The following code shows creating the
- graph type, and then creating the graph object. We fill in the edges
- and also assign names to the vertices. The edges will represent ``who
- owes who''.
- <P>
- <PRE>
- typedef property<first_name_t, std::string> FirstNameProperty;
- typedef adjacency_list<vecS, vecS, directedS,
- FirstNameProperty> MyGraphType;
- typedef pair<int,int> Pair;
- Pair edge_array[11] = { Pair(0,1), Pair(0,2), Pair(0,3),
- Pair(0,4), Pair(2,0), Pair(3,0),
- Pair(2,4), Pair(3,1), Pair(3,4),
- Pair(4,0), Pair(4,1) };
-
- MyGraphType G(5);
- for (int i = 0; i < 11; ++i)
- add_edge(edge_array[i].first, edge_array[i].second, G);
- property_map<MyGraphType, first_name_t>::type
- name = get(first_name_t(), G);
-
- boost::put(name, 0, "Jeremy");
- boost::put(name, 1, "Rich");
- boost::put(name, 2, "Andrew");
- boost::put(name, 3, "Jeff");
- name[4] = "Kinis"; // you can use operator[] too
-
- who_owes_who(edges(G).first, edges(G).second, G);
- </PRE>
- <P>
- The <TT>who_owes_who()</TT> function written for this example was
- implemented in a generic style. The input is templated so we do not
- know the actual graph type. To find out the type of the property
- map for our first-name property, we need to use the
- <TT>property_map</TT> traits class. The <TT>const_type</TT>
- is used since the graph parameter is const. Once we have the property
- map type, we can deduce the value type of the property using the
- <TT>property_traits</TT> class. In this example, we know that the
- property's value type will be <TT>std::string</TT>, but written in this
- generic fashion the <TT>who_owes_who()</TT> function could work with
- other property value types.
- <P>
- <PRE>
- template <class EdgeIter, class Graph>
- void who_owes_who(EdgeIter first, EdgeIter last, const Graph& G)
- {
- // Access the propety acessor type for this graph
- typedef typename property_map<Graph,
- first_name_t>::const_type NameMap;
- NameMap name = get(first_name, G);
- typedef typename boost::property_traits<NameMap>
- ::value_type NameType;
- NameType src_name, targ_name;
- while (first != last) {
- src_name = boost::get(name, source(*first, G));
- targ_name = boost::get(name, target(*first, G));
- cout << src_name << " owes "
- << targ_name << " some money" << endl;
- ++first;
- }
- </PRE>
- The output is:
- <PRE>
- Jeremy owes Rich some money
- Jeremy owes Andrew some money
- Jeremy owes Jeff some money
- Jeremy owes Kinis some money
- Andrew owes Jeremy some money
- Andrew owes Kinis some money
- Jeff owes Jeremy some money
- Jeff owes Rich some money
- Jeff owes Kinis some money
- Kinis owes Jeremy some money
- Kinis owes Rich some money
- </PRE>
- The complete source code to this example is in the file
- <TT>interior_property_map.cpp</TT>.
- <P>
- <H2><A NAME="sec:custom-storage"></A>
- Customizing the Adjacency List Storage
- </H2>
- <P>
- The <TT>adjacency_list</TT> is constructed out of two kinds of
- containers. One type of container to hold all the vertices in the
- graph, and another type of container for the out-edge list (and
- potentially in-edge list) for each vertex. BGL provides selector
- classes that allow the user to choose between several of the containers
- from the STL. It is also possible to use your own container types.
- When customizing the <TT>VertexList</TT> you need to define a container
- generator as described below. When customizing the <TT>OutEdgeList</TT> you
- will need to define a container generator and the parallel edge
- traits. The file <TT>container_gen.cpp</TT> has an example of
- how to use a custom storage type.
- <P>
- <H3><A NAME="SECTION00834100000000000000">
- Container Generator</A>
- </H3>
- <P>
- The <TT>adjacency_list</TT> class uses a traits class called
- <TT>container_gen</TT> to map the <TT>OutEdgeList</TT> and <TT>VertexList</TT>
- selectors to the actual container types used for the graph storage.
- The default version of the traits class is listed below, along with an
- example of how the class is specialized for the <TT>listS</TT> selector.
- <P>
- <PRE>
- namespace boost {
- template <class Selector, class ValueType>
- struct container_gen { };
- template <class ValueType>
- struct container_gen<listS, ValueType> {
- typedef std::list<ValueType> type;
- };
- }
- </PRE>
- <P>
- To use some other container of your choice, define a
- selector class and then specialize the <TT>container_gen</TT>
- for your selector.
- <P>
- <PRE>
- struct custom_containerS { }; // your selector
- namespace boost {
- // the specialization for your selector
- template <class ValueType>
- struct container_gen<custom_containerS, ValueType> {
- typedef custom_container<ValueType> type;
- };
- }
- </PRE>
- <P>
- There may also be situations when you want to use a container that has
- more template parameters than just <TT>ValueType</TT>. For instance,
- you may want to supply the allocator type. One way to do this is to
- hard-code in the extra parameters within the specialization of
- <TT>container_gen</TT>. However, if you want more flexibility then you
- can add a template parameter to the selector class. In the code below
- we show how to create a selector that lets you specify the allocator
- to be used with the <TT>std::list</TT>.
- <P>
- <PRE>
- template <class Allocator>
- struct list_with_allocatorS { };
- namespace boost {
- template <class Alloc, class ValueType>
- struct container_gen<list_with_allocatorS<Alloc>, ValueType>
- {
- typedef typename Alloc::template rebind<ValueType>::other Allocator;
- typedef std::list<ValueType, Allocator> type;
- };
- }
- // now you can define a graph using std::list
- // and a specific allocator
- typedef adjacency_list< list_with_allocatorS< std::allocator<int> >, vecS, directedS> MyGraph;
- </PRE>
- <P>
- <H3><A NAME="SECTION00834300000000000000">
- Push and Erase for the Custom Container</A>
- </H3>
- <P>
- You must also tell the <TT>adjacency_list</TT> how elements can be
- efficiently added and removed from the custom container. This is
- accomplished by overloading the <TT>push()</TT> and <TT>erase()</TT>
- functions for the custom container type. The <TT>push()</TT> function
- should return an iterator pointing to the newly inserted element and a
- <TT>bool</TT> flag saying whether the edge was inserted.
- <PRE>
- template <class T>
- std::pair<typename custom_container<T>::iterator, bool>
- push(custom_container<T>& c, const T& v)
- {
- // this implementation may need to change for your container
- c.push_back(v);
- return std::make_pair(boost::prior(c.end()), true);
- }
- template <class T>
- void erase(custom_container<T>& c, const T& x)
- {
- // this implementation may need to change for your container
- c.erase(std::remove(c.begin(), c.end(), x), c.end());
- }
- </PRE>
- <P> There are default <TT>push()</TT> and <TT>erase()</TT> functions
- implemented for the STL container types.
- <H3><A NAME="SECTION00834200000000000000">
- Parallel Edge Traits</A>
- </H3>
- <P>
- When customizing the <TT>OutEdgeList</TT>, you must also specialize
- the <TT>parallel_edge_traits</TT> class to specify whether the
- container type allows parallel edges (and is a <a
- href="http://www.boost.org/sgi/stl/Sequence.html">Sequence</a>) or if
- the container does not allow parallel edges (and is an <a
- href="http://www.boost.org/sgi/stl/AssociativeContainer.html">AssociativeContainer</a>).
- <P>
- <PRE>
- template <>
- struct parallel_edge_traits<custom_containerS> {
- typedef allow_parallel_edge_tag type;
- };
- </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>)
- </TD></TR></TABLE>
- </BODY>
- </HTML>
|