Added DAG class and various minor improvements
authorJoris Mooij <joris.mooij@tuebingen.mpg.de>
Wed, 5 May 2010 09:17:55 +0000 (11:17 +0200)
committerJoris Mooij <joris.mooij@tuebingen.mpg.de>
Wed, 5 May 2010 09:17:55 +0000 (11:17 +0200)
12 files changed:
ChangeLog
Makefile
examples/example_imagesegmentation.cpp
include/dai/bipgraph.h
include/dai/dag.h [new file with mode: 0644]
include/dai/doc.h
include/dai/graph.h
src/bipgraph.cpp
src/dag.cpp [new file with mode: 0644]
src/graph.cpp
tests/unit/dag_test.cpp [new file with mode: 0644]
tests/unit/graph_test.cpp

index 0177d8c..01d9255 100644 (file)
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,6 +1,7 @@
 git master HEAD
 ---------------
 
 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
 * Improved regression test
 * Added examples/example_imagesegmentation
 * [Ofer Meshi] Added a script for converting from FastInf to libDAI format
@@ -158,6 +159,7 @@ git master HEAD
   - Fixed bug in createGraphGrid3D()
   - Fixed bug in createGraphRegular()
   - Added GraphAL::hasEdge(size_t,size_t)
   - 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:
   - Added GraphAL::operator==( const GraphAL& )
   - Added operator<<( std::ostream&, const GraphAL& )
 * Improved smallset.h/cpp:
index c44c637..8b112df 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -44,7 +44,7 @@ ifdef WITH_DOC
 endif
 
 # Define conditional build targets
 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
 ifdef WITH_BP
   WITHFLAGS:=$(WITHFLAGS) -DDAI_WITH_BP
   NAMES:=$(NAMES) bp
@@ -91,7 +91,7 @@ ifdef WITH_CBP
 endif
 
 # Define standard libDAI header dependencies, source file names and object file names
 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))
 
 SOURCES:=$(foreach name,$(NAMES),$(SRC)/$(name).cpp)
 OBJECTS:=$(foreach name,$(NAMES),$(name)$(OE))
 
@@ -121,12 +121,13 @@ examples : examples/example$(EE) examples/example_bipgraph$(EE) examples/example
 
 matlabs : matlab/dai$(ME) matlab/dai_readfg$(ME) matlab/dai_writefg$(ME) matlab/dai_potstrength$(ME)
 
 
 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)
        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)
        tests/unit/bipgraph_test$(EE)
        tests/unit/weightedgraph_test$(EE)
        tests/unit/enum_test$(EE)
@@ -298,7 +299,7 @@ clean :
        -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 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
        -rm factorgraph_test.fg alldai_test.aliases
        -rm utils/fg2dot$(EE) utils/createfg$(EE) utils/fginfo$(EE) utils/uai2fg$(EE)
        -rm -R doc
index aa85ab8..dc9b3da 100644 (file)
@@ -209,6 +209,9 @@ int main(int argc,char **argv) {
     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 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
     const char *file_fg = cimg_option( "-fg", "", "Output factor graph" );
 
     // Read input images
@@ -274,16 +277,7 @@ int main(int argc,char **argv) {
     CImgDisplay disp5( dimx, dimy, "Beliefs during inference", 0 );
     vector<double> m; // Stores the final magnetizations
     cout << "Solving the inference problem...please be patient!" << endl;
     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++ )
 
     // Visualize the final magnetizations
     for( size_t i = 0; i < dimx; i++ )
index 530e51e..4dbd543 100644 (file)
@@ -283,7 +283,7 @@ class BipartiteGraph {
         /// 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.
          */
         /// 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
     //@}
 
     /// \name Erasing nodes and edges
@@ -380,7 +380,7 @@ class BipartiteGraph {
         /// 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
         /// 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() )
          */
         bool operator==( const BipartiteGraph& x ) const {
             if( nrNodes1() != x.nrNodes1() )
diff --git a/include/dai/dag.h b/include/dai/dag.h
new file mode 100644 (file)
index 0000000..5a188e0
--- /dev/null
@@ -0,0 +1,393 @@
+/*  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
index a24ee2f..6b7eba6 100644 (file)
@@ -11,6 +11,9 @@
 /** \file
  *  \brief Contains additional doxygen documentation
  *
 /** \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
  *  \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
index b2e0623..7953a4f 100644 (file)
@@ -22,6 +22,7 @@
 #include <algorithm>
 #include <dai/util.h>
 #include <dai/exceptions.h>
 #include <algorithm>
 #include <dai/util.h>
 #include <dai/exceptions.h>
+#include <dai/smallset.h>
 
 
 namespace dai {
 
 
 namespace dai {
@@ -209,7 +210,7 @@ class GraphAL {
         /// 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.
          */
         /// 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
     //@}
 
     /// \name Erasing nodes and edges
@@ -262,6 +263,9 @@ class GraphAL {
             return nb(n1).size();
         }
 
             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;
 
         /// Returns true if the graph is connected
         bool isConnected() const;
 
@@ -274,7 +278,7 @@ class GraphAL {
         /// 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
         /// 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() )
          */
         bool operator==( const GraphAL& x ) const {
             if( nrNodes() != x.nrNodes() )
index e6e3244..afd0472 100644 (file)
@@ -18,7 +18,7 @@ namespace dai {
 using namespace std;
 
 
 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;
     DAI_ASSERT( n1 < nrNodes1() );
     DAI_ASSERT( n2 < nrNodes2() );
     bool exists = false;
@@ -36,6 +36,7 @@ void BipartiteGraph::addEdge( size_t n1, size_t n2, bool check ) {
         nb1(n1).push_back( nb_1 );
         nb2(n2).push_back( nb_2 );
     }
         nb1(n1).push_back( nb_1 );
         nb2(n2).push_back( nb_2 );
     }
+    return *this;
 }
 
 
 }
 
 
@@ -50,13 +51,10 @@ void BipartiteGraph::eraseNode1( size_t n1 ) {
             if( m1.node == n1 ) {
                 // delete this entry, because it points to the deleted node
                 nb2(n2).erase( nb2(n2).begin() + iter );
             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
             } 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++;
             }
                 nb1( m1.node, m1.dual ).dual = iter;
                 m1.iter = iter++;
             }
@@ -76,13 +74,10 @@ void BipartiteGraph::eraseNode2( size_t n2 ) {
             if( m2.node == n2 ) {
                 // delete this entry, because it points to the deleted node
                 nb1(n1).erase( nb1(n1).begin() + 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
             } 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++;
             }
                 nb2( m2.node, m2.dual ).dual = iter;
                 m2.iter = iter++;
             }
diff --git a/src/dag.cpp b/src/dag.cpp
new file mode 100644 (file)
index 0000000..8b4e989
--- /dev/null
@@ -0,0 +1,279 @@
+/*  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
index 501fa75..3667f09 100644 (file)
@@ -10,9 +10,6 @@
 
 
 #include <dai/graph.h>
 
 
 #include <dai/graph.h>
-#include <dai/weightedgraph.h>
-#include <boost/graph/adjacency_list.hpp>
-#include <boost/graph/connected_components.hpp>
 
 
 namespace dai {
 
 
 namespace dai {
@@ -21,7 +18,7 @@ namespace dai {
 using namespace std;
 
 
 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;
     DAI_ASSERT( n1 < nrNodes() );
     DAI_ASSERT( n2 < nrNodes() );
     bool exists = false;
@@ -39,6 +36,7 @@ void GraphAL::addEdge( size_t n1, size_t n2, bool check ) {
         nb(n1).push_back( nb_1 );
         nb(n2).push_back( nb_2 );
     }
         nb(n1).push_back( nb_1 );
         nb(n2).push_back( nb_2 );
     }
+    return *this;
 }
 
 
 }
 
 
@@ -53,13 +51,10 @@ void GraphAL::eraseNode( size_t n ) {
             if( m.node == n ) {
                 // delete this entry, because it points to the deleted node
                 nb(n2).erase( nb(n2).begin() + iter );
             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
             } 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++;
             }
                 nb( m.node, m.dual ).dual = iter;
                 m.iter = iter++;
             }
@@ -101,6 +96,14 @@ void GraphAL::eraseEdge( size_t n1, size_t n2 ) {
 }
 
 
 }
 
 
+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;
 bool GraphAL::isConnected() const {
     if( nrNodes() == 0 ) {
         return true;
@@ -227,16 +230,6 @@ void GraphAL::checkConsistency() const {
             iter++;
         }
     }
             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++;
-        }
-    }
 }
 
 
 }
 
 
diff --git a/tests/unit/dag_test.cpp b/tests/unit/dag_test.cpp
new file mode 100644 (file)
index 0000000..35209c9
--- /dev/null
@@ -0,0 +1,400 @@
+/*  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, "}" );
+}
index 9adfef1..b1c6fdd 100644 (file)
@@ -88,6 +88,9 @@ BOOST_AUTO_TEST_CASE( NeighborTest ) {
     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_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 ) );
 }
 
 
 }