Loading...
Searching...
No Matches
graphAlgorithms.h
Go to the documentation of this file.
#ifndef BALL_DATATYPE_GRAPH_GRAPHALGORITHMS_H
#define BALL_DATATYPE_GRAPH_GRAPHALGORITHMS_H
#ifndef BALL_COMMON_GLOBAL_H
# include <BALL/COMMON/global.h>
#endif
#ifndef BALL_COMMON_EXCEPTION_H
# include <BALL/COMMON/exception.h>
#endif
#ifndef BALL_DATATYPE_STRING_H
# include <BALL/DATATYPE/string.h>
#endif
#include <boost/graph/properties.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/tree_traits.hpp>
#include <boost/graph/iteration_macros.hpp>
#include <boost/graph/copy.hpp>
#include <boost/shared_ptr.hpp>
#include <iostream>
namespace boost
{
enum vertex_atom_ptr_t { vertex_atom_ptr };
enum vertex_orig_ptr_t { vertex_orig_ptr };
enum edge_bond_ptr_t { edge_bond_ptr };
enum edge_orig_ptr_t { edge_orig_ptr };
BOOST_INSTALL_PROPERTY(vertex, atom_ptr);
BOOST_INSTALL_PROPERTY(vertex, orig_ptr);
BOOST_INSTALL_PROPERTY(edge, bond_ptr);
BOOST_INSTALL_PROPERTY(edge, orig_ptr);
}
namespace BALL
{
namespace GRAPH
{
template <class UndirectedGraph> class UndoEliminateOperation;
class BALL_EXPORT IllegalStateException
: public Exception::GeneralException
{
public:
IllegalStateException(const char* file, int line, String message);
};
class BALL_EXPORT UnconnectedGraphException
: public Exception::GeneralException
{
public:
UnconnectedGraphException(const char * file, int line);
UnconnectedGraphException(const char * file, int line, BALL::String computation);
};
template <class Graph>
class GraphTraits
{
public:
typedef typename boost::graph_traits<Graph>::vertex_descriptor VertexType;
typedef typename boost::graph_traits<Graph>::vertex_iterator VertexIterator;
typedef typename boost::graph_traits<Graph>::adjacency_iterator NeighbourIterator;
typedef typename boost::graph_traits<Graph>::edge_descriptor EdgeType;
// this defines an editable version of the graph, i.e., a graph with list-based storage types
// that has property maps on the edges and vertices pointing to edges and vertices of an instance
// of the original graph type
typedef boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS,
boost::property<boost::vertex_orig_ptr_t, VertexType,
boost::property<boost::vertex_index_t, int> >,
boost::property<boost::edge_orig_ptr_t, EdgeType> > EditableGraph;
};
template <typename Graph1, typename Graph2>
struct EditableEdgeCopier
{
EditableEdgeCopier(const Graph1& /*g1*/, Graph2& g2)
: edge_orig_map(get(boost::edge_orig_ptr, g2))
{}
template <typename Edge1, typename Edge2>
void operator()(const Edge1& e1, Edge2& e2) const
{
put(edge_orig_map, e2, e1);
}
mutable typename boost::property_map<Graph2, boost::edge_orig_ptr_t>::type edge_orig_map;
};
template <typename Graph1, typename Graph2>
inline EditableEdgeCopier<Graph1,Graph2>
makeEditableEdgeCopier(const Graph1& g1, Graph2& g2)
{
return EditableEdgeCopier<Graph1,Graph2>(g1, g2);
}
template <typename Graph1, typename Graph2>
struct EditableVertexCopier
{
EditableVertexCopier(const Graph1& g1_, Graph2& g2_)
: vertex_orig_map(get(boost::vertex_orig_ptr, g2_)),
g1(g1_),
g2(g2_)
{}
template <typename Vertex1, typename Vertex2>
void operator()(const Vertex1& v1, Vertex2& v2) const
{
boost::put(vertex_orig_map, v2, v1);
boost::put(boost::vertex_index, g2, v2, boost::get(boost::vertex_index, g1, v1));
}
mutable typename boost::property_map<Graph2, boost::vertex_orig_ptr_t>::type vertex_orig_map;
Graph1 const& g1;
Graph2& g2;
};
template <typename Graph1, typename Graph2>
inline EditableVertexCopier<Graph1,Graph2>
makeEditableVertexCopier(const Graph1& g1, Graph2& g2)
{
return EditableVertexCopier<Graph1,Graph2>(g1, g2);
}
template <class UndirectedGraph>
void eliminateVertex(typename GraphTraits<UndirectedGraph>::VertexType& vertex, UndirectedGraph& graph)
{
typename GraphTraits<UndirectedGraph>::NeighbourIterator ai, bi, ai_end;
for (boost::tie(ai, ai_end) = adjacent_vertices(vertex, graph); ai != ai_end; ++ai)
{
bi = ai; ++bi;
for (; bi != ai_end; ++bi)
if (*bi != *ai && !boost::edge(*ai, *bi, graph).second)
boost::add_edge(*ai, *bi, graph);
}
boost::clear_vertex(vertex, graph);
boost::remove_vertex(vertex, graph);
}
template <class UndirectedGraph>
UndoEliminateOperation<UndirectedGraph> eliminateVertexUndoable(typename GraphTraits<UndirectedGraph>::VertexType const& vertex,
UndirectedGraph& graph)
{
typename GraphTraits<UndirectedGraph>::NeighbourIterator ai, bi, ai_end;
UndoEliminateOperation<UndirectedGraph> result(graph, vertex);
for (boost::tie(ai, ai_end) = adjacent_vertices(vertex, graph); ai != ai_end; ++ai)
{
result.getNeighbours().push_back(boost::get(boost::vertex_index, graph, *ai));
result.getEdgeProperties().push_back(boost::get(boost::edge_all_t(), graph, boost::edge(vertex, *ai, graph).first));
bi = ai; ++bi;
for (; bi != ai_end; ++bi)
{
if (!boost::edge(*ai, *bi, graph).second)
{
boost::add_edge(*ai, *bi, graph);
result.getEdges().push_back(std::make_pair(boost::get(boost::vertex_index, graph, *ai),
boost::get(boost::vertex_index, graph, *bi)));
}
}
}
boost::clear_vertex(vertex, graph);
boost::remove_vertex(vertex, graph);
return result;
}
template <class UndirectedGraph>
class UndoEliminateOperation
{
public:
typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor VertexType;
typedef typename boost::graph_traits<UndirectedGraph>::edge_descriptor EdgeType;
typedef typename boost::graph_traits<UndirectedGraph>::adjacency_iterator NeighbourIterator;
typedef typename boost::property_traits<typename boost::property_map<UndirectedGraph,
boost::vertex_all_t>::type>::value_type VertexProperties;
typedef typename boost::property_traits<typename boost::property_map<UndirectedGraph,
boost::edge_all_t>::type>::value_type EdgeProperties;
UndoEliminateOperation(UndirectedGraph& graph, VertexType const& a);
VertexType& getEliminatedVertex();
VertexType undo();
std::vector<std::pair<int, int> >& getEdges() { return edges_; }
std::vector<EdgeProperties>& getEdgeProperties() { return edge_properties_; }
std::vector<int>& getNeighbours() { return neighbours_; }
protected:
UndirectedGraph* graph;
VertexType vertex;
VertexProperties vertex_properties_;
std::vector<std::pair<int, int> > edges_;
std::vector<EdgeProperties> edge_properties_;
std::vector<int> neighbours_;
bool applied;
};
template <class UndirectedGraph>
UndoEliminateOperation<UndirectedGraph>::UndoEliminateOperation(UndirectedGraph& ugraph, VertexType const& a)
: graph(&ugraph),
vertex(a),
edges_(),
neighbours_(),
applied(true)
{
vertex_properties_ = boost::get(boost::vertex_all_t(), ugraph, a);
}
template <class UndirectedGraph>
typename UndoEliminateOperation<UndirectedGraph>::VertexType&
UndoEliminateOperation<UndirectedGraph>::getEliminatedVertex()
{
return vertex;
}
template <class UndirectedGraph>
typename UndoEliminateOperation<UndirectedGraph>::VertexType UndoEliminateOperation<UndirectedGraph>::undo()
{
if (!applied)
{
throw IllegalStateException(__FILE__, __LINE__, "Can't undo an elimination twice");
}
applied = false;
VertexType v = boost::add_vertex(vertex_properties_, *graph);
std::map<int, VertexType> index_to_vertex;
BGL_FORALL_VERTICES_T(v, *graph, UndirectedGraph)
{
index_to_vertex[boost::get(boost::vertex_index, *graph, v)] = v;
}
for (Position i=0; i<neighbours_.size(); ++i)
{
boost::add_edge(v, index_to_vertex[neighbours_[i]], edge_properties_[i], *graph);
}
for (Position i=0; i<edges_.size(); ++i)
{
boost::remove_edge(index_to_vertex[edges_[i].first], index_to_vertex[edges_[i].second], *graph);
}
return v;
}
template <class UndirectedGraph>
void deepCopy(const UndirectedGraph& src, UndirectedGraph& target)
{
typedef std::map<typename boost::graph_traits<UndirectedGraph>::vertex_descriptor,int> VertexIndexMap;
typedef boost::associative_property_map<VertexIndexMap> VertexIndexPropertyMap;
VertexIndexMap vertex_map;
VertexIndexPropertyMap vertex_property_map(vertex_map);
typename boost::graph_traits<UndirectedGraph>::vertices_size_type count = 0;
typename boost::graph_traits<UndirectedGraph>::vertex_iterator vi, vend;
for (boost::tie(vi, vend) = boost::vertices(src); vi != vend; ++vi)
vertex_map[*vi] = count++;
boost::copy_graph(src, target, vertex_index_map(vertex_property_map));
}
template <class Tree, class From, class To, class Functor>
class PostOrderFolding
{
public:
typedef typename Tree::children_iterator ChildrenIterator;
typedef typename std::vector<To>::iterator ArgumentIterator;
PostOrderFolding(Tree& tree, Functor& f)
: return_stack_(boost::shared_ptr<std::vector<To> >(new std::vector<To>())),
tree_(&tree),
f_(&f)
{
boost::traverse_tree(root(*tree_), *tree_, *this);
}
To getResult()
{
return *return_stack_->begin();
}
template <class Node>
void preorder(Node, Tree&)
{
}
template <class Node>
void inorder(Node, Tree&)
{
}
template <class Node>
void postorder(Node n, Tree& t)
{
ChildrenIterator c_i, c_end;
boost::tie(c_i, c_end) = children(n, t);
bool is_leaf = (c_i == c_end);
ArgumentIterator begin_arg = return_stack_->end();
ArgumentIterator end_arg = return_stack_->end();
if (!is_leaf)
{
for (; c_i != c_end; ++c_i)
{
--begin_arg;
}
}
To value = (*f_)(n, begin_arg, end_arg);
if (begin_arg != end_arg)
{
return_stack_->erase(begin_arg, end_arg);
}
return_stack_->push_back(value);
}
protected:
boost::shared_ptr<std::vector<To> > return_stack_;
Tree* tree_;
Functor* f_;
};
}
}
#endif // BALL_DATATYPE_GRAPH_GRAPHALGORITHMS_H
exception.h
global.h
BALL_EXPORT
#define BALL_EXPORT
Definition COMMON/global.h:50
BALL::Exception::GeneralException
Definition COMMON/exception.h:61
BALL::GRAPH::GraphTraits
Definition graphAlgorithms.h:75
BALL::GRAPH::GraphTraits::NeighbourIterator
boost::graph_traits< Graph >::adjacency_iterator NeighbourIterator
Definition graphAlgorithms.h:79
BALL::GRAPH::GraphTraits::VertexIterator
boost::graph_traits< Graph >::vertex_iterator VertexIterator
Definition graphAlgorithms.h:78
BALL::GRAPH::GraphTraits::VertexType
boost::graph_traits< Graph >::vertex_descriptor VertexType
Definition graphAlgorithms.h:77
BALL::GRAPH::GraphTraits::EditableGraph
boost::adjacency_list< boost::listS, boost::listS, boost::undirectedS, boost::property< boost::vertex_orig_ptr_t, VertexType, boost::property< boost::vertex_index_t, int > >, boost::property< boost::edge_orig_ptr_t, EdgeType > > EditableGraph
Definition graphAlgorithms.h:88
BALL::GRAPH::GraphTraits::EdgeType
boost::graph_traits< Graph >::edge_descriptor EdgeType
Definition graphAlgorithms.h:80
BALL::GRAPH::IllegalStateException
Definition graphAlgorithms.h:54
BALL::GRAPH::IllegalStateException::IllegalStateException
IllegalStateException(const char *file, int line, String message)
BALL::GRAPH::PostOrderFolding::ArgumentIterator
std::vector< To >::iterator ArgumentIterator
Definition graphAlgorithms.h:330
BALL::GRAPH::PostOrderFolding::preorder
void preorder(Node, Tree &)
Definition graphAlgorithms.h:346
BALL::GRAPH::PostOrderFolding::ChildrenIterator
Tree::children_iterator ChildrenIterator
Definition graphAlgorithms.h:328
BALL::GRAPH::PostOrderFolding::tree_
Tree * tree_
Definition graphAlgorithms.h:387
BALL::GRAPH::PostOrderFolding::inorder
void inorder(Node, Tree &)
Definition graphAlgorithms.h:351
BALL::GRAPH::PostOrderFolding::PostOrderFolding
PostOrderFolding(Tree &tree, Functor &f)
Definition graphAlgorithms.h:332
BALL::GRAPH::PostOrderFolding::f_
Functor * f_
Definition graphAlgorithms.h:388
BALL::GRAPH::PostOrderFolding::getResult
To getResult()
Definition graphAlgorithms.h:340
BALL::GRAPH::PostOrderFolding::return_stack_
boost::shared_ptr< std::vector< To > > return_stack_
Definition graphAlgorithms.h:385
BALL::GRAPH::PostOrderFolding::postorder
void postorder(Node n, Tree &t)
Definition graphAlgorithms.h:356
BALL::GRAPH::UnconnectedGraphException::UnconnectedGraphException
UnconnectedGraphException(const char *file, int line, BALL::String computation)
BALL::GRAPH::UnconnectedGraphException::UnconnectedGraphException
UnconnectedGraphException(const char *file, int line)
BALL::GRAPH::UndoEliminateOperation
Definition graphAlgorithms.h:215
BALL::GRAPH::UndoEliminateOperation::graph
UndirectedGraph * graph
Definition graphAlgorithms.h:248
BALL::GRAPH::UndoEliminateOperation::UndoEliminateOperation
UndoEliminateOperation(UndirectedGraph &graph, VertexType const &a)
Definition graphAlgorithms.h:258
BALL::GRAPH::UndoEliminateOperation::getEdgeProperties
std::vector< EdgeProperties > & getEdgeProperties()
Definition graphAlgorithms.h:244
BALL::GRAPH::UndoEliminateOperation::edge_properties_
std::vector< EdgeProperties > edge_properties_
Definition graphAlgorithms.h:252
BALL::GRAPH::UndoEliminateOperation::vertex_properties_
VertexProperties vertex_properties_
Definition graphAlgorithms.h:250
BALL::GRAPH::UndoEliminateOperation::EdgeType
boost::graph_traits< UndirectedGraph >::edge_descriptor EdgeType
Definition graphAlgorithms.h:218
BALL::GRAPH::UndoEliminateOperation::undo
VertexType undo()
Definition graphAlgorithms.h:276
BALL::GRAPH::UndoEliminateOperation::getEdges
std::vector< std::pair< int, int > > & getEdges()
Definition graphAlgorithms.h:243
BALL::GRAPH::UndoEliminateOperation::vertex
VertexType vertex
Definition graphAlgorithms.h:249
BALL::GRAPH::UndoEliminateOperation::NeighbourIterator
boost::graph_traits< UndirectedGraph >::adjacency_iterator NeighbourIterator
Definition graphAlgorithms.h:219
BALL::GRAPH::UndoEliminateOperation::VertexType
boost::graph_traits< UndirectedGraph >::vertex_descriptor VertexType
Definition graphAlgorithms.h:217
BALL::GRAPH::UndoEliminateOperation::getEliminatedVertex
VertexType & getEliminatedVertex()
Definition graphAlgorithms.h:270
BALL::GRAPH::UndoEliminateOperation::getNeighbours
std::vector< int > & getNeighbours()
Definition graphAlgorithms.h:245
BALL::GRAPH::UndoEliminateOperation::VertexProperties
boost::property_traits< typenameboost::property_map< UndirectedGraph, boost::vertex_all_t >::type >::value_type VertexProperties
Definition graphAlgorithms.h:222
BALL::GRAPH::UndoEliminateOperation::EdgeProperties
boost::property_traits< typenameboost::property_map< UndirectedGraph, boost::edge_all_t >::type >::value_type EdgeProperties
Definition graphAlgorithms.h:224
BALL::GRAPH::UndoEliminateOperation::applied
bool applied
Definition graphAlgorithms.h:254
BALL::GRAPH::UndoEliminateOperation::neighbours_
std::vector< int > neighbours_
Definition graphAlgorithms.h:253
BALL::GRAPH::UndoEliminateOperation::edges_
std::vector< std::pair< int, int > > edges_
Definition graphAlgorithms.h:251
BALL::String
Definition string.h:57
BALL::GRAPH
Definition graphAlgorithms.h:44
BALL::GRAPH::eliminateVertex
void eliminateVertex(typename GraphTraits< UndirectedGraph >::VertexType &vertex, UndirectedGraph &graph)
Definition graphAlgorithms.h:149
BALL::GRAPH::makeEditableVertexCopier
EditableVertexCopier< Graph1, Graph2 > makeEditableVertexCopier(const Graph1 &g1, Graph2 &g2)
Definition graphAlgorithms.h:138
BALL::GRAPH::makeEditableEdgeCopier
EditableEdgeCopier< Graph1, Graph2 > makeEditableEdgeCopier(const Graph1 &g1, Graph2 &g2)
Definition graphAlgorithms.h:110
BALL::GRAPH::eliminateVertexUndoable
UndoEliminateOperation< UndirectedGraph > eliminateVertexUndoable(typename GraphTraits< UndirectedGraph >::VertexType const &vertex, UndirectedGraph &graph)
Definition graphAlgorithms.h:174
BALL::GRAPH::deepCopy
void deepCopy(const UndirectedGraph &src, UndirectedGraph &target)
Definition graphAlgorithms.h:307
BALL
Definition constants.h:13
BALL::Position
BALL_SIZE_TYPE Position
Definition COMMON/global.h:140
boost
Definition graphAlgorithms.h:27
boost::vertex_orig_ptr_t
vertex_orig_ptr_t
Definition graphAlgorithms.h:29
boost::vertex_orig_ptr
@ vertex_orig_ptr
Definition graphAlgorithms.h:29
boost::edge_orig_ptr_t
edge_orig_ptr_t
Definition graphAlgorithms.h:32
boost::edge_orig_ptr
@ edge_orig_ptr
Definition graphAlgorithms.h:32
boost::vertex_atom_ptr_t
vertex_atom_ptr_t
Definition graphAlgorithms.h:28
boost::vertex_atom_ptr
@ vertex_atom_ptr
Definition graphAlgorithms.h:28
boost::edge_bond_ptr_t
edge_bond_ptr_t
Definition graphAlgorithms.h:31
boost::edge_bond_ptr
@ edge_bond_ptr
Definition graphAlgorithms.h:31
boost::BOOST_INSTALL_PROPERTY
BOOST_INSTALL_PROPERTY(vertex, atom_ptr)
std
STL namespace.
string.h
BALL::GRAPH::EditableEdgeCopier
Definition graphAlgorithms.h:94
BALL::GRAPH::EditableEdgeCopier::operator()
void operator()(const Edge1 &e1, Edge2 &e2) const
Definition graphAlgorithms.h:100
BALL::GRAPH::EditableEdgeCopier::EditableEdgeCopier
EditableEdgeCopier(const Graph1 &, Graph2 &g2)
Definition graphAlgorithms.h:95
BALL::GRAPH::EditableEdgeCopier::edge_orig_map
boost::property_map< Graph2, boost::edge_orig_ptr_t >::type edge_orig_map
Definition graphAlgorithms.h:105
BALL::GRAPH::EditableVertexCopier
Definition graphAlgorithms.h:117
BALL::GRAPH::EditableVertexCopier::g1
Graph1 const & g1
Definition graphAlgorithms.h:132
BALL::GRAPH::EditableVertexCopier::operator()
void operator()(const Vertex1 &v1, Vertex2 &v2) const
Definition graphAlgorithms.h:125
BALL::GRAPH::EditableVertexCopier::vertex_orig_map
boost::property_map< Graph2, boost::vertex_orig_ptr_t >::type vertex_orig_map
Definition graphAlgorithms.h:131
BALL::GRAPH::EditableVertexCopier::g2
Graph2 & g2
Definition graphAlgorithms.h:133
BALL::GRAPH::EditableVertexCopier::EditableVertexCopier
EditableVertexCopier(const Graph1 &g1_, Graph2 &g2_)
Definition graphAlgorithms.h:118