Gibt es eine Bibliothek, die eine (gerichtete) HyperGraph -Implementierung in C ++ bietet?

Question

Ich arbeite derzeit an einem Projekt, das die K-Best-Lösungen eines dynamischen Programms unter Verwendung eines gerichteten Hypergraph-Frameworks auflistet. Meine aktuelle Implementierung (in Python) funktioniert gut, ist aber ziemlich langsam. Der Algorithmus führt eine Reihe enger Loops und ein gutes Stück Rekursion aus. Ich denke wirklich, dass ich mit einer C ++ - Implementierung erhebliche Geschwindigkeitsverbesserungen erkennen könnte. Nach einem kleinen Teil der Suche konnte ich jedoch keine Bibliotheken finden, die HyperGraph -Implementierungen in C ++ bereitstellen (speziell gerichtete Hypergraphen -, aber ich konnte nicht einmal Bibliotheken für ungerichtete Hypergraphs finden). Kennt jemand eine solche Bibliothek? Es scheint, dass es einen GSOC -Vorschlag gab, vor ein paar Jahren Hypergraph -Unterstützung zu bringen, um zu steigern, aber es sieht so aus, als ob es nicht wirklich herausgekommen ist.

Answer 1

Ich kenne keine Bibliothek, aber Sie könnten Ihre eigenen rollen.

Nachdem ich drei Tage lang mit dem Code herumgespielt hatte, bekam ich endlich eine Hypermap, um sie ohne Warnungen auf MSVC10 und GCC zu kompilieren (GCC (http://ideone.com/oj46o).
Erklärungen:

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

Definitionen:

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

}

Beachten Sie, dass dies ist nicht gründlich getestet, aber es kompiliert und lief meine Mini-Suite ohne Fehler. (Wie in der ideone -Verbindung gezeigt). Die Scheitelpunkttypen und die Kantenkennung können alle gewünschten Typen sein, mit denen ich getestet habe int vertiecen und string Kantenidentifikatoren.

Answer 2

Hypergraphen werden zur Dekodierung in der statistischen maschinellen Übersetzung verwendet. Es gibt Implementierungen von Hypergraph -Datenstrukturen und Algorithmen in CDEC -Decoder oder Entspannungsteuerung

Eine Einschränkung ist die Kanten in dieser Implementierung haben mehrere Schwänzeknoten, aber nur einen einzelnen Kopfknoten.