C'è una libreria che fornisce un (diretto) implementazione ipergrafo in C ++?

Question

Al momento sto lavorando su un progetto che enumera le-best k soluzioni di un programma dinamico utilizzando un framework ipergrafo diretto. Il mio attuale implementazione (in Python) funziona bene, ma è piuttosto lento. L'algoritmo esegue una serie di cicli stretti e un po 'di ricorsione. Credo davvero che avrei potuto realizzare significativi miglioramenti di velocità utilizzando un'implementazione C ++. Tuttavia, dopo un bel po 'di ricerche, sono stato in grado di trovare tutte le librerie che forniscono implementazioni ipergrafo in C ++ (ipergrafi specificamente dirette - ma sono stato in grado di trovare le librerie anche per ipergrafi non orientati). Qualcuno sa di tale libreria un? Sembra che ci fosse una proposta GSoC per portare sostegno ipergrafo per aumentare di qualche anno fa, ma sembra che non ha veramente pan.

Answer 1

Non so di una libreria, ma si potrebbe rotolare il proprio.

Dopo fare in giro con il codice per tre giorni, ho finalmente avuto un HyperMap per compilare senza avvisi su MSVC10 e GCC ( http://ideone.com / oj46o ).
Dichiarazioni:

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

Definizioni:

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

}

Si noti che questo è non accuratamente testato, ma si compila e corse attraverso il mio mini-suite senza errori. (Come indicato nel link Ideone). I tipi di vertice e gli identificatori di bordo può essere qualsiasi tipo che si desidera, ho provato con verteces int e string identificatori bordo.

Answer 2

ipergrafi sono utilizzati per la decodifica nella traduzione automatica statistica. Ci sono implementazioni delle strutture dati e algoritmi ipergrafo in CDEC decoder o relax-decodifica

Una limitazione è bordi in queste implementazioni hanno multipla nodo code ma solo un singolo nodo principale.