X-Git-Url: http://git.tuebingen.mpg.de/?p=libdai.git;a=blobdiff_plain;f=include%2Fdai%2Fbipgraph.h;h=15845ded04f26f00315325b0c0157b6cf2acab52;hp=17b39a7000bbe0f2bf8015b5933762e0e849e735;hb=ae0fc30e10be6683cbfc209dcee56f34234a6cb8;hpb=3ad3c2c9ce7cee50cf0fa731cb5c6bf6f36fa45a diff --git a/include/dai/bipgraph.h b/include/dai/bipgraph.h index 17b39a7..15845de 100644 --- a/include/dai/bipgraph.h +++ b/include/dai/bipgraph.h @@ -56,14 +56,59 @@ namespace dai { */ class BipartiteGraph { public: - /// Describes a neighboring node of some other node in a BipartiteGraph. - /** A Neighbor structure has three members: \a iter, \a node and \a dual. The \a - * node member is the most important member: it contains the index of the neighboring node. The \a iter - * member is useful for iterating over neighbors, and contains the index of this Neighbor entry in the - * corresponding BipartiteGraph::Neighbors variable. The \a dual member is useful to find the dual Neighbor - * element: a pair of neighboring nodes can be either specified as a node of type 1 and a neighbor of type - * 2, or as a node of type 2 and a neighbor of type 1; the \a dual member contains the index of the dual - * Neighbor element (see the example for another explanation of the dual member). + /// Describes the neighbor relationship of two nodes in a BipartiteGraph. + /** Sometimes we want to do an action, such as sending a + * message, for all edges in a graph. However, most graphs + * will be sparse, so we need some way of storing a set of + * the neighbors of a node, which is both fast and + * memory-efficient. We also need to be able to go between + * viewing node \a A as a neighbor of node \a B, and node \a + * B as a neighbor of node \a A. The Neighbor struct solves + * both of these problems. Each node has a list of neighbors, + * stored as a vector, and extra information is + * included in the Neighbor struct which allows us to access + * a node as a neighbor of its neighbor (the \a dual member). + * + * By convention, variable identifiers naming indices into a + * vector of neighbors are prefixed with an underscore ("_"). + * The neighbor list which they point into is then understood + * from context. For example: + * + * \code + * void BP::calcNewMessage( size_t i, size_t _I ) + * \endcode + * + * Here, \a i is the "absolute" index of node i, but \a _I is + * understood as a "relative" index, giving node I's entry in + * nb1(i). The corresponding Neighbor structure can be + * accessed as nb1(i,_I) or nb1(i)[_I]. The absolute index of + * \a _I, which would be called \a I, can be recovered from + * the \a node member: nb1(i,_I).node. The \a iter member + * gives the relative index \a _I, and the \a dual member + * gives the "dual" relative index, i.e. the index of \a i in + * \a I's neighbor list. + * + * \code + * Neighbor n = nb1(i,_I); + * n.node == I && + * n.iter == _I && + * nb2(n.node,n.dual).node == i + * \endcode + * + * In a FactorGraph, nb1 is called nbV, and nb2 is called + * nbF. + * + * There is no easy way to transform a pair of absolute node + * indices \a i and \a I into a Neighbor structure relative + * to one of the nodes. Such a feature has never yet been + * found to be necessary. Iteration over edges can always be + * accomplished using the Neighbor lists, and by writing + * functions that accept relative indices: + * \code + * for( size_t i = 0; i < nrVars(); ++i ) + * foreach( const Neighbor &I, nbV(i) ) + * calcNewMessage( i, I.iter ); + * \endcode */ struct Neighbor { /// Corresponds to the index of this Neighbor entry in the vector of neighbors @@ -101,9 +146,19 @@ class BipartiteGraph { std::vector ind2; // indices of nodes of type 2 }; + /// @name Backwards compatibility layer (to be removed soon) + //@{ + /// Enable backwards compatibility layer? + bool _edge_indexed; + /// Call indexEdges() first to initialize these members + std::vector _edges; + /// Call indexEdges() first to initialize these members + hash_map _vv2e; + //}@ + public: /// Default constructor (creates an empty bipartite graph) - BipartiteGraph() : _nb1(), _nb2() {} + BipartiteGraph() : _nb1(), _nb2(), _edge_indexed(false) {} /// Constructs BipartiteGraph from a range of edges. /** \tparam EdgeInputIterator Iterator that iterates over instances of BipartiteGraph::Edge. @@ -113,7 +168,7 @@ class BipartiteGraph { * \param end Points just beyond the last edge. */ template - BipartiteGraph( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) : _nb1( nr1 ), _nb2( nr2 ) { + BipartiteGraph( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) : _nb1( nr1 ), _nb2( nr2 ), _edge_indexed(false) { construct( nr1, nr2, begin, end ); } @@ -318,6 +373,53 @@ class BipartiteGraph { /// Writes this BipartiteGraph to an output stream in GraphViz .dot syntax void printDot( std::ostream& os ) const; + /// @name Backwards compatibility layer (to be removed soon) + //@{ + void indexEdges() { + std::cerr << "Warning: this BipartiteGraph edge interface is obsolete!" << std::endl; + _edges.clear(); + _vv2e.clear(); + size_t i=0; + foreach(const Neighbors &nb1s, _nb1) { + foreach(const Neighbor &n2, nb1s) { + Edge e(i, n2.node); + _edges.push_back(e); + } + i++; + } + sort(_edges.begin(), _edges.end()); // unnecessary? + + i=0; + foreach(const Edge& e, _edges) { + _vv2e[e] = i++; + } + + _edge_indexed = true; + } + + const Edge& edge(size_t e) const { + assert(_edge_indexed); + return _edges[e]; + } + + const std::vector& edges() const { + return _edges; + } + + size_t VV2E(size_t n1, size_t n2) const { + assert(_edge_indexed); + Edge e(n1,n2); + hash_map::const_iterator i = _vv2e.find(e); + assert(i != _vv2e.end()); + return i->second; + } + + size_t nr_edges() const { + assert(_edge_indexed); + return _edges.size(); + } + //}@ + private: /// Checks internal consistency void check() const;