+* Fixed bug in BipartiteGraph::eraseEdge()
+* Added python and octave ports for examples/example_sprinkler.cpp
+* [Patrick Pletscher] Added SWIG wrapper code for python and octave
* Added init parameter to HAK/GBP to allow for random initialization
* Replaced the standard assert() macro by DAI_ASSERT, which throws a
dai::Exception and is even active if NDEBUG is defined
--- /dev/null
+BODY,H1,H2,H3,H4,H5,H6,P,CENTER,TD,TH,UL,DL,DIV {
+ font-family: Geneva, Arial, Helvetica, sans-serif;
+}
+EM {
+ color: #602020;
+}
+BODY,TD {
+ font-size: 90%;
+}
+H1 {
+ text-align: center;
+ font-size: 160%;
+}
+H2 {
+ font-size: 120%;
+}
+H3 {
+ font-size: 100%;
+}
+CAPTION {
+ font-weight: bold
+}
+DIV.qindex {
+ width: 100%;
+ background-color: #e8eef2;
+ border: 1px solid #84b0c7;
+ text-align: center;
+ margin: 2px;
+ padding: 2px;
+ line-height: 140%;
+}
+DIV.navpath {
+ width: 100%;
+ background-color: #e8eef2;
+ border: 1px solid #84b0c7;
+ text-align: center;
+ margin: 2px;
+ padding: 2px;
+ line-height: 140%;
+}
+DIV.navtab {
+ background-color: #e8eef2;
+ border: 1px solid #84b0c7;
+ text-align: center;
+ margin: 2px;
+ margin-right: 15px;
+ padding: 2px;
+}
+TD.navtab {
+ font-size: 70%;
+}
+A.qindex {
+ text-decoration: none;
+ font-weight: bold;
+ color: #1A419D;
+}
+A.qindex:visited {
+ text-decoration: none;
+ font-weight: bold;
+ color: #1A419D
+}
+A.qindex:hover {
+ text-decoration: none;
+ background-color: #ddddff;
+}
+A.qindexHL {
+ text-decoration: none;
+ font-weight: bold;
+ background-color: #6666cc;
+ color: #ffffff;
+ border: 1px double #9295C2;
+}
+A.qindexHL:hover {
+ text-decoration: none;
+ background-color: #6666cc;
+ color: #ffffff;
+}
+A.qindexHL:visited {
+ text-decoration: none;
+ background-color: #6666cc;
+ color: #ffffff
+}
+A.el {
+ text-decoration: none;
+ font-weight: bold
+}
+A.elRef {
+ font-weight: bold
+}
+A.code:link {
+ text-decoration: none;
+ font-weight: normal;
+ color: #0000FF
+}
+A.code:visited {
+ text-decoration: none;
+ font-weight: normal;
+ color: #0000FF
+}
+A.codeRef:link {
+ font-weight: normal;
+ color: #0000FF
+}
+A.codeRef:visited {
+ font-weight: normal;
+ color: #0000FF
+}
+A:hover {
+ text-decoration: none;
+ background-color: #f2f2ff
+}
+DL.el {
+ margin-left: -1cm
+}
+.fragment {
+ font-family: monospace, fixed;
+ font-size: 95%;
+}
+PRE.fragment {
+ border: 1px solid #CCCCCC;
+ background-color: #f5f5f5;
+ margin-top: 4px;
+ margin-bottom: 4px;
+ margin-left: 2px;
+ margin-right: 8px;
+ padding-left: 6px;
+ padding-right: 6px;
+ padding-top: 4px;
+ padding-bottom: 4px;
+}
+DIV.ah {
+ background-color: black;
+ font-weight: bold;
+ color: #ffffff;
+ margin-bottom: 3px;
+ margin-top: 3px
+}
+
+DIV.groupHeader {
+ margin-left: 16px;
+ margin-top: 12px;
+ margin-bottom: 6px;
+ font-weight: bold;
+}
+DIV.groupText {
+ margin-left: 16px;
+ font-style: italic;
+ font-size: 90%
+}
+BODY {
+ background: white;
+ color: black;
+ margin-right: 20px;
+ margin-left: 20px;
+}
+TD.indexkey {
+ background-color: #e8eef2;
+ font-weight: bold;
+ padding-right : 10px;
+ padding-top : 2px;
+ padding-left : 10px;
+ padding-bottom : 2px;
+ margin-left : 0px;
+ margin-right : 0px;
+ margin-top : 2px;
+ margin-bottom : 2px;
+ border: 1px solid #CCCCCC;
+}
+TD.indexvalue {
+ background-color: #e8eef2;
+ font-style: italic;
+ padding-right : 10px;
+ padding-top : 2px;
+ padding-left : 10px;
+ padding-bottom : 2px;
+ margin-left : 0px;
+ margin-right : 0px;
+ margin-top : 2px;
+ margin-bottom : 2px;
+ border: 1px solid #CCCCCC;
+}
+TR.memlist {
+ background-color: #f0f0f0;
+}
+P.formulaDsp {
+ text-align: center;
+}
+IMG.formulaDsp {
+}
+IMG.formulaInl {
+ vertical-align: middle;
+}
+SPAN.keyword { color: #008000 }
+SPAN.keywordtype { color: #604020 }
+SPAN.keywordflow { color: #e08000 }
+SPAN.comment { color: #800000 }
+SPAN.preprocessor { color: #806020 }
+SPAN.stringliteral { color: #002080 }
+SPAN.charliteral { color: #008080 }
+SPAN.vhdldigit { color: #ff00ff }
+SPAN.vhdlchar { color: #000000 }
+SPAN.vhdlkeyword { color: #700070 }
+SPAN.vhdllogic { color: #ff0000 }
+
+.mdescLeft {
+ padding: 0px 8px 4px 8px;
+ font-size: 80%;
+ font-style: italic;
+ background-color: #FAFAFA;
+ border-top: 1px none #E0E0E0;
+ border-right: 1px none #E0E0E0;
+ border-bottom: 1px none #E0E0E0;
+ border-left: 1px none #E0E0E0;
+ margin: 0px;
+}
+.mdescRight {
+ padding: 0px 8px 4px 8px;
+ font-size: 80%;
+ font-style: italic;
+ background-color: #FAFAFA;
+ border-top: 1px none #E0E0E0;
+ border-right: 1px none #E0E0E0;
+ border-bottom: 1px none #E0E0E0;
+ border-left: 1px none #E0E0E0;
+ margin: 0px;
+}
+.memItemLeft {
+ padding: 1px 0px 0px 8px;
+ margin: 4px;
+ border-top-width: 1px;
+ border-right-width: 1px;
+ border-bottom-width: 1px;
+ border-left-width: 1px;
+ border-top-color: #E0E0E0;
+ border-right-color: #E0E0E0;
+ border-bottom-color: #E0E0E0;
+ border-left-color: #E0E0E0;
+ border-top-style: solid;
+ border-right-style: none;
+ border-bottom-style: none;
+ border-left-style: none;
+ background-color: #FAFAFA;
+ font-size: 80%;
+}
+.memItemRight {
+ padding: 1px 8px 0px 8px;
+ margin: 4px;
+ border-top-width: 1px;
+ border-right-width: 1px;
+ border-bottom-width: 1px;
+ border-left-width: 1px;
+ border-top-color: #E0E0E0;
+ border-right-color: #E0E0E0;
+ border-bottom-color: #E0E0E0;
+ border-left-color: #E0E0E0;
+ border-top-style: solid;
+ border-right-style: none;
+ border-bottom-style: none;
+ border-left-style: none;
+ background-color: #FAFAFA;
+ font-size: 80%;
+}
+.memTemplItemLeft {
+ padding: 1px 0px 0px 8px;
+ margin: 4px;
+ border-top-width: 1px;
+ border-right-width: 1px;
+ border-bottom-width: 1px;
+ border-left-width: 1px;
+ border-top-color: #E0E0E0;
+ border-right-color: #E0E0E0;
+ border-bottom-color: #E0E0E0;
+ border-left-color: #E0E0E0;
+ border-top-style: none;
+ border-right-style: none;
+ border-bottom-style: none;
+ border-left-style: none;
+ background-color: #FAFAFA;
+ font-size: 80%;
+}
+.memTemplItemRight {
+ padding: 1px 8px 0px 8px;
+ margin: 4px;
+ border-top-width: 1px;
+ border-right-width: 1px;
+ border-bottom-width: 1px;
+ border-left-width: 1px;
+ border-top-color: #E0E0E0;
+ border-right-color: #E0E0E0;
+ border-bottom-color: #E0E0E0;
+ border-left-color: #E0E0E0;
+ border-top-style: none;
+ border-right-style: none;
+ border-bottom-style: none;
+ border-left-style: none;
+ background-color: #FAFAFA;
+ font-size: 80%;
+}
+.memTemplParams {
+ padding: 1px 0px 0px 8px;
+ margin: 4px;
+ border-top-width: 1px;
+ border-right-width: 1px;
+ border-bottom-width: 1px;
+ border-left-width: 1px;
+ border-top-color: #E0E0E0;
+ border-right-color: #E0E0E0;
+ border-bottom-color: #E0E0E0;
+ border-left-color: #E0E0E0;
+ border-top-style: solid;
+ border-right-style: none;
+ border-bottom-style: none;
+ border-left-style: none;
+ color: #606060;
+ background-color: #FAFAFA;
+ font-size: 80%;
+}
+.search {
+ color: #003399;
+ font-weight: bold;
+}
+FORM.search {
+ margin-bottom: 0px;
+ margin-top: 0px;
+}
+INPUT.search {
+ font-size: 75%;
+ color: #000080;
+ font-weight: normal;
+ background-color: #e8eef2;
+}
+TD.tiny {
+ font-size: 75%;
+}
+a {
+ color: #1A41A8;
+}
+a:visited {
+ color: #2A3798;
+}
+.dirtab {
+ padding: 4px;
+ border-collapse: collapse;
+ border: 1px solid #84b0c7;
+}
+TH.dirtab {
+ background: #e8eef2;
+ font-weight: bold;
+}
+HR {
+ height: 1px;
+ border: none;
+ border-top: 1px solid black;
+}
+
+/* Style for detailed member documentation */
+.memtemplate {
+ font-size: 80%;
+ color: #606060;
+ font-weight: normal;
+ margin-left: 3px;
+}
+.memnav {
+ background-color: #e8eef2;
+ border: 1px solid #84b0c7;
+ text-align: center;
+ margin: 2px;
+ margin-right: 15px;
+ padding: 2px;
+}
+.memitem {
+ padding: 4px;
+ background-color: #eef3f5;
+ border-width: 1px;
+ border-style: solid;
+ border-color: #dedeee;
+ -moz-border-radius: 8px 8px 8px 8px;
+}
+.memname {
+ white-space: nowrap;
+ font-weight: bold;
+}
+.memdoc{
+ padding-left: 10px;
+}
+.memproto {
+ background-color: #d5e1e8;
+ width: 100%;
+ border-width: 1px;
+ border-style: solid;
+ border-color: #84b0c7;
+ font-weight: bold;
+ -moz-border-radius: 8px 8px 8px 8px;
+}
+.paramkey {
+ text-align: right;
+}
+.paramtype {
+ white-space: nowrap;
+}
+.paramname {
+ color: #602020;
+ font-style: italic;
+ white-space: nowrap;
+}
+/* End Styling for detailed member documentation */
+
+/* for the tree view */
+.ftvtree {
+ font-family: sans-serif;
+ margin:0.5em;
+}
+.directory {
+ font-size: 9pt;
+ font-weight: bold;
+}
+.directory h3 {
+ margin: 0px;
+ margin-top: 1em;
+ font-size: 11pt;
+}
+.directory > h3 {
+ margin-top: 0;
+}
+.directory p {
+ margin: 0px;
+ white-space: nowrap;
+}
+.directory div {
+ display: none;
+ margin: 0px;
+}
+.directory img {
+ vertical-align: -30%;
+}
+
# members were ordinary class members. Constructors, destructors and assignment
# operators of the base classes will not be shown.
-INLINE_INHERITED_MEMB = YES
+INLINE_INHERITED_MEMB = NO
# If the FULL_PATH_NAMES tag is set to YES then Doxygen will prepend the full
# path before files name in the file list and in the header files. If set
# the style sheet file to the HTML output directory, so don't put your own
# stylesheet in the HTML output directory as well, or it will be erased!
-HTML_STYLESHEET =
+HTML_STYLESHEET = customdoxygen.css
# If the HTML_ALIGN_MEMBERS tag is set to YES, the members of classes,
# files or namespaces will be aligned in HTML using tables. If set to
/// \file
-/// \brief Defines BipartiteGraph class
+/// \brief Defines the BipartiteGraph class
#ifndef __defined_libdai_bipgraph_h
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
* 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
+ * 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.
* 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
+ * 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<Neighbor>, 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 ("_").
* \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
+ * <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);
* 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
/// 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; }
};
std::vector<Edge> _edges;
/// Call indexEdges() first to initialize these members
hash_map<Edge,size_t> _vv2e;
- //}@
+ //@}
public:
+ /// @name Constructors and destructors
+ //@{
/// Default constructor (creates an empty bipartite graph)
BipartiteGraph() : _nb1(), _nb2(), _edge_indexed(false) {}
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<typename EdgeInputIterator>
- 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
+ /// @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 ) {
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
+ /// 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
+ /// 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
+ /// 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
+ /// 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
+ /// 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
+ /// 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;
- }
+ /// @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<typename EdgeInputIterator>
+ void construct( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end );
- /// Adds a node of type 1 without neighbors.
- void add1() { _nb1.push_back( Neighbors() ); }
+ /// 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.
- void add2() { _nb2.push_back( Neighbors() ); }
+ /// 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 <typename NodeInputIterator>
- 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;
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 <typename NodeInputIterator>
- 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;
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 );
- /// Removes edge between node n1 of type 1 and node n2 of type 2.
- void eraseEdge( size_t n1, size_t n2 ) {
- DAI_ASSERT( n1 < nr1() );
- DAI_ASSERT( n2 < nr2() );
- for( Neighbors::iterator i1 = _nb1[n1].begin(); i1 != _nb1[n1].end(); i1++ )
- if( i1->node == n2 ) {
- _nb1[n1].erase( i1 );
- break;
- }
- for( Neighbors::iterator i2 = _nb2[n2].begin(); i2 != _nb2[n2].end(); i2++ )
- if( i2->node == n1 ) {
- _nb2[n2].erase( i2 );
- break;
- }
- }
+ /// Removes edge between node \a n1 of type 1 and node \a n2 of type 2.
+ void eraseEdge( size_t n1, 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 ) {
- DAI_ASSERT( n1 < nr1() );
- DAI_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 );
- }
+ /// @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 second-order neighbors (i.e., neighbors of neighbors) of node n1 of type 1.
- /** If include == true, includes n1 itself, otherwise excludes 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;
- /// Calculates second-order neighbors (i.e., neighbors of neighbors) of node n2 of type 2.
- /** If include == true, includes n2 itself, otherwise excludes 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;
/// 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;
+ //@}
// OBSOLETE
- /// @name Backwards compatibility layer (to be removed soon)
- //@{
+ /// @name Backwards compatibility layer (to be removed soon)
+ //@{
void indexEdges() {
std::cerr << "Warning: this BipartiteGraph edge interface is obsolete!" << std::endl;
_edges.clear();
DAI_ASSERT(_edge_indexed);
return _edges.size();
}
- //}@
-
- private:
- /// Checks internal consistency
- void check() const;
+ //@}
};
/// \file
/// \brief Defines class BP_dual
/// \todo This replicates a large part of the functionality of BP; would it not be shorter to adapt BP instead?
+/// \todo Improve documentation
#ifndef __defined_libdai_bp_dual_h
/** \file
* \brief Contains additional doxygen documentation
*
+ * \todo Improve documentation
+ *
* \todo Merge COPYING into doxygen documentation
* \todo Merge README into doxygen documentation
* \todo Document examples, tests and utils
*
* \todo Use "gcc -MM" to generate dependencies for targets: http://make.paulandlesley.org/autodep.html
* \todo Investigate whether switching to cmake as cross-platform build system would be a good idea.
- * \todo Switch from nmake to GNU make under Windows http://gnuwin32.sourceforge.net/
*
* \todo Replace VarSets by SmallSet<size_t> where appropriate, in order to minimize the use of FactorGraph::findVar().
*
*
* \idea Use Boost::uBLAS framework to deal with matrices, especially, with 2D sparse matrices.
* See http://www.boost.org/libs/numeric/ublas/doc/matrix_sparse.htm
+ * I read somewhere that boost::uBLAS concentrates more on correct implementation than on performance.
*
* \idea Introduce naming scheme:
* - all Vars should be named v_..., e.g. v_i instead of i
/// \file
/// \brief Defines classes related to Expectation Maximization: EMAlg, ParameterEstimation, CondProbEstimation and SharedParameters
/// \todo Describe EM file format
+/// \todo Improve documentation
namespace dai {
/// \file
-/// \brief Defines the DAI_ENUM macro
+/// \brief Defines the DAI_ENUM macro, which can be used to define an \c enum with additional functionality.
#ifndef __defined_libdai_enum_h
#include <dai/exceptions.h>
-/// Extends the C++ enum type by supporting input/output streaming and conversion to and from const char* and size_t
+/// Extends the C++ \c enum type by supporting input/output streaming and conversion to and from <tt>const char*</tt> and \c size_t
/** For more details see the source code.
*
* \par Example:
/// \file
/// \brief Defines classes Evidence and Observation
/// \todo Describe tabular data file format
+/// \todo Improve documentation
#ifndef __defined_libdai_evidence_h
/// \file
-/// \brief Defines Exception class and the DAI_THROW macro
-/// \todo Improve documentation
+/// \brief Defines the Exception class and macros for throwing exceptions and doing assertions
#ifndef __defined_libdai_exceptions_h
/// Used by DAI_THROW
#define DAI_TOSTRING(x) DAI_QUOTE(x)
-/// Macro that simplifies throwing an exception with a useful error message.
-/** \param cod Corresponds to one of the enum values in dai::Exception::codes
+/// Macro that simplifies throwing an exception with a useful default error message.
+/** The error message consists of a description of the exception, the source
+ * code file and line number where the exception has been thrown.
+ * \param cod Corresponds to one of the enum values of dai::Exception::Code
*
- * Example:
+ * \par Example:
* \code
* DAI_THROW(NOT_IMPLEMENTED);
* \endcode
*/
#define DAI_THROW(cod) throw dai::Exception(dai::Exception::cod, std::string(__FILE__ ", line " DAI_TOSTRING(__LINE__)))
-/// Macro that simplifies throwing an exception with a useful error message. It also allows for writing a detailed error message to stderr.
-/** \param cod Corresponds to one of the enum values in dai::Exception::codes
+/// Macro that simplifies throwing an exception with a user-defined error message.
+/** \param cod Corresponds to one of the enum values of dai::Exception::Code
* \param msg Detailed error message that will be written to std::cerr.
*
- * Example:
+ * \par Example:
* \code
* DAI_THROWE(NOT_IMPLEMENTED,"Detailed error message");
* \endcode
*/
#define DAI_THROWE(cod,msg) throw dai::Exception(dai::Exception::cod, std::string(__FILE__ ", line " DAI_TOSTRING(__LINE__)), msg)
-/// Assertion mechanism, similar to the standard assert() macro, but is always active, even if NDEBUG is defined
-#define DAI_ASSERT(condition) ((condition) ? ((void)0) : DAI_THROWE(ASSERTION_FAILED, #condition))
+/// Assertion mechanism, similar to the standard assert() macro. It is always active, even if NDEBUG is defined
+#define DAI_ASSERT(condition) ((condition) ? ((void)0) : DAI_THROWE(ASSERTION_FAILED, std::string("Assertion \"" #condition "\" failed")))
// Assertion only if DAI_DEBUG is defined
#ifdef DAI_DEBUG
namespace dai {
-/// Represents an exception (based on std::runtime_error)
+/// Error handling in libDAI is done by throwing an instance of the Exception class.
+/** The Exception class inherits from std::runtime_error. It defines several types of exceptions
+ * and corresponding error messages. The recommended way to throw an instance of the Exception
+ * class is by using the #DAI_THROW or #DAI_THROWE macros.
+ */
class Exception : public std::runtime_error {
public:
/// Enumeration of exceptions used in libDAI
- enum Code {ASSERTION_FAILED,
- NOT_IMPLEMENTED,
+ enum Code {NOT_IMPLEMENTED,
+ ASSERTION_FAILED,
+ IMPOSSIBLE_TYPECAST,
+ OBJECT_NOT_FOUND,
+ UNKNOWN_ENUM_VALUE,
UNKNOWN_DAI_ALGORITHM,
+ UNKNOWN_PARAMETER_ESTIMATION_METHOD,
UNKNOWN_PROPERTY_TYPE,
MALFORMED_PROPERTY,
- UNKNOWN_ENUM_VALUE,
+ NOT_ALL_PROPERTIES_SPECIFIED,
CANNOT_READ_FILE,
CANNOT_WRITE_FILE,
INVALID_FACTORGRAPH_FILE,
- NOT_ALL_PROPERTIES_SPECIFIED,
+ INVALID_EVIDENCE_FILE,
+ INVALID_EMALG_FILE,
+ NOT_NORMALIZABLE,
MULTIPLE_UNDO,
FACTORGRAPH_NOT_CONNECTED,
- IMPOSSIBLE_TYPECAST,
INTERNAL_ERROR,
RUNTIME_ERROR,
- NOT_NORMALIZABLE,
- INVALID_EVIDENCE_FILE,
- INVALID_EMALG_FILE,
- UNKNOWN_PARAMETER_ESTIMATION_METHOD,
- OBJECT_NOT_FOUND,
NUM_ERRORS}; // NUM_ERRORS should be the last entry
/// Constructor
std::cerr << "ERROR: " << detailedMsg << std::endl;
}
- /// Copy constructor
- Exception( const Exception &e ) : std::runtime_error(e), errorcode(e.errorcode) {}
-
/// Returns error code of this exception
Code code() const { return errorcode; }
+ /// Returns error message corresponding to an error code
+ const std::string &message( const Code c ) const { return ErrorStrings[c]; }
+
private:
/// Contains the error code of this exception
/// \file
/// \brief Defines TFactor<T> and Factor classes
+/// \todo Improve documentation
#ifndef __defined_libdai_factor_h
void indexEdges() { G.indexEdges(); }
size_t nr_edges() const { return G.nr_edges(); }
const std::vector<Edge>& edges() const { return G.edges(); }
- //}@
+ //@}
private:
/// Part of constructors (creates edges, neighbors and adjacency matrix)
/// \file
/// \brief Defines TProb<T> and Prob classes
/// \todo Rename to Vector<T>
+/// \todo Check documentation
#ifndef __defined_libdai_prob_h
/// \file
-/// \brief Defines SmallSet<T> class
+/// \brief Defines the SmallSet<T> class, which represents a set; the implementation is optimized for a small number of elements.
+/// \todo Check documentation
#ifndef __defined_libdai_smallset_h
std::vector<T> _elements;
public:
+ /// @name Constructors and destructors
+ //@{
/// Default constructor (construct an empty set)
SmallSet() : _elements() {}
typename std::vector<T>::iterator new_end = std::unique( _elements.begin(), _elements.end() );
_elements.erase( new_end, _elements.end() );
}
+ //@}
+ /// @name Operators for set-theoretic operations
+ //@{
/// Set-minus operator: returns all elements in *this, except those in x
SmallSet operator/ ( const SmallSet& x ) const {
SmallSet res;
bool operator>> ( const SmallSet& x ) const {
return std::includes( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end() );
}
+ //@}
+ /// @name Queries
+ //@{
/// Returns true if *this and x have elements in common
bool intersects( const SmallSet& x ) const {
return( (*this & x).size() > 0 );
return std::binary_search( _elements.begin(), _elements.end(), t );
}
+ /// Returns number of elements
+ typename std::vector<T>::size_type size() const { return _elements.size(); }
+
+ /// Returns whether the SmallSet is empty
+ bool empty() const { return _elements.size() == 0; }
+ //@}
+
/// Constant iterator over the elements
typedef typename std::vector<T>::const_iterator const_iterator;
/// Iterator over the elements
/// Reverse iterator over the elements
typedef typename std::vector<T>::reverse_iterator reverse_iterator;
+ /// @name Iterator interface
+ //@{
/// Returns iterator that points to the first element
iterator begin() { return _elements.begin(); }
/// Returns constant iterator that points to the first element
reverse_iterator rend() { return _elements.rend(); }
/// Returns constant reverse iterator that points beyond the first element
const_reverse_iterator rend() const { return _elements.rend(); }
+ //@}
- /// Returns number of elements
- typename std::vector<T>::size_type size() const { return _elements.size(); }
-
- /// Returns whether the SmallSet is empty
- bool empty() const { return _elements.size() == 0; }
-
+ /// @name Comparison operators
+ //@{
/// Returns true if a and b are identical
friend bool operator==( const SmallSet &a, const SmallSet &b ) {
return (a._elements == b._elements);
friend bool operator<( const SmallSet &a, const SmallSet &b ) {
return a._elements < b._elements;
}
+ //@}
};
/// \file
-/// \brief Defines class Var
+/// \brief Defines class Var, which represents a discrete random variable.
#ifndef __defined_libdai_var_h
/** A Var stores the \a label of the variable (an integer-valued unique ID)
* and the number of possible values (\a states) of that variable. Two
* Var objects with the same label are assumed to be identical (i.e., it
- * is assumed that their states are also the same).
+ * is assumed that they have the same number of possible states).
*
- * In this manual, we use the following notational conventions. The discrete
+ * In the documentation, we use the following notational conventions. The discrete
* random variable with label \f$l\f$ is denoted as \f$x_l\f$, and the number
* of possible values of this variable as \f$S_l\f$; this is represented in
* code by the object Var(\f$l\f$,\f$S_l\f$). The set of possible values of
size_t _states;
public:
- /// Default constructor
+ /// Default constructor (creates a variable with label -1 and 0 states)
Var() : _label(-1), _states(0) {}
- /// Constructor
+ /// Constructs a variable with a given label and number of states
Var( long label, size_t states ) : _label(label), _states(states) {}
/// Returns the label
/// Returns reference to number of states
size_t& states () { return _states; }
- /// Smaller-than operator (compares only labels)
+ /// Smaller-than operator (only compares labels)
bool operator < ( const Var& n ) const { return( _label < n._label ); }
- /// Larger-than operator (compares only labels)
+ /// Larger-than operator (only compares labels)
bool operator > ( const Var& n ) const { return( _label > n._label ); }
/// Smaller-than-or-equal-to operator (only compares labels)
bool operator <= ( const Var& n ) const {
/// \file
-/// \brief Defines VarSet class
+/// \brief Defines the VarSet class, which represents a set of random variables.
#ifndef __defined_libdai_varset_h
*/
class VarSet : public SmallSet<Var> {
public:
- /// Default constructor
+ /// @name Constructors and destructors
+ //@{
+ /// Default constructor (constructs an empty set)
VarSet() : SmallSet<Var>() {}
- /// Construct from SmallSet<Var>
+ /// Construct from \link SmallSet \endlink<\link Var \endlink> \a x
VarSet( const SmallSet<Var> &x ) : SmallSet<Var>(x) {}
- /// Calculates the number of states of this VarSet.
+ /// Construct a VarSet with one element, \a v
+ VarSet( const Var &v ) : SmallSet<Var>(v) {}
+
+ /// Construct a VarSet with two elements, \a v1 and \a v2
+ VarSet( const Var &v1, const Var &v2 ) : SmallSet<Var>(v1,v2) {}
+
+ /// Construct a VarSet from the range between \a begin and \a end.
+ /** \tparam VarIterator Iterates over instances of type Var.
+ * \param begin Points to first Var to be added.
+ * \param end Points just beyond last Var to be added.
+ * \param sizeHint For efficiency, the number of elements can be speficied by \a sizeHint.
+ */
+ template <typename VarIterator>
+ VarSet( VarIterator begin, VarIterator end, size_t sizeHint=0 ) : SmallSet<Var>(begin,end,sizeHint) {}
+ //@}
+
+ /// @name Queries
+ //@{
+ /// Calculates the number of states of this VarSet, which is simply the number of possible joint states of the variables in \c *this.
/** The number of states of the Cartesian product of the variables in this VarSet
* is simply the product of the number of states of each variable in this VarSet.
- * If *this corresponds with the set \f$\{x_l\}_{l\in L}\f$,
+ * If \c *this corresponds with the set \f$\{x_l\}_{l\in L}\f$,
* where variable \f$x_l\f$ has label \f$l\f$, and denoting by \f$S_l\f$ the
* number of possible values ("states") of variable \f$x_l\f$, the number of
* joint configurations of the variables in \f$\{x_l\}_{l\in L}\f$ is given by \f$\prod_{l\in L} S_l\f$.
return states;
}
- /// Construct a VarSet with one element
- VarSet( const Var &n ) : SmallSet<Var>(n) {}
-
- /// Construct a VarSet with two elements
- VarSet( const Var &n1, const Var &n2 ) : SmallSet<Var>(n1,n2) {}
-
- /// Construct a VarSet from a range.
- /** \tparam VarIterator Iterates over instances of type Var.
- * \param begin Points to first Var to be added.
- * \param end Points just beyond last Var to be added.
- * \param sizeHint For efficiency, the number of elements can be speficied by sizeHint.
- */
- template <typename VarIterator>
- VarSet( VarIterator begin, VarIterator end, size_t sizeHint=0 ) : SmallSet<Var>(begin,end,sizeHint) {}
-
- /// Calculates the linear index in the Cartesian product of the variables in *this, which corresponds to a particular joint assignment of the variables specified by \a states.
+ /// Calculates the linear index in the Cartesian product of the variables in \c *this that corresponds to a particular joint assignment of the variables, specified by \a states.
/** \param states Specifies the states of some variables.
- * \return The linear index in the Cartesian product of the variables in *this
- * corresponding with the joint assignment specified by \a states, where it is
- * assumed that \a states[\a m]==0 for all \a m in *this which are not in \a states.
+ * \return The linear index in the Cartesian product of the variables in \c *this
+ * corresponding with the joint assignment specified by \a states, where variables
+ * for which no state is specified are assumed to be in state 0.
*
- * The linear index is calculated as follows. The variables in *this are
- * ordered according to their label (in ascending order); say *this corresponds with
+ * The linear index is calculated as follows. The variables in \c *this are
+ * ordered according to their label (in ascending order); say \c *this corresponds with
* the set \f$\{x_{l(0)},x_{l(1)},\dots,x_{l(n-1)}\}\f$ with \f$l(0) < l(1) < \dots < l(n-1)\f$,
* where variable \f$x_l\f$ has label \a l. Denote by \f$S_l\f$ the number of possible values
* ("states") of variable \f$x_l\f$. The argument \a states corresponds
* with a mapping \a s that assigns to each variable \f$x_l\f$ a state \f$s(x_l) \in \{0,1,\dots,S_l-1\}\f$,
- * where \f$s(x_l)=0\f$ if \f$x_l\f$ is not specified in \a states. The linear index \a S corresponding
- * with \a states is now calculated as:
+ * where \f$s(x_l)=0\f$ if \f$x_l\f$ is not specified in \a states. The linear index \f$S\f$ corresponding
+ * with \a states is now calculated by:
* \f{eqnarray*}
* S &:=& \sum_{i=0}^{n-1} s(x_{l(i)}) \prod_{j=0}^{i-1} S_{l(j)} \\
* &= & s(x_{l(0)}) + s(x_{l(1)}) S_{l(0)} + s(x_{l(2)}) S_{l(0)} S_{l(1)} + \dots + s(x_{l(n-1)}) S_{l(0)} \cdots S_{l(n-2)}.
* \f}
*
- * \note If *this corresponds with \f$\{x_l\}_{l\in L}\f$, and \a states specifies a state
- * for each variable \f$x_l\f$ for \f$l\in L\f$, calcState(const std::map<Var,size_t> &) induces a mapping
+ * \note If \c *this corresponds with \f$\{x_l\}_{l\in L}\f$, and \a states specifies a state
+ * for each variable \f$x_l\f$ for \f$l\in L\f$, calcState() induces a mapping
* \f$\sigma : \prod_{l\in L} X_l \to \{0,1,\dots,\prod_{l\in L} S_l-1\}\f$ that
* maps a joint state to a linear index; this is the inverse of the mapping
- * \f$\sigma^{-1}\f$ induced by calcStates(size_t).
+ * \f$\sigma^{-1}\f$ induced by calcStates().
*/
size_t calcState( const std::map<Var, size_t> &states ) {
size_t prod = 1;
return state;
}
- /// Calculates the joint assignment of the variables in *this corresponding to the linear index \a linearState.
+ /// Calculates the joint assignment of the variables in \c *this corresponding to the linear index \a linearState.
/** \param linearState should be smaller than nrStates().
- * \return A mapping \f$s\f$ that maps each Var \f$x_l\f$ in *this to its state \f$s(x_l)\f$, as specified by \a linearState.
+ * \return A mapping \f$s\f$ that maps each Var \f$x_l\f$ in \c *this to its state \f$s(x_l)\f$, as specified by \a linearState.
*
- * The variables in *this are ordered according to their label (in ascending order); say *this corresponds with
+ * The variables in \c *this are ordered according to their label (in ascending order); say \c *this corresponds with
* the set \f$\{x_{l(0)},x_{l(1)},\dots,x_{l(n-1)}\}\f$ with \f$l(0) < l(1) < \dots < l(n-1)\f$,
* where variable \f$x_l\f$ has label \a l. Denote by \f$S_l\f$ the number of possible values
* ("states") of variable \f$x_l\f$ with label \a l.
- * The mapping \a s returned by this function is defined as:
+ * The mapping \f$s\f$ returned by this function is defined as:
* \f{eqnarray*}
* s(x_{l(i)}) = \left\lfloor\frac{S \mbox { mod } \prod_{j=0}^{i} S_{l(j)}}{\prod_{j=0}^{i-1} S_{l(j)}}\right\rfloor \qquad \mbox{for all $i=0,\dots,n-1$}.
* \f}
* where \f$S\f$ denotes the value of \a linearState.
*
- * \note If *this corresponds with \f$\{x_l\}_{l\in L}\f$, calcStates(size_t) induces a mapping
+ * \note If \c *this corresponds with \f$\{x_l\}_{l\in L}\f$, calcStates() induces a mapping
* \f$\sigma^{-1} : \{0,1,\dots,\prod_{l\in L} S_l-1\} \to \prod_{l\in L} X_l\f$ that
* maps a linear index to a joint state; this is the inverse of the mapping \f$\sigma\f$
- * induced by calcState(const std::map<Var,size_t> &).
+ * induced by calcState().
*/
std::map<Var, size_t> calcStates( size_t linearState ) {
std::map<Var, size_t> states;
DAI_ASSERT( linearState == 0 );
return states;
}
+ //@}
+ /// @name Input and output
+ //@{
/// Writes a VarSet to an output stream
- friend std::ostream& operator<< (std::ostream &os, const VarSet& ns) {
+ friend std::ostream& operator<<( std::ostream &os, const VarSet &vs ) {
os << "{";
- for( VarSet::const_iterator n = ns.begin(); n != ns.end(); n++ )
- os << (n != ns.begin() ? "," : "") << *n;
+ for( VarSet::const_iterator v = vs.begin(); v != vs.end(); v++ )
+ os << (v != vs.begin() ? "," : "") << *v;
os << "}";
return( os );
}
+ //@}
};
using namespace std;
+void BipartiteGraph::addEdge( size_t n1, size_t n2, bool check ) {
+ DAI_ASSERT( n1 < nr1() );
+ DAI_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 BipartiteGraph::erase1( size_t n1 ) {
DAI_ASSERT( n1 < nr1() );
// Erase neighbor entry of node n1
}
+void BipartiteGraph::eraseEdge( size_t n1, size_t n2 ) {
+ DAI_ASSERT( n1 < nr1() );
+ DAI_ASSERT( n2 < nr2() );
+ size_t iter;
+ // Search for edge among neighbors of n1
+ for( iter = 0; iter < nb1(n1).size(); iter++ )
+ if( nb1(n1, iter).node == n2 ) {
+ // Remove it
+ nb1(n1).erase( nb1(n1).begin() + iter );
+ break;
+ }
+ // Change the iter and dual values of the subsequent neighbors
+ for( ; iter < nb1(n1).size(); iter++ ) {
+ Neighbor &m2 = nb1( n1, iter );
+ m2.iter = iter;
+ nb2( m2.node, m2.dual ).dual = iter;
+ }
+ // Search for edge among neighbors of n2
+ for( iter = 0; iter < nb2(n2).size(); iter++ )
+ if( nb2(n2, iter).node == n1 ) {
+ // Remove it
+ nb2(n2).erase( nb2(n2).begin() + iter );
+ break;
+ }
+ // Change the iter and node values of the subsequent neighbors
+ for( ; iter < nb2(n2).size(); iter++ ) {
+ Neighbor &m1 = nb2( n2, iter );
+ m1.iter = iter;
+ nb1( m1.node, m1.dual ).dual = iter;
+ }
+}
+
+
std::vector<size_t> BipartiteGraph::delta1( size_t n1, bool include ) const {
// get all second-order neighbors
std::vector<size_t> result;
}
-void BipartiteGraph::check() const {
+void BipartiteGraph::checkConsistency() const {
size_t N1 = nr1();
size_t N2 = nr2();
for( size_t n1 = 0; n1 < N1; n1++ ) {
std::string Exception::ErrorStrings[NUM_ERRORS] = {
- "Assertion failed",
"Feature not implemented",
+ "Assertion failed",
+ "Impossible typecast",
+ "Requested object not found",
+ "Unknown ENUM value",
"Unknown DAI algorithm",
+ "Unrecognized parameter estimation method",
"Unknown Property type",
"Malformed Property",
- "Unknown ENUM value",
+ "Not all mandatory Properties specified",
"Cannot read file",
"Cannot write file",
"Invalid FactorGraph file",
- "Not all mandatory Properties specified",
+ "Invalid Evidence file",
+ "Invalid Expectation-Maximization file",
+ "Quantity not normalizable",
"Multiple undo levels unsupported",
"FactorGraph is not connected",
- "Impossible typecast",
"Internal error",
- "Runtime error",
- "Quantity not normalizable",
- "Invalid Evidence file",
- "Invalid Expectation-Maximization file",
- "Unrecognized parameter estimation method",
- "Requested object not found"
+ "Runtime error"
};
projects / libdai.git / commitdiff