All geek questions in one place

Is there a library that provides (directed) implementation of a hypergraph in C ++?

I am currently working on a project that lists the k-best solutions of a dynamic program using a directional hypergraph frame. My current implementation (in Python) works well, but is rather slow. The algorithm performs many hard loops and a fair bit of recursion. I really think that I can implement significant speed improvements using a C ++ implementation. However, after an honest search, I could not find libraries that provide the implementation of hypergraphs in C ++ (in particular, directional hypergraphs - but I could not even find libraries for non-oriented hypergraphs). Does anyone know about such a library? It seems that there was a GSoC proposal to support hypergraph support a few years ago, but it does not seem to be reflected.

+4
source share
2 answers

I don't know about the library, but you can tip over.

After messing up the code for three days, I finally got a hypermap for compilation without warning on MSVC10 and GCC ( http://ideone.com/oj46o ).
Ads:

#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();} }

Please note that this has not been fully verified, but it compiles and passes through my mini-package without errors. (As shown on the IDEOne link). Vertex types and Edge identifiers can be any types you want, I tested with int verteces and string edge identifiers.

+8
source

Hypergraphs are used for decoding in statistical machine translation. There are implementations of hypergraph data structures and algorithms in the cdec or relax-decode decoder

One limitation is that the edges in this implementation have several node tails, but only one node head.

+2
source

Source: https://habr.com/ru/post/1384211/

More articles:


All Articles