Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/graph/doc/leda_conversion.html @ 29

Last change on this file since 29 was 29, checked in by landauf, 17 years ago

updated boost from 1_33_1 to 1_34_1
File size: 9.8 KB
Line 
1<HTML>
2<!--
3  -- Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000
4  --
5  -- Distributed under the Boost Software License, Version 1.0.
6  -- (See accompanying file LICENSE_1_0.txt or copy at
7  -- http://www.boost.org/LICENSE_1_0.txt)
8  -->
9<Head>
10<Title>Boost Graph Library: Converting Existing Graphs to BGL</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:leda-conversion">How to Convert Existing Graphs to BGL</H1>
20
21<P>
22Though the main goal of  BGL is to aid the development of new
23applications and graph algorithms, there are quite a few existing codes
24that could benefit from using BGL algorithms. One way to use the BGL
25algorithms with existing graph data structures is to copy data from
26the older graph format into a BGL graph which could then be used in
27the BGL algorithms. The problem with this approach is that it can be
28expensive to make this copy. Another approach is to wrap the existing
29graph data structure with a BGL interface.
30
31<P>
32The Adaptor pattern&nbsp;[<A
33 HREF="bibliography.html#gamma95:_design_patterns">12</A>] typically requires
34that the adaptee object be contained inside a new class that provides the
35desired interface. This containment is not required when wrapping a
36graph for  BGL because the BGL graph interface consists solely of
37free (global) functions. Instead of creating a new graph class, you
38need to overload all the free functions required by the interface.  We
39call this free function wrapper approach <I>external adaptation</I>.
40
41<P>
42One of the more commonly used graph classes is the LEDA parameterized
43<a
44href="http://www.mpi-sb.mpg.de/LEDA/MANUAL/bgraph.html"><TT>GRAPH</TT></a>
45class&nbsp;[<A HREF="bibliography.html#mehlhorn99:_leda">22</A>]. In
46this section we will show how to create a BGL interface for this
47class. The first question is which BGL interfaces (or concepts) we
48should implement. The following concepts are straightforward and easy
49to implement on top of LEDA: <a
50href="./VertexListGraph.html">VertexListGraph</a>, <a
51href="./BidirectionalGraph.html">BidirectionalGraph</a>, and <a
52href="./MutableGraph.html">MutableGraph</a>.
53
54<P>
55All types associated with a BGL graph class are accessed though the
56<TT>graph_traits</TT> class. We can partially specialize this traits
57class for the LEDA <TT>GRAPH</TT> class in the following way. The
58<TT>node</TT> and <TT>edge</TT> are the LEDA types for representing
59vertices and edges. The LEDA <TT>GRAPH</TT> is for directed graphs, so
60we choose <TT>directed_tag</TT> for the <TT>directed_category</TT>.
61The LEDA <TT>GRAPH</TT> does not automatically prevent the insertion
62of parallel edges, so we choose <TT>allow_parallel_edge_tag</TT> for
63the <TT>edge_parallel_category</TT>. The return type for the LEDA
64function <TT>number_of_nodes()</TT> and <TT>number_of_edges()</TT> is
65<TT>int</TT>, so we choose that type for the
66<TT>vertices_size_type</TT> and <tt>edges_size_type</tt> of the
67graph. The iterator types will be more complicated, so we leave that
68for later.
69
70<P>
71<PRE>
72namespace boost {
73  template &lt;class vtype, class etype&gt;
74  struct graph_traits&lt; GRAPH&lt;vtype,etype&gt; &gt; {
75    typedef node vertex_descriptor;
76    typedef edge edge_descriptor;
77
78    // iterator typedefs...
79
80    typedef directed_tag directed_category;
81    typedef allow_parallel_edge_tag edge_parallel_category;
82    typedef int vertices_size_type;
83    typedef int edges_size_type;
84  };
85} // namespace boost
86</PRE>
87
88<P>
89First we will write the <TT>source()</TT> and <TT>target()</TT>
90functions of the <a href="./IncidenceGraph.html">IncidenceGraph</a>
91concept, which is part of the <a
92href="./VertexListGraph.html">VertexListGraph</a> concept. We use the
93LEDA <TT>GRAPH</TT> type for the graph parameter, and use
94<TT>graph_traits</TT> to specify the edge parameter and the vertex
95return type. We could also just use the LEDA types <TT>node</TT> and
96<TT>edge</TT> here, but it is better practice to always use
97<TT>graph_traits</TT>. If there is a need to change the associated
98vertex or edge type, you will only need to do it in one place, inside
99the specialization of <TT>graph_traits</TT> instead of throughout your
100code. LEDA provides <TT>source()</TT> and <TT>target()</TT> functions,
101so we merely call them.
102
103<P>
104<PRE>
105namespace boost {
106  template &lt;class vtype, class etype&gt;
107  typename graph_traits&lt; GRAPH&lt;vtype,etype&gt; &gt;::vertex_descriptor
108  source(
109    typename graph_traits&lt; GRAPH&lt;vtype,etype&gt; &gt;::edge_descriptor e,
110    const GRAPH&lt;vtype,etype&gt;&amp; g)
111  {
112    return source(e);
113  }
114
115  template &lt;class vtype, class etype&gt;
116  typename graph_traits&lt; GRAPH&lt;vtype,etype&gt; &gt;::vertex_descriptor
117  target(
118    typename graph_traits&lt; GRAPH&lt;vtype,etype&gt; &gt;::edge_descriptor e,
119    const GRAPH&lt;vtype,etype&gt;&amp; g)
120  {
121    return target(e);
122  }
123} // namespace boost
124</PRE>
125
126<P>
127The next function from <a
128href="./IncidenceGraph.html">IncidenceGraph</a> that we need to
129implement is <TT>out_edges()</TT>. This function returns a pair of
130out-edge iterators. Since LEDA does not use STL-style iterators we
131need to implement some. There is a very handy boost utility for
132implementing iterators, called <TT>iterator_adaptor</TT>.  Writing a
133standard conforming iterator classes is actually quite difficult,
134harder than you may think. With the <TT>iterator_adaptor</TT> class,
135you just implement a policy class and the rest is taken care of. The
136following code is the policy class for our out-edge iterator. In LEDA,
137the edge object itself is used like an iterator. It has functions
138<TT>Succ_Adj_Edge()</TT> and <TT>Pred_Adj_Edge()</TT> to move to the
139next and previous (successor and predecessor) edge. One gotcha in
140using the LEDA <TT>edge</TT> as an iterator comes up in the
141<TT>dereference()</TT> function, which merely returns the edge
142object. The dereference operator for standard compliant iterators must
143be a const member function, which is why the edge argument is
144const. However, the return type should not be const, hence the need
145for <TT>const_cast</TT>.
146
147<P>
148<PRE>
149namespace boost {
150  struct out_edge_iterator_policies
151  {
152    static void increment(edge&amp; e)
153    { e = Succ_Adj_Edge(e,0); }
154
155    static void decrement(edge&amp; e)
156    { e = Pred_Adj_Edge(e,0); }
157
158    template &lt;class Reference&gt;
159    static Reference dereference(type&lt;Reference&gt;, const edge&amp; e)
160    { return const_cast&lt;Reference&gt;(e); }
161
162    static bool equal(const edge&amp; x, const edge&amp; y)
163    { return x == y; }
164  };
165} // namespace boost
166</PRE>
167
168<P>
169Now we go back to the <TT>graph_traits</TT> class, and use
170<TT>iterator_adaptor</TT> to fill in the
171<TT>out_edge_iterator</TT>. We use the <TT>iterator</TT> type
172to specify the associated types of the iterator, including iterator
173category and value type.
174
175<P>
176<PRE>
177  namespace boost {
178    template &lt;class vtype, class etype&gt;
179    struct graph_traits&lt; GRAPH&lt;vtype,etype&gt; &gt; {
180      // ...
181      typedef iterator_adaptor&lt;edge,
182        out_edge_iterator_policies,
183        iterator&lt;std::bidirectional_iterator_tag,edge&gt;
184      &gt; out_edge_iterator;
185      // ...
186    };
187  } // namespace boost
188</PRE>
189
190<P>
191With the <TT>out_edge_iterator</TT> defined in <TT>graph_traits</TT> we
192are ready to define the <TT>out_edges()</TT> function. The following
193definition looks complicated at first glance, but it is really quite
194simple. The return type should be a pair of out-edge iterators, so we
195use <TT>std::pair</TT> and then <TT>graph_traits</TT> to access the
196out-edge iterator types. In the body of the function we construct the
197out-edge iterators by passing in the first adjacenct edge for the
198begin iterator, and 0 for the end iterator (which is used in LEDA as
199the end sentinel). The 0 argument to <TT>First_Adj_Edge</TT> tells
200LEDA we want out-edges (and not in-edges).
201
202<P>
203<PRE>
204namespace boost {
205  template &lt;class vtype, class etype&gt;
206  inline std::pair&lt;
207    typename graph_traits&lt; GRAPH&lt;vtype,etype&gt; &gt;::out_edge_iterator,
208    typename graph_traits&lt; GRAPH&lt;vtype,etype&gt; &gt;::out_edge_iterator &gt; 
209  out_edges(
210    typename graph_traits&lt; GRAPH&lt;vtype,etype&gt; &gt;::vertex_descriptor u,
211    const GRAPH&lt;vtype,etype&gt;&amp; g)
212  {
213    typedef typename graph_traits&lt; GRAPH&lt;vtype,etype&gt; &gt;
214      ::out_edge_iterator Iter;
215    return std::make_pair( Iter(First_Adj_Edge(u,0)), Iter(0) );
216  }
217} // namespace boost
218</PRE>
219
220<P>
221The rest of the iterator types and interface functions are constructed
222using the same techniques as above.  The complete code for the LEDA
223wrapper interface is in <a
224href="../../../boost/graph/leda_graph.hpp"><TT>boost/graph/leda_graph.hpp</TT></a>. In
225the following code we use the BGL concept checks to make sure that we
226correctly implemented the BGL interface. These checks do not test the
227run-time behaviour of the implementation; that is tested in <a
228href="../test/graph.cpp"><TT>test/graph.cpp</TT></a>.
229
230<P>
231<PRE>
232  #include &lt;boost/graph/graph_concepts.hpp&gt;
233  #include &lt;boost/graph/leda_graph.hpp&gt;
234
235  int
236  main(int,char*[])
237  {
238    typedef GRAPH&lt;int,int&gt; Graph;
239    function_requires&lt; VertexListGraphConcept&lt;Graph&gt; &gt;();
240    function_requires&lt; BidirectionalGraphConcept&lt;Graph&gt; &gt;();
241    function_requires&lt; MutableGraphConcept&lt;Graph&gt; &gt;();
242    return 0;
243  }
244</PRE>
245
246
247
248<br>
249<HR>
250<TABLE>
251<TR valign=top>
252<TD nowrap>Copyright &copy 2000-2001</TD><TD>
253<A HREF="../../../people/jeremy_siek.htm">Jeremy Siek</A>,
254Indiana University (<A
255HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br>
256<A HREF="../../../people/liequan_lee.htm">Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@cs.indiana.edu">llee@cs.indiana.edu</A>)<br>
257<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
258Indiana University (<A
259HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
260</TD></TR></TABLE>
261
262</BODY>
263</HTML> 
Note: See TracBrowser for help on using the repository browser.