git master HEAD
---------------
+* Added dag.h/cpp, an implementation for Directed Acyclic Graphs
* Improved regression test
* Added examples/example_imagesegmentation
* [Ofer Meshi] Added a script for converting from FastInf to libDAI format
- Fixed bug in createGraphGrid3D()
- Fixed bug in createGraphRegular()
- Added GraphAL::hasEdge(size_t,size_t)
+ - Added GraphAL::nbSet(size_t)
- Added GraphAL::operator==( const GraphAL& )
- Added operator<<( std::ostream&, const GraphAL& )
* Improved smallset.h/cpp:
endif
# Define conditional build targets
-NAMES:=bipgraph graph varset daialg alldai clustergraph factor factorgraph properties regiongraph util weightedgraph exceptions exactinf evidence emalg
+NAMES:=graph dag bipgraph varset daialg alldai clustergraph factor factorgraph properties regiongraph util weightedgraph exceptions exactinf evidence emalg
ifdef WITH_BP
WITHFLAGS:=$(WITHFLAGS) -DDAI_WITH_BP
NAMES:=$(NAMES) bp
endif
# Define standard libDAI header dependencies, source file names and object file names
-HEADERS=$(foreach name,bipgraph graph index var factor varset smallset prob daialg properties alldai enum exceptions util,$(INC)/$(name).h)
+HEADERS=$(foreach name,graph dag bipgraph index var factor varset smallset prob daialg properties alldai enum exceptions util,$(INC)/$(name).h)
SOURCES:=$(foreach name,$(NAMES),$(SRC)/$(name).cpp)
OBJECTS:=$(foreach name,$(NAMES),$(name)$(OE))
matlabs : matlab/dai$(ME) matlab/dai_readfg$(ME) matlab/dai_writefg$(ME) matlab/dai_potstrength$(ME)
-unittests : tests/unit/var_test$(EE) tests/unit/smallset_test$(EE) tests/unit/varset_test$(EE) tests/unit/graph_test$(EE) tests/unit/bipgraph_test$(EE) tests/unit/weightedgraph_test$(EE) tests/unit/enum_test$(EE) tests/unit/enum_test$(EE) tests/unit/util_test$(EE) tests/unit/exceptions_test$(EE) tests/unit/properties_test$(EE) tests/unit/index_test$(EE) tests/unit/prob_test$(EE) tests/unit/factor_test$(EE) tests/unit/factorgraph_test$(EE) tests/unit/clustergraph_test$(EE) tests/unit/regiongraph_test$(EE) tests/unit/daialg_test$(EE) tests/unit/alldai_test$(EE)
+unittests : tests/unit/var_test$(EE) tests/unit/smallset_test$(EE) tests/unit/varset_test$(EE) tests/unit/graph_test$(EE) tests/unit/dag_test$(EE) tests/unit/bipgraph_test$(EE) tests/unit/weightedgraph_test$(EE) tests/unit/enum_test$(EE) tests/unit/enum_test$(EE) tests/unit/util_test$(EE) tests/unit/exceptions_test$(EE) tests/unit/properties_test$(EE) tests/unit/index_test$(EE) tests/unit/prob_test$(EE) tests/unit/factor_test$(EE) tests/unit/factorgraph_test$(EE) tests/unit/clustergraph_test$(EE) tests/unit/regiongraph_test$(EE) tests/unit/daialg_test$(EE) tests/unit/alldai_test$(EE)
echo Running unit tests...
tests/unit/var_test$(EE)
tests/unit/smallset_test$(EE)
tests/unit/varset_test$(EE)
tests/unit/graph_test$(EE)
+ tests/unit/dag_test$(EE)
tests/unit/bipgraph_test$(EE)
tests/unit/weightedgraph_test$(EE)
tests/unit/enum_test$(EE)
-rm matlab/*$(ME)
-rm examples/example$(EE) examples/example_bipgraph$(EE) examples/example_varset$(EE) examples/example_permute$(EE) examples/example_sprinkler$(EE) examples/example_sprinkler_gibbs$(EE) examples/example_sprinkler_em$(EE) examples/example_imagesegmentation$(EE)
-rm tests/testdai$(EE) tests/testem/testem$(EE) tests/testbbp$(EE)
- -rm tests/unit/var_test$(EE) tests/unit/smallset_test$(EE) tests/unit/varset_test$(EE) tests/unit/graph_test$(EE) tests/unit/bipgraph_test$(EE) tests/unit/weightedgraph_test$(EE) tests/unit/enum_test$(EE) tests/unit/util_test$(EE) tests/unit/exceptions_test$(EE) tests/unit/properties_test$(EE) tests/unit/index_test$(EE) tests/unit/prob_test$(EE) tests/unit/factor_test$(EE) tests/unit/factorgraph_test$(EE) tests/unit/clustergraph_test$(EE) tests/unit/regiongraph_test$(EE) tests/unit/daialg_test$(EE) tests/unit/alldai_test$(EE)
+ -rm tests/unit/var_test$(EE) tests/unit/smallset_test$(EE) tests/unit/varset_test$(EE) tests/unit/graph_test$(EE) tests/unit/dag_test$(EE) tests/unit/bipgraph_test$(EE) tests/unit/weightedgraph_test$(EE) tests/unit/enum_test$(EE) tests/unit/util_test$(EE) tests/unit/exceptions_test$(EE) tests/unit/properties_test$(EE) tests/unit/index_test$(EE) tests/unit/prob_test$(EE) tests/unit/factor_test$(EE) tests/unit/factorgraph_test$(EE) tests/unit/clustergraph_test$(EE) tests/unit/regiongraph_test$(EE) tests/unit/daialg_test$(EE) tests/unit/alldai_test$(EE)
-rm factorgraph_test.fg alldai_test.aliases
-rm utils/fg2dot$(EE) utils/createfg$(EE) utils/fginfo$(EE) utils/uai2fg$(EE)
-rm -R doc
const double th_max = cimg_option( "-thmax", 3.2, "Local evidence strength of foreground" );
const double scale = cimg_option( "-scale", 40.0, "Typical difference in pixel values between fore- and background" );
const double pbg = cimg_option( "-pbg", 90.0, "Percentage of background in image" );
+ const char *infname = cimg_option( "-method", "BP[updates=SEQMAX,maxiter=1,tol=1e-9,logdomain=0]", "Inference method in format name[key1=val1,...,keyn=valn]" );
+ const size_t maxiter = cimg_option( "-maxiter", 100, "Maximum number of iterations for inference method" );
+ const double tol = cimg_option( "-tol", 1e-9, "Desired tolerance level for inference method" );
const char *file_fg = cimg_option( "-fg", "", "Output factor graph" );
// Read input images
CImgDisplay disp5( dimx, dimy, "Beliefs during inference", 0 );
vector<double> m; // Stores the final magnetizations
cout << "Solving the inference problem...please be patient!" << endl;
- // doInference( fg, "BP[updates=SEQFIX,maxiter=1,tol=1e-9,verbose=0,logdomain=0]", 100, 1e-9, m, dimx, dimy, disp5 );
- doInference( fg, "BP[updates=SEQMAX,maxiter=1,tol=1e-9,verbose=0,logdomain=0]", 100, 1e-9, m, dimx, dimy, disp5 );
- // doInference( fg, "BP[updates=SEQRND,maxiter=1,tol=1e-9,verbose=0,logdomain=0]", 100, 1e-9, m, dimx, dimy, disp5 );
- // doInference( fg, "HAK[doubleloop=0,clusters=LOOP,init=UNIFORM,loopdepth=4,tol=1e-9,maxiter=1,verbose=3]", 1000, 1e-5, m, dimx, dimy, disp5 );
- // doInference( fg, "HAK[doubleloop=0,clusters=BETHE,init=UNIFORM,maxiter=1,tol=1e-9,verbose=3]", 1000, 1e-5, m, dimx, dimy, disp5 );
- // doInference( fg, "MF[tol=1e-9,maxiter=1,damping=0.0,init=RANDOM,updates=HARDSPIN]", 1000, 1e-5, m, dimx, dimy, disp5 );
- // doInference( fg, "TREEEP[type=ORG,tol=1e-9,maxiter=10000,verbose=3]", 1000, 1e-5, m, dimx, dimy, disp5 );
- // doInference( fg, "GIBBS[iters=1,burnin=0]", 100, 1e-9, m, dimx, dimy, disp5 );
- // doInference( fg, "GIBBS[iters=1,burnin=0]", 100, 1e-9, m, dimx, dimy, disp5 );
- // doInference( fg, "GIBBS[iters=1,burnin=0]", 100, 1e-9, m, dimx, dimy, disp5 );
+ doInference( fg, infname, maxiter, tol, m, dimx, dimy, disp5 );
// Visualize the final magnetizations
for( size_t i = 0; i < dimx; i++ )
/// 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 );
+ BipartiteGraph& addEdge( size_t n1, size_t n2, bool check = true );
//@}
/// \name Erasing nodes and edges
/// Comparison operator which returns true if two graphs are identical
/** \note Two graphs are called identical if they have the same number of nodes
* of both types and the same edges (i.e., \a x has an edge between nodes
- * n1 and n2 if and only if \c *this has an edge between nodes n1 and n2).
+ * \a n1 and \a n2 if and only if \c *this has an edge between nodes \a n1 and \a n2).
*/
bool operator==( const BipartiteGraph& x ) const {
if( nrNodes1() != x.nrNodes1() )
--- /dev/null
+/* 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) 2010 Joris Mooij [joris dot mooij at libdai dot org]
+ */
+
+
+/// \file
+/// \brief Defines the DAG class, which represents a directed acyclic graph
+
+
+#ifndef __defined_libdai_dag_h
+#define __defined_libdai_dag_h
+
+
+#include <ostream>
+#include <vector>
+#include <algorithm>
+#include <dai/util.h>
+#include <dai/exceptions.h>
+#include <dai/smallset.h>
+
+
+namespace dai {
+
+
+/// Represents the neighborhood structure of nodes in a directed cyclic graph.
+/** A directed cyclic graph has nodes connected by directed edges, such that there is no
+ * directed cycle of edges n1->n2->n3->...->n1. Nodes are indexed by an unsigned integer.
+ * If there are nrNodes() nodes, they are numbered 0,1,2,...,nrNodes()-1. An edge
+ * from node \a n1 to node \a n2 is represented by a DAG::Edge(\a n1,\a n2).
+ *
+ * DAG is implemented as a sparse adjacency list, i.e., it stores for each node a list of
+ * its parents and a list of its children. Both lists are implemented as a vector of Neighbor
+ * structures (accessible by the pa() and ch() methods). Thus, each node has two associated
+ * variables of type DAG::Neighbors, which are vectors of Neighbor structures, describing their
+ * parent and children nodes.
+ */
+class DAG {
+ public:
+ /// Describes the parent/child relationship of two nodes in a DAG.
+ /** 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 two lists of neighbors
+ * (a list of parents and a list of children), 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),
+ * i.e., as a child of its parent or as a parent of its child.
+ *
+ * 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, <tt>pa(i,_j)</tt> gives the
+ * \a _j 'th parent of node \a i, and <tt>ch(k,_l)</tt>
+ * gives the \a _l 'th child of node \a k.
+ * Here, \a i and \a k are "absolute" indexes of nodes \a i and \a k,
+ * but \a _j and \a _k are understood as "relative" indexes
+ * within the list <tt>pa(i)</tt> of parents of \a i and the
+ * list of children <tt>ch(k)</tt> of \a k. The
+ * absolute index of \a _j, which would be called \a j, can be
+ * recovered from the \c node member: <tt>j = pa(i,_j).node</tt>.
+ * Similarly, the absolute index of \a _l, which would be called
+ * \a l, can be recovered from the \c node member:
+ * <tt>l = ch(k,_l).node</tt>.
+ * The \c iter member gives the relative index \a _j or \a _l,
+ * and the \c dual member gives the "dual" relative index, i.e.,
+ * the index of \a i in \a j 's children list or the index of
+ * \a k in \a l 's parent list.
+ *
+ * \code
+ * Neighbor p = pa(i,_j);
+ * p.node == j &&
+ * p.iter == _j &&
+ * ch(p.node,p.dual).node == i
+ *
+ * Neighbor c = ch(k,_l);
+ * c.node == l &&
+ * c.iter == _l &&
+ * pa(c.node,c.dual).node == k
+ * \endcode
+ *
+ * There is no cheap way to transform a pair of absolute node
+ * indices \a i and \a j 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
+ * for( size_t i = 0; i < nrNodes(); ++i )
+ * foreach( const Neighbor &j, ch(i) )
+ * assert( hasEdge( i, j ) );
+ * \endcode
+ */
+ struct Neighbor {
+ /// Corresponds to the index of this Neighbor entry in the vector of neighbors
+ size_t iter;
+ /// Contains the number of the neighboring node
+ size_t node;
+ /// Contains the "dual" iter
+ size_t dual;
+
+ /// Default constructor
+ Neighbor() {}
+ /// 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; }
+ };
+
+ /// Type for storing the parents/children of some node.
+ typedef std::vector<Neighbor> Neighbors;
+
+ /// Represents a directed edge: an Edge(\a n1,\a n2) corresponds to the edge from node \a n1 to node \a n2.
+ typedef std::pair<size_t,size_t> Edge;
+
+ private:
+ /// Contains for each node a vector of its parent nodes
+ std::vector<Neighbors> _pa;
+
+ /// Contains for each node a vector of its children nodes
+ std::vector<Neighbors> _ch;
+
+ public:
+ /// \name Constructors and destructors
+ //@{
+ /// Default constructor (creates an empty DAG).
+ DAG() : _pa(), _ch() {}
+
+ /// Constructs DAG with \a nr nodes and no edges.
+ DAG( size_t nr ) : _pa( nr ), _ch( nr ) {}
+
+ /// Constructs DAG from a range of edges.
+ /** \tparam EdgeInputIterator Iterator that iterates over instances of DAG::Edge.
+ * \param nr The number of nodes.
+ * \param begin Points to the first edge.
+ * \param end Points just beyond the last edge.
+ * \param check Whether to only add an edge if it does not exist already and
+ * if it does not introduce a cycle
+ */
+ template<typename EdgeInputIterator>
+ DAG( size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check=true ) : _pa(), _ch() {
+ construct( nr, begin, end, check );
+ }
+ //@}
+
+ /// \name Accessors and mutators
+ //@{
+ /// Returns constant reference to the \a _p 'th parent of node \a n
+ const Neighbor& pa( size_t n, size_t _p ) const {
+ DAI_DEBASSERT( n < _pa.size() );
+ DAI_DEBASSERT( _p < _pa[n].size() );
+ return _pa[n][_p];
+ }
+ /// Returns reference to the \a _p 'th parent of node \a n
+ Neighbor& pa( size_t n, size_t _p ) {
+ DAI_DEBASSERT( n < _pa.size() );
+ DAI_DEBASSERT( _p < _pa[n].size() );
+ return _pa[n][_p];
+ }
+
+ /// Returns constant reference to all parents of node \a n
+ const Neighbors& pa( size_t n ) const {
+ DAI_DEBASSERT( n < _pa.size() );
+ return _pa[n];
+ }
+ /// Returns reference to all parents of node \a n
+ Neighbors& pa( size_t n ) {
+ DAI_DEBASSERT( n < _pa.size() );
+ return _pa[n];
+ }
+
+ /// Returns constant reference to the \a _c 'th child of node \a n
+ const Neighbor& ch( size_t n, size_t _c ) const {
+ DAI_DEBASSERT( n < _ch.size() );
+ DAI_DEBASSERT( _c < _ch[n].size() );
+ return _ch[n][_c];
+ }
+ /// Returns reference to the \a _c 'th child of node \a n
+ Neighbor& ch( size_t n, size_t _c ) {
+ DAI_DEBASSERT( n < _ch.size() );
+ DAI_DEBASSERT( _c < _ch[n].size() );
+ return _ch[n][_c];
+ }
+
+ /// Returns constant reference to all children of node \a n
+ const Neighbors& ch( size_t n ) const {
+ DAI_DEBASSERT( n < _ch.size() );
+ return _ch[n];
+ }
+ /// Returns reference to all children of node \a n
+ Neighbors& ch( size_t n ) {
+ DAI_DEBASSERT( n < _ch.size() );
+ return _ch[n];
+ }
+ //@}
+
+ /// \name Adding nodes and edges
+ //@{
+ /// (Re)constructs DAG from a range of edges.
+ /** \tparam EdgeInputIterator Iterator that iterates over instances of DAG::Edge.
+ * \param nr The number of nodes.
+ * \param begin Points to the first edge.
+ * \param end Points just beyond the last edge.
+ * \param check Whether to only add an edge if it does not exist already and does not introduce a cycle.
+ */
+ template<typename EdgeInputIterator>
+ void construct( size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check=true );
+
+ /// Adds a node without parents and children and returns the index of the added node.
+ size_t addNode() {
+ _pa.push_back( Neighbors() );
+ _ch.push_back( Neighbors() );
+ return _pa.size() - 1;
+ }
+
+ /// Adds a node with parents specified by a range of nodes.
+ /** \tparam NodeInputIterator Iterator that iterates over instances of \c size_t.
+ * \param begin Points to the first index of the nodes that should become parents of the added node.
+ * \param end Points just beyond the last index of the nodes that should become parents 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>
+ size_t addNode( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint=0 ) {
+ Neighbors newparents;
+ newparents.reserve( sizeHint );
+ size_t iter = 0;
+ for( NodeInputIterator it = begin; it != end; ++it ) {
+ DAI_ASSERT( *it < nrNodes() );
+ Neighbor newparent( iter, *it, ch(*it).size() );
+ Neighbor newchild( ch(*it).size(), nrNodes(), iter++ );
+ newparents.push_back( newparent );
+ ch( *it ).push_back( newchild );
+ }
+ _pa.push_back( newparents );
+ _ch.push_back( Neighbors() );
+ return _pa.size() - 1;
+ }
+
+ /// Adds an edge from node \a n1 and node \a n2.
+ /** If \a check == \c true, only adds the edge if it does not exist already and it would not introduce a cycle.
+ */
+ DAG& addEdge( size_t n1, size_t n2, bool check=true );
+ //@}
+
+ /// \name Erasing nodes and edges
+ //@{
+ /// Removes node \a n and all ingoing and outgoing edges; indices of other nodes are changed accordingly.
+ void eraseNode( size_t n );
+
+ /// Removes edge from node \a n1 to node \a n2.
+ void eraseEdge( size_t n1, size_t n2 );
+ //@}
+
+ /// \name Queries
+ //@{
+ /// Returns number of nodes
+ size_t nrNodes() const {
+ DAI_DEBASSERT( _pa.size() == _ch.size() );
+ return _pa.size();
+ }
+
+ /// Calculates the number of edges, time complexity: O(nrNodes())
+ size_t nrEdges() const {
+ size_t sum = 0;
+ for( size_t i = 0; i < _pa.size(); i++ )
+ sum += _pa[i].size();
+ return sum;
+ }
+
+ /// Returns true if the DAG contains an edge from node \a n1 and \a n2
+ /** \note The time complexity is linear in the number of children of \a n1 or the number of parents of \a n2, whichever is smaller
+ */
+ bool hasEdge( size_t n1, size_t n2 ) const {
+ if( ch(n1).size() < pa(n2).size() ) {
+ for( size_t _n2 = 0; _n2 < ch(n1).size(); _n2++ )
+ if( ch( n1, _n2 ) == n2 )
+ return true;
+ } else {
+ for( size_t _n1 = 0; _n1 < pa(n2).size(); _n1++ )
+ if( pa( n2, _n1 ) == n1 )
+ return true;
+ }
+ return false;
+ }
+
+ /// Returns the index of a given node \a p amongst the parents of \a n
+ /** \note The time complexity is linear in the number of parents of \a n
+ * \throw OBJECT_NOT_FOUND if \a p is not a parent of \a n
+ */
+ size_t findPa( size_t n, size_t p ) {
+ for( size_t _p = 0; _p < pa(n).size(); _p++ )
+ if( pa( n, _p ) == p )
+ return _p;
+ DAI_THROW(OBJECT_NOT_FOUND);
+ return pa(n).size();
+ }
+
+ /// Returns the index of a given node \a c amongst the children of \a n
+ /** \note The time complexity is linear in the number of children of \a n
+ * \throw OBJECT_NOT_FOUND if \a c is not a child \a n
+ */
+ size_t findCh( size_t n, size_t c ) {
+ for( size_t _c = 0; _c < ch(n).size(); _c++ )
+ if( ch( n, _c ) == c )
+ return _c;
+ DAI_THROW(OBJECT_NOT_FOUND);
+ return ch(n).size();
+ }
+
+ /// Returns parents of node \a n as a SmallSet<size_t>.
+ SmallSet<size_t> paSet( size_t n ) const;
+
+ /// Returns children of node \a n as a SmallSet<size_t>.
+ SmallSet<size_t> chSet( size_t n ) const;
+
+ /// Returns the set of ancestors of node \a n, i.e., all nodes \a a such that there exists a directed path from \a a to \a n (excluding \a n itself)
+ std::set<size_t> ancestors( size_t n ) const;
+
+ /// Returns the set of descendants of node \a n, i.e., all nodes \a d such that there exists a directed path from \a n to \a d (excluding \a n itself)
+ std::set<size_t> descendants( size_t n ) const;
+
+ /// Returns whether there exists a directed path from node \a n1 to node \a n2 (which may consist of zero edges)
+ bool existsDirectedPath( size_t n1, size_t n2 ) const;
+
+ /// Returns true if the DAG is connected
+ bool isConnected() const;
+
+ /// Asserts internal consistency
+ void checkConsistency() const;
+
+ /// Comparison operator which returns true if two DAGs are identical
+ /** \note Two DAGs are called identical if they have the same number
+ * of nodes and the same edges (i.e., \a x has an edge from \a n1 to \a n2
+ * if and only if \c *this has an edge from node \a n1 to \a n2).
+ */
+ bool operator==( const DAG& x ) const {
+ if( nrNodes() != x.nrNodes() )
+ return false;
+ for( size_t n1 = 0; n1 < nrNodes(); n1++ ) {
+ if( pa(n1).size() != x.pa(n1).size() )
+ return false;
+ foreach( const Neighbor &n2, pa(n1) )
+ if( !x.hasEdge( n2, n1 ) )
+ return false;
+ foreach( const Neighbor &n2, x.pa(n1) )
+ if( !hasEdge( n2, n1 ) )
+ return false;
+ }
+ return true;
+ }
+ //@}
+
+ /// \name Input and output
+ //@{
+ /// Writes this DAG to an output stream in GraphViz .dot syntax
+ void printDot( std::ostream& os ) const;
+
+ /// Writes this DAG to an output stream
+ friend std::ostream& operator<<( std::ostream& os, const DAG& g ) {
+ g.printDot( os );
+ return os;
+ }
+ //@}
+};
+
+
+template<typename EdgeInputIterator>
+void DAG::construct( size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check ) {
+ _pa.clear();
+ _pa.resize( nr );
+ _ch.clear();
+ _ch.resize( nr );
+
+ for( EdgeInputIterator e = begin; e != end; e++ )
+ addEdge( e->first, e->second, check );
+}
+
+
+} // end of namespace dai
+
+
+#endif
/** \file
* \brief Contains additional doxygen documentation
*
+ * \todo Replace all Neighbor subclasses with a global Neighbor class, and
+ * introduce global (un)directed edge classes
+ *
* \todo Replace all Name members by virtual functions (or add virtual functions returning the Name)
*
* \idea Adapt (part of the) guidelines in http://www.boost.org/development/requirements.html#Design_and_Programming
#include <algorithm>
#include <dai/util.h>
#include <dai/exceptions.h>
+#include <dai/smallset.h>
namespace dai {
/// Adds an edge between node \a n1 and node \a n2.
/** 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 );
+ GraphAL& addEdge( size_t n1, size_t n2, bool check = true );
//@}
/// \name Erasing nodes and edges
return nb(n1).size();
}
+ /// Returns neighbors of node \a n as a SmallSet<size_t>.
+ SmallSet<size_t> nbSet( size_t n ) const;
+
/// Returns true if the graph is connected
bool isConnected() const;
/// Comparison operator which returns true if two graphs are identical
/** \note Two graphs are called identical if they have the same number
* of nodes and the same edges (i.e., \a x has an edge between nodes
- * n1 and n2 if and only if \c *this has an edge between nodes n1 and n2).
+ * \a n1 and \a n2 if and only if \c *this has an edge between nodes \a n1 and \a n2).
*/
bool operator==( const GraphAL& x ) const {
if( nrNodes() != x.nrNodes() )
using namespace std;
-void BipartiteGraph::addEdge( size_t n1, size_t n2, bool check ) {
+BipartiteGraph& BipartiteGraph::addEdge( size_t n1, size_t n2, bool check ) {
DAI_ASSERT( n1 < nrNodes1() );
DAI_ASSERT( n2 < nrNodes2() );
bool exists = false;
nb1(n1).push_back( nb_1 );
nb2(n2).push_back( nb_2 );
}
+ return *this;
}
if( m1.node == n1 ) {
// delete this entry, because it points to the deleted node
nb2(n2).erase( nb2(n2).begin() + iter );
- } else if( m1.node > n1 ) {
- // update this entry and the corresponding dual of the neighboring node of type 1
- m1.node--;
- nb1( m1.node, m1.dual ).dual = iter;
- m1.iter = iter++;
} else {
// update this entry and the corresponding dual of the neighboring node of type 1
+ if( m1.node > n1 )
+ m1.node--;
nb1( m1.node, m1.dual ).dual = iter;
m1.iter = iter++;
}
if( m2.node == n2 ) {
// delete this entry, because it points to the deleted node
nb1(n1).erase( nb1(n1).begin() + iter );
- } else if( m2.node > n2 ) {
- // update this entry and the corresponding dual of the neighboring node of type 2
- m2.node--;
- nb2( m2.node, m2.dual ).dual = iter;
- m2.iter = iter++;
} else {
// update this entry and the corresponding dual of the neighboring node of type 2
+ if( m2.node > n2 )
+ m2.node--;
nb2( m2.node, m2.dual ).dual = iter;
m2.iter = iter++;
}
--- /dev/null
+/* 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) 2010 Joris Mooij [joris dot mooij at libdai dot org]
+ */
+
+
+#include <dai/dag.h>
+
+
+namespace dai {
+
+
+using namespace std;
+
+
+DAG& DAG::addEdge( size_t n1, size_t n2, bool check ) {
+ DAI_ASSERT( n1 < nrNodes() );
+ DAI_ASSERT( n2 < nrNodes() );
+ bool allowed = true;
+ if( check ) {
+ // Check whether the edge already exists
+ foreach( const Neighbor& n, ch(n1) )
+ if( n == n2 ) {
+ allowed = false;
+ break;
+ }
+ // Check whether there exists a directed path from n2 to n1 already
+ if( allowed && existsDirectedPath( n2, n1 ) )
+ allowed = false;
+ }
+ if( allowed && n1 != n2 ) { // Add edge
+ Neighbor ch_1( ch(n1).size(), n2, pa(n2).size() );
+ Neighbor pa_2( ch_1.dual, n1, ch_1.iter );
+ ch(n1).push_back( ch_1 );
+ pa(n2).push_back( pa_2 );
+ }
+ return *this;
+}
+
+
+void DAG::eraseNode( size_t n ) {
+ DAI_ASSERT( n < nrNodes() );
+ // Erase parents entry of node n
+ _pa.erase( _pa.begin() + n );
+ // Erase children entry of node n
+ _ch.erase( _ch.begin() + n );
+ // Adjust parents and children entries of remaining nodes
+ for( size_t m = 0; m < nrNodes(); m++ ) {
+ // Adjust parents entries of node m
+ for( size_t iter = 0; iter < pa(m).size(); ) {
+ Neighbor &p = pa(m, iter);
+ if( p.node == n ) {
+ // delete this entry, because it points to the deleted node
+ pa(m).erase( pa(m).begin() + iter );
+ } else {
+ // update this entry and the corresponding dual of the child node
+ if( p.node > n )
+ p.node--;
+ ch( p.node, p.dual ).dual = iter;
+ p.iter = iter++;
+ }
+ }
+ // Adjust children entries of node m
+ for( size_t iter = 0; iter < ch(m).size(); ) {
+ Neighbor &c = ch(m, iter);
+ if( c.node == n ) {
+ // delete this entry, because it points to the deleted node
+ ch(m).erase( ch(m).begin() + iter );
+ } else {
+ if( c.node > n )
+ c.node--;
+ // update this entry and the corresponding dual of the child node
+ pa( c.node, c.dual ).dual = iter;
+ c.iter = iter++;
+ }
+ }
+ }
+}
+
+
+void DAG::eraseEdge( size_t n1, size_t n2 ) {
+ DAI_ASSERT( n1 < nrNodes() );
+ DAI_ASSERT( n2 < nrNodes() );
+ size_t iter;
+ // Search for edge among children of n1
+ for( iter = 0; iter < ch(n1).size(); iter++ )
+ if( ch(n1, iter).node == n2 ) {
+ // Remove it
+ ch(n1).erase( ch(n1).begin() + iter );
+ break;
+ }
+ // Change the iter and dual values of the subsequent children
+ for( ; iter < ch(n1).size(); iter++ ) {
+ Neighbor &m = ch( n1, iter );
+ m.iter = iter;
+ pa( m.node, m.dual ).dual = iter;
+ }
+ // Search for edge among parents of n2
+ for( iter = 0; iter < pa(n2).size(); iter++ )
+ if( pa(n2, iter).node == n1 ) {
+ // Remove it
+ pa(n2).erase( pa(n2).begin() + iter );
+ break;
+ }
+ // Change the iter and node values of the subsequent parents
+ for( ; iter < pa(n2).size(); iter++ ) {
+ Neighbor &m = pa( n2, iter );
+ m.iter = iter;
+ ch( m.node, m.dual ).dual = iter;
+ }
+}
+
+
+SmallSet<size_t> DAG::paSet( size_t n ) const {
+ SmallSet<size_t> result;
+ foreach( const Neighbor &p, pa(n) )
+ result |= p;
+ return result;
+}
+
+
+SmallSet<size_t> DAG::chSet( size_t n ) const {
+ SmallSet<size_t> result;
+ foreach( const Neighbor &c, ch(n) )
+ result |= c;
+ return result;
+}
+
+
+/// Returns the set of ancestors of node \a n, i.e., all nodes \a m such that there exists a directed path from \a m to \a n (excluding \a n itself)
+std::set<size_t> DAG::ancestors( size_t n ) const {
+ set<size_t> anc;
+
+ set<size_t> curParents;
+ curParents.insert( n );
+ while( curParents.size() ) {
+ size_t node = *(curParents.begin());
+ // Add node to ancestors
+ if( node != n )
+ anc.insert( node );
+ // Add all parents of node to curParents
+ foreach( const Neighbor& p, pa(node) )
+ curParents.insert( p.node );
+ // Erase node from curParents
+ curParents.erase( node );
+ }
+
+ return anc;
+}
+
+
+/// Returns the set of descendants of node \a n, i.e., all nodes \a m such that there exists a directed path from \a n to \a m (excluding \a n itself)
+std::set<size_t> DAG::descendants( size_t n ) const {
+ set<size_t> desc;
+
+ set<size_t> curChildren;
+ curChildren.insert( n );
+ while( curChildren.size() ) {
+ size_t node = *(curChildren.begin());
+ // Add node to descendants
+ if( node != n )
+ desc.insert( node );
+ // Add all children of node to curChildren
+ foreach( const Neighbor& c, ch(node) )
+ curChildren.insert( c.node );
+ // Erase node from curChildren
+ curChildren.erase( node );
+ }
+
+ return desc;
+}
+
+
+bool DAG::existsDirectedPath( size_t n1, size_t n2 ) const {
+ set<size_t> curChildren;
+
+ curChildren.insert( n1 );
+ while( curChildren.size() ) {
+ size_t node = *(curChildren.begin());
+ // If we reached n2, we found a directed path from n1 to n2
+ if( node == n2 )
+ return true;
+ // Add all children of node to curChildren
+ foreach( const Neighbor& c, ch(node) )
+ curChildren.insert( c.node );
+ // Erase node from curChildren
+ curChildren.erase( node );
+ }
+ return false;
+}
+
+
+bool DAG::isConnected() const {
+ if( nrNodes() == 0 ) {
+ return true;
+ } else {
+ std::vector<bool> incomponent( nrNodes(), false );
+
+ incomponent[0] = true;
+ bool found_new_nodes;
+ do {
+ found_new_nodes = false;
+
+ // For all nodes, check if they are connected with the (growing) component
+ for( size_t n1 = 0; n1 < nrNodes(); n1++ ) {
+ if( !incomponent[n1] ) {
+ foreach( const Neighbor &n2, pa(n1) )
+ if( incomponent[n2] ) {
+ found_new_nodes = true;
+ incomponent[n1] = true;
+ break;
+ }
+ }
+ if( !incomponent[n1] ) {
+ foreach( const Neighbor &n2, ch(n1) )
+ if( incomponent[n2] ) {
+ found_new_nodes = true;
+ incomponent[n1] = true;
+ break;
+ }
+ }
+ }
+ } while( found_new_nodes );
+
+ // Check if there are remaining nodes (not in the component)
+ bool all_connected = true;
+ for( size_t n1 = 0; (n1 < nrNodes()) && all_connected; n1++ )
+ if( !incomponent[n1] )
+ all_connected = false;
+
+ return all_connected;
+ }
+}
+
+
+void DAG::printDot( std::ostream& os ) const {
+ os << "digraph DAG {" << endl;
+ os << "node[shape=circle,width=0.4,fixedsize=true];" << endl;
+ for( size_t n = 0; n < nrNodes(); n++ )
+ os << "\tx" << n << ";" << endl;
+ for( size_t n1 = 0; n1 < nrNodes(); n1++ )
+ foreach( const Neighbor &n2, ch(n1) )
+ os << "\tx" << n1 << " -> x" << n2 << ";" << endl;
+ os << "}" << endl;
+}
+
+
+void DAG::checkConsistency() const {
+ size_t N = nrNodes();
+ for( size_t n1 = 0; n1 < N; n1++ ) {
+ size_t iter = 0;
+ foreach( const Neighbor &n2, pa(n1) ) {
+ DAI_ASSERT( n2.iter == iter );
+ DAI_ASSERT( n2.node < N );
+ DAI_ASSERT( n2.dual < ch(n2).size() );
+ DAI_ASSERT( ch(n2, n2.dual) == n1 );
+ iter++;
+ }
+ iter = 0;
+ foreach( const Neighbor &n2, ch(n1) ) {
+ DAI_ASSERT( n2.iter == iter );
+ DAI_ASSERT( n2.node < N );
+ DAI_ASSERT( n2.dual < pa(n2).size() );
+ DAI_ASSERT( pa(n2, n2.dual) == n1 );
+ iter++;
+ }
+ }
+ // Check acyclicity
+ for( size_t n1 = 0; n1 < N; n1++ )
+ foreach( const Neighbor& n2, ch(n1) )
+ DAI_ASSERT( !existsDirectedPath( n2, n1 ) );
+}
+
+
+} // end of namespace dai
#include <dai/graph.h>
-#include <dai/weightedgraph.h>
-#include <boost/graph/adjacency_list.hpp>
-#include <boost/graph/connected_components.hpp>
namespace dai {
using namespace std;
-void GraphAL::addEdge( size_t n1, size_t n2, bool check ) {
+GraphAL& GraphAL::addEdge( size_t n1, size_t n2, bool check ) {
DAI_ASSERT( n1 < nrNodes() );
DAI_ASSERT( n2 < nrNodes() );
bool exists = false;
nb(n1).push_back( nb_1 );
nb(n2).push_back( nb_2 );
}
+ return *this;
}
if( m.node == n ) {
// delete this entry, because it points to the deleted node
nb(n2).erase( nb(n2).begin() + iter );
- } else if( m.node > n ) {
- // update this entry and the corresponding dual of the neighboring node
- m.node--;
- nb( m.node, m.dual ).dual = iter;
- m.iter = iter++;
} else {
// update this entry and the corresponding dual of the neighboring node
+ if( m.node > n )
+ m.node--;
nb( m.node, m.dual ).dual = iter;
m.iter = iter++;
}
}
+SmallSet<size_t> GraphAL::nbSet( size_t n ) const {
+ SmallSet<size_t> result;
+ foreach( const Neighbor &m, nb(n) )
+ result |= m;
+ return result;
+}
+
+
bool GraphAL::isConnected() const {
if( nrNodes() == 0 ) {
return true;
iter++;
}
}
- for( size_t n2 = 0; n2 < N; n2++ ) {
- size_t iter = 0;
- foreach( const Neighbor &n1, nb(n2) ) {
- DAI_ASSERT( n1.iter == iter );
- DAI_ASSERT( n1.node < N );
- DAI_ASSERT( n1.dual < nb(n1).size() );
- DAI_ASSERT( nb(n1, n1.dual) == n2 );
- iter++;
- }
- }
}
--- /dev/null
+/* 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) 2010 Joris Mooij [joris dot mooij at libdai dot org]
+ */
+
+
+#include <dai/dag.h>
+#include <vector>
+#include <set>
+#include <strstream>
+
+
+using namespace dai;
+
+
+#define BOOST_TEST_MODULE DAGTest
+
+
+#include <boost/test/unit_test.hpp>
+
+
+BOOST_AUTO_TEST_CASE( ConstructorsTest ) {
+ // check constructors
+ DAG G0;
+ BOOST_CHECK_EQUAL( G0.nrNodes(), 0 );
+ BOOST_CHECK_EQUAL( G0.nrEdges(), 0 );
+ BOOST_CHECK_EQUAL( G0.isConnected(), true );
+ G0.checkConsistency();
+
+ DAG G2( 2 );
+ BOOST_CHECK_EQUAL( G2.nrNodes(), 2 );
+ BOOST_CHECK_EQUAL( G2.nrEdges(), 0 );
+ BOOST_CHECK_EQUAL( G2.isConnected(), false );
+ G2.checkConsistency();
+ BOOST_CHECK( !(G2 == G0) );
+
+ typedef DAG::Edge Edge;
+ std::vector<Edge> edges;
+ edges.push_back( Edge( 0, 1 ) );
+ edges.push_back( Edge( 1, 2 ) );
+ edges.push_back( Edge( 2, 1 ) );
+ edges.push_back( Edge( 1, 2 ) );
+ DAG G3( 3, edges.begin(), edges.end() );
+ BOOST_CHECK_EQUAL( G3.nrNodes(), 3 );
+ BOOST_CHECK_EQUAL( G3.nrEdges(), 2 );
+ BOOST_CHECK_EQUAL( G3.isConnected(), true );
+ G3.checkConsistency();
+ BOOST_CHECK( !(G3 == G0) );
+ BOOST_CHECK( !(G3 == G2) );
+
+ DAG G4( G3 );
+ BOOST_CHECK( !(G4 == G0) );
+ BOOST_CHECK( !(G4 == G2) );
+ BOOST_CHECK( G4 == G3 );
+
+ DAG G5 = G3;
+ BOOST_CHECK( !(G5 == G0) );
+ BOOST_CHECK( !(G5 == G2) );
+ BOOST_CHECK( G5 == G3 );
+}
+
+
+BOOST_AUTO_TEST_CASE( NeighborTest ) {
+ // check pa(), ch() accessors / mutators
+ typedef DAG::Edge Edge;
+ std::vector<Edge> edges;
+ edges.push_back( Edge( 0, 2 ) );
+ edges.push_back( Edge( 1, 2 ) );
+ edges.push_back( Edge( 1, 3 ) );
+ DAG G( 4, edges.begin(), edges.end() );
+
+ BOOST_CHECK_EQUAL( G.pa(0).size(), 0 );
+ BOOST_CHECK_EQUAL( G.pa(1).size(), 0 );
+ BOOST_CHECK_EQUAL( G.pa(2).size(), 2 );
+ BOOST_CHECK_EQUAL( G.pa(3).size(), 1 );
+ BOOST_CHECK_EQUAL( G.pa(2,0).iter, 0 );
+ BOOST_CHECK_EQUAL( G.pa(2,0).node, 0 );
+ BOOST_CHECK_EQUAL( G.pa(2,0).dual, 0 );
+ BOOST_CHECK_EQUAL( G.pa(2,1).iter, 1 );
+ BOOST_CHECK_EQUAL( G.pa(2,1).node, 1 );
+ BOOST_CHECK_EQUAL( G.pa(2,1).dual, 0 );
+ BOOST_CHECK_EQUAL( G.pa(3,0).iter, 0 );
+ BOOST_CHECK_EQUAL( G.pa(3,0).node, 1 );
+ BOOST_CHECK_EQUAL( G.pa(3,0).dual, 1 );
+
+ BOOST_CHECK( G.paSet(0) == SmallSet<size_t>() );
+ BOOST_CHECK( G.paSet(1) == SmallSet<size_t>() );
+ BOOST_CHECK( G.paSet(2) == SmallSet<size_t>(0,1) );
+ BOOST_CHECK( G.paSet(3) == SmallSet<size_t>(1) );
+
+ BOOST_CHECK_EQUAL( G.ch(0).size(), 1 );
+ BOOST_CHECK_EQUAL( G.ch(1).size(), 2 );
+ BOOST_CHECK_EQUAL( G.ch(2).size(), 0 );
+ BOOST_CHECK_EQUAL( G.ch(3).size(), 0 );
+ BOOST_CHECK_EQUAL( G.ch(0,0).iter, 0 );
+ BOOST_CHECK_EQUAL( G.ch(0,0).node, 2 );
+ BOOST_CHECK_EQUAL( G.ch(0,0).dual, 0 );
+ BOOST_CHECK_EQUAL( G.ch(1,0).iter, 0 );
+ BOOST_CHECK_EQUAL( G.ch(1,0).node, 2 );
+ BOOST_CHECK_EQUAL( G.ch(1,0).dual, 1 );
+ BOOST_CHECK_EQUAL( G.ch(1,1).iter, 1 );
+ BOOST_CHECK_EQUAL( G.ch(1,1).node, 3 );
+ BOOST_CHECK_EQUAL( G.ch(1,1).dual, 0 );
+
+ BOOST_CHECK( G.chSet(0) == SmallSet<size_t>(2) );
+ BOOST_CHECK( G.chSet(1) == SmallSet<size_t>(2,3) );
+ BOOST_CHECK( G.chSet(2) == SmallSet<size_t>() );
+ BOOST_CHECK( G.chSet(3) == SmallSet<size_t>() );
+}
+
+
+BOOST_AUTO_TEST_CASE( AddEraseTest ) {
+ // check addition and erasure of nodes and edges
+ typedef DAG::Edge Edge;
+ std::vector<Edge> edges;
+ edges.push_back( Edge( 0, 1 ) );
+ edges.push_back( Edge( 1, 2 ) );
+ edges.push_back( Edge( 1, 0 ) );
+ DAG G( 2 );
+ G.construct( 3, edges.begin(), edges.end() );
+ G.checkConsistency();
+ BOOST_CHECK_EQUAL( G.nrNodes(), 3 );
+ BOOST_CHECK_EQUAL( G.nrEdges(), 2 );
+ BOOST_CHECK_EQUAL( G, DAG(3).addEdge(0,1).addEdge(1,2) );
+ BOOST_CHECK_EQUAL( G.addNode(), 3 );
+ BOOST_CHECK_EQUAL( G, DAG(4).addEdge(0,1).addEdge(1,2) );
+ G.checkConsistency();
+ std::vector<size_t> pa;
+ pa.push_back( 3 );
+ BOOST_CHECK_EQUAL( G.addNode( pa.begin(), pa.end() ), 4 );
+ BOOST_CHECK_EQUAL( G, DAG(5).addEdge(0,1).addEdge(1,2).addEdge(3,4) );
+ BOOST_CHECK_EQUAL( G.addNode(), 5 );
+ BOOST_CHECK_EQUAL( G, DAG(6).addEdge(0,1).addEdge(1,2).addEdge(3,4) );
+ G.checkConsistency();
+ G.addEdge( 0, 4 );
+ BOOST_CHECK_EQUAL( G, DAG(6).addEdge(0,1).addEdge(1,2).addEdge(3,4).addEdge(0,4) );
+ G.checkConsistency();
+ G.addEdge( 0, 5 );
+ BOOST_CHECK_EQUAL( G, DAG(6).addEdge(0,1).addEdge(1,2).addEdge(3,4).addEdge(0,4).addEdge(0,5) );
+ G.checkConsistency();
+ BOOST_CHECK_EQUAL( G.nrNodes(), 6 );
+ BOOST_CHECK_EQUAL( G.nrEdges(), 5 );
+ G.addEdge( 2, 3 );
+ BOOST_CHECK_EQUAL( G, DAG(6).addEdge(0,1).addEdge(1,2).addEdge(3,4).addEdge(0,4).addEdge(0,5).addEdge(2,3) );
+ G.addEdge( 3, 0 );
+ BOOST_CHECK_EQUAL( G, DAG(6).addEdge(0,1).addEdge(1,2).addEdge(3,4).addEdge(0,4).addEdge(0,5).addEdge(2,3) );
+
+ G.addEdge( 5, 3 );
+ BOOST_CHECK_EQUAL( G, DAG(6).addEdge(0,1).addEdge(1,2).addEdge(3,4).addEdge(0,4).addEdge(0,5).addEdge(2,3).addEdge(5,3) );
+ G.eraseNode( 0 );
+ BOOST_CHECK_EQUAL( G, DAG(5).addEdge(0,1).addEdge(1,2).addEdge(4,2).addEdge(2,3) );
+ G.checkConsistency();
+ G.eraseEdge( 0, 1 );
+ BOOST_CHECK_EQUAL( G, DAG(5).addEdge(1,2).addEdge(4,2).addEdge(2,3) );
+ G.checkConsistency();
+ BOOST_CHECK( !G.isConnected() );
+ G.eraseNode( 0 );
+ BOOST_CHECK_EQUAL( G, DAG(4).addEdge(0,1).addEdge(3,1).addEdge(1,2) );
+ G.checkConsistency();
+ G.addEdge( 3, 2 );
+ BOOST_CHECK_EQUAL( G, DAG(4).addEdge(0,1).addEdge(3,1).addEdge(1,2).addEdge(3,2) );
+ G.checkConsistency();
+ G.eraseNode( 1 );
+ BOOST_CHECK_EQUAL( G, DAG(3).addEdge(2,1) );
+ G.checkConsistency();
+ BOOST_CHECK( !G.isConnected() );
+ G.eraseNode( 2 );
+ BOOST_CHECK_EQUAL( G, DAG(2) );
+ G.checkConsistency();
+ BOOST_CHECK( !G.isConnected() );
+ G.addEdge( 1, 0 );
+ BOOST_CHECK_EQUAL( G, DAG(2).addEdge(1,0) );
+ G.checkConsistency();
+ BOOST_CHECK( G.isConnected() );
+ G.eraseNode( 1 );
+ BOOST_CHECK_EQUAL( G, DAG(1) );
+ G.checkConsistency();
+ BOOST_CHECK( G.isConnected() );
+ G.eraseNode( 0 );
+ BOOST_CHECK_EQUAL( G, DAG() );
+ BOOST_CHECK( G.isConnected() );
+ BOOST_CHECK_EQUAL( G.nrNodes(), 0 );
+ BOOST_CHECK_EQUAL( G.nrEdges(), 0 );
+
+ G.addNode();
+ G.addNode();
+ G.addNode();
+ G.addNode();
+ G.addEdge( 0, 1 );
+ G.addEdge( 2, 3 );
+ G.addEdge( 0, 3 );
+ G.checkConsistency();
+ G.eraseNode( 2 );
+ G.checkConsistency();
+}
+
+
+BOOST_AUTO_TEST_CASE( RandomAddEraseTest ) {
+ // check adding and erasing nodes and edges randomly
+ DAG G;
+ for( size_t maxN = 2; maxN < 50; maxN++ )
+ for( size_t repeats = 0; repeats < 10000; repeats++ ) {
+ size_t action = rnd( 5 );
+ size_t N = G.nrNodes();
+ size_t M = G.nrEdges();
+ size_t maxM = N * (N - 1) / 2;
+ if( action == 0 ) {
+ // add node
+ if( N < maxN )
+ G.addNode();
+ } else if( action == 1 ) {
+ // erase node
+ if( N > 0 )
+ G.eraseNode( rnd( N ) );
+ } else if( action == 2 || action == 3 ) {
+ // add edge
+ if( N >= 2 && M < maxM ) {
+ size_t n1 = 0;
+ size_t n2 = 0;
+ do {
+ n1 = rnd( N );
+ n2 = rnd( N );
+ } while( n1 == n2 || G.ch(n1).size() >= N - 1 || G.pa(n2).size() >= N - 1 || G.hasEdge( n1, n2 ) || G.existsDirectedPath( n2, n1 ) );
+ G.addEdge( n1, n2 );
+ }
+ } else if( action == 4 ) {
+ // erase edge
+ if( M > 0 ) {
+ size_t n1 = 0;
+ do {
+ n1 = rnd( N );
+ } while( G.ch(n1).size() == 0 );
+ size_t n2 = 0;
+ do {
+ n2 = rnd( N );
+ } while( !G.hasEdge( n1, n2 ) );
+ G.eraseEdge( n1, n2 );
+ }
+ }
+ G.checkConsistency();
+ }
+}
+
+
+BOOST_AUTO_TEST_CASE( QueriesTest ) {
+ // check queries which have not been tested in another test case
+ typedef DAG::Edge Edge;
+ std::vector<Edge> edges;
+ edges.push_back( Edge( 0, 1 ) );
+ edges.push_back( Edge( 0, 3 ) );
+ edges.push_back( Edge( 2, 3 ) );
+ DAG G( 4, edges.begin(), edges.end() );
+ G.checkConsistency();
+
+ BOOST_CHECK( !G.hasEdge( 0, 0 ) );
+ BOOST_CHECK( G.hasEdge( 0, 1 ) );
+ BOOST_CHECK( !G.hasEdge( 0, 2 ) );
+ BOOST_CHECK( G.hasEdge( 0, 3 ) );
+ BOOST_CHECK( !G.hasEdge( 1, 0 ) );
+ BOOST_CHECK( !G.hasEdge( 1, 1 ) );
+ BOOST_CHECK( !G.hasEdge( 1, 2 ) );
+ BOOST_CHECK( !G.hasEdge( 1, 3 ) );
+ BOOST_CHECK( !G.hasEdge( 2, 0 ) );
+ BOOST_CHECK( !G.hasEdge( 2, 1 ) );
+ BOOST_CHECK( !G.hasEdge( 2, 2 ) );
+ BOOST_CHECK( G.hasEdge( 2, 3 ) );
+ BOOST_CHECK( !G.hasEdge( 3, 0 ) );
+ BOOST_CHECK( !G.hasEdge( 3, 1 ) );
+ BOOST_CHECK( !G.hasEdge( 3, 2 ) );
+ BOOST_CHECK( !G.hasEdge( 3, 3 ) );
+
+ BOOST_CHECK_THROW( G.findPa( 0, 0 ), Exception );
+ BOOST_CHECK_THROW( G.findPa( 0, 1 ), Exception );
+ BOOST_CHECK_THROW( G.findPa( 0, 2 ), Exception );
+ BOOST_CHECK_THROW( G.findPa( 0, 3 ), Exception );
+ BOOST_CHECK_EQUAL( G.findPa( 1, 0 ), 0 );
+ BOOST_CHECK_THROW( G.findPa( 1, 1 ), Exception );
+ BOOST_CHECK_THROW( G.findPa( 1, 2 ), Exception );
+ BOOST_CHECK_THROW( G.findPa( 1, 3 ), Exception );
+ BOOST_CHECK_THROW( G.findPa( 2, 0 ), Exception );
+ BOOST_CHECK_THROW( G.findPa( 2, 1 ), Exception );
+ BOOST_CHECK_THROW( G.findPa( 2, 2 ), Exception );
+ BOOST_CHECK_THROW( G.findPa( 2, 3 ), Exception );
+ BOOST_CHECK_EQUAL( G.findPa( 3, 0 ), 0 );
+ BOOST_CHECK_THROW( G.findPa( 3, 1 ), Exception );
+ BOOST_CHECK_EQUAL( G.findPa( 3, 2 ), 1 );
+ BOOST_CHECK_THROW( G.findPa( 3, 3 ), Exception );
+
+ BOOST_CHECK_THROW( G.findCh( 0, 0 ), Exception );
+ BOOST_CHECK_EQUAL( G.findCh( 0, 1 ), 0 );
+ BOOST_CHECK_THROW( G.findCh( 0, 2 ), Exception );
+ BOOST_CHECK_EQUAL( G.findCh( 0, 3 ), 1 );
+ BOOST_CHECK_THROW( G.findCh( 1, 0 ), Exception );
+ BOOST_CHECK_THROW( G.findCh( 1, 1 ), Exception );
+ BOOST_CHECK_THROW( G.findCh( 1, 2 ), Exception );
+ BOOST_CHECK_THROW( G.findCh( 1, 3 ), Exception );
+ BOOST_CHECK_THROW( G.findCh( 2, 0 ), Exception );
+ BOOST_CHECK_THROW( G.findCh( 2, 1 ), Exception );
+ BOOST_CHECK_THROW( G.findCh( 2, 2 ), Exception );
+ BOOST_CHECK_EQUAL( G.findCh( 2, 3 ), 0 );
+ BOOST_CHECK_THROW( G.findCh( 3, 0 ), Exception );
+ BOOST_CHECK_THROW( G.findCh( 3, 1 ), Exception );
+ BOOST_CHECK_THROW( G.findCh( 3, 2 ), Exception );
+ BOOST_CHECK_THROW( G.findCh( 3, 3 ), Exception );
+
+ BOOST_CHECK( G.existsDirectedPath( 0, 0 ) );
+ BOOST_CHECK( G.existsDirectedPath( 0, 1 ) );
+ BOOST_CHECK( !G.existsDirectedPath( 0, 2 ) );
+ BOOST_CHECK( G.existsDirectedPath( 0, 3 ) );
+ BOOST_CHECK( !G.existsDirectedPath( 1, 0 ) );
+ BOOST_CHECK( G.existsDirectedPath( 1, 1 ) );
+ BOOST_CHECK( !G.existsDirectedPath( 1, 2 ) );
+ BOOST_CHECK( !G.existsDirectedPath( 1, 3 ) );
+ BOOST_CHECK( !G.existsDirectedPath( 2, 0 ) );
+ BOOST_CHECK( !G.existsDirectedPath( 2, 1 ) );
+ BOOST_CHECK( G.existsDirectedPath( 2, 2 ) );
+ BOOST_CHECK( G.existsDirectedPath( 2, 3 ) );
+ BOOST_CHECK( !G.existsDirectedPath( 3, 0 ) );
+ BOOST_CHECK( !G.existsDirectedPath( 3, 1 ) );
+ BOOST_CHECK( !G.existsDirectedPath( 3, 2 ) );
+ BOOST_CHECK( G.existsDirectedPath( 3, 3 ) );
+
+ std::set<size_t> s;
+ G.addNode();
+ G.addEdge( 3, 4 );
+ G.addNode();
+ G.addEdge( 1, 4 );
+ G.addEdge( 1, 5 );
+ BOOST_CHECK( G.descendants( 4 ) == s );
+ BOOST_CHECK( G.descendants( 5 ) == s );
+ s.insert( 4 );
+ BOOST_CHECK( G.descendants( 3 ) == s );
+ s.insert( 5 );
+ BOOST_CHECK( G.descendants( 1 ) == s );
+ s.erase( 5 );
+ s.insert( 3 );
+ BOOST_CHECK( G.descendants( 2 ) == s );
+ s.insert( 1 );
+ s.insert( 5 );
+ BOOST_CHECK( G.descendants( 0 ) == s );
+
+ s.clear();
+ BOOST_CHECK( G.ancestors( 0 ) == s );
+ BOOST_CHECK( G.ancestors( 2 ) == s );
+ s.insert( 0 );
+ BOOST_CHECK( G.ancestors( 1 ) == s );
+ s.insert( 2 );
+ BOOST_CHECK( G.ancestors( 3 ) == s );
+ s.erase( 2 );
+ s.insert( 1 );
+ BOOST_CHECK( G.ancestors( 5 ) == s );
+ s.insert( 2 );
+ s.insert( 3 );
+ BOOST_CHECK( G.ancestors( 4 ) == s );
+}
+
+
+BOOST_AUTO_TEST_CASE( StreamTest ) {
+ // check printDot
+ DAG G( 4 );
+ G.addEdge( 0, 1 );
+ G.addEdge( 0, 2 );
+ G.addEdge( 1, 3 );
+ G.addEdge( 2, 3 );
+ G.addEdge( 2, 2 );
+ G.addEdge( 3, 2 );
+
+ std::stringstream ss;
+ std::string s;
+
+ G.printDot( ss );
+ std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "digraph DAG {" );
+ std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "node[shape=circle,width=0.4,fixedsize=true];" );
+ std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "\tx0;" );
+ std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "\tx1;" );
+ std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "\tx2;" );
+ std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "\tx3;" );
+ std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "\tx0 -> x1;" );
+ std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "\tx0 -> x2;" );
+ std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "\tx1 -> x3;" );
+ std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "\tx2 -> x3;" );
+ std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "}" );
+
+ ss << G;
+ std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "digraph DAG {" );
+ std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "node[shape=circle,width=0.4,fixedsize=true];" );
+ std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "\tx0;" );
+ std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "\tx1;" );
+ std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "\tx2;" );
+ std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "\tx3;" );
+ std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "\tx0 -> x1;" );
+ std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "\tx0 -> x2;" );
+ std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "\tx1 -> x3;" );
+ std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "\tx2 -> x3;" );
+ std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "}" );
+}
BOOST_CHECK_EQUAL( G.nb(2,0).iter, 0 );
BOOST_CHECK_EQUAL( G.nb(2,0).node, 1 );
BOOST_CHECK_EQUAL( G.nb(2,0).dual, 1 );
+ BOOST_CHECK( G.nbSet(0) == SmallSet<size_t>( 1 ) );
+ BOOST_CHECK( G.nbSet(1) == SmallSet<size_t>( 0, 2 ) );
+ BOOST_CHECK( G.nbSet(2) == SmallSet<size_t>( 1 ) );
}
projects / libdai.git / commitdiff