jackb
Reputation: 704
On Converting Existing Graphs to BGL
I tried to follow the guidelines concerning the implementation of the graph traits for accessing the vertex/edge data, as well as defining iterators for scanning the graph, but this tutorial lacks the description concerning the property maps that are declared in this other full implementation (e.g., I am stuck at understanding the whole codebase as in the example provided down below, but I'm wondering how the remainder works for making the BLG graph algorithms work!). In other words, which are precisely the property maps as outlined here that guarantee me that I could run all the algorithms from the Boost Graph Library? Thanks
//=======================================================================
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
// Copyright 2004 The Trustees of Indiana University.
// Copyright 2007 University of Karlsruhe
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Douglas Gregor,
// Jens Mueller
//
// 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)
//=======================================================================
#ifndef BOOST_GRAPH_LEDA_HPP
#define BOOST_GRAPH_LEDA_HPP
#include <boost/config.hpp>
#include <boost/iterator/iterator_facade.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/properties.hpp>
#include <LEDA/graph/graph.h>
#include <LEDA/graph/node_array.h>
#include <LEDA/graph/node_map.h>
// The functions and classes in this file allows the user to
// treat a LEDA GRAPH object as a boost graph "as is". No
// wrapper is needed for the GRAPH object.
// Warning: this implementation relies on partial specialization
// for the graph_traits class (so it won't compile with Visual C++)
// Warning: this implementation is in alpha and has not been tested
namespace boost
{
struct leda_graph_traversal_category : public virtual bidirectional_graph_tag,
public virtual adjacency_graph_tag,
public virtual vertex_list_graph_tag
{
};
template < class vtype, class etype >
struct graph_traits< leda::GRAPH< vtype, etype > >
{
typedef leda::node vertex_descriptor;
typedef leda::edge edge_descriptor;
class adjacency_iterator
: public iterator_facade< adjacency_iterator, leda::node,
bidirectional_traversal_tag, leda::node, const leda::node* >
{
public:
adjacency_iterator(
leda::node node = 0, const leda::GRAPH< vtype, etype >* g = 0)
: base(node), g(g)
{
}
private:
leda::node dereference() const { return leda::target(base); }
bool equal(const adjacency_iterator& other) const
{
return base == other.base;
}
void increment() { base = g->adj_succ(base); }
void decrement() { base = g->adj_pred(base); }
leda::edge base;
const leda::GRAPH< vtype, etype >* g;
friend class iterator_core_access;
};
class out_edge_iterator
: public iterator_facade< out_edge_iterator, leda::edge,
bidirectional_traversal_tag, const leda::edge&, const leda::edge* >
{
public:
out_edge_iterator(
leda::node node = 0, const leda::GRAPH< vtype, etype >* g = 0)
: base(node), g(g)
{
}
private:
const leda::edge& dereference() const { return base; }
bool equal(const out_edge_iterator& other) const
{
return base == other.base;
}
void increment() { base = g->adj_succ(base); }
void decrement() { base = g->adj_pred(base); }
leda::edge base;
const leda::GRAPH< vtype, etype >* g;
friend class iterator_core_access;
};
class in_edge_iterator
: public iterator_facade< in_edge_iterator, leda::edge,
bidirectional_traversal_tag, const leda::edge&, const leda::edge* >
{
public:
in_edge_iterator(
leda::node node = 0, const leda::GRAPH< vtype, etype >* g = 0)
: base(node), g(g)
{
}
private:
const leda::edge& dereference() const { return base; }
bool equal(const in_edge_iterator& other) const
{
return base == other.base;
}
void increment() { base = g->in_succ(base); }
void decrement() { base = g->in_pred(base); }
leda::edge base;
const leda::GRAPH< vtype, etype >* g;
friend class iterator_core_access;
};
class vertex_iterator
: public iterator_facade< vertex_iterator, leda::node,
bidirectional_traversal_tag, const leda::node&, const leda::node* >
{
public:
vertex_iterator(
leda::node node = 0, const leda::GRAPH< vtype, etype >* g = 0)
: base(node), g(g)
{
}
private:
const leda::node& dereference() const { return base; }
bool equal(const vertex_iterator& other) const
{
return base == other.base;
}
void increment() { base = g->succ_node(base); }
void decrement() { base = g->pred_node(base); }
leda::node base;
const leda::GRAPH< vtype, etype >* g;
friend class iterator_core_access;
};
class edge_iterator
: public iterator_facade< edge_iterator, leda::edge,
bidirectional_traversal_tag, const leda::edge&, const leda::edge* >
{
public:
edge_iterator(
leda::edge edge = 0, const leda::GRAPH< vtype, etype >* g = 0)
: base(edge), g(g)
{
}
private:
const leda::edge& dereference() const { return base; }
bool equal(const edge_iterator& other) const
{
return base == other.base;
}
void increment() { base = g->succ_edge(base); }
void decrement() { base = g->pred_edge(base); }
leda::node base;
const leda::GRAPH< vtype, etype >* g;
friend class iterator_core_access;
};
typedef directed_tag directed_category;
typedef allow_parallel_edge_tag edge_parallel_category; // not sure here
typedef leda_graph_traversal_category traversal_category;
typedef int vertices_size_type;
typedef int edges_size_type;
typedef int degree_size_type;
};
template <> struct graph_traits< leda::graph >
{
typedef leda::node vertex_descriptor;
typedef leda::edge edge_descriptor;
class adjacency_iterator
: public iterator_facade< adjacency_iterator, leda::node,
bidirectional_traversal_tag, leda::node, const leda::node* >
{
public:
adjacency_iterator(leda::edge edge = 0, const leda::graph* g = 0)
: base(edge), g(g)
{
}
private:
leda::node dereference() const { return leda::target(base); }
bool equal(const adjacency_iterator& other) const
{
return base == other.base;
}
void increment() { base = g->adj_succ(base); }
void decrement() { base = g->adj_pred(base); }
leda::edge base;
const leda::graph* g;
friend class iterator_core_access;
};
class out_edge_iterator
: public iterator_facade< out_edge_iterator, leda::edge,
bidirectional_traversal_tag, const leda::edge&, const leda::edge* >
{
public:
out_edge_iterator(leda::edge edge = 0, const leda::graph* g = 0)
: base(edge), g(g)
{
}
private:
const leda::edge& dereference() const { return base; }
bool equal(const out_edge_iterator& other) const
{
return base == other.base;
}
void increment() { base = g->adj_succ(base); }
void decrement() { base = g->adj_pred(base); }
leda::edge base;
const leda::graph* g;
friend class iterator_core_access;
};
class in_edge_iterator
: public iterator_facade< in_edge_iterator, leda::edge,
bidirectional_traversal_tag, const leda::edge&, const leda::edge* >
{
public:
in_edge_iterator(leda::edge edge = 0, const leda::graph* g = 0)
: base(edge), g(g)
{
}
private:
const leda::edge& dereference() const { return base; }
bool equal(const in_edge_iterator& other) const
{
return base == other.base;
}
void increment() { base = g->in_succ(base); }
void decrement() { base = g->in_pred(base); }
leda::edge base;
const leda::graph* g;
friend class iterator_core_access;
};
class vertex_iterator
: public iterator_facade< vertex_iterator, leda::node,
bidirectional_traversal_tag, const leda::node&, const leda::node* >
{
public:
vertex_iterator(leda::node node = 0, const leda::graph* g = 0)
: base(node), g(g)
{
}
private:
const leda::node& dereference() const { return base; }
bool equal(const vertex_iterator& other) const
{
return base == other.base;
}
void increment() { base = g->succ_node(base); }
void decrement() { base = g->pred_node(base); }
leda::node base;
const leda::graph* g;
friend class iterator_core_access;
};
class edge_iterator
: public iterator_facade< edge_iterator, leda::edge,
bidirectional_traversal_tag, const leda::edge&, const leda::edge* >
{
public:
edge_iterator(leda::edge edge = 0, const leda::graph* g = 0)
: base(edge), g(g)
{
}
private:
const leda::edge& dereference() const { return base; }
bool equal(const edge_iterator& other) const
{
return base == other.base;
}
void increment() { base = g->succ_edge(base); }
void decrement() { base = g->pred_edge(base); }
leda::edge base;
const leda::graph* g;
friend class iterator_core_access;
};
typedef directed_tag directed_category;
typedef allow_parallel_edge_tag edge_parallel_category; // not sure here
typedef leda_graph_traversal_category traversal_category;
typedef int vertices_size_type;
typedef int edges_size_type;
typedef int degree_size_type;
};
} // namespace boost
namespace boost
{
//===========================================================================
// functions for GRAPH<vtype,etype>
template < class vtype, class etype >
typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor source(
typename graph_traits< leda::GRAPH< vtype, etype > >::edge_descriptor e,
const leda::GRAPH< vtype, etype >& g)
{
return source(e);
}
template < class vtype, class etype >
typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor target(
typename graph_traits< leda::GRAPH< vtype, etype > >::edge_descriptor e,
const leda::GRAPH< vtype, etype >& g)
{
return target(e);
}
template < class vtype, class etype >
inline std::pair<
typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_iterator,
typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_iterator >
vertices(const leda::GRAPH< vtype, etype >& g)
{
typedef
typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_iterator
Iter;
return std::make_pair(Iter(g.first_node(), &g), Iter(0, &g));
}
template < class vtype, class etype >
inline std::pair<
typename graph_traits< leda::GRAPH< vtype, etype > >::edge_iterator,
typename graph_traits< leda::GRAPH< vtype, etype > >::edge_iterator >
edges(const leda::GRAPH< vtype, etype >& g)
{
typedef typename graph_traits< leda::GRAPH< vtype, etype > >::edge_iterator
Iter;
return std::make_pair(Iter(g.first_edge(), &g), Iter(0, &g));
}
template < class vtype, class etype >
inline std::pair<
typename graph_traits< leda::GRAPH< vtype, etype > >::out_edge_iterator,
typename graph_traits< leda::GRAPH< vtype, etype > >::out_edge_iterator >
out_edges(
typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u,
const leda::GRAPH< vtype, etype >& g)
{
typedef
typename graph_traits< leda::GRAPH< vtype, etype > >::out_edge_iterator
Iter;
return std::make_pair(Iter(g.first_adj_edge(u, 0), &g), Iter(0, &g));
}
template < class vtype, class etype >
inline std::pair<
typename graph_traits< leda::GRAPH< vtype, etype > >::in_edge_iterator,
typename graph_traits< leda::GRAPH< vtype, etype > >::in_edge_iterator >
in_edges(
typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u,
const leda::GRAPH< vtype, etype >& g)
{
typedef
typename graph_traits< leda::GRAPH< vtype, etype > >::in_edge_iterator
Iter;
return std::make_pair(Iter(g.first_adj_edge(u, 1), &g), Iter(0, &g));
}
template < class vtype, class etype >
inline std::pair<
typename graph_traits< leda::GRAPH< vtype, etype > >::adjacency_iterator,
typename graph_traits< leda::GRAPH< vtype, etype > >::adjacency_iterator >
adjacent_vertices(
typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u,
const leda::GRAPH< vtype, etype >& g)
{
typedef
typename graph_traits< leda::GRAPH< vtype, etype > >::adjacency_iterator
Iter;
return std::make_pair(Iter(g.first_adj_edge(u, 0), &g), Iter(0, &g));
}
template < class vtype, class etype >
typename graph_traits< leda::GRAPH< vtype, etype > >::vertices_size_type
num_vertices(const leda::GRAPH< vtype, etype >& g)
{
return g.number_of_nodes();
}
template < class vtype, class etype >
typename graph_traits< leda::GRAPH< vtype, etype > >::edges_size_type num_edges(
const leda::GRAPH< vtype, etype >& g)
{
return g.number_of_edges();
}
template < class vtype, class etype >
typename graph_traits< leda::GRAPH< vtype, etype > >::degree_size_type
out_degree(
typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u,
const leda::GRAPH< vtype, etype >& g)
{
return g.outdeg(u);
}
template < class vtype, class etype >
typename graph_traits< leda::GRAPH< vtype, etype > >::degree_size_type
in_degree(
typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u,
const leda::GRAPH< vtype, etype >& g)
{
return g.indeg(u);
}
template < class vtype, class etype >
typename graph_traits< leda::GRAPH< vtype, etype > >::degree_size_type degree(
typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u,
const leda::GRAPH< vtype, etype >& g)
{
return g.outdeg(u) + g.indeg(u);
}
template < class vtype, class etype >
typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor
add_vertex(leda::GRAPH< vtype, etype >& g)
{
return g.new_node();
}
template < class vtype, class etype >
typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor
add_vertex(const vtype& vp, leda::GRAPH< vtype, etype >& g)
{
return g.new_node(vp);
}
template < class vtype, class etype >
void clear_vertex(
typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u,
leda::GRAPH< vtype, etype >& g)
{
typename graph_traits< leda::GRAPH< vtype, etype > >::out_edge_iterator ei,
ei_end;
for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ei++)
remove_edge(*ei);
typename graph_traits< leda::GRAPH< vtype, etype > >::in_edge_iterator iei,
iei_end;
for (boost::tie(iei, iei_end) = in_edges(u, g); iei != iei_end; iei++)
remove_edge(*iei);
}
template < class vtype, class etype >
void remove_vertex(
typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u,
leda::GRAPH< vtype, etype >& g)
{
g.del_node(u);
}
template < class vtype, class etype >
std::pair<
typename graph_traits< leda::GRAPH< vtype, etype > >::edge_descriptor,
bool >
add_edge(
typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u,
typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor v,
leda::GRAPH< vtype, etype >& g)
{
return std::make_pair(g.new_edge(u, v), true);
}
template < class vtype, class etype >
std::pair<
typename graph_traits< leda::GRAPH< vtype, etype > >::edge_descriptor,
bool >
add_edge(
typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u,
typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor v,
const etype& et, leda::GRAPH< vtype, etype >& g)
{
return std::make_pair(g.new_edge(u, v, et), true);
}
template < class vtype, class etype >
void remove_edge(
typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u,
typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor v,
leda::GRAPH< vtype, etype >& g)
{
typename graph_traits< leda::GRAPH< vtype, etype > >::out_edge_iterator i,
iend;
for (boost::tie(i, iend) = out_edges(u, g); i != iend; ++i)
if (target(*i, g) == v)
g.del_edge(*i);
}
template < class vtype, class etype >
void remove_edge(
typename graph_traits< leda::GRAPH< vtype, etype > >::edge_descriptor e,
leda::GRAPH< vtype, etype >& g)
{
g.del_edge(e);
}
//===========================================================================
// functions for graph (non-templated version)
graph_traits< leda::graph >::vertex_descriptor source(
graph_traits< leda::graph >::edge_descriptor e, const leda::graph& g)
{
return source(e);
}
graph_traits< leda::graph >::vertex_descriptor target(
graph_traits< leda::graph >::edge_descriptor e, const leda::graph& g)
{
return target(e);
}
inline std::pair< graph_traits< leda::graph >::vertex_iterator,
graph_traits< leda::graph >::vertex_iterator >
vertices(const leda::graph& g)
{
typedef graph_traits< leda::graph >::vertex_iterator Iter;
return std::make_pair(Iter(g.first_node(), &g), Iter(0, &g));
}
inline std::pair< graph_traits< leda::graph >::edge_iterator,
graph_traits< leda::graph >::edge_iterator >
edges(const leda::graph& g)
{
typedef graph_traits< leda::graph >::edge_iterator Iter;
return std::make_pair(Iter(g.first_edge(), &g), Iter(0, &g));
}
inline std::pair< graph_traits< leda::graph >::out_edge_iterator,
graph_traits< leda::graph >::out_edge_iterator >
out_edges(
graph_traits< leda::graph >::vertex_descriptor u, const leda::graph& g)
{
typedef graph_traits< leda::graph >::out_edge_iterator Iter;
return std::make_pair(Iter(g.first_adj_edge(u), &g), Iter(0, &g));
}
inline std::pair< graph_traits< leda::graph >::in_edge_iterator,
graph_traits< leda::graph >::in_edge_iterator >
in_edges(graph_traits< leda::graph >::vertex_descriptor u, const leda::graph& g)
{
typedef graph_traits< leda::graph >::in_edge_iterator Iter;
return std::make_pair(Iter(g.first_in_edge(u), &g), Iter(0, &g));
}
inline std::pair< graph_traits< leda::graph >::adjacency_iterator,
graph_traits< leda::graph >::adjacency_iterator >
adjacent_vertices(
graph_traits< leda::graph >::vertex_descriptor u, const leda::graph& g)
{
typedef graph_traits< leda::graph >::adjacency_iterator Iter;
return std::make_pair(Iter(g.first_adj_edge(u), &g), Iter(0, &g));
}
graph_traits< leda::graph >::vertices_size_type num_vertices(
const leda::graph& g)
{
return g.number_of_nodes();
}
graph_traits< leda::graph >::edges_size_type num_edges(const leda::graph& g)
{
return g.number_of_edges();
}
graph_traits< leda::graph >::degree_size_type out_degree(
graph_traits< leda::graph >::vertex_descriptor u, const leda::graph& g)
{
return g.outdeg(u);
}
graph_traits< leda::graph >::degree_size_type in_degree(
graph_traits< leda::graph >::vertex_descriptor u, const leda::graph& g)
{
return g.indeg(u);
}
graph_traits< leda::graph >::degree_size_type degree(
graph_traits< leda::graph >::vertex_descriptor u, const leda::graph& g)
{
return g.outdeg(u) + g.indeg(u);
}
graph_traits< leda::graph >::vertex_descriptor add_vertex(leda::graph& g)
{
return g.new_node();
}
void remove_edge(graph_traits< leda::graph >::vertex_descriptor u,
graph_traits< leda::graph >::vertex_descriptor v, leda::graph& g)
{
graph_traits< leda::graph >::out_edge_iterator i, iend;
for (boost::tie(i, iend) = out_edges(u, g); i != iend; ++i)
if (target(*i, g) == v)
g.del_edge(*i);
}
void remove_edge(graph_traits< leda::graph >::edge_descriptor e, leda::graph& g)
{
g.del_edge(e);
}
void clear_vertex(
graph_traits< leda::graph >::vertex_descriptor u, leda::graph& g)
{
graph_traits< leda::graph >::out_edge_iterator ei, ei_end;
for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ei++)
remove_edge(*ei, g);
graph_traits< leda::graph >::in_edge_iterator iei, iei_end;
for (boost::tie(iei, iei_end) = in_edges(u, g); iei != iei_end; iei++)
remove_edge(*iei, g);
}
void remove_vertex(
graph_traits< leda::graph >::vertex_descriptor u, leda::graph& g)
{
g.del_node(u);
}
std::pair< graph_traits< leda::graph >::edge_descriptor, bool > add_edge(
graph_traits< leda::graph >::vertex_descriptor u,
graph_traits< leda::graph >::vertex_descriptor v, leda::graph& g)
{
return std::make_pair(g.new_edge(u, v), true);
}
#endif // BOOST_GRAPH_LEDA_HPP
Upvotes: 2
Views: 90
Answers (1)
sehe
Reputation: 392883
In other words, which are precisely the property maps as outlined here that guarantee me that I could run all the algorithms from the Boost Graph Library?
That's asking the wrong question. One of the key design choices of the BGL (much like the STL) is separation of data structures and algorithms. The set of properties required by algorithm varies by algorithm (and even by usage of the same algorithm), and can be satisfied in many ways generically.
Which property map(s) are required is documented with the algorithm. This, by the way, in addition to which concept the graph model must satisfy.
I do know that the documentation can be slightly out of date¹ and more specifically, life with c++14+ can be significantly easier than in the documentation examples.
In case it helps, here are "modern" examples on adapting your own datastructures for use with BGL:
- What is needed to use BGL algorithms on existing data structures ( edges and vertices as vector<Object *>)?
- Interestingly, someone later ran into precisely your question about additional requirements for a specific algorithm. In this answer: What is required for a custom BGL graph to work with topological sort? I show not only how to figure out what requirements have to be satisfied but also how to achieve that.
I invite you to read these, and apply them to your particular situation. If you get stuck on something along the way you'll have a new (better) question well-suited to ask on StackOverflow.
¹ like with Boost Geometry, which has a similar design philosophy as BGL, but where this is much bigger problem than with BGL
Upvotes: 2
Related Questions
- Using C++ Boost's Graph Library
- What is needed to use BGL algorithms on existing data structures ( edges and vertices as vector<Object *>)?
- Some questions about the C++ boost graph library
- BGL custom graph connected_components
- Simple Distributed Graph BGL Example
- On C++ Boost Graph Creation With Bundled Properties
- Create undirected graph by boost graph same as the input
- drawing custom BGL graph with graphviz
- Output BGL Edge Weights
- How to use a BGL directed graph as an undirected one (for use in layout algorithm)?