-/* Copyright (C) 2006-2008 Joris Mooij [j dot mooij at science dot ru dot nl]
- Radboud University Nijmegen, The Netherlands
-
- 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.
+/* 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) 2006-2009 Joris Mooij [joris dot mooij at libdai dot org]
+ * Copyright (C) 2006-2007 Radboud University Nijmegen, The Netherlands
+ */
- 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 02110-1301 USA
-*/
+/// \file
+/// \brief Defines the BipartiteGraph class, which represents a bipartite graph
#ifndef __defined_libdai_bipgraph_h
#include <ostream>
#include <vector>
-#include <cassert>
#include <algorithm>
#include <dai/util.h>
+#include <dai/exceptions.h>
namespace dai {
-/// A BipartiteGraph 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, edges are indexed as
- * a pair of unsigned integers (where the pair (a,b) means the b'th neighbor of the a'th node).
- * The BipartiteGraph stores neighborhood structures as vectors of vectors of Neighbor entries.
+ * nodes of different type. Nodes are indexed by an unsigned integer. If there are nrNodes1()
+ * nodes of type 1 and nrNodes2() nodes of type 2, the nodes of type 1 are numbered
+ * 0,1,2,...,nrNodes1()-1 and the nodes of type 2 are numbered 0,1,2,...,nrNodes2()-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. 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 second-order neighborhoods in BipartiteGraph.
*/
class BipartiteGraph {
public:
- /// A Neighbor describes a neighboring node of some other node.
- /** Iterating over all neighbors of node n1 of type 1 can be done in the following way:
+ /// 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 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 ("_").
+ * 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 \a I 's entry in
+ * <tt>nb1(i)</tt>. The corresponding Neighbor structure can be
+ * accessed as <tt>nb1(i,_I)</tt> or <tt>nb1(i)[_I]</tt>. The
+ * absolute index of \a _I, which would be called \a I, can be
+ * recovered from the \c node member: <tt>nb1(i,_I).node</tt>.
+ * 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);
+ * n.node == I &&
+ * n.iter == _I &&
+ * nb2(n.node,n.dual).node == i
+ * \endcode
+ *
+ * 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
+ * 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
- * foreach( const BipartiteGraph::Neighbor &n2, nb1(n1) ) {
- * size_t _n2 = n2.iter;
- * size_t _n1 = n2.dual;
- * // n2 == n2.node;
- * // The _n2'th neighbor of n1 is n2, and the _n1'th neighbor of n2 is n1:
- * // nb1(n1)[_n2] == n2, nb2(n2)[_n1] == n1
- * }
+ * 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
- unsigned iter;
+ size_t iter;
/// Contains the number of the neighboring node
- unsigned node;
+ size_t node;
/// Contains the "dual" iter
- unsigned dual;
- /// Cast to unsigned returns node
- operator unsigned () const { return node; }
+ size_t dual;
+
/// Default constructor
Neighbor() {}
- /// Constructor
+ /// 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 \c size_t returns \c node member
+ operator size_t () const { return node; }
};
- /// Neighbors is a vector of Neighbor entries; each node has an associated Neighbors variable, which describes its neighbors.
+ /// Describes the neighbors of some node.
typedef std::vector<Neighbor> Neighbors;
- /// Edge is used as index of an edge: an Edge(a,b) corresponds to the edge between the a'th node and its b'th neighbor.
+ /// Represents an edge: an Edge(\a n1,\a n2) corresponds to the edge between node \a n1 of type 1 and node \a n2 of type 2.
typedef std::pair<size_t,size_t> Edge;
private:
- /// _nb1 contains for each node of type 1 a vector of its neighbors
+ /// Contains for each node of type 1 a vector of its neighbors
std::vector<Neighbors> _nb1;
- /// _nb2 contains for each node of type 2 a vector of its neighbors
+
+ /// Contains for each node of type 2 a vector of its neighbors
std::vector<Neighbors> _nb2;
/// Used internally by isTree()
struct levelType {
- std::vector<size_t> ind1; // indices of vertices of type 1
- std::vector<size_t> ind2; // indices of vertices of type 2
+ /// Indices of nodes of type 1
+ std::vector<size_t> ind1;
+ /// Indices of nodes of type 2
+ std::vector<size_t> ind2;
};
public:
- /// Default constructor
+ /// \name Constructors and destructors
+ //@{
+ /// Default constructor (creates an empty bipartite graph)
BipartiteGraph() : _nb1(), _nb2() {}
- /// Copy constructor
- BipartiteGraph( const BipartiteGraph & x ) : _nb1(x._nb1), _nb2(x._nb2) {}
-
- /// Assignment operator
- BipartiteGraph & operator=( const BipartiteGraph & x ) {
- if( this != &x ) {
- _nb1 = x._nb1;
- _nb2 = x._nb2;
- }
- return *this;
- }
-
- /// Create bipartite graph from a range of edges.
- /** nr1 is the number of nodes of type 1, nr2 the number of nodes of type 2.
- * The value_type of an EdgeInputIterator should be Edge.
- */
- template<typename EdgeInputIterator>
- void create( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end );
-
- /// Construct bipartite graph from a range of edges.
- /** nr1 is the number of nodes of type 1, nr2 the number of nodes of type 2.
- * The value_type of an EdgeInputIterator should be Edge.
+ /// Constructs BipartiteGraph from a range of edges.
+ /** \tparam EdgeInputIterator Iterator that iterates over instances of BipartiteGraph::Edge.
+ * \param nrNodes1 The number of nodes of type 1.
+ * \param nrNodes2 The number of nodes of type 2.
+ * \param begin Points to the first edge.
+ * \param end Points just beyond the last edge.
*/
template<typename EdgeInputIterator>
- BipartiteGraph( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) : _nb1( nr1 ), _nb2( nr2 ) {
- create( nr1, nr2, begin, end );
+ BipartiteGraph( size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end ) : _nb1(), _nb2() {
+ construct( nrNodes1, nrNodes2, begin, 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];
}
+ //@}
+
+ /// \name Adding nodes and edges
+ //@{
+ /// (Re)constructs BipartiteGraph from a range of edges.
+ /** \tparam EdgeInputIterator Iterator that iterates over instances of BipartiteGraph::Edge.
+ * \param nrNodes1 The number of nodes of type 1.
+ * \param nrNodes2 The number of nodes of type 2.
+ * \param begin Points to the first edge.
+ * \param end Points just beyond the last edge.
+ */
+ template<typename EdgeInputIterator>
+ void construct( size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end );
- /// 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
- size_t nrEdges() const {
- size_t sum = 0;
- for( size_t i1 = 0; i1 < nr1(); i1++ )
- sum += nb1(i1).size();
- return sum;
- }
-
- /// Add node of type 1 without neighbors.
- void add1() { _nb1.push_back( Neighbors() ); }
-
- /// Add node of type 2 without neighbors.
- void add2() { _nb2.push_back( Neighbors() ); }
+ /// Adds a node of type 1 without neighbors and returns the index of the added node.
+ size_t addNode1() { _nb1.push_back( Neighbors() ); return _nb1.size() - 1; }
- /// Add node of type 1 with neighbors specified by a range.
- /** The value_type of an NodeInputIterator should be a size_t, corresponding to
- * the indices of nodes of type 2 that should become neighbors of the added node.
- * For improved efficiency, the size of the range may be specified by sizeHint.
+ /// Adds a node of type 2 without neighbors and returns the index of the added node.
+ size_t addNode2() { _nb2.push_back( Neighbors() ); return _nb2.size() - 1; }
+
+
+ /// Adds a node of type 1 without neighbors and returns the index of the added node.
+ /** \deprecated Please use dai::BipartiteGraph::addNode1() instead.
+ */
+ size_t add1() { return addNode1(); }
+
+ /// Adds a node of type 2 without neighbors and returns the index of the added node.
+ /** \deprecated Please use dai::BipartiteGraph::addNode2() instead.
+ */
+ size_t add2() { return addNode2(); }
+
+ /// 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 \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 \a sizeHint.
+ * \returns Index of the added node.
*/
template <typename NodeInputIterator>
- void add1( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
+ size_t addNode1( 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 < nrNodes2() );
Neighbor nb1new( iter, *it, nb2(*it).size() );
- Neighbor nb2new( nb2(*it).size(), nr1(), iter++ );
+ Neighbor nb2new( nb2(*it).size(), nrNodes1(), iter++ );
nbs1new.push_back( nb1new );
nb2( *it ).push_back( nb2new );
}
_nb1.push_back( nbs1new );
+ return _nb1.size() - 1;
}
- /// Add node of type 2 with neighbors specified by a range.
- /** The value_type of an NodeInputIterator should be a size_t, corresponding to
- * the indices of nodes of type 1 that should become neighbors of the added node.
- * For improved efficiency, the size of the range may be specified by sizeHint.
+ /// 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 \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 \a sizeHint.
+ * \returns Index of the added node.
*/
template <typename NodeInputIterator>
- void add2( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
+ size_t addNode2( 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 < nrNodes1() );
Neighbor nb2new( iter, *it, nb1(*it).size() );
- Neighbor nb1new( nb1(*it).size(), nr2(), iter++ );
+ Neighbor nb1new( nb1(*it).size(), nrNodes2(), iter++ );
nbs2new.push_back( nb2new );
nb1( *it ).push_back( nb1new );
}
_nb2.push_back( nbs2new );
+ return _nb2.size() - 1;
}
- /// Remove node n1 of type 1 and all incident edges.
- void erase1( size_t n1 );
+ /// Adds a node of type 1, with neighbors specified by a range of nodes of type 2.
+ /** \deprecated Please use dai::BipartiteGraph::addNode1( NodeInputIterator, NodeInputIterator, size_t) instead.
+ */
+ template <typename NodeInputIterator>
+ size_t add1( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
+ return addNode1( begin, end, sizeHint );
+ }
- /// Remove node n2 of type 2 and all incident edges.
- void erase2( size_t n2 );
+ /// Adds a node of type 2, with neighbors specified by a range of nodes of type 1.
+ /** \deprecated Please use dai::BipartiteGraph::addNode2( NodeInputIterator, NodeInputIterator, size_t) instead.
+ */
+ template <typename NodeInputIterator>
+ size_t add2( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
+ return addNode2( begin, end, sizeHint );
+ }
+
+ /// 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 );
+ //@}
- /// Add 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.
+ /// \name Erasing nodes and edges
+ //@{
+ /// Removes node \a n1 of type 1 and all incident edges; indices of other nodes are changed accordingly.
+ void eraseNode1( size_t n1 );
+
+ /// Removes node \a n2 of type 2 and all incident edges; indices of other nodes are changed accordingly.
+ void eraseNode2( size_t n2 );
+
+ /// Removes node \a n1 of type 1 and all incident edges; indices of other nodes are changed accordingly.
+ /** \deprecated Please use dai::BipartiteGraph::eraseNode1(size_t) instead.
*/
- 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 );
- }
+ void erase1( size_t n1 ) { eraseNode1( n1 ); }
+
+ /// Removes node \a n2 of type 2 and all incident edges; indices of other nodes are changed accordingly.
+ /** \deprecated Please use dai::BipartiteGraph::eraseNode2(size_t) instead.
+ */
+ void erase2( size_t n2 ) { eraseNode2( n2 ); }
+
+ /// 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 nrNodes1() const { return _nb1.size(); }
+ /// Returns number of nodes of type 2
+ size_t nrNodes2() const { return _nb2.size(); }
+
+ /// Returns number of nodes of type 1
+ /** \deprecated Please use dai::BipartiteGraph::nrNodes1() instead.
+ */
+ size_t nr1() const { return nrNodes1(); }
+
+ /// Returns number of nodes of type 2
+ /** \deprecated Please use dai::BipartiteGraph::nrNodes2() instead.
+ */
+ size_t nr2() const { return nrNodes2(); }
+
+ /// Calculates the number of edges, time complexity: O(nrNodes1())
+ size_t nrEdges() const {
+ size_t sum = 0;
+ for( size_t i1 = 0; i1 < nrNodes1(); i1++ )
+ sum += nb1(i1).size();
+ return sum;
}
- /// Calculate second-order neighbors (i.e., neighbors of neighbors) of node n1 of type 1.
- /** If include == true, include n1 itself, otherwise exclude n1.
+ /// Calculates second-order 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<size_t> delta1( size_t n1, bool include = false ) const;
- /// Calculate second-order neighbors (i.e., neighbors of neighbors) of node n2 of type 2.
- /** If include == true, include n2 itself, otherwise exclude n2.
+ /// Calculates second-order 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<size_t> delta2( size_t n2, bool include = false ) const;
bool isConnected() const;
/// Returns true if the graph is a tree, i.e., if it is singly connected and connected.
- /** This is equivalent to whether for each pair of vertices in the graph, there exists
- * a unique path in the graph that starts at the first and ends at the second vertex.
- */
bool isTree() const;
- /// Stream to output stream os in graphviz .dot syntax
- void display( std::ostream& os ) const;
-
/// Checks internal consistency
- void check() const;
+ void checkConsistency() const;
+ //@}
+
+ /// \name Input and output
+ //@{
+ /// Writes this BipartiteGraph to an output stream in GraphViz .dot syntax
+ void printDot( std::ostream& os ) const;
+ //@}
};
template<typename EdgeInputIterator>
-void BipartiteGraph::create( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) {
+void BipartiteGraph::construct( size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end ) {
_nb1.clear();
- _nb1.resize( nr1 );
+ _nb1.resize( nrNodes1 );
_nb2.clear();
- _nb2.resize( nr2 );
+ _nb2.resize( nrNodes2 );
for( EdgeInputIterator e = begin; e != end; e++ ) {
#ifdef DAI_DEBUG
} // end of namespace dai
+/** \example example_bipgraph.cpp
+ * This example deals with the following bipartite graph:
+ * \dot
+ * graph example {
+ * ordering=out;
+ * subgraph cluster_type1 {
+ * node[shape=circle,width=0.4,fixedsize=true,style=filled];
+ * 12 [label="2"];
+ * 11 [label="1"];
+ * 10 [label="0"];
+ * }
+ * subgraph cluster_type2 {
+ * node[shape=polygon,regular=true,sides=4,width=0.4,fixedsize=true,style=filled];
+ * 21 [label="1"];
+ * 20 [label="0"];
+ * }
+ * 10 -- 20;
+ * 11 -- 20;
+ * 12 -- 20;
+ * 11 -- 21;
+ * 12 -- 21;
+ * }
+ * \enddot
+ * 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.
+ *
+ * \section Output
+ * \verbinclude examples/example_bipgraph.out
+ *
+ * \section Source
+ */
+
+
#endif
projects / libdai.git / blobdiff