From 87755700037e1741ac2934f4c3e807178a5a139c Mon Sep 17 00:00:00 2001 From: Joris Mooij Date: Mon, 22 Sep 2008 08:35:48 +0200 Subject: [PATCH] Small doc changes --- STATUS | 7 +++++++ doxygen.conf | 16 ++++++++-------- include/dai/bipgraph.h | 13 +++++++------ include/dai/var.h | 20 ++++++++++---------- include/dai/varset.h | 34 +++++++++++++++++----------------- src/bipgraph.cpp | 17 ++--------------- 6 files changed, 51 insertions(+), 56 deletions(-) diff --git a/STATUS b/STATUS index d712b2c..3c2a492 100644 --- a/STATUS +++ b/STATUS @@ -10,12 +10,15 @@ class ExtFactorGraph : public FactorGraph { // 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 @@ -37,3 +40,7 @@ var.h utils/createfg.cpp exceptions.h exceptions.cpp + +DOCUMENTATION READY: +- bipgraph.h, bipgraph.cpp +- var.h diff --git a/doxygen.conf b/doxygen.conf index c04f07b..febd3e1 100644 --- a/doxygen.conf +++ b/doxygen.conf @@ -123,7 +123,7 @@ STRIP_FROM_PATH = # 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 @@ -160,7 +160,7 @@ MULTILINE_CPP_IS_BRIEF = NO # 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 @@ -221,7 +221,7 @@ OPTIMIZE_OUTPUT_VHDL = NO # 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. @@ -367,7 +367,7 @@ INLINE_INFO = YES # 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 @@ -644,13 +644,13 @@ STRIP_CODE_COMMENTS = YES # 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 @@ -896,13 +896,13 @@ LATEX_HEADER = # 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 diff --git a/include/dai/bipgraph.h b/include/dai/bipgraph.h index 19eb434..b385476 100644 --- a/include/dai/bipgraph.h +++ b/include/dai/bipgraph.h @@ -36,12 +36,13 @@ namespace dai { /// 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) ) { @@ -60,7 +61,7 @@ class BipartiteGraph { 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() {} @@ -71,7 +72,7 @@ class BipartiteGraph { /// Neighbors is a vector of Neighbor entries; each node has an associated Neighbors variable, which describes its neighbors. typedef std::vector 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 Edge; private: @@ -187,7 +188,7 @@ class BipartiteGraph { /// 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++ ) diff --git a/include/dai/var.h b/include/dai/var.h index 7deaa95..4d027b9 100644 --- a/include/dai/var.h +++ b/include/dai/var.h @@ -37,7 +37,7 @@ namespace dai { */ class Var { private: - /// Internal label of the variable + /// Label of the variable (its unique ID) long _label; /// Number of possible values @@ -49,30 +49,30 @@ class Var { /// 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() << "]" ); } diff --git a/include/dai/varset.h b/include/dai/varset.h index 94ae3eb..883cb62 100644 --- a/include/dai/varset.h +++ b/include/dai/varset.h @@ -36,14 +36,14 @@ namespace dai { -/// Represents a set of variables. +/// A VarSet represents a set of variables. /** - * It is implemented as an ordered vector for efficiency reasons - * (this is more efficient than a set). In addition, it provides - * an interface for common set-theoretic operations. + * It is implemented as an ordered std::vector for efficiency reasons + * (indeed, it was found that a std::set 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 _vars; @@ -73,7 +73,7 @@ class VarSet { } /// 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. */ @@ -100,13 +100,13 @@ class VarSet { } - /// 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() ) ); @@ -114,7 +114,7 @@ class VarSet { 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() ) ); @@ -122,7 +122,7 @@ class VarSet { 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() ) ); @@ -195,13 +195,13 @@ class VarSet { return( os ); } - // Constant iterator + /// Constant iterator over Vars typedef std::vector::const_iterator const_iterator; - /// Iterator + /// Iterator over Vars typedef std::vector::iterator iterator; - // Constant reverse iterator + /// Constant reverse iterator over Vars typedef std::vector::const_reverse_iterator const_reverse_iterator; - /// Reverse Iterator + /// Reverse iterator over Vars typedef std::vector::reverse_iterator reverse_iterator; /// Returns iterator that points to the first variable @@ -229,7 +229,7 @@ class VarSet { std::vector::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; } @@ -263,8 +263,8 @@ class VarSet { return state; } - protected: - /// Calculate number of states + private: + /// Calculates the number of states size_t calcStates() { _states = 1; foreach( Var &i, _vars ) diff --git a/src/bipgraph.cpp b/src/bipgraph.cpp index 1e87de1..6632ee5 100644 --- a/src/bipgraph.cpp +++ b/src/bipgraph.cpp @@ -28,7 +28,6 @@ namespace dai { 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 @@ -55,7 +54,6 @@ void BipartiteGraph::erase1( size_t 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 @@ -82,10 +80,8 @@ void BipartiteGraph::erase2( size_t 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 BipartiteGraph::delta1( size_t n1, bool include ) const { + // get all second-order neighbors std::vector result; foreach( const Neighbor &n2, nb1(n1) ) foreach( const Neighbor &m1, nb2(n2) ) @@ -98,10 +94,8 @@ std::vector BipartiteGraph::delta1( size_t n1, bool include ) 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. - */ std::vector BipartiteGraph::delta2( size_t n2, bool include ) const { + // store all second-order neighbors std::vector result; foreach( const Neighbor &n1, nb2(n2) ) foreach( const Neighbor &m2, nb1(n1) ) @@ -114,7 +108,6 @@ std::vector BipartiteGraph::delta2( size_t n2, bool include ) const { } -/// Returns true if the graph is connected bool BipartiteGraph::isConnected() const { if( nr1() == 0 ) { return true; @@ -166,10 +159,6 @@ bool BipartiteGraph::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 BipartiteGraph::isTree() const { using namespace std; vector levels; @@ -238,7 +227,6 @@ bool BipartiteGraph::isTree() const { } -/// Stream to output stream os in graphviz .dot syntax void BipartiteGraph::display( std::ostream& os ) const { using namespace std; os << "graph G {" << endl; @@ -255,7 +243,6 @@ void BipartiteGraph::display( std::ostream& os ) const { } -/// Checks internal consistency void BipartiteGraph::check() const { size_t N1 = nr1(); size_t N2 = nr2(); -- 2.20.1