ceph/src/boost/libs/graph/doc/leda_conversion.html

   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>
  22 Though the main goal of  BGL is to aid the development of new
  23 applications and graph algorithms, there are quite a few existing codes
  24 that could benefit from using BGL algorithms. One way to use the BGL
  25 algorithms with existing graph data structures is to copy data from
  26 the older graph format into a BGL graph which could then be used in
  27 the BGL algorithms. The problem with this approach is that it can be
  28 expensive to make this copy. Another approach is to wrap the existing
  29 graph data structure with a BGL interface.
  30
  31 <P>
  32 The Adaptor pattern&nbsp;[<A
  33  HREF="bibliography.html#gamma95:_design_patterns">12</A>] typically requires
  34 that the adaptee object be contained inside a new class that provides the
  35 desired interface. This containment is not required when wrapping a
  36 graph for  BGL because the BGL graph interface consists solely of
  37 free (global) functions. Instead of creating a new graph class, you
  38 need to overload all the free functions required by the interface.  We
  39 call this free function wrapper approach <I>external adaptation</I>.
  40
  41 <P>
  42 One of the more commonly used graph classes is the LEDA parameterized
  43 <a
  44 href="http://www.mpi-sb.mpg.de/LEDA/MANUAL/bgraph.html"><TT>GRAPH</TT></a>
  45 class&nbsp;[<A HREF="bibliography.html#mehlhorn99:_leda">22</A>]. In
  46 this section we will show how to create a BGL interface for this
  47 class. The first question is which BGL interfaces (or concepts) we
  48 should implement. The following concepts are straightforward and easy
  49 to implement on top of LEDA: <a
  50 href="./VertexListGraph.html">VertexListGraph</a>, <a
  51 href="./BidirectionalGraph.html">BidirectionalGraph</a>, and <a
  52 href="./MutableGraph.html">MutableGraph</a>.
  53
  54 <P>
  55 All types associated with a BGL graph class are accessed though the
  56 <TT>graph_traits</TT> class. We can partially specialize this traits
  57 class 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
  59 vertices and edges. The LEDA <TT>GRAPH</TT> is for directed graphs, so
  60 we choose <TT>directed_tag</TT> for the <TT>directed_category</TT>.
  61 The LEDA <TT>GRAPH</TT> does not automatically prevent the insertion
  62 of parallel edges, so we choose <TT>allow_parallel_edge_tag</TT> for
  63 the <TT>edge_parallel_category</TT>. The return type for the LEDA
  64 function <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
  67 graph. The iterator types will be more complicated, so we leave that
  68 for later.
  69
  70 <P>
  71 <PRE>
  72 namespace 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>
  89 First we will write the <TT>source()</TT> and <TT>target()</TT>
  90 functions of the <a href="./IncidenceGraph.html">IncidenceGraph</a>
  91 concept, which is part of the <a
  92 href="./VertexListGraph.html">VertexListGraph</a> concept. We use the
  93 LEDA <TT>GRAPH</TT> type for the graph parameter, and use
  94 <TT>graph_traits</TT> to specify the edge parameter and the vertex
  95 return 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
  98 vertex or edge type, you will only need to do it in one place, inside
  99 the specialization of <TT>graph_traits</TT> instead of throughout your
 100 code. LEDA provides <TT>source()</TT> and <TT>target()</TT> functions,
 101 so we merely call them.
 102
 103 <P>
 104 <PRE>
 105 namespace 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>
 127 The next function from <a
 128 href="./IncidenceGraph.html">IncidenceGraph</a> that we need to
 129 implement is <TT>out_edges()</TT>. This function returns a pair of
 130 out-edge iterators. Since LEDA does not use STL-style iterators we
 131 need to implement some. There is a very handy boost utility for
 132 implementing iterators, called <TT>iterator_adaptor</TT>.  Writing a
 133 standard conforming iterator classes is actually quite difficult,
 134 harder than you may think. With the <TT>iterator_adaptor</TT> class,
 135 you just implement a policy class and the rest is taken care of. The
 136 following code is the policy class for our out-edge iterator. In LEDA,
 137 the 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
 139 next and previous (successor and predecessor) edge. One gotcha in
 140 using the LEDA <TT>edge</TT> as an iterator comes up in the
 141 <TT>dereference()</TT> function, which merely returns the edge
 142 object. The dereference operator for standard compliant iterators must
 143 be a const member function, which is why the edge argument is
 144 const. However, the return type should not be const, hence the need
 145 for <TT>const_cast</TT>.
 146
 147 <P>
 148 <PRE>
 149 namespace 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>
 169 Now 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
 172 to specify the associated types of the iterator, including iterator
 173 category 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>
 191 With the <TT>out_edge_iterator</TT> defined in <TT>graph_traits</TT> we
 192 are ready to define the <TT>out_edges()</TT> function. The following
 193 definition looks complicated at first glance, but it is really quite
 194 simple. The return type should be a pair of out-edge iterators, so we
 195 use <TT>std::pair</TT> and then <TT>graph_traits</TT> to access the
 196 out-edge iterator types. In the body of the function we construct the
 197 out-edge iterators by passing in the first adjacenct edge for the
 198 begin iterator, and 0 for the end iterator (which is used in LEDA as
 199 the end sentinel). The 0 argument to <TT>First_Adj_Edge</TT> tells
 200 LEDA we want out-edges (and not in-edges).
 201
 202 <P>
 203 <PRE>
 204 namespace 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>
 221 The rest of the iterator types and interface functions are constructed
 222 using the same techniques as above.  The complete code for the LEDA
 223 wrapper interface is in <a
 224 href="../../../boost/graph/leda_graph.hpp"><TT>boost/graph/leda_graph.hpp</TT></a>. In
 225 the following code we use the BGL concept checks to make sure that we
 226 correctly implemented the BGL interface. These checks do not test the
 227 run-time behaviour of the implementation; that is tested in <a
 228 href="../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     BOOST_CONCEPT_ASSERT(( VertexListGraphConcept&lt;Graph&gt; ));
 240     BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept&lt;Graph&gt; ));
 241     BOOST_CONCEPT_ASSERT(( MutableGraphConcept&lt;Graph&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="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>,
 254 Indiana University (<A
 255 HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br>
 256 <A HREF="http://www.boost.org/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>,
 258 Indiana University (<A
 259 HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
 260 </TD></TR></TABLE>
 261
 262 </BODY>
 263 </HTML>