[ceph.git] / ceph / src / boost / libs / graph / doc / leda_conversion.html

<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&nbsp;[<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="http://www.mpi-sb.mpg.de/LEDA/MANUAL/bgraph.html"><TT>GRAPH</TT></a>
class&nbsp;[<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 &lt;class vtype, class etype&gt;
  struct graph_traits&lt; GRAPH&lt;vtype,etype&gt; &gt; {
    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 &lt;class vtype, class etype&gt;
  typename graph_traits&lt; GRAPH&lt;vtype,etype&gt; &gt;::vertex_descriptor
  source(
    typename graph_traits&lt; GRAPH&lt;vtype,etype&gt; &gt;::edge_descriptor e,
    const GRAPH&lt;vtype,etype&gt;&amp; g)
  {
    return source(e);
  }

  template &lt;class vtype, class etype&gt;
  typename graph_traits&lt; GRAPH&lt;vtype,etype&gt; &gt;::vertex_descriptor
  target(
    typename graph_traits&lt; GRAPH&lt;vtype,etype&gt; &gt;::edge_descriptor e,
    const GRAPH&lt;vtype,etype&gt;&amp; 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&amp; e)
    { e = Succ_Adj_Edge(e,0); }

    static void decrement(edge&amp; e)
    { e = Pred_Adj_Edge(e,0); }

    template &lt;class Reference&gt;
    static Reference dereference(type&lt;Reference&gt;, const edge&amp; e)
    { return const_cast&lt;Reference&gt;(e); }

    static bool equal(const edge&amp; x, const edge&amp; 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 &lt;class vtype, class etype&gt;
    struct graph_traits&lt; GRAPH&lt;vtype,etype&gt; &gt; {
      // ...
      typedef iterator_adaptor&lt;edge,
        out_edge_iterator_policies, 
        iterator&lt;std::bidirectional_iterator_tag,edge&gt;
      &gt; 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 &lt;class vtype, class etype&gt;
  inline std::pair&lt;
    typename graph_traits&lt; GRAPH&lt;vtype,etype&gt; &gt;::out_edge_iterator,
    typename graph_traits&lt; GRAPH&lt;vtype,etype&gt; &gt;::out_edge_iterator &gt;  
  out_edges(
    typename graph_traits&lt; GRAPH&lt;vtype,etype&gt; &gt;::vertex_descriptor u, 
    const GRAPH&lt;vtype,etype&gt;&amp; g)
  {
    typedef typename graph_traits&lt; GRAPH&lt;vtype,etype&gt; &gt;
      ::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 &lt;boost/graph/graph_concepts.hpp&gt;
  #include &lt;boost/graph/leda_graph.hpp&gt;

  int
  main(int,char*[])
  {
    typedef GRAPH&lt;int,int&gt; Graph;
    BOOST_CONCEPT_ASSERT(( VertexListGraphConcept&lt;Graph&gt; ));
    BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept&lt;Graph&gt; ));
    BOOST_CONCEPT_ASSERT(( MutableGraphConcept&lt;Graph&gt; ));
    return 0;
  }
</PRE>


<br>
<HR>
<TABLE>
<TR valign=top>
<TD nowrap>Copyright &copy; 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="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>,
Indiana University (<A
HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
</TD></TR></TABLE>

</BODY>
</HTML>
Commit	Line	Data
7c673cae FG	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 [<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 [<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 <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>
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 <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>
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& 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>
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 <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>
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 <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>
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 <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>,
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>