// blabla
}
A disadvantage of this approach may be worse cachability.
+- BipartiteGraph::isConnected should be optimized.
- http://www.boost.org/development/requirements.html#Design_and_Programming
- Would it be a good idea to cache second-order neighborhoods (delta's) in BipGraph?
- Would it be a good idea to add the variable label -> index hashmap in FactorGraph,
to replace the linear searches that are performed every time for findVar()?
No, a better idea is to avoid calls to findVar() as much as possible.
- Can the FactorGraph constructors be optimized further?
+- Solve the proliferation of type checks for all different ENUM's in
+properties.cpp
TODO FOR RELEASE:
- Test Visual C++ compatibility
utils/createfg.cpp
exceptions.h
exceptions.cpp
+
+DOCUMENTATION READY:
+- bipgraph.h, bipgraph.cpp
+- var.h
# definition is used. Otherwise one should specify the include paths that
# are normally passed to the compiler using the -I flag.
-STRIP_FROM_INC_PATH =
+STRIP_FROM_INC_PATH = include/
# If the SHORT_NAMES tag is set to YES, doxygen will generate much shorter
# (but less readable) file names. This can be useful is your file systems
# If set to NO, the detailed description appears after the member
# documentation.
-DETAILS_AT_TOP = NO
+DETAILS_AT_TOP = YES
# If the INHERIT_DOCS tag is set to YES (the default) then an undocumented
# member inherits the documentation from any documented member that it
# func(std::string) {}). This also make the inheritance and collaboration
# diagrams that involve STL classes more complete and accurate.
-BUILTIN_STL_SUPPORT = NO
+BUILTIN_STL_SUPPORT = YES
# If you use Microsoft's C++/CLI language, you should set this option to YES to
# enable parsing support.
# alphabetically by member name. If set to NO the members will appear in
# declaration order.
-SORT_MEMBER_DOCS = YES
+SORT_MEMBER_DOCS = NO
# If the SORT_BRIEF_DOCS tag is set to YES then doxygen will sort the
# brief documentation of file, namespace and class members alphabetically
# then for each documented function all documented
# functions referencing it will be listed.
-REFERENCED_BY_RELATION = YES
+REFERENCED_BY_RELATION = NO
# If the REFERENCES_RELATION tag is set to YES (the default)
# then for each documented function all documented entities
# called/used by that function will be listed.
-REFERENCES_RELATION = YES
+REFERENCES_RELATION = NO
# If the REFERENCES_LINK_SOURCE tag is set to YES (the default)
# and SOURCE_BROWSER tag is set to YES, then the hyperlinks from
# contain links (just like the HTML output) instead of page references
# This makes the output suitable for online browsing using a pdf viewer.
-PDF_HYPERLINKS = NO
+PDF_HYPERLINKS = YES
# If the USE_PDFLATEX tag is set to YES, pdflatex will be used instead of
# plain latex in the generated Makefile. Set this option to YES to get a
# higher quality PDF documentation.
-USE_PDFLATEX = NO
+USE_PDFLATEX = YES
# If the LATEX_BATCHMODE tag is set to YES, doxygen will add the \\batchmode.
# command to the generated LaTeX files. This will instruct LaTeX to keep
/// A BipartiteGraph represents the neighborhood structure of nodes in a 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.
+ * 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:
+ * each node has a vector of Neighbor entries, which is also known as a Neighbors type.
*/
class BipartiteGraph {
public:
- /// A Neighbor describes a neighboring node of some other node.
+ /// A Neighbor describes a neighboring node of some other node in a BipartiteGraph.
/** Iterating over all neighbors of node n1 of type 1 can be done in the following way:
* \code
* foreach( const BipartiteGraph::Neighbor &n2, nb1(n1) ) {
unsigned node;
/// Contains the "dual" iter
unsigned dual;
- /// Cast to unsigned returns node
+ /// Cast to unsigned returns node member
operator unsigned () const { return node; }
/// Default constructor
Neighbor() {}
/// Neighbors is a vector of Neighbor entries; each node has an associated Neighbors variable, which describes its neighbors.
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.
+ /// 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. It depends on the context whether the first node (with index a) is of type 1 or of type 2.
typedef std::pair<size_t,size_t> Edge;
private:
/// Returns number of nodes of type 2
size_t nr2() const { return _nb2.size(); }
- /// Calculates the number of edges
+ /// Calculates the number of edges, using O(nr1()) time
size_t nrEdges() const {
size_t sum = 0;
for( size_t i1 = 0; i1 < nr1(); i1++ )
*/
class Var {
private:
- /// Internal label of the variable
+ /// Label of the variable (its unique ID)
long _label;
/// Number of possible values
/// Constructor
Var( long label, size_t states ) : _label(label), _states(states) {}
- /// Gets the label
+ /// Returns the label
long label() const { return _label; }
/// Returns reference to label
long & label() { return _label; }
- /// Gets the number of states
+ /// Returns the number of states
size_t states () const { return _states; }
/// Returns reference to number of states
size_t& states () { return _states; }
- /// Smaller-than operator (compares labels)
+ /// Smaller-than operator (only compares labels)
bool operator < ( const Var& n ) const { return( _label < n._label ); }
- /// Larger-than operator (compares labels)
+ /// Larger-than operator (only compares labels)
bool operator > ( const Var& n ) const { return( _label > n._label ); }
- /// Smaller-than-or-equal-to operator (compares labels)
+ /// Smaller-than-or-equal-to operator (only compares labels)
bool operator <= ( const Var& n ) const { return( _label <= n._label ); }
- /// Larger-than-or-equal-to operator (compares labels)
+ /// Larger-than-or-equal-to operator (only compares labels)
bool operator >= ( const Var& n ) const { return( _label >= n._label ); }
- /// Not-equal-to operator (compares labels)
+ /// Not-equal-to operator (only compares labels)
bool operator != ( const Var& n ) const { return( _label != n._label ); }
- /// Equal-to operator (compares labels)
+ /// Equal-to operator (only compares labels)
bool operator == ( const Var& n ) const { return( _label == n._label ); }
- /// Write this Var to stream
+ /// Write a Var to output stream
friend std::ostream& operator << ( std::ostream& os, const Var& n ) {
return( os << "[" << n.label() << "]" );
}
namespace dai {
-/// Represents a set of variables.
+/// A VarSet represents a set of variables.
/**
- * It is implemented as an ordered vector<Var> for efficiency reasons
- * (this is more efficient than a set<Var>). In addition, it provides
- * an interface for common set-theoretic operations.
+ * It is implemented as an ordered std::vector<Var> for efficiency reasons
+ * (indeed, it was found that a std::set<Var> usually has more overhead).
+ * In addition, it provides an interface for common set-theoretic operations.
*/
class VarSet {
- protected:
+ private:
/// The variables in this set
std::vector<Var> _vars;
}
/// Construct from a range of iterators
- /* The value_type of the VarIterator should be Var.
+ /** The value_type of the VarIterator should be Var.
* For efficiency, the number of variables can be
* speficied by sizeHint.
*/
}
- /// Return the product of the number of states of each variable in this set
+ /// Returns the product of the number of states of each variable in this set
size_t states() const {
return _states;
}
- /// Setminus operator (result contains all variables except those in ns)
+ /// Setminus operator (result contains all variables in *this, except those in ns)
VarSet operator/ ( const VarSet& ns ) const {
VarSet res;
std::set_difference( _vars.begin(), _vars.end(), ns._vars.begin(), ns._vars.end(), inserter( res._vars, res._vars.begin() ) );
return res;
}
- /// Set-union operator (result contains all variables plus those in ns)
+ /// Set-union operator (result contains all variables in *this, plus those in ns)
VarSet operator| ( const VarSet& ns ) const {
VarSet res;
std::set_union( _vars.begin(), _vars.end(), ns._vars.begin(), ns._vars.end(), inserter( res._vars, res._vars.begin() ) );
return res;
}
- /// Set-intersection operator (result contains all variables that are also contained in ns)
+ /// Set-intersection operator (result contains all variables in *this that are also contained in ns)
VarSet operator& ( const VarSet& ns ) const {
VarSet res;
std::set_intersection( _vars.begin(), _vars.end(), ns._vars.begin(), ns._vars.end(), inserter( res._vars, res._vars.begin() ) );
return( os );
}
- // Constant iterator
+ /// Constant iterator over Vars
typedef std::vector<Var>::const_iterator const_iterator;
- /// Iterator
+ /// Iterator over Vars
typedef std::vector<Var>::iterator iterator;
- // Constant reverse iterator
+ /// Constant reverse iterator over Vars
typedef std::vector<Var>::const_reverse_iterator const_reverse_iterator;
- /// Reverse Iterator
+ /// Reverse iterator over Vars
typedef std::vector<Var>::reverse_iterator reverse_iterator;
/// Returns iterator that points to the first variable
std::vector<Var>::size_type size() const { return _vars.size(); }
- /// Returns whether the set is empty
+ /// Returns whether the VarSet is empty
bool empty() const { return _vars.size() == 0; }
return state;
}
- protected:
- /// Calculate number of states
+ private:
+ /// Calculates the number of states
size_t calcStates() {
_states = 1;
foreach( Var &i, _vars )
using namespace std;
-/// Remove node of type 1 and all incident edges.
void BipartiteGraph::erase1( size_t n1 ) {
assert( n1 < nr1() );
// Erase neighbor entry of node n1
}
-/// Remove node of type 2 and all incident edges.
void BipartiteGraph::erase2( size_t n2 ) {
assert( n2 < nr2() );
// Erase neighbor entry of node n2
}
-/// Calculate second-order neighbors (i.e., neighbors of neighbors) of node n1 of type 1.
-/** If include == true, include n1 itself, otherwise exclude n1.
- */
std::vector<size_t> BipartiteGraph::delta1( size_t n1, bool include ) const {
+ // get all second-order neighbors
std::vector<size_t> result;
foreach( const Neighbor &n2, nb1(n1) )
foreach( const Neighbor &m1, nb2(n2) )
}
-/// Calculate second-order neighbors (i.e., neighbors of neighbors) of node n2 of type 2.
-/** If include == true, include n2 itself, otherwise exclude n2.
- */
std::vector<size_t> BipartiteGraph::delta2( size_t n2, bool include ) const {
+ // store all second-order neighbors
std::vector<size_t> result;
foreach( const Neighbor &n1, nb2(n2) )
foreach( const Neighbor &m2, nb1(n1) )
}
-/// Returns true if the graph is connected
bool BipartiteGraph::isConnected() const {
if( nr1() == 0 ) {
return true;
}
-/// 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 BipartiteGraph::isTree() const {
using namespace std;
vector<levelType> levels;
}
-/// Stream to output stream os in graphviz .dot syntax
void BipartiteGraph::display( std::ostream& os ) const {
using namespace std;
os << "graph G {" << endl;
}
-/// Checks internal consistency
void BipartiteGraph::check() const {
size_t N1 = nr1();
size_t N2 = nr2();
projects / libdai.git / commitdiff