XGitUrl: http://git.tuebingen.mpg.de/?p=libdai.git;a=blobdiff_plain;f=include%2Fdai%2Fbipgraph.h;h=25f20b21725ba23706250ea8ac2da3b2c6d59184;hp=b9c8f5837dffb58cfc1ae241a29a00125e7f56ea;hb=76cf77837c617f54202590125c7a566ae443d0ab;hpb=ef341fb1cf1af803f7cb018a7b5e1f0e49577252
diff git a/include/dai/bipgraph.h b/include/dai/bipgraph.h
index b9c8f58..25f20b2 100644
 a/include/dai/bipgraph.h
+++ b/include/dai/bipgraph.h
@@ 1,27 +1,16 @@
/* Copyright (C) 20062008 Joris Mooij [joris dot mooij at tuebingen dot mpg dot de]
 Radboud University Nijmegen, The Netherlands /
 Max Planck Institute for Biological Cybernetics, Germany

 This file is part of libDAI.

 libDAI is free software; you can redistribute it and/or modify
 it under the terms of the GNU General Public License as published by
 the Free Software Foundation; either version 2 of the License, or
 (at your option) any later version.

 libDAI is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with libDAI; if not, write to the Free Software
 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 021101301 USA
*/
+/* This file is part of libDAI  http://www.libdai.org/
+ *
+ * libDAI is licensed under the terms of the GNU General Public License version
+ * 2, or (at your option) any later version. libDAI is distributed without any
+ * warranty. See the file COPYING for more details.
+ *
+ * Copyright (C) 20062009 Joris Mooij [joris dot mooij at libdai dot org]
+ * Copyright (C) 20062007 Radboud University Nijmegen, The Netherlands
+ */
/// \file
/// \brief Defines BipartiteGraph class
+/// \brief Defines the BipartiteGraph class, which represents a bipartite graph
#ifndef __defined_libdai_bipgraph_h
@@ 30,26 +19,26 @@
#include
#include
#include
#include
#include
+#include
namespace dai {
/// Represents the neighborhood structure of nodes in a bipartite graph.
+/// Represents the neighborhood structure of nodes in an undirected, bipartite graph.
/** A bipartite graph has two types of nodes: type 1 and type 2. Edges can occur only between
* nodes of different type. Nodes are indexed by an unsigned integer. If there are nr1()
 * nodes of type 1 and nr2() nodes of type 2, the nodes of type 1 are numbered
+ * nodes of type 1 and nr2() nodes of type 2, the nodes of type 1 are numbered
* 0,1,2,...,nr1()1 and the nodes of type 2 are numbered 0,1,2,...,nr2()1. An edge
* between node \a n1 of type 1 and node \a n2 of type 2 is represented by a BipartiteGraph::Edge(\a n1,\a n2).
*
* A BipartiteGraph is implemented as a sparse adjacency list, i.e., it stores for each node a list of
 * its neighboring nodes. In particular, it stores for each node of type 1 a vector of Neighbor structures
 * (accessible by the nb1() method) describing the neighboring nodes of type 2; similarly, for each node
 * of type 2 it stores a vector of Neighbor structures (accessibly by the nb2() method) describing the
 * neighboring nodes of type 1.
+ * its neighboring nodes. More precisely: it stores for each node of type 1 a vector of Neighbor structures
+ * (accessible by the nb1() method) describing the neighboring nodes of type 2; similarly, for each node
+ * of type 2 it stores a vector of Neighbor structures (accessibly by the nb2() method) describing the
+ * neighboring nodes of type 1.
* Thus, each node has an associated variable of type BipartiteGraph::Neighbors, which is a vector of
* Neighbor structures, describing its neighboring nodes of the other type.
* \idea Cache secondorder neighborhoods in BipartiteGraph.
@@ 62,15 +51,16 @@ class BipartiteGraph {
* will be sparse, so we need some way of storing a set of
* the neighbors of a node, which is both fast and
* memoryefficient. 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
+ * 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).
+ * stored as a std::vector<\link Neighbor \endlink>, and
+ * extra information is included in the Neighbor struct which
+ * allows us to access a node as a neighbor of its neighbor
+ * (the \c dual member).
*
* By convention, variable identifiers naming indices into a
 * vector of neighbors are prefixed with an underscore ("_").
+ * vector of neighbors are prefixed with an underscore ("_").
* The neighbor list which they point into is then understood
* from context. For example:
*
@@ 79,14 +69,14 @@ class BipartiteGraph {
* \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.
+ * understood as a "relative" index, giving node \a 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 \c node member: nb1(i,_I).node.
+ * The \c iter member gives the relative index \a _I, and the
+ * \c 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);
@@ 95,8 +85,9 @@ class BipartiteGraph {
* nb2(n.node,n.dual).node == i
* \endcode
*
 * In a FactorGraph, nb1 is called nbV, and nb2 is called
 * nbF.
+ * In a FactorGraph, the nodes of type 1 represent variables, and
+ * the nodes of type 2 represent factors. For convenience, nb1() is
+ * called FactorGraph::nbV(), and nb2() is called FactorGraph::nbF().
*
* There is no easy way to transform a pair of absolute node
* indices \a i and \a I into a Neighbor structure relative
@@ 123,7 +114,7 @@ class BipartiteGraph {
/// Constructor that sets the Neighbor members according to the parameters
Neighbor( size_t iter, size_t node, size_t dual ) : iter(iter), node(node), dual(dual) {}
 /// Cast to size_t returns node member
+ /// Cast to \c size_t returns \c node member
operator size_t () const { return node; }
};
@@ 142,28 +133,39 @@ class BipartiteGraph {
/// Used internally by isTree()
struct levelType {
 std::vector ind1; // indices of nodes of type 1
 std::vector ind2; // indices of nodes of type 2
+ /// Indices of nodes of type 1
+ std::vector ind1;
+ /// Indices of nodes of type 2
+ std::vector ind2;
};
 /// @name Backwards compatibility layer (to be removed soon)
+ // OBSOLETE
+ /// \name Backwards compatibility layer (to be removed soon)
//@{
/// Enable backwards compatibility layer?
+ /** \deprecated Please use the BipartiteGraph::Neighbor interface instead
+ */
bool _edge_indexed;
/// Call indexEdges() first to initialize these members
+ /** \deprecated Please use the BipartiteGraph::Neighbor interface instead
+ */
std::vector _edges;
/// Call indexEdges() first to initialize these members
+ /** \deprecated Please use the BipartiteGraph::Neighbor interface instead
+ */
hash_map _vv2e;
 //}@
+ //@}
public:
+ /// \name Constructors and destructors
+ //@{
/// Default constructor (creates an empty bipartite graph)
BipartiteGraph() : _nb1(), _nb2(), _edge_indexed(false) {}
/// Constructs BipartiteGraph from a range of edges.
/** \tparam EdgeInputIterator Iterator that iterates over instances of BipartiteGraph::Edge.
* \param nr1 The number of nodes of type 1.
 * \param nr2 The number of nodes of type 2.
+ * \param nr2 The number of nodes of type 2.
* \param begin Points to the first edge.
* \param end Points just beyond the last edge.
*/
@@ 171,178 +173,163 @@ class BipartiteGraph {
BipartiteGraph( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) : _nb1( nr1 ), _nb2( nr2 ), _edge_indexed(false) {
construct( nr1, nr2, begin, end );
}

 /// (Re)constructs BipartiteGraph from a range of edges.
 /** \tparam EdgeInputIterator Iterator that iterates over instances of BipartiteGraph::Edge.
 * \param nr1 The number of nodes of type 1.
 * \param nr2 The number of nodes of type 2.
 * \param begin Points to the first edge.
 * \param end Points just beyond the last edge.
 */
 template
 void construct( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end );

 /// Returns constant reference to the _i2'th neighbor of node i1 of type 1
 const Neighbor & nb1( size_t i1, size_t _i2 ) const {
#ifdef DAI_DEBUG
 assert( i1 < _nb1.size() );
 assert( _i2 < _nb1[i1].size() );
#endif
 return _nb1[i1][_i2];
+ //@}
+
+ /// \name Accessors and mutators
+ //@{
+ /// Returns constant reference to the \a _i2 'th neighbor of node \a i1 of type 1
+ const Neighbor & nb1( size_t i1, size_t _i2 ) const {
+ DAI_DEBASSERT( i1 < _nb1.size() );
+ DAI_DEBASSERT( _i2 < _nb1[i1].size() );
+ return _nb1[i1][_i2];
}
 /// Returns reference to the _i2'th neighbor of node i1 of type 1
+ /// Returns reference to the \a _i2 'th neighbor of node \a i1 of type 1
Neighbor & nb1( size_t i1, size_t _i2 ) {
#ifdef DAI_DEBUG
 assert( i1 < _nb1.size() );
 assert( _i2 < _nb1[i1].size() );
#endif
 return _nb1[i1][_i2];
+ DAI_DEBASSERT( i1 < _nb1.size() );
+ DAI_DEBASSERT( _i2 < _nb1[i1].size() );
+ return _nb1[i1][_i2];
}
 /// Returns constant reference to the _i1'th neighbor of node i2 of type 2
 const Neighbor & nb2( size_t i2, size_t _i1 ) const {
#ifdef DAI_DEBUG
 assert( i2 < _nb2.size() );
 assert( _i1 < _nb2[i2].size() );
#endif
 return _nb2[i2][_i1];
+ /// Returns constant reference to the \a _i1 'th neighbor of node \a i2 of type 2
+ const Neighbor & nb2( size_t i2, size_t _i1 ) const {
+ DAI_DEBASSERT( i2 < _nb2.size() );
+ DAI_DEBASSERT( _i1 < _nb2[i2].size() );
+ return _nb2[i2][_i1];
}
 /// Returns reference to the _i1'th neighbor of node i2 of type 2
 Neighbor & nb2( size_t i2, size_t _i1 ) {
#ifdef DAI_DEBUG
 assert( i2 < _nb2.size() );
 assert( _i1 < _nb2[i2].size() );
#endif
 return _nb2[i2][_i1];
+ /// Returns reference to the \a _i1 'th neighbor of node \a i2 of type 2
+ Neighbor & nb2( size_t i2, size_t _i1 ) {
+ DAI_DEBASSERT( i2 < _nb2.size() );
+ DAI_DEBASSERT( _i1 < _nb2[i2].size() );
+ return _nb2[i2][_i1];
}
 /// Returns constant reference to all neighbors of node i1 of type 1
 const Neighbors & nb1( size_t i1 ) const {
#ifdef DAI_DEBUG
 assert( i1 < _nb1.size() );
#endif
 return _nb1[i1];
+ /// Returns constant reference to all neighbors of node \a i1 of type 1
+ const Neighbors & nb1( size_t i1 ) const {
+ DAI_DEBASSERT( i1 < _nb1.size() );
+ return _nb1[i1];
}
 /// Returns reference to all neighbors of node of i1 type 1
 Neighbors & nb1( size_t i1 ) {
#ifdef DAI_DEBUG
 assert( i1 < _nb1.size() );
#endif
 return _nb1[i1];
+ /// Returns reference to all neighbors of node \a i1 of type 1
+ Neighbors & nb1( size_t i1 ) {
+ DAI_DEBASSERT( i1 < _nb1.size() );
+ return _nb1[i1];
}
 /// Returns constant reference to all neighbors of node i2 of type 2
 const Neighbors & nb2( size_t i2 ) const {
#ifdef DAI_DEBUG
 assert( i2 < _nb2.size() );
#endif
 return _nb2[i2];
+ /// Returns constant reference to all neighbors of node \a i2 of type 2
+ const Neighbors & nb2( size_t i2 ) const {
+ DAI_DEBASSERT( i2 < _nb2.size() );
+ return _nb2[i2];
}
 /// Returns reference to all neighbors of node i2 of type 2
 Neighbors & nb2( size_t i2 ) {
#ifdef DAI_DEBUG
 assert( i2 < _nb2.size() );
#endif
 return _nb2[i2];
+ /// Returns reference to all neighbors of node \a i2 of type 2
+ Neighbors & nb2( size_t i2 ) {
+ DAI_DEBASSERT( i2 < _nb2.size() );
+ return _nb2[i2];
}
+ //@}
 /// Returns number of nodes of type 1
 size_t nr1() const { return _nb1.size(); }
 /// Returns number of nodes of type 2
 size_t nr2() const { return _nb2.size(); }

 /// Calculates the number of edges, time complexity: O(nr1())
 size_t nrEdges() const {
 size_t sum = 0;
 for( size_t i1 = 0; i1 < nr1(); i1++ )
 sum += nb1(i1).size();
 return sum;
 }

 /// Adds a node of type 1 without neighbors.
 void add1() { _nb1.push_back( Neighbors() ); }

 /// Adds a node of type 2 without neighbors.
 void add2() { _nb2.push_back( Neighbors() ); }
+ /// \name Adding nodes and edges
+ //@{
+ /// (Re)constructs BipartiteGraph from a range of edges.
+ /** \tparam EdgeInputIterator Iterator that iterates over instances of BipartiteGraph::Edge.
+ * \param nr1 The number of nodes of type 1.
+ * \param nr2 The number of nodes of type 2.
+ * \param begin Points to the first edge.
+ * \param end Points just beyond the last edge.
+ */
+ template
+ void construct( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end );
+
+ /// Adds a node of type 1 without neighbors and returns the index of the added node.
+ size_t add1() { _nb1.push_back( Neighbors() ); return _nb1.size()  1; }
+
+ /// Adds a node of type 2 without neighbors and returns the index of the added node.
+ size_t add2() { _nb2.push_back( Neighbors() ); return _nb2.size()  1; }
/// Adds a node of type 1, with neighbors specified by a range of nodes of type 2.
 /** \tparam NodeInputIterator Iterator that iterates over instances of size_t.
+ /** \tparam NodeInputIterator Iterator that iterates over instances of \c size_t.
* \param begin Points to the first index of the nodes of type 2 that should become neighbors of the added node.
* \param end Points just beyond the last index of the nodes of type 2 that should become neighbors of the added node.
 * \param sizeHint For improved efficiency, the size of the range may be specified by sizeHint.
+ * \param sizeHint For improved efficiency, the size of the range may be specified by \a sizeHint.
+ * \returns Index of the added node.
*/
template
 void add1( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
+ size_t add1( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
Neighbors nbs1new;
nbs1new.reserve( sizeHint );
size_t iter = 0;
for( NodeInputIterator it = begin; it != end; ++it ) {
 assert( *it < nr2() );
+ DAI_ASSERT( *it < nr2() );
Neighbor nb1new( iter, *it, nb2(*it).size() );
Neighbor nb2new( nb2(*it).size(), nr1(), iter++ );
nbs1new.push_back( nb1new );
nb2( *it ).push_back( nb2new );
}
_nb1.push_back( nbs1new );
+ return _nb1.size()  1;
}
/// Adds a node of type 2, with neighbors specified by a range of nodes of type 1.
 /** \tparam NodeInputIterator Iterator that iterates over instances of size_t.
+ /** \tparam NodeInputIterator Iterator that iterates over instances of \c size_t.
* \param begin Points to the first index of the nodes of type 1 that should become neighbors of the added node.
* \param end Points just beyond the last index of the nodes of type 1 that should become neighbors of the added node.
 * \param sizeHint For improved efficiency, the size of the range may be specified by sizeHint.
+ * \param sizeHint For improved efficiency, the size of the range may be specified by \a sizeHint.
+ * \returns Index of the added node.
*/
template
 void add2( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
+ size_t add2( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
Neighbors nbs2new;
nbs2new.reserve( sizeHint );
size_t iter = 0;
for( NodeInputIterator it = begin; it != end; ++it ) {
 assert( *it < nr1() );
+ DAI_ASSERT( *it < nr1() );
Neighbor nb2new( iter, *it, nb1(*it).size() );
Neighbor nb1new( nb1(*it).size(), nr2(), iter++ );
nbs2new.push_back( nb2new );
nb1( *it ).push_back( nb1new );
}
_nb2.push_back( nbs2new );
+ return _nb2.size()  1;
}
 /// Removes node n1 of type 1 and all incident edges.
+ /// Adds an edge between node \a n1 of type 1 and node \a n2 of type 2.
+ /** If \a check == \c true, only adds the edge if it does not exist already.
+ */
+ void addEdge( size_t n1, size_t n2, bool check = true );
+ //@}
+
+ /// \name Erasing nodes and edges
+ //@{
+ /// Removes node \a n1 of type 1 and all incident edges; indices of other nodes are changed accordingly.
void erase1( size_t n1 );
 /// Removes node n2 of type 2 and all incident edges.
+ /// Removes node \a n2 of type 2 and all incident edges; indices of other nodes are changed accordingly.
void erase2( size_t n2 );
 /// Adds an edge between node n1 of type 1 and node n2 of type 2.
 /** If check == true, only adds the edge if it does not exist already.
 */
 void addEdge( size_t n1, size_t n2, bool check = true ) {
 assert( n1 < nr1() );
 assert( n2 < nr2() );
 bool exists = false;
 if( check ) {
 // Check whether the edge already exists
 foreach( const Neighbor &nb2, nb1(n1) )
 if( nb2 == n2 ) {
 exists = true;
 break;
 }
 }
 if( !exists ) { // Add edge
 Neighbor nb_1( _nb1[n1].size(), n2, _nb2[n2].size() );
 Neighbor nb_2( nb_1.dual, n1, nb_1.iter );
 _nb1[n1].push_back( nb_1 );
 _nb2[n2].push_back( nb_2 );
 }
+ /// Removes edge between node \a n1 of type 1 and node \a n2 of type 2.
+ void eraseEdge( size_t n1, size_t n2 );
+ //@}
+
+ /// \name Queries
+ //@{
+ /// Returns number of nodes of type 1
+ size_t nr1() const { return _nb1.size(); }
+ /// Returns number of nodes of type 2
+ size_t nr2() const { return _nb2.size(); }
+
+ /// Calculates the number of edges, time complexity: O(nr1())
+ size_t nrEdges() const {
+ size_t sum = 0;
+ for( size_t i1 = 0; i1 < nr1(); i1++ )
+ sum += nb1(i1).size();
+ return sum;
}
 /// Calculates secondorder neighbors (i.e., neighbors of neighbors) of node n1 of type 1.
 /** If include == true, includes n1 itself, otherwise excludes n1.
+ /// Calculates secondorder neighbors (i.e., neighbors of neighbors) of node \a n1 of type 1.
+ /** If \a include == \c true, includes \a n1 itself, otherwise excludes \a n1.
*/
std::vector delta1( size_t n1, bool include = false ) const;
 /// Calculates secondorder neighbors (i.e., neighbors of neighbors) of node n2 of type 2.
 /** If include == true, includes n2 itself, otherwise excludes n2.
+ /// Calculates secondorder neighbors (i.e., neighbors of neighbors) of node \a n2 of type 2.
+ /** If \a include == \c true, includes \a n2 itself, otherwise excludes \a n2.
*/
std::vector delta2( size_t n2, bool include = false ) const;
@@ 354,12 +341,24 @@ class BipartiteGraph {
/// Returns true if the graph is a tree, i.e., if it is singly connected and connected.
bool isTree() const;
+ /// Checks internal consistency
+ void checkConsistency() const;
+ //@}
+
+ /// \name Input and output
+ //@{
/// 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)
 //@{
+ // OBSOLETE
+ /// \name Backwards compatibility layer (to be removed soon)
+ //@{
+ /// Prepare backwards compatibility layer for indexed edges
+ /** \deprecated Please use the BipartiteGraph::Neighbor interface instead
+ */
void indexEdges() {
+ std::cerr << "Warning: this BipartiteGraph edge interface is obsolete!" << std::endl;
_edges.clear();
_vv2e.clear();
size_t i=0;
@@ 379,33 +378,41 @@ class BipartiteGraph {
_edge_indexed = true;
}

+
+ /// Returns edge with index \a e
+ /** \deprecated Please use the BipartiteGraph::Neighbor interface instead
+ */
const Edge& edge(size_t e) const {
 assert(_edge_indexed);
+ DAI_ASSERT(_edge_indexed);
return _edges[e];
}

+
+ /// Returns all edges
+ /** \deprecated Please use the BipartiteGraph::Neighbor interface instead
+ */
const std::vector& edges() const {
return _edges;
}

+
+ /// Converts a pair of node indices to an edge index
+ /** \deprecated Please use the BipartiteGraph::Neighbor interface instead
+ */
size_t VV2E(size_t n1, size_t n2) const {
 assert(_edge_indexed);
+ DAI_ASSERT(_edge_indexed);
Edge e(n1,n2);
hash_map::const_iterator i = _vv2e.find(e);
 assert(i != _vv2e.end());
+ DAI_ASSERT(i != _vv2e.end());
return i>second;
}
+ /// Returns number of edges
+ /** \deprecated Please use the BipartiteGraph::Neighbor interface instead
+ */
size_t nr_edges() const {
 assert(_edge_indexed);
+ DAI_ASSERT(_edge_indexed);
return _edges.size();
}
 //}@

 private:
 /// Checks internal consistency
 void check() const;
+ //@}
};
@@ 452,7 +459,7 @@ void BipartiteGraph::construct( size_t nr1, size_t nr2, EdgeInputIterator begin,
* 12  21;
* }
* \enddot
 * It has three nodes of type 1 (drawn as circles) and two nodes of type 2 (drawn as rectangles).
+ * It has three nodes of type 1 (drawn as circles) and two nodes of type 2 (drawn as rectangles).
* Node 0 of type 1 has only one neighbor (node 0 of type 2), but node 0 of type 2 has three neighbors (nodes 0,1,2 of type 1).
* The example code shows how to construct a BipartiteGraph object representing this bipartite graph and
* how to iterate over nodes and their neighbors.