I'm currently working on a project that enumerates the k-best solutions of a dynamic program using a directed hypergraph framework. My current implementation (in Python) works well, but is fairly slow. The algorithm performs a number of tight loops and a fair bit of recursion. I really think that I could realize significant speed improvements using a C++ implementation. However, after a fair bit of searching, I was unable to find any libraries that provide hypergraph implementations in C++ (specifically directed hypergraphs -- but I was unable to find even libraries for undirected hypergraphs). Does anyone know of such a library? It seems there was a GSoC proposal to bring hypergraph support to boost a few years ago, but it looks like it didn't really pan out.
Is there a library that provides a (directed) hypergraph implementation in C++?
Asked Answered
en.wikipedia.org/wiki/Hypergraph for people like me who need to look it up –
Acoustic
wait, how can a hypergraph have a direction? "Direction" is only on the wiki in the section where edges can connect to other edges. –
Acoustic
A directed hypergraph differentiates the nodes that participate in a hyperedge. There is a single node designated as the "head" of the hyperedge and a set of nodes designated as the "tail". This is also sometimes commonly referred to as a forward hypergraph. –
Bolin
I don't know of a library, but you could roll your own.
After messing around with the code for three days, I finally got a hypermap to compile without warnings on MSVC10 and GCC(http://ideone.com/oj46o).
Declarations:
#include <map>
#include <functional>
#include <memory>
template<class V, class E=int, class PV = std::less<V>, class PE=std::less<E>, class A=std::allocator<V> >
// V is data type of vertex
// E is identifier of Edge
// PV is node sorting predicate
// PE is edge sorting predicate
// A is allocator
class hypergraph {
#if _MSC_VER <= 1600
typedef A sub_allocator;
#else
typedef std::scoped_allocator_adaptor<A> sub_allocator;
#endif
public:
class vertex;
class edge;
typedef std::map<V, vertex, PV, sub_allocator> vertexset;
typedef std::map<E, edge, PE, sub_allocator> edgeset;
typedef typename vertexset::iterator vertexiter;
typedef typename edgeset::iterator edgeiter;
typedef typename vertexset::const_iterator cvertexiter;
typedef typename edgeset::const_iterator cedgeiter;
typedef std::reference_wrapper<const V> rwv;
typedef std::reference_wrapper<const E> rwe;
typedef std::reference_wrapper<vertex> rwvertex;
typedef std::reference_wrapper<edge> rwedge;
typedef std::map<rwv, rwvertex, PV, sub_allocator> ivertexset;
typedef std::map<rwe, rwedge, PE, sub_allocator> iedgeset;
typedef typename ivertexset::iterator ivertexiter;
typedef typename iedgeset::iterator iedgeiter;
typedef typename ivertexset::const_iterator civertexiter;
typedef typename iedgeset::const_iterator ciedgeiter;
class vertex {
friend class hypergraph<V,E,PV,PE,A>;
iedgeset edges_;
vertex(const PE&, const sub_allocator&);/* so users can'V make their own vertices*/
public:
vertex(vertex&&);
vertex& operator=(vertex&&);
iedgeset& edges();
const iedgeset& edges() const;
};
class edge {
friend class hypergraph<V,E,PV,PE,A>;
ivertexset vertices_;
ivertexiter head_;
edge(const PV&, const sub_allocator&); /* so users can'V make their own edges*/
public:
edge(edge&&);
edge& operator=(edge&&);
void set_head(const V& v);
const V* get_head() const;
ivertexset& vertices();
const ivertexset& vertices() const;
};
hypergraph(const PV& vertexpred=PV(), const PE& edgepred=PE(), const A& alloc=A());
std::pair<vertexiter,bool> add_vertex(V v=V());
std::pair<edgeiter,bool> add_edge(E e=E());
vertexiter erase_vertex(const vertexiter& iter);
vertexiter erase_vertex(const V& rhs);
edgeiter erase_edge(const edgeiter& iter);
edgeiter erase_edge(const E& rhs);
void connect(const E& e, const V& v);
void connect(const edgeiter& ei, const vertexiter& vi);
void disconnect(const E& e, const V& v);
void disconnect(const edgeiter& ei, const vertexiter& vi);
vertexset& vertices();
const vertexset& vertices() const;
edgeset& edges();
const edgeset& edges() const;
A get_allocator() const;
protected:
hypergraph(const hypergraph& rhs);
hypergraph& operator=(const hypergraph& rhs);
PV pv_;
PE pe_;
A a_;
vertexset vertices_;
edgeset edges_;
};
namespace std {
template<class E, class T, class R>
std::basic_ostream<E,T>& operator<<(std::basic_ostream<E,T>& s, const std::reference_wrapper<R>& r);
template<class E, class T, class R>
std::basic_istream<E,T>& operator>>(std::basic_istream<E,T>& s, std::reference_wrapper<R>& r);
}
Definitions:
#include <algorithm>
#include <cassert>
template<class V, class E, class PV, class PE, class A>
inline hypergraph<V,E,PV,PE,A>::vertex::vertex(const PE& pred, const typename hypergraph<V,E,PV,PE,A>::sub_allocator& alloc)
: edges_(pred, alloc)
{}
template<class V, class E, class PV, class PE, class A>
inline hypergraph<V,E,PV,PE,A>::vertex::vertex(typename hypergraph<V,E,PV,PE,A>::vertex&& rhs)
: edges_(std::move(rhs.edges_))
{}
template<class V, class E, class PV, class PE, class A>
inline typename hypergraph<V,E,PV,PE,A>::vertex& hypergraph<V,E,PV,PE,A>::vertex::operator=(typename hypergraph<V,E,PV,PE,A>::vertex&& rhs)
{
edges_ = std::move(rhs);
return *this;
}
template<class V, class E, class PV, class PE, class A>
inline typename hypergraph<V,E,PV,PE,A>::iedgeset& hypergraph<V,E,PV,PE,A>::vertex::edges()
{return edges_;}
template<class V, class E, class PV, class PE, class A>
inline const typename hypergraph<V,E,PV,PE,A>::iedgeset& hypergraph<V,E,PV,PE,A>::vertex::edges() const
{return edges_;}
template<class V, class E, class PV, class PE, class A>
inline hypergraph<V,E,PV,PE,A>::edge::edge(const PV& pred, const typename hypergraph<V,E,PV,PE,A>::sub_allocator& alloc)
: vertices_(pred, alloc)
, head_(vertices_.end())
{}
template<class V, class E, class PV, class PE, class A>
inline hypergraph<V,E,PV,PE,A>::edge::edge(edge&& rhs)
: vertices_(rhs.vertices_)
, head_(rhs.head_!=rhs.vertices_.end() ? vertices_.find(rhs.head_->first) : vertices_.end())
{}
template<class V, class E, class PV, class PE, class A>
inline typename hypergraph<V,E,PV,PE,A>::edge& hypergraph<V,E,PV,PE,A>::edge::operator=(typename hypergraph<V,E,PV,PE,A>::edge&& rhs)
{
vertices_ = std::move(rhs);
if (rhs.head_ != rhs.vertices_.end())
head_ = vertices_.find(rhs.head_->first);
else
head_ = vertices_.end();
return *this;
}
template<class V, class E, class PV, class PE, class A>
inline void hypergraph<V,E,PV,PE,A>::edge::set_head(const V& v)
{
ivertexiter iter = vertices_.find(std::ref(v));
assert(iter != vertices_.end());
head_ = iter;
}
template<class V, class E, class PV, class PE, class A>
inline const V* hypergraph<V,E,PV,PE,A>::edge::get_head() const
{return (head_ != vertices_.end() ? &head_->first.get() : NULL);}
template<class V, class E, class PV, class PE, class A>
inline const typename hypergraph<V,E,PV,PE,A>::ivertexset& hypergraph<V,E,PV,PE,A>::edge::vertices() const
{ return vertices_; }
template<class V, class E, class PV, class PE, class A>
inline typename hypergraph<V,E,PV,PE,A>::ivertexset& hypergraph<V,E,PV,PE,A>::edge::vertices()
{ return vertices_; }
template<class V, class E, class PV, class PE, class A>
inline hypergraph<V,E,PV,PE,A>::hypergraph(const PV& vertexpred, const PE& edgepred, const A& alloc)
:pv_(vertexpred)
,pe_(edgepred)
,a_(alloc)
,vertices_(vertexpred, a_)
,edges_(edgepred, a_)
{}
template<class V, class E, class PV, class PE, class A>
inline std::pair<typename hypergraph<V,E,PV,PE,A>::vertexiter, bool> hypergraph<V,E,PV,PE,A>::add_vertex(V v)
{ return vertices_.insert(std::pair<V, vertex>(std::move(v),vertex(pe_, a_))); }
template<class V, class E, class PV, class PE, class A>
inline std::pair<typename hypergraph<V,E,PV,PE,A>::edgeiter, bool> hypergraph<V,E,PV,PE,A>::add_edge(E e)
{ return edges_.insert(std::pair<E,edge>(std::move(e), edge(pv_, a_))); }
template<class V, class E, class PV, class PE, class A>
inline typename hypergraph<V,E,PV,PE,A>::vertexiter hypergraph<V,E,PV,PE,A>::erase_vertex(const typename hypergraph<V,E,PV,PE,A>::vertexiter& iter)
{
for(auto i = iter->edges().begin(); i != iter->edges().end(); ++i)
i->erase(*iter);
return vertices_.erase(iter);
}
template<class V, class E, class PV, class PE, class A>
inline typename hypergraph<V,E,PV,PE,A>::vertexiter hypergraph<V,E,PV,PE,A>::erase_vertex(const V& rhs)
{
vertexiter vi = vertices_.find(rhs);
assert(vi != vertices_.end());
vertex& v = vi->second;
for(auto i = v.edges().begin(); i != v.edges().end(); ++i)
i->second.get().vertices_.erase(std::ref(vi->first));
return vertices_.erase(vi);
}
template<class V, class E, class PV, class PE, class A>
inline typename hypergraph<V,E,PV,PE,A>::edgeiter hypergraph<V,E,PV,PE,A>::erase_edge(const typename hypergraph<V,E,PV,PE,A>::edgeiter& iter)
{
for(auto i = iter->vertices().begin(); i != iter->vertices().end(); ++i)
i->edges_.erase(*iter);
return edges_.erase(iter);
}
template<class V, class E, class PV, class PE, class A>
inline typename hypergraph<V,E,PV,PE,A>::edgeiter hypergraph<V,E,PV,PE,A>::erase_edge(const E& rhs)
{
edgeiter ei = edges_.find(rhs);
assert(ei != edges_.end());
edge& e = ei->second;
for(auto i = e.vertices().begin(); i != e.vertices().end(); ++i)
i->second.get().edges_.erase(std::ref(ei->first));
return edges_.erase(ei);
}
template<class V, class E, class PV, class PE, class A>
inline void hypergraph<V,E,PV,PE,A>::connect(const E& e, const V& v)
{
vertexiter vi = vertices_.find(v);
edgeiter ei = edges_.find(e);
assert(vi != vertices_.end());
assert(ei != edges_.end());
vi->second.edges_.insert(typename iedgeset::value_type(std::ref(ei->first), std::ref(ei->second)));
auto n = ei->second.vertices_.insert(typename ivertexset::value_type(std::ref(vi->first), std::ref(vi->second)));
if (ei->second.vertices_.size()==1)
ei->second.head_ = n.first;
}
template<class V, class E, class PV, class PE, class A>
inline void hypergraph<V,E,PV,PE,A>::connect(const typename hypergraph<V,E,PV,PE,A>::edgeiter& ei, const typename hypergraph<V,E,PV,PE,A>::vertexiter& vi)
{
assert(std::distance(vertices_.begin(), vi)>=0); //actually asserts that the iterator belongs to this container
assert(std::distance(edges_.begin(), ei)>=0); //actually asserts that the iterator belongs to this container
vi->edges_.insert(typename iedgeset::value_type(std::ref(ei->first), std::ref(ei->second)));
auto n = ei->vertices_.insert(typename ivertexset::value_type(std::ref(vi->first), std::ref(vi->second)));
if (ei->second.verticies_.size()==1)
ei->second.head_ = n.first;
}
template<class V, class E, class PV, class PE, class A>
inline void hypergraph<V,E,PV,PE,A>::disconnect(const E& e, const V& v)
{
edgeiter ei = edges_.find(e);
vertexiter vi = vertices_.find(v);
assert(ei != edges.end());
assert(vi != vertices_.end());
if (ei->head_.first == v) {
if (ei->head_ != ei->vertices.begin())
ei->head = ei->vertices.begin();
else
ei->head = ei->vertices.end();
}
ei->vertices_.erase(std::ref(vi->first));
vi->edges_.erase(std::ref(ei->first));
}
template<class V, class E, class PV, class PE, class A>
inline void hypergraph<V,E,PV,PE,A>::disconnect(const typename hypergraph<V,E,PV,PE,A>::edgeiter& ei, const typename hypergraph<V,E,PV,PE,A>::vertexiter& vi)
{
assert(std::distance(edges_.begin(), ei)>=0); //actually asserts that the iterator belongs to this container
assert(std::distance(vertices_.begin(), vi)>=0); //actually asserts that the iterator belongs to this container
if (ei->head_.first == vi->first) {
if (ei->head_ != ei->vertices.begin())
ei->head = ei->vertices.begin();
else
ei->head = ei->vertices.end();
}
ei->vertices_.erase(std::ref(vi->first));
vi->edges_.erase(std::ref(ei->first));
}
template<class V, class E, class PV, class PE, class A>
inline typename hypergraph<V,E,PV,PE,A>::vertexset& hypergraph<V,E,PV,PE,A>::vertices()
{ return vertices_;}
template<class V, class E, class PV, class PE, class A>
inline const typename hypergraph<V,E,PV,PE,A>::vertexset& hypergraph<V,E,PV,PE,A>::vertices() const
{ return vertices_;}
template<class V, class E, class PV, class PE, class A>
inline typename hypergraph<V,E,PV,PE,A>::edgeset& hypergraph<V,E,PV,PE,A>::edges()
{ return edges_;}
template<class V, class E, class PV, class PE, class A>
inline const typename hypergraph<V,E,PV,PE,A>::edgeset& hypergraph<V,E,PV,PE,A>::edges() const
{ return edges_;}
template<class V, class E, class PV, class PE, class A>
inline A hypergraph<V,E,PV,PE,A>::get_allocator() const
{ return a_;}
namespace std {
template<class E, class T, class R>
std::basic_ostream<E,T>& operator<<(std::basic_ostream<E,T>& s, const std::reference_wrapper<R>& r)
{return s << r.get();}
template<class E, class T, class R>
std::basic_istream<E,T>& operator>>(std::basic_istream<E,T>& s, std::reference_wrapper<R>& r)
{return s >> r.get();}
}
Note that this is not thoroughly tested, but it compiles and ran through my mini-suite without errors. (As shown in the IDEOne link). The Vertex types and the Edge identifiers can be any types you want, I tested with int verteces and string edge identifiers.
@Nomad: turns out this is MUCH trickier to get right than I thought. I've been working on an implementation for the last few days. I'll put it up as soon as I get it working, but I thought I'd let you know I'm working on it. –
Acoustic
@Nomad: I got the hypermap to compile and run. –
Acoustic
Yea, the hypergraph is a tricky structure to get right (and efficient). Thanks for the suggestions (and the code ;P)! –
Bolin
Hypergraphs are used for decoding in statistical machine translation. There are implementations of hypergraph data structures and algorithms in cdec decoder or relax-decode
One limitation is the edges in these implementation have multiple tails node but only a single head node.
Thanks Paul. Actually, that's precisely the type of hypergraph I'm looking for (I believe they usually call them forward hypergraphs). –
Bolin
© 2022 - 2024 — McMap. All rights reserved.