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 [<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="https://algorithmic-solutions.info/leda_guide/graphs/param_graph.html"><TT>GRAPH</TT></a> 45class [<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 <class vtype, class etype> 74 struct graph_traits< GRAPH<vtype,etype> > { 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 <class vtype, class etype> 107 typename graph_traits< GRAPH<vtype,etype> >::vertex_descriptor 108 source( 109 typename graph_traits< GRAPH<vtype,etype> >::edge_descriptor e, 110 const GRAPH<vtype,etype>& g) 111 { 112 return source(e); 113 } 114 115 template <class vtype, class etype> 116 typename graph_traits< GRAPH<vtype,etype> >::vertex_descriptor 117 target( 118 typename graph_traits< GRAPH<vtype,etype> >::edge_descriptor e, 119 const GRAPH<vtype,etype>& 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& e) 153 { e = Succ_Adj_Edge(e,0); } 154 155 static void decrement(edge& e) 156 { e = Pred_Adj_Edge(e,0); } 157 158 template <class Reference> 159 static Reference dereference(type<Reference>, const edge& e) 160 { return const_cast<Reference>(e); } 161 162 static bool equal(const edge& x, const edge& 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 <class vtype, class etype> 179 struct graph_traits< GRAPH<vtype,etype> > { 180 // ... 181 typedef iterator_adaptor<edge, 182 out_edge_iterator_policies, 183 iterator<std::bidirectional_iterator_tag,edge> 184 > 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 <class vtype, class etype> 206 inline std::pair< 207 typename graph_traits< GRAPH<vtype,etype> >::out_edge_iterator, 208 typename graph_traits< GRAPH<vtype,etype> >::out_edge_iterator > 209 out_edges( 210 typename graph_traits< GRAPH<vtype,etype> >::vertex_descriptor u, 211 const GRAPH<vtype,etype>& g) 212 { 213 typedef typename graph_traits< GRAPH<vtype,etype> > 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 <boost/graph/graph_concepts.hpp> 233 #include <boost/graph/leda_graph.hpp> 234 235 int 236 main(int,char*[]) 237 { 238 typedef GRAPH<int,int> Graph; 239 BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> )); 240 BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<Graph> )); 241 BOOST_CONCEPT_ASSERT(( MutableGraphConcept<Graph> )); 242 return 0; 243 } 244</PRE> 245 246 247 248<br> 249<HR> 250<TABLE> 251<TR valign=top> 252<TD nowrap>Copyright © 2000-2001</TD><TD> 253<A HREF="http://www.boost.org/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="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="https://homes.cs.washington.edu/~al75">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> 264
