¿Hay una biblioteca que proporcione una implementación de hipergrafio (dirigido) en C ++?

Question

Actualmente estoy trabajando en un proyecto que enumera las soluciones K-Best de un programa dinámico utilizando un marco de hipergrafio dirigido. Mi implementación actual (en Python) funciona bien, pero es bastante lenta. El algoritmo realiza una serie de bucles ajustados y un poco de recursión. Realmente creo que podría realizar mejoras de velocidad significativas utilizando una implementación de C ++. Sin embargo, después de un poco de búsqueda, no pude encontrar ninguna biblioteca que proporcionara implementaciones de hipergrafías en C ++ (específicamente hipergrafios dirigidos, pero no pude encontrar bibliotecas ni bibliotecas para hipergrafos no dirigidos). ¿Alguien sabe de una biblioteca así? Parece que hubo una propuesta de GSOC para aportar el soporte de hipergrafías para aumentar hace unos años, pero parece que realmente no funcionó.

Answer 1

No conozco una biblioteca, pero podrías rodar la tuya.

Después de jugar con el código durante tres días, finalmente obtuve un hipermap para compilar sin advertencias en MSVC10 y GCC (http://ideone.com/oj46o).
Declaraciones:

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

Definiciones:

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

}

Tenga en cuenta que esto es no Completamente probado, pero se compila y corrió por mi mini suite sin errores. (Como se muestra en el enlace de ideona). Los tipos de vértices y los identificadores de borde pueden ser cualquier tipo que desee, probé con int vérttes y string Identificadores de borde.

Answer 2

Los hipergrafios se utilizan para decodificar en la traducción automática estadística. Hay implementaciones de estructuras de datos y algoritmos de hipergrafías en decodificador de CDEC o decisión relajante

Una limitación es que los bordes en esta implementación tienen múltiples nodos de colas pero solo un nodo de cabeza.