Y at-il une bibliothèque qui fournit un (dirigé) la mise en œuvre de hypergraphe en C ++?

Question

Je travaille actuellement sur un projet qui énumère les k-meilleures solutions d'un programme dynamique à l'aide d'un cadre de hypergraphe dirigé. Ma mise en œuvre actuelle (en Python) fonctionne bien, mais il est assez lent. L'algorithme effectue un certain nombre de boucles serrées et un peu de juste de récursivité. Je pense vraiment que je pouvais réaliser des améliorations de vitesse importantes en utilisant une implémentation C ++. Cependant, après un peu de mal de recherche, je ne pouvais pas trouver toutes les bibliothèques qui fournissent des implémentations hypergraphe en C ++ (spécifiquement dirigés hypergraphes - mais je ne pouvais pas trouver même les bibliothèques pour hypergraphes) non orientés. Quelqu'un sait-il d'une telle bibliothèque? Il semble qu'il y avait une proposition GSoC d'apporter un soutien hypergraphe pour stimuler il y a quelques années, mais il semble que ça n'a pas vraiment panoramique.

Answer 1

Je ne sais pas d'une bibliothèque, mais vous pouvez rouler votre propre.

Après déconner avec le code de trois jours, j'ai finalement obtenu un hypercarte compiler sans avertissement sur MSVC10 et GCC ( http://ideone.com / oj46o ).
Déclarations:

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

Définitions:

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

}

Notez que ceci est pas testé à fond, mais il compile et RAN dans mon mini-suite sans erreurs. (Comme cela est montré dans la liaison de IDEOne). Les types Vertex et les identificateurs de bord peuvent être tous les types que vous voulez, je l'ai testé avec verteces de int et les identifiants de bord de string.

Answer 2

Hypergraphes sont utilisés pour le décodage dans la traduction automatique statistique. Il existe des implémentations de structures de données et algorithmes hypergraphes dans cdec décodeur ou relax-decode

Une limitation est les bords de ces implémentations ont plusieurs nœuds queues, mais un seul nœud principal.