Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_33_1/libs/graph/doc/leda_conversion.html @ 12

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

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