Made members Neighbor, Neighbors and Edge of Graph, BipartiteGraph and DAG global
authorJoris Mooij <joris.mooij@tuebingen.mpg.de>
Thu, 5 Aug 2010 12:58:18 +0000 (14:58 +0200)
committerJoris Mooij <joris.mooij@tuebingen.mpg.de>
Thu, 5 Aug 2010 12:58:18 +0000 (14:58 +0200)
19 files changed:
ChangeLog
examples/example_bipgraph.cpp
include/dai/bipgraph.h
include/dai/clustergraph.h
include/dai/dag.h
include/dai/doc.h
include/dai/factorgraph.h
include/dai/graph.h
include/dai/mr.h
include/dai/weightedgraph.h
src/bbp.cpp
src/bp_dual.cpp
src/regiongraph.cpp
swig/dai.i
tests/unit/bipgraph_test.cpp
tests/unit/clustergraph_test.cpp
tests/unit/dag_test.cpp
tests/unit/graph_test.cpp
utils/createfg.cpp

index 043b2f9..577ce6a 100644 (file)
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,11 @@
 git HEAD
 --------
+* Deprecated Graph::Neighbor, BipartiteGraph::Neighbor and DAG::Neighbor
+  and replaced them by a globally defined Neighbor structure
+* Deprecated Graph::Neighbors, BipartiteGraph::Neighbors and DAG::Neighbors
+  and replaced them by a globally defined Neighbors type
+* Deprecated Graph::Edge, BipartiteGraph::Edge and DAG::Edge
+  and replaced them by a globally defined Edge type
 * Added io.h/io.cpp which currently provides functionality for reading
   files in the UAI Approximate Inference Challenge fileformats
   (supporting both the 2006/2008 evidence file format and the 2010
index ff5ebae..a5302d6 100644 (file)
@@ -15,13 +15,13 @@ using namespace dai;
 
 int main() {
     // Create a list of edges
-    vector<BipartiteGraph::Edge> edges;
+    vector<Edge> edges;
     edges.reserve( 5 );
-    edges.push_back( BipartiteGraph::Edge(0, 0) );
-    edges.push_back( BipartiteGraph::Edge(1, 0) );
-    edges.push_back( BipartiteGraph::Edge(2, 0) );
-    edges.push_back( BipartiteGraph::Edge(1, 1) );
-    edges.push_back( BipartiteGraph::Edge(2, 1) );
+    edges.push_back( Edge(0, 0) );
+    edges.push_back( Edge(1, 0) );
+    edges.push_back( Edge(2, 0) );
+    edges.push_back( Edge(1, 1) );
+    edges.push_back( Edge(2, 1) );
 
     // Create a bipartite graph with 3 nodes of type 1,
     // 2 nodes of type 2 and edge list edges.
@@ -34,7 +34,7 @@ int main() {
     for( size_t n1 = 0; n1 < G.nrNodes1(); n1++ ) {
         cout << "Node " << n1 << " of type 1 has " << G.nb1(n1).size() << " neighbors:" << endl;
         // Iterate over all neighbors n2 of n1
-        foreach( const BipartiteGraph::Neighbor &n2, G.nb1(n1) ) {
+        foreach( const Neighbor &n2, G.nb1(n1) ) {
             // The n2.iter'th neighbor of n1 is n2:
             DAI_ASSERT( G.nb1(n1)[n2.iter] == n2 );
 
index 4dbd543..999e5d3 100644 (file)
@@ -23,6 +23,7 @@
 #include <dai/util.h>
 #include <dai/smallset.h>
 #include <dai/exceptions.h>
+#include <dai/graph.h>
 
 
 namespace dai {
@@ -33,7 +34,7 @@ namespace dai {
  *  nodes of different type. Nodes are indexed by an unsigned integer. If there are nrNodes1()
  *  nodes of type 1 and nrNodes2() nodes of type 2, the nodes of type 1 are numbered
  *  0,1,2,...,nrNodes1()-1 and the nodes of type 2 are numbered 0,1,2,...,nrNodes2()-1. An edge
- *  between node \a n1 of type 1 and node \a n2 of type 2 is represented by a BipartiteGraph::Edge(\a n1,\a n2).
+ *  between node \a n1 of type 1 and node \a n2 of type 2 is represented by a Edge(\a n1,\a n2).
  *
  *  A BipartiteGraph is implemented as a sparse adjacency list, i.e., it stores for each node a list of
  *  its neighboring nodes. More precisely: it stores for each node of type 1 a vector of Neighbor structures
@@ -45,85 +46,20 @@ namespace dai {
  *  \idea Cache second-order neighborhoods in BipartiteGraph.
  */
 class BipartiteGraph {
-    public:
         /// Describes the neighbor relationship of two nodes in a BipartiteGraph.
-        /** 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 a list of neighbors,
-         *  stored as a std::vector<\link Neighbor \endlink>, and 
-         *  extra information is included in the Neighbor struct which 
-         *  allows us to access a node as a neighbor of its neighbor 
-         *  (the \c dual member).
-         *
-         *  By convention, variable identifiers naming indices into a
-         *  vector of neighbors are prefixed with an underscore ("_").
-         *  The neighbor list which they point into is then understood
-         *  from context. For example:
-         *
-         *  \code
-         *  void BP::calcNewMessage( size_t i, size_t _I )
-         *  \endcode
-         *
-         *  Here, \a i is the "absolute" index of node i, but \a _I is
-         *  understood as a "relative" index, giving node \a I 's entry in
-         *  <tt>nb1(i)</tt>. The corresponding Neighbor structure can be
-         *  accessed as <tt>nb1(i,_I)</tt> or <tt>nb1(i)[_I]</tt>. The 
-         *  absolute index of \a _I, which would be called \a I, can be 
-         *  recovered from the \c node member: <tt>nb1(i,_I).node</tt>. 
-         *  The \c iter member gives the relative index \a _I, and the 
-         *  \c dual member gives the "dual" relative index, i.e., the 
-         *  index of \a i in \a I 's neighbor list.
-         *
-         *  \code
-         *  Neighbor n = nb1(i,_I);
-         *  n.node == I &&
-         *  n.iter == _I &&
-         *  nb2(n.node,n.dual).node == i
-         *  \endcode
-         *
-         *  In a FactorGraph, the nodes of type 1 represent variables, and
-         *  the nodes of type 2 represent factors. For convenience, nb1() is 
-         *  called FactorGraph::nbV(), and nb2() is called FactorGraph::nbF().
-         *
-         *  There is no easy way to transform a pair of absolute node
-         *  indices \a i and \a I into a Neighbor structure relative
-         *  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 < nrVars(); ++i )
-         *      foreach( const Neighbor &I, nbV(i) )
-         *          calcNewMessage( i, I.iter );
-         *  \endcode
+        /** \deprecated Please use dai::Neighbor instead
          */
-        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; }
-        };
+        typedef dai::Neighbor Neighbor;
 
         /// Describes the neighbors of some node.
-        typedef std::vector<Neighbor> Neighbors;
+        /** \deprecated Please use dai::Neighbors instead
+         */
+        typedef dai::Neighbors Neighbors;
 
         /// Represents an edge: an Edge(\a n1,\a n2) corresponds to the edge between node \a n1 of type 1 and node \a n2 of type 2.
-        typedef std::pair<size_t,size_t> Edge;
+        /** \deprecated Please use dai::Edge instead
+         */
+        typedef dai::Edge Edge;
 
     private:
         /// Contains for each node of type 1 a vector of its neighbors
@@ -150,7 +86,7 @@ class BipartiteGraph {
         BipartiteGraph( size_t nr1, size_t nr2 ) : _nb1(nr1), _nb2(nr2) {}
 
         /// Constructs BipartiteGraph from a range of edges.
-        /** \tparam EdgeInputIterator Iterator that iterates over instances of BipartiteGraph::Edge.
+        /** \tparam EdgeInputIterator Iterator that iterates over instances of Edge.
          *  \param nrNodes1 The number of nodes of type 1.
          *  \param nrNodes2 The number of nodes of type 2.
          *  \param begin Points to the first edge.
@@ -217,7 +153,7 @@ class BipartiteGraph {
     /// \name Adding nodes and edges
     //@{
         /// (Re)constructs BipartiteGraph from a range of edges.
-        /** \tparam EdgeInputIterator Iterator that iterates over instances of BipartiteGraph::Edge.
+        /** \tparam EdgeInputIterator Iterator that iterates over instances of Edge.
          *  \param nrNodes1 The number of nodes of type 1.
          *  \param nrNodes2 The number of nodes of type 2.
          *  \param begin Points to the first edge.
index 3e84bd0..c51b3f2 100644 (file)
@@ -35,13 +35,6 @@ namespace dai {
      *  \todo Remove the _vars and _clusters variables and use only the graph and a contextual factor graph.
      */
     class ClusterGraph {
-        public:
-            /// Shorthand for BipartiteGraph::Neighbor
-            typedef BipartiteGraph::Neighbor Neighbor;
-
-            /// Shorthand for BipartiteGraph::Edge
-            typedef BipartiteGraph::Edge     Edge;
-
         private:
             /// Stores the neighborhood structure
             BipartiteGraph       _G;
index 5a188e0..4822e72 100644 (file)
@@ -22,6 +22,7 @@
 #include <dai/util.h>
 #include <dai/exceptions.h>
 #include <dai/smallset.h>
+#include <dai/graph.h>
 
 
 namespace dai {
@@ -31,7 +32,7 @@ namespace dai {
 /** 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).
+ *  from node \a n1 to node \a n2 is represented by a 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
@@ -40,88 +41,20 @@ namespace dai {
  *  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
+        /** \deprecated Please use dai::Neighbor instead
          */
-        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; }
-        };
+        typedef dai::Neighbor Neighbor;
 
         /// Type for storing the parents/children of some node.
-        typedef std::vector<Neighbor> Neighbors;
+        /** \deprecated Please use dai::Neighbors instead
+         */
+        typedef dai::Neighbors 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;
+        /** \deprecated Please use dai::Edge instead
+         */
+        typedef dai::Edge Edge;
 
     private:
         /// Contains for each node a vector of its parent nodes
@@ -140,7 +73,7 @@ class DAG {
         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.
+        /** \tparam EdgeInputIterator Iterator that iterates over instances of Edge.
          *  \param nr The number of nodes.
          *  \param begin Points to the first edge.
          *  \param end Points just beyond the last edge.
@@ -207,7 +140,7 @@ class DAG {
     /// \name Adding nodes and edges
     //@{
         /// (Re)constructs DAG from a range of edges.
-        /** \tparam EdgeInputIterator Iterator that iterates over instances of DAG::Edge.
+        /** \tparam EdgeInputIterator Iterator that iterates over instances of Edge.
          *  \param nr The number of nodes.
          *  \param begin Points to the first edge.
          *  \param end Points just beyond the last edge.
index 829eecf..aa17d0c 100644 (file)
@@ -11,9 +11,6 @@
 /** \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
index 4c384d1..47195ca 100644 (file)
@@ -62,18 +62,10 @@ namespace dai {
  *  (ones/delta/full) and act accordingly. Update: it seems that the proposed functionality 
  *  would not be enough for CBP, for which it would make more sense to add more levels of
  *  backup/restore.
+ *
+ *  \todo Write a method that applies evidence (should we represent evidence as a map<Var,size_t> or as a map<size_t,size_t>?)
  */ 
 class FactorGraph {
-    public:
-        /// Shorthand for BipartiteGraph::Neighbor
-        typedef BipartiteGraph::Neighbor  Neighbor;
-
-        /// Shorthand for BipartiteGraph::Neighbors
-        typedef BipartiteGraph::Neighbors Neighbors;
-
-        /// Shorthand for BipartiteGraph::Edge
-        typedef BipartiteGraph::Edge      Edge;
-
     private:
         /// Stores the neighborhood structure
         BipartiteGraph           _G;
index 7953a4f..e9506af 100644 (file)
 namespace dai {
 
 
+/// Describes the neighbor relationship of two nodes in a graph.
+/** Most graphs that libDAI deals with are sparse. Therefore,
+ *  a fast and memory-efficient way of representing the structure
+ *  of a sparse graph is needed. A frequently used operation that
+ *  also needs to be fast is switching 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.
+ *
+ *  Most sparse graphs in libDAI are represented by storing for each
+ *  node in the graph the set of its neighbors. In practice, this set
+ *  of neighbors is stored using the Neighbors type, which is simply a
+ *  std::vector<\link Neighbor \endlink>. The Neighbor struct contains
+ *  the label of the neighboring node (the \c node member) and 
+ *  additional information which allows to access a node as a neighbor 
+ *  of its neighbor (the \c dual member). For convenience, each Neighbor 
+ *  structure also stores its index in the Neighbors vector that it is 
+ *  part of (the \c iter member).
+ *
+ *  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 the context.
+ *
+ *  Let us denote the \a _j 'th neighbor of node \a i by <tt>nb(i,_j)</tt>,
+ *  which is of the Neighbor type. Here, \a i is the "absolute" index of 
+ *  node \a i, but \a _j is understood as a "relative" index, giving node 
+ *  \a j 's entry in the Neighbors <tt>nb(i)</tt> of node \a i. The absolute
+ *  index of \a _j, which would be denoted \a j, can be recovered from the 
+ *  \c node member, <tt>nb(i,_j).node</tt>. The \c iter member 
+ *  <tt>nb(i,_j).iter</tt> gives the relative index \a _j, and the \c dual 
+ *  member <tt>nb(i,_j).dual</tt> gives the "dual" relative index, i.e., 
+ *  the index of \a i in \a j 's neighbor list.
+ *
+ *  Iteration over edges can be easily accomplished:
+ *  \code
+ *  for( size_t i = 0; i < nrNodes(); ++i ) {
+ *      size_t _j = 0;
+ *      foreach( const Neighbor &j, nb(i) ) {
+ *          assert( j == nb(i,j.iter) );
+ *          assert( nb(j.node,j.dual).node == i );
+ *          assert( _j = j.iter );
+ *          _j++;
+ *      }
+ *  }
+ *  \endcode
+ */
+struct Neighbor {
+    /// Corresponds to the index of this Neighbor entry in the vector of neighbors
+    size_t iter;
+    /// Contains the absolute index of the neighboring node
+    size_t node;
+    /// Contains the "dual" index (i.e., the index of this node in the Neighbors vector of the neighboring node)
+    size_t dual;
+
+    /// Default constructor
+    Neighbor() {}
+    /// Constructor that allows setting the values of the member variables
+    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; }
+};
+
+
+/// Describes the set of neighbors of some node in a graph
+typedef std::vector<Neighbor> Neighbors;
+
+
+/// Represents an edge in a graph: an Edge(\a i,\a j) corresponds to the edge between node \a i and node \a j.
+/** \note If the edge is interpreted as a directed edge, then it points from \a i to \a j.
+ *  \note If the edge is part of a bipartite graph, \a i is understood to correspond to a node of type 1, and
+ *  \a j to a node of type 2.
+ */
+typedef std::pair<size_t,size_t> Edge;
+
+
 /// Represents the neighborhood structure of nodes in an undirected graph.
 /** A graph has nodes connected by edges. Nodes are indexed by an unsigned integer. 
  *  If there are nrNodes() nodes, they are numbered 0,1,2,...,nrNodes()-1. An edge
- *  between node \a n1 and node \a n2 is represented by a GraphAL::Edge(\a n1,\a n2).
+ *  between node \a n1 and node \a n2 is represented by a Edge(\a n1,\a n2).
  *
  *  GraphAL is implemented as a sparse adjacency list, i.e., it stores for each node a list of
  *  its neighboring nodes. The list of neighboring nodes is implemented as a vector of Neighbor
@@ -42,79 +117,19 @@ namespace dai {
 class GraphAL {
     public:
         /// Describes the neighbor relationship of two nodes in a GraphAL.
-        /** 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 a list of neighbors,
-         *  stored as a std::vector<\link Neighbor \endlink>, and 
-         *  extra information is included in the Neighbor struct which 
-         *  allows us to access a node as a neighbor of its neighbor 
-         *  (the \c dual member).
-         *
-         *  By convention, variable identifiers naming indices into a
-         *  vector of neighbors are prefixed with an underscore ("_").
-         *  The neighbor list which they point into is then understood
-         *  from context. For example:
-         *
-         *  \code
-         *  Real MR::T( size_t i, size_t _j );
-         *  \endcode
-         *
-         *  Here, \a i is the "absolute" index of node i, but \a _j is
-         *  understood as a "relative" index, giving node \a j 's entry in
-         *  <tt>nb(i)</tt>. The corresponding Neighbor structure can be
-         *  accessed as <tt>nb(i,_j)</tt> or <tt>nb(i)[_j]</tt>. The 
-         *  absolute index of \a _j, which would be called \a j, can be 
-         *  recovered from the \c node member: <tt>nb(i,_j).node</tt>. 
-         *  The \c iter member gives the relative index \a _j, and the 
-         *  \c dual member gives the "dual" relative index, i.e., the 
-         *  index of \a i in \a j 's neighbor list.
-         *
-         *  \code
-         *  Neighbor n = nb(i,_j);
-         *  n.node == j &&
-         *  n.iter == _j &&
-         *  nb(n.node,n.dual).node == i
-         *  \endcode
-         *
-         *  There is no easy 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, nb(i) )
-         *          T( i, j.iter );
-         *  \endcode
+        /** \deprecated Please use dai::Neighbor instead
          */
-        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; }
-        };
+        typedef dai::Neighbor Neighbor;
 
         /// Describes the neighbors of some node.
-        typedef std::vector<Neighbor> Neighbors;
+        /** \deprecated Please use dai::Neighbors instead
+         */
+        typedef dai::Neighbors Neighbors;
 
         /// Represents an edge: an Edge(\a n1,\a n2) corresponds to the edge between node \a n1 and node \a n2.
-        typedef std::pair<size_t,size_t> Edge;
+        /** \deprecated Please use dai::Edge instead
+         */
+        typedef dai::Edge Edge;
 
     private:
         /// Contains for each node a vector of its neighbors
@@ -130,7 +145,7 @@ class GraphAL {
         GraphAL( size_t nr ) : _nb( nr ) {}
 
         /// Constructs GraphAL from a range of edges.
-        /** \tparam EdgeInputIterator Iterator that iterates over instances of GraphAL::Edge.
+        /** \tparam EdgeInputIterator Iterator that iterates over instances of Edge.
          *  \param nr The number of nodes.
          *  \param begin Points to the first edge.
          *  \param end Points just beyond the last edge.
@@ -172,7 +187,7 @@ class GraphAL {
     /// \name Adding nodes and edges
     //@{
         /// (Re)constructs GraphAL from a range of edges.
-        /** \tparam EdgeInputIterator Iterator that iterates over instances of GraphAL::Edge.
+        /** \tparam EdgeInputIterator Iterator that iterates over instances of Edge.
          *  \param nr The number of nodes.
          *  \param begin Points to the first edge.
          *  \param end Points just beyond the last edge.
index 02daa7e..ed56172 100644 (file)
@@ -43,9 +43,6 @@ class MR : public DAIAlgFG {
         /// The interaction graph (Markov graph)
         GraphAL G;
 
-        /// Convenience shortcut
-        typedef GraphAL::Neighbor Neighbor;
-
         /// tJ[i][_j] is the hyperbolic tangent of the interaction between spin \a i and its neighbour G.nb(i,_j)
         std::vector<std::vector<Real> >                 tJ;
         /// theta[i] is the local field on spin \a i
index d186ea4..1f68c67 100644 (file)
@@ -126,7 +126,7 @@ class GraphEL : public std::set<UEdge> {
         /// Construct from GraphAL
         GraphEL( const GraphAL& G ) {
             for( size_t n1 = 0; n1 < G.nrNodes(); n1++ )
-                foreach( const GraphAL::Neighbor n2, G.nb(n1) )
+                foreach( const Neighbor n2, G.nb(n1) )
                     if( n1 < n2 )
                         insert( UEdge( n1, n2 ) );
         }
index b4bd072..0b31c1f 100644 (file)
@@ -21,10 +21,6 @@ namespace dai {
 using namespace std;
 
 
-/// Convenience typedef
-typedef BipartiteGraph::Neighbor Neighbor;
-
-
 /// Returns the entry of the I'th factor corresponding to a global state
 size_t getFactorEntryForState( const FactorGraph &fg, size_t I, const vector<size_t> &state ) {
     size_t f_entry = 0;
index 1591492..c6b4bbc 100644 (file)
@@ -23,9 +23,6 @@ namespace dai {
 using namespace std;
 
 
-typedef BipartiteGraph::Neighbor Neighbor;
-
-
 void BP_dual::init() {
     regenerateMessages();
     regenerateBeliefs();
index 50b5d04..76dbd73 100644 (file)
@@ -227,7 +227,7 @@ ostream & operator << (ostream & os, const RegionGraph & rg) {
     for( size_t beta = 0; beta < rg.nrIRs(); beta++ )
         os << "\tb" << beta << " [label=\"b" << beta << ": " << (VarSet)rg.IR(beta) << ", c=" << rg.IR(beta).c() << "\"];" << endl;
     for( size_t alpha = 0; alpha < rg.nrORs(); alpha++ )
-        foreach( const RegionGraph::Neighbor &beta, rg.nbOR(alpha) )
+        foreach( const Neighbor &beta, rg.nbOR(alpha) )
             os << "\ta" << alpha << " -> b" << beta << ";" << endl;
     os << "}" << endl;
     return os;
index 8e1e010..fbc0882 100644 (file)
 
 %module dai
 
-        struct Neighbor {
-            size_t iter;
-            size_t node;
-            size_t dual;
-
-            Neighbor() {}
-            Neighbor( size_t iter, size_t node, size_t dual ) : iter(iter), node(node), dual(dual) {}
-
-            operator size_t () const { return node; }
-        };
-
 %{
 #include "../include/dai/var.h"
 #include "../include/dai/smallset.h"
 #include "../include/dai/varset.h"
 #include "../include/dai/prob.h"
 #include "../include/dai/factor.h"
+#include "../include/dai/graph.h"
 #include "../include/dai/bipgraph.h"
 #include "../include/dai/factorgraph.h"
 #include "../include/dai/util.h"
@@ -65,8 +55,8 @@
 };
 
 %template(Factor) dai::TFactor<dai::Real>;
-%include "../include/dai/bipgraph.h"
 %include "../include/dai/graph.h"
+%include "../include/dai/bipgraph.h"
 %include "../include/dai/factorgraph.h"
 %include "std_vector.i"
 // TODO: typemaps for the vectors (input/output python arrays)
@@ -77,10 +67,6 @@ typedef std::vector< VecFactor > VecVecFactor;
 %template(VecFactor) std::vector< dai::Factor >;
 %template(VecVecFactor) std::vector< VecFactor >;
 
-%{
-typedef dai::BipartiteGraph::Neighbor Neighbor;
-%}
-
 %include "../include/dai/index.h"
 %extend dai::multifor {
     inline size_t __getitem__(int i) const {
index a0a08e6..ce1103a 100644 (file)
@@ -24,8 +24,6 @@ using namespace dai;
 
 BOOST_AUTO_TEST_CASE( ConstructorsTest ) {
     // check constructors
-    typedef BipartiteGraph::Edge Edge;
-
     BipartiteGraph G;
     BOOST_CHECK_EQUAL( G.nrNodes1(), 0 );
     BOOST_CHECK_EQUAL( G.nrNodes2(), 0 );
@@ -105,7 +103,6 @@ BOOST_AUTO_TEST_CASE( ConstructorsTest ) {
 
 BOOST_AUTO_TEST_CASE( NeighborTest ) {
     // check nb() accessor / mutator
-    typedef BipartiteGraph::Edge Edge;
     std::vector<Edge> edges;
     edges.push_back( Edge(0, 0) );
     edges.push_back( Edge(0, 1) );
@@ -156,7 +153,6 @@ BOOST_AUTO_TEST_CASE( NeighborTest ) {
 
 BOOST_AUTO_TEST_CASE( AddEraseTest ) {
     // check addition and erasure of nodes and edges
-    typedef BipartiteGraph::Edge Edge;
     std::vector<Edge> edges;
     edges.push_back( Edge( 0, 0 ) );
     edges.push_back( Edge( 0, 1 ) );
@@ -347,7 +343,6 @@ BOOST_AUTO_TEST_CASE( RandomAddEraseTest ) {
 
 BOOST_AUTO_TEST_CASE( QueriesTest ) {
     // check queries which have not been tested in another test case
-    typedef BipartiteGraph::Edge Edge;
     std::vector<Edge> edges;
     edges.push_back( Edge( 0, 1 ) );
     edges.push_back( Edge( 1, 1 ) );
@@ -385,7 +380,6 @@ BOOST_AUTO_TEST_CASE( QueriesTest ) {
 
 BOOST_AUTO_TEST_CASE( StreamTest ) {
     // check printDot
-    typedef BipartiteGraph::Edge Edge;
     std::vector<Edge> edges;
     edges.push_back( Edge(0, 0) );
     edges.push_back( Edge(0, 1) );
index 2d86253..46cefe4 100644 (file)
@@ -127,7 +127,6 @@ BOOST_AUTO_TEST_CASE( ConstructorsTest ) {
     BOOST_CHECK_EQUAL( G4.cluster(1), v12 );
     BOOST_CHECK_EQUAL( G4.cluster(2), v23 );
     BOOST_CHECK_EQUAL( G4.cluster(3), v13 );
-    typedef BipartiteGraph::Edge Edge;
     std::vector<Edge> edges;
     edges.push_back( Edge(0, 0) );
     edges.push_back( Edge(1, 0) );
index 35209c9..36a429e 100644 (file)
@@ -38,7 +38,6 @@ BOOST_AUTO_TEST_CASE( ConstructorsTest ) {
     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 ) );
@@ -66,7 +65,6 @@ BOOST_AUTO_TEST_CASE( ConstructorsTest ) {
 
 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 ) );
@@ -115,7 +113,6 @@ BOOST_AUTO_TEST_CASE( NeighborTest ) {
 
 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 ) );
@@ -248,7 +245,6 @@ BOOST_AUTO_TEST_CASE( RandomAddEraseTest ) {
 
 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 ) );
index b1c6fdd..80d570f 100644 (file)
@@ -39,7 +39,6 @@ BOOST_AUTO_TEST_CASE( ConstructorsTest ) {
     G2.checkConsistency();
     BOOST_CHECK( !(G2 == G0) );
     
-    typedef GraphAL::Edge Edge;
     std::vector<Edge> edges;
     edges.push_back( Edge( 0, 1 ) );
     edges.push_back( Edge( 1, 2 ) );
@@ -68,7 +67,6 @@ BOOST_AUTO_TEST_CASE( ConstructorsTest ) {
 
 BOOST_AUTO_TEST_CASE( NeighborTest ) {
     // check nb() accessor / mutator
-    typedef GraphAL::Edge Edge;
     std::vector<Edge> edges;
     edges.push_back( Edge( 0, 1 ) );
     edges.push_back( Edge( 1, 2 ) );
@@ -96,7 +94,6 @@ BOOST_AUTO_TEST_CASE( NeighborTest ) {
 
 BOOST_AUTO_TEST_CASE( AddEraseTest ) {
     // check addition and erasure of nodes and edges
-    typedef GraphAL::Edge Edge;
     std::vector<Edge> edges;
     edges.push_back( Edge( 0, 1 ) );
     edges.push_back( Edge( 1, 2 ) );
@@ -232,7 +229,7 @@ BOOST_AUTO_TEST_CASE( QueriesAndCreationTest ) {
         BOOST_CHECK( G.isConnected() );
         BOOST_CHECK_EQUAL( G.isTree(), N < 3 );
         for( size_t n1 = 0; n1 < G.nrNodes(); n1++ ) {
-            foreach( const GraphAL::Neighbor &n2, G.nb(n1) ) {
+            foreach( const Neighbor &n2, G.nb(n1) ) {
                 BOOST_CHECK( G.hasEdge( n1, n2 ) );
                 BOOST_CHECK( G.hasEdge( n2, n1 ) );
             }
@@ -256,7 +253,7 @@ BOOST_AUTO_TEST_CASE( QueriesAndCreationTest ) {
             BOOST_CHECK( G.isConnected() );
             BOOST_CHECK_EQUAL( G.isTree(), (N1 <= 1) || (N2 <= 1) );
             for( size_t n1 = 0; n1 < G.nrNodes(); n1++ ) {
-                foreach( const GraphAL::Neighbor &n2, G.nb(n1) ) {
+                foreach( const Neighbor &n2, G.nb(n1) ) {
                     BOOST_CHECK( G.hasEdge( n1, n2 ) );
                     BOOST_CHECK( G.hasEdge( n2, n1 ) );
                 }
@@ -279,7 +276,7 @@ BOOST_AUTO_TEST_CASE( QueriesAndCreationTest ) {
             BOOST_CHECK( G.isConnected() );
             BOOST_CHECK_EQUAL( G.isTree(), (G.nrNodes() <= 2) );
             for( size_t n1 = 0; n1 < G.nrNodes(); n1++ ) {
-                foreach( const GraphAL::Neighbor &n2, G.nb(n1) ) {
+                foreach( const Neighbor &n2, G.nb(n1) ) {
                     BOOST_CHECK( G.hasEdge( n1, n2 ) );
                     BOOST_CHECK( G.hasEdge( n2, n1 ) );
                 }
@@ -304,7 +301,7 @@ BOOST_AUTO_TEST_CASE( QueriesAndCreationTest ) {
                 BOOST_CHECK( G.isConnected() );
                 BOOST_CHECK_EQUAL( G.isTree(), (G.nrNodes() == 0) || (N1 <= 1 && N2 <= 1) || (N1 <= 1 && N3 <= 1) || (N2 <= 1 && N3 <= 1) );
                 for( size_t n1 = 0; n1 < G.nrNodes(); n1++ ) {
-                    foreach( const GraphAL::Neighbor &n2, G.nb(n1) ) {
+                    foreach( const Neighbor &n2, G.nb(n1) ) {
                         BOOST_CHECK( G.hasEdge( n1, n2 ) );
                         BOOST_CHECK( G.hasEdge( n2, n1 ) );
                     }
@@ -327,7 +324,7 @@ BOOST_AUTO_TEST_CASE( QueriesAndCreationTest ) {
                 BOOST_CHECK( G.isConnected() );
                 BOOST_CHECK_EQUAL( G.isTree(), (G.nrNodes() <= 2) );
                 for( size_t n1 = 0; n1 < G.nrNodes(); n1++ ) {
-                    foreach( const GraphAL::Neighbor &n2, G.nb(n1) ) {
+                    foreach( const Neighbor &n2, G.nb(n1) ) {
                         BOOST_CHECK( G.hasEdge( n1, n2 ) );
                         BOOST_CHECK( G.hasEdge( n2, n1 ) );
                     }
@@ -355,7 +352,7 @@ BOOST_AUTO_TEST_CASE( QueriesAndCreationTest ) {
         BOOST_CHECK( G.isConnected() );
         BOOST_CHECK_EQUAL( G.isTree(), N <= 2 );
         for( size_t n1 = 0; n1 < G.nrNodes(); n1++ ) {
-            foreach( const GraphAL::Neighbor &n2, G.nb(n1) ) {
+            foreach( const Neighbor &n2, G.nb(n1) ) {
                 BOOST_CHECK( G.hasEdge( n1, n2 ) );
                 BOOST_CHECK( G.hasEdge( n2, n1 ) );
             }
@@ -378,7 +375,7 @@ BOOST_AUTO_TEST_CASE( QueriesAndCreationTest ) {
         BOOST_CHECK( G.isConnected() );
         BOOST_CHECK( G.isTree() );
         for( size_t n1 = 0; n1 < G.nrNodes(); n1++ ) {
-            foreach( const GraphAL::Neighbor &n2, G.nb(n1) ) {
+            foreach( const Neighbor &n2, G.nb(n1) ) {
                 BOOST_CHECK( G.hasEdge( n1, n2 ) );
                 BOOST_CHECK( G.hasEdge( n2, n1 ) );
             }
@@ -402,7 +399,7 @@ BOOST_AUTO_TEST_CASE( QueriesAndCreationTest ) {
                 BOOST_CHECK_EQUAL( G.nrEdges(), d * N / 2 );
                 for( size_t n1 = 0; n1 < G.nrNodes(); n1++ ) {
                     BOOST_CHECK_EQUAL( G.nb(n1).size(), d );
-                    foreach( const GraphAL::Neighbor &n2, G.nb(n1) ) {
+                    foreach( const Neighbor &n2, G.nb(n1) ) {
                         BOOST_CHECK( G.hasEdge( n1, n2 ) );
                         BOOST_CHECK( G.hasEdge( n2, n1 ) );
                     }
index 0f8b97b..deb3786 100644 (file)
@@ -82,7 +82,7 @@ FactorGraph createFG( const GraphAL &G, FactorType ft, size_t states, const Prop
     factors.reserve( G.nrEdges() + N );
     // Pairwise factors
     for( size_t i = 0; i < N; i++ )
-        foreach( const GraphAL::Neighbor &j, G.nb(i) )
+        foreach( const Neighbor &j, G.nb(i) )
             if( i < j ) {
                 if( ft == FactorType::POTTS )
                     factors.push_back( createFactorPotts( vars[i], vars[j], beta ) );
@@ -174,10 +174,10 @@ BipartiteGraph createRandomBipartiteGraph( size_t N1, size_t N2, size_t d1, size
     random_shuffle( stubs2.begin(), stubs2.end() );
 
     // add edges
-    vector<BipartiteGraph::Edge> edges;
+    vector<Edge> edges;
     edges.reserve( N1*d1 );
     for( size_t e = 0; e < N1*d1; e++ )
-        edges.push_back( BipartiteGraph::Edge(stubs1[e], stubs2[e]) );
+        edges.push_back( Edge(stubs1[e], stubs2[e]) );
 
     // finish construction
     G.construct( N1, N2, edges.begin(), edges.end() );
@@ -224,7 +224,6 @@ BipartiteGraph createSmallLDPCGraph() {
     BipartiteGraph G;
     size_t N=4, j=3, K=4; // k=3;
 
-    typedef BipartiteGraph::Edge Edge;
     vector<Edge> edges;
     edges.reserve( N*j );
     edges.push_back( Edge(0,0) ); edges.push_back( Edge(1,0) ); edges.push_back( Edge(2,0) );
@@ -272,7 +271,6 @@ BipartiteGraph createGroupStructuredLDPCGraph( size_t p, size_t j, size_t k ) {
 
     DAI_ASSERT( N * n == K * k );
 
-    typedef BipartiteGraph::Edge Edge;
     vector<Edge> edges;
     edges.reserve( N * n );