123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263 |
- <HTML>
- <!--
- Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 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>Boost Graph Library: Converting Existing Graphs to BGL</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="sec:leda-conversion">How to Convert Existing Graphs to BGL</H1>
- <P>
- Though the main goal of BGL is to aid the development of new
- applications and graph algorithms, there are quite a few existing codes
- that could benefit from using BGL algorithms. One way to use the BGL
- algorithms with existing graph data structures is to copy data from
- the older graph format into a BGL graph which could then be used in
- the BGL algorithms. The problem with this approach is that it can be
- expensive to make this copy. Another approach is to wrap the existing
- graph data structure with a BGL interface.
- <P>
- The Adaptor pattern [<A
- HREF="bibliography.html#gamma95:_design_patterns">12</A>] typically requires
- that the adaptee object be contained inside a new class that provides the
- desired interface. This containment is not required when wrapping a
- graph for BGL because the BGL graph interface consists solely of
- free (global) functions. Instead of creating a new graph class, you
- need to overload all the free functions required by the interface. We
- call this free function wrapper approach <I>external adaptation</I>.
- <P>
- One of the more commonly used graph classes is the LEDA parameterized
- <a
- href="https://algorithmic-solutions.info/leda_guide/graphs/param_graph.html"><TT>GRAPH</TT></a>
- class [<A HREF="bibliography.html#mehlhorn99:_leda">22</A>]. In
- this section we will show how to create a BGL interface for this
- class. The first question is which BGL interfaces (or concepts) we
- should implement. The following concepts are straightforward and easy
- to implement on top of LEDA: <a
- href="./VertexListGraph.html">VertexListGraph</a>, <a
- href="./BidirectionalGraph.html">BidirectionalGraph</a>, and <a
- href="./MutableGraph.html">MutableGraph</a>.
- <P>
- All types associated with a BGL graph class are accessed though the
- <TT>graph_traits</TT> class. We can partially specialize this traits
- class for the LEDA <TT>GRAPH</TT> class in the following way. The
- <TT>node</TT> and <TT>edge</TT> are the LEDA types for representing
- vertices and edges. The LEDA <TT>GRAPH</TT> is for directed graphs, so
- we choose <TT>directed_tag</TT> for the <TT>directed_category</TT>.
- The LEDA <TT>GRAPH</TT> does not automatically prevent the insertion
- of parallel edges, so we choose <TT>allow_parallel_edge_tag</TT> for
- the <TT>edge_parallel_category</TT>. The return type for the LEDA
- function <TT>number_of_nodes()</TT> and <TT>number_of_edges()</TT> is
- <TT>int</TT>, so we choose that type for the
- <TT>vertices_size_type</TT> and <tt>edges_size_type</tt> of the
- graph. The iterator types will be more complicated, so we leave that
- for later.
- <P>
- <PRE>
- namespace boost {
- template <class vtype, class etype>
- struct graph_traits< GRAPH<vtype,etype> > {
- typedef node vertex_descriptor;
- typedef edge edge_descriptor;
- // iterator typedefs...
- typedef directed_tag directed_category;
- typedef allow_parallel_edge_tag edge_parallel_category;
- typedef int vertices_size_type;
- typedef int edges_size_type;
- };
- } // namespace boost
- </PRE>
- <P>
- First we will write the <TT>source()</TT> and <TT>target()</TT>
- functions of the <a href="./IncidenceGraph.html">IncidenceGraph</a>
- concept, which is part of the <a
- href="./VertexListGraph.html">VertexListGraph</a> concept. We use the
- LEDA <TT>GRAPH</TT> type for the graph parameter, and use
- <TT>graph_traits</TT> to specify the edge parameter and the vertex
- return type. We could also just use the LEDA types <TT>node</TT> and
- <TT>edge</TT> here, but it is better practice to always use
- <TT>graph_traits</TT>. If there is a need to change the associated
- vertex or edge type, you will only need to do it in one place, inside
- the specialization of <TT>graph_traits</TT> instead of throughout your
- code. LEDA provides <TT>source()</TT> and <TT>target()</TT> functions,
- so we merely call them.
- <P>
- <PRE>
- namespace boost {
- template <class vtype, class etype>
- typename graph_traits< GRAPH<vtype,etype> >::vertex_descriptor
- source(
- typename graph_traits< GRAPH<vtype,etype> >::edge_descriptor e,
- const GRAPH<vtype,etype>& g)
- {
- return source(e);
- }
- template <class vtype, class etype>
- typename graph_traits< GRAPH<vtype,etype> >::vertex_descriptor
- target(
- typename graph_traits< GRAPH<vtype,etype> >::edge_descriptor e,
- const GRAPH<vtype,etype>& g)
- {
- return target(e);
- }
- } // namespace boost
- </PRE>
- <P>
- The next function from <a
- href="./IncidenceGraph.html">IncidenceGraph</a> that we need to
- implement is <TT>out_edges()</TT>. This function returns a pair of
- out-edge iterators. Since LEDA does not use STL-style iterators we
- need to implement some. There is a very handy boost utility for
- implementing iterators, called <TT>iterator_adaptor</TT>. Writing a
- standard conforming iterator classes is actually quite difficult,
- harder than you may think. With the <TT>iterator_adaptor</TT> class,
- you just implement a policy class and the rest is taken care of. The
- following code is the policy class for our out-edge iterator. In LEDA,
- the edge object itself is used like an iterator. It has functions
- <TT>Succ_Adj_Edge()</TT> and <TT>Pred_Adj_Edge()</TT> to move to the
- next and previous (successor and predecessor) edge. One gotcha in
- using the LEDA <TT>edge</TT> as an iterator comes up in the
- <TT>dereference()</TT> function, which merely returns the edge
- object. The dereference operator for standard compliant iterators must
- be a const member function, which is why the edge argument is
- const. However, the return type should not be const, hence the need
- for <TT>const_cast</TT>.
- <P>
- <PRE>
- namespace boost {
- struct out_edge_iterator_policies
- {
- static void increment(edge& e)
- { e = Succ_Adj_Edge(e,0); }
- static void decrement(edge& e)
- { e = Pred_Adj_Edge(e,0); }
- template <class Reference>
- static Reference dereference(type<Reference>, const edge& e)
- { return const_cast<Reference>(e); }
- static bool equal(const edge& x, const edge& y)
- { return x == y; }
- };
- } // namespace boost
- </PRE>
- <P>
- Now we go back to the <TT>graph_traits</TT> class, and use
- <TT>iterator_adaptor</TT> to fill in the
- <TT>out_edge_iterator</TT>. We use the <TT>iterator</TT> type
- to specify the associated types of the iterator, including iterator
- category and value type.
- <P>
- <PRE>
- namespace boost {
- template <class vtype, class etype>
- struct graph_traits< GRAPH<vtype,etype> > {
- // ...
- typedef iterator_adaptor<edge,
- out_edge_iterator_policies,
- iterator<std::bidirectional_iterator_tag,edge>
- > out_edge_iterator;
- // ...
- };
- } // namespace boost
- </PRE>
- <P>
- With the <TT>out_edge_iterator</TT> defined in <TT>graph_traits</TT> we
- are ready to define the <TT>out_edges()</TT> function. The following
- definition looks complicated at first glance, but it is really quite
- simple. The return type should be a pair of out-edge iterators, so we
- use <TT>std::pair</TT> and then <TT>graph_traits</TT> to access the
- out-edge iterator types. In the body of the function we construct the
- out-edge iterators by passing in the first adjacenct edge for the
- begin iterator, and 0 for the end iterator (which is used in LEDA as
- the end sentinel). The 0 argument to <TT>First_Adj_Edge</TT> tells
- LEDA we want out-edges (and not in-edges).
- <P>
- <PRE>
- namespace boost {
- template <class vtype, class etype>
- inline std::pair<
- typename graph_traits< GRAPH<vtype,etype> >::out_edge_iterator,
- typename graph_traits< GRAPH<vtype,etype> >::out_edge_iterator >
- out_edges(
- typename graph_traits< GRAPH<vtype,etype> >::vertex_descriptor u,
- const GRAPH<vtype,etype>& g)
- {
- typedef typename graph_traits< GRAPH<vtype,etype> >
- ::out_edge_iterator Iter;
- return std::make_pair( Iter(First_Adj_Edge(u,0)), Iter(0) );
- }
- } // namespace boost
- </PRE>
- <P>
- The rest of the iterator types and interface functions are constructed
- using the same techniques as above. The complete code for the LEDA
- wrapper interface is in <a
- href="../../../boost/graph/leda_graph.hpp"><TT>boost/graph/leda_graph.hpp</TT></a>. In
- the following code we use the BGL concept checks to make sure that we
- correctly implemented the BGL interface. These checks do not test the
- run-time behaviour of the implementation; that is tested in <a
- href="../test/graph.cpp"><TT>test/graph.cpp</TT></a>.
- <P>
- <PRE>
- #include <boost/graph/graph_concepts.hpp>
- #include <boost/graph/leda_graph.hpp>
- int
- main(int,char*[])
- {
- typedef GRAPH<int,int> Graph;
- BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> ));
- BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<Graph> ));
- BOOST_CONCEPT_ASSERT(( MutableGraphConcept<Graph> ));
- return 0;
- }
- </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>)<br>
- <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>
- <A HREF="https://homes.cs.washington.edu/~al75">Andrew Lumsdaine</A>,
- Indiana University (<A
- HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
- </TD></TR></TABLE>
- </BODY>
- </HTML>
|