include/dai/bipgraph.h

   1 /*  Copyright (C) 2006-2008  Joris Mooij  [joris dot mooij at tuebingen dot mpg dot de]
   2     Radboud University Nijmegen, The Netherlands /
   3     Max Planck Institute for Biological Cybernetics, Germany
   4
   5     This file is part of libDAI.
   6
   7     libDAI is free software; you can redistribute it and/or modify
   8     it under the terms of the GNU General Public License as published by
   9     the Free Software Foundation; either version 2 of the License, or
  10     (at your option) any later version.
  11
  12     libDAI is distributed in the hope that it will be useful,
  13     but WITHOUT ANY WARRANTY; without even the implied warranty of
  14     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15     GNU General Public License for more details.
  16
  17     You should have received a copy of the GNU General Public License
  18     along with libDAI; if not, write to the Free Software
  19     Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  20 */
  21
  22
  23 #ifndef __defined_libdai_bipgraph_h
  24 #define __defined_libdai_bipgraph_h
  25
  26
  27 #include <ostream>
  28 #include <vector>
  29 #include <cassert>
  30 #include <algorithm>
  31 #include <dai/util.h>
  32
  33
  34 namespace dai {
  35
  36
  37 /// A BipartiteGraph represents the neighborhood structure of nodes in a bipartite graph.
  38 /** A bipartite graph has two types of nodes: type 1 and type 2. Edges can occur only between
  39  *  nodes of different type. Nodes are indexed by an unsigned integer, edges are indexed as
  40  *  a pair of unsigned integers, where the pair (a,b) means the b'th neighbor of the a'th node.
  41  *  The BipartiteGraph stores neighborhood structures as vectors of vectors of Neighbor entries:
  42  *  each node has a vector of Neighbor entries, which is also known as a Neighbors type.
  43  */
  44 class BipartiteGraph {
  45     public:
  46         /// A Neighbor describes a neighboring node of some other node in a BipartiteGraph.
  47         /** Iterating over all neighbors of node n1 of type 1 can be done in the following way:
  48          *  \code
  49          *      foreach( const BipartiteGraph::Neighbor &n2, nb1(n1) ) {
  50          *          size_t _n2 = n2.iter;
  51          *          size_t _n1 = n2.dual;
  52          *          // n2 == n2.node;
  53          *          // The _n2'th neighbor of n1 is n2, and the _n1'th neighbor of n2 is n1:
  54          *          // nb1(n1)[_n2] == n2, nb2(n2)[_n1] == n1
  55          *      }
  56          *  \endcode
  57          */
  58         struct Neighbor {
  59             /// Corresponds to the index of this Neighbor entry in the vector of neighbors
  60             unsigned iter;
  61             /// Contains the number of the neighboring node
  62             unsigned node;
  63             /// Contains the "dual" iter
  64             unsigned dual;
  65             /// Cast to unsigned returns node member
  66             operator unsigned () const { return node; }
  67             /// Default constructor
  68             Neighbor() {}
  69             /// Constructor
  70             Neighbor( size_t iter, size_t node, size_t dual ) : iter(iter), node(node), dual(dual) {}
  71         };
  72
  73         /// Neighbors is a vector of Neighbor entries; each node has an associated Neighbors variable, which describes its neighbors.
  74         typedef std::vector<Neighbor> Neighbors;
  75
  76         /// Edge is used as index of an edge: an Edge(a,b) corresponds to the edge between the a'th node and its b'th neighbor. It depends on the context whether the first node (with index a) is of type 1 or of type 2.
  77         typedef std::pair<size_t,size_t> Edge;
  78
  79     private:
  80         /// _nb1 contains for each node of type 1 a vector of its neighbors
  81         std::vector<Neighbors> _nb1;
  82         /// _nb2 contains for each node of type 2 a vector of its neighbors
  83         std::vector<Neighbors> _nb2;
  84
  85         /// Used internally by isTree()
  86         struct levelType {
  87             std::vector<size_t> ind1;       // indices of vertices of type 1
  88             std::vector<size_t> ind2;       // indices of vertices of type 2
  89         };
  90
  91     public:
  92         /// Default constructor
  93         BipartiteGraph() : _nb1(), _nb2() {}
  94
  95         /// Copy constructor
  96         BipartiteGraph( const BipartiteGraph & x ) : _nb1(x._nb1), _nb2(x._nb2) {}
  97
  98         /// Assignment operator
  99         BipartiteGraph & operator=( const BipartiteGraph & x ) {
 100             if( this != &x ) {
 101                 _nb1 = x._nb1;
 102                 _nb2 = x._nb2;
 103             }
 104             return *this;
 105         }
 106
 107         /// Create bipartite graph from a range of edges.
 108         /** nr1 is the number of nodes of type 1, nr2 the number of nodes of type 2.
 109          *  The value_type of an EdgeInputIterator should be Edge.
 110          */
 111         template<typename EdgeInputIterator>
 112         void construct( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end );
 113
 114         /// Construct bipartite graph from a range of edges.
 115         /** nr1 is the number of nodes of type 1, nr2 the number of nodes of type 2.
 116          *  The value_type of an EdgeInputIterator should be Edge.
 117          */
 118         template<typename EdgeInputIterator>
 119         BipartiteGraph( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) : _nb1( nr1 ), _nb2( nr2 ) {
 120             construct( nr1, nr2, begin, end );
 121         }
 122
 123         /// Returns constant reference to the _i2'th neighbor of node i1 of type 1
 124         const Neighbor & nb1( size_t i1, size_t _i2 ) const {
 125 #ifdef DAI_DEBUG
 126             assert( i1 < _nb1.size() );
 127             assert( _i2 < _nb1[i1].size() );
 128 #endif
 129             return _nb1[i1][_i2];
 130         }
 131         /// Returns reference to the _i2'th neighbor of node i1 of type 1
 132         Neighbor & nb1( size_t i1, size_t _i2 ) {
 133 #ifdef DAI_DEBUG
 134             assert( i1 < _nb1.size() );
 135             assert( _i2 < _nb1[i1].size() );
 136 #endif
 137             return _nb1[i1][_i2];
 138         }
 139
 140         /// Returns constant reference to the _i1'th neighbor of node i2 of type 2
 141         const Neighbor & nb2( size_t i2, size_t _i1 ) const {
 142 #ifdef DAI_DEBUG
 143             assert( i2 < _nb2.size() );
 144             assert( _i1 < _nb2[i2].size() );
 145 #endif
 146             return _nb2[i2][_i1];
 147         }
 148         /// Returns reference to the _i1'th neighbor of node i2 of type 2
 149         Neighbor & nb2( size_t i2, size_t _i1 ) {
 150 #ifdef DAI_DEBUG
 151             assert( i2 < _nb2.size() );
 152             assert( _i1 < _nb2[i2].size() );
 153 #endif
 154             return _nb2[i2][_i1];
 155         }
 156
 157         /// Returns constant reference to all neighbors of node i1 of type 1
 158         const Neighbors & nb1( size_t i1 ) const {
 159 #ifdef DAI_DEBUG
 160             assert( i1 < _nb1.size() );
 161 #endif
 162             return _nb1[i1];
 163         }
 164         /// Returns reference to all neighbors of node of i1 type 1
 165         Neighbors & nb1( size_t i1 ) {
 166 #ifdef DAI_DEBUG
 167             assert( i1 < _nb1.size() );
 168 #endif
 169             return _nb1[i1];
 170         }
 171
 172         /// Returns constant reference to all neighbors of node i2 of type 2
 173         const Neighbors & nb2( size_t i2 ) const {
 174 #ifdef DAI_DEBUG
 175             assert( i2 < _nb2.size() );
 176 #endif
 177             return _nb2[i2];
 178         }
 179         /// Returns reference to all neighbors of node i2 of type 2
 180         Neighbors & nb2( size_t i2 ) {
 181 #ifdef DAI_DEBUG
 182             assert( i2 < _nb2.size() );
 183 #endif
 184             return _nb2[i2];
 185         }
 186
 187         /// Returns number of nodes of type 1
 188         size_t nr1() const { return _nb1.size(); }
 189         /// Returns number of nodes of type 2
 190         size_t nr2() const { return _nb2.size(); }
 191
 192         /// Calculates the number of edges, using O(nr1()) time
 193         size_t nrEdges() const {
 194             size_t sum = 0;
 195             for( size_t i1 = 0; i1 < nr1(); i1++ )
 196                 sum += nb1(i1).size();
 197             return sum;
 198         }
 199
 200         /// Add node of type 1 without neighbors.
 201         void add1() { _nb1.push_back( Neighbors() ); }
 202
 203         /// Add node of type 2 without neighbors.
 204         void add2() { _nb2.push_back( Neighbors() ); }
 205
 206         /// Add node of type 1 with neighbors specified by a range.
 207         /** The value_type of an NodeInputIterator should be a size_t, corresponding to
 208          *  the indices of nodes of type 2 that should become neighbors of the added node.
 209          *  For improved efficiency, the size of the range may be specified by sizeHint.
 210          */
 211         template <typename NodeInputIterator>
 212         void add1( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
 213             Neighbors nbs1new;
 214             nbs1new.reserve( sizeHint );
 215             size_t iter = 0;
 216             for( NodeInputIterator it = begin; it != end; ++it ) {
 217                 assert( *it < nr2() );
 218                 Neighbor nb1new( iter, *it, nb2(*it).size() );
 219                 Neighbor nb2new( nb2(*it).size(), nr1(), iter++ );
 220                 nbs1new.push_back( nb1new );
 221                 nb2( *it ).push_back( nb2new );
 222             }
 223             _nb1.push_back( nbs1new );
 224         }
 225
 226         /// Add node of type 2 with neighbors specified by a range.
 227         /** The value_type of an NodeInputIterator should be a size_t, corresponding to
 228          *  the indices of nodes of type 1 that should become neighbors of the added node.
 229          *  For improved efficiency, the size of the range may be specified by sizeHint.
 230          */
 231         template <typename NodeInputIterator>
 232         void add2( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
 233             Neighbors nbs2new;
 234             nbs2new.reserve( sizeHint );
 235             size_t iter = 0;
 236             for( NodeInputIterator it = begin; it != end; ++it ) {
 237                 assert( *it < nr1() );
 238                 Neighbor nb2new( iter, *it, nb1(*it).size() );
 239                 Neighbor nb1new( nb1(*it).size(), nr2(), iter++ );
 240                 nbs2new.push_back( nb2new );
 241                 nb1( *it ).push_back( nb1new );
 242             }
 243             _nb2.push_back( nbs2new );
 244         }
 245
 246         /// Remove node n1 of type 1 and all incident edges.
 247         void erase1( size_t n1 );
 248
 249         /// Remove node n2 of type 2 and all incident edges.
 250         void erase2( size_t n2 );
 251
 252         /// Add edge between node n1 of type 1 and node n2 of type 2.
 253         /** If check == true, only adds the edge if it does not exist already.
 254          */
 255         void addEdge( size_t n1, size_t n2, bool check = true ) {
 256             assert( n1 < nr1() );
 257             assert( n2 < nr2() );
 258             bool exists = false;
 259             if( check ) {
 260                 // Check whether the edge already exists
 261                 foreach( const Neighbor &nb2, nb1(n1) )
 262                     if( nb2 == n2 ) {
 263                         exists = true;
 264                         break;
 265                     }
 266             }
 267             if( !exists ) { // Add edge
 268                 Neighbor nb_1( _nb1[n1].size(), n2, _nb2[n2].size() );
 269                 Neighbor nb_2( nb_1.dual, n1, nb_1.iter );
 270                 _nb1[n1].push_back( nb_1 );
 271                 _nb2[n2].push_back( nb_2 );
 272             }
 273         }
 274
 275         /// Calculate second-order neighbors (i.e., neighbors of neighbors) of node n1 of type 1.
 276         /** If include == true, include n1 itself, otherwise exclude n1.
 277          */
 278         std::vector<size_t> delta1( size_t n1, bool include = false ) const;
 279
 280         /// Calculate second-order neighbors (i.e., neighbors of neighbors) of node n2 of type 2.
 281         /** If include == true, include n2 itself, otherwise exclude n2.
 282          */
 283         std::vector<size_t> delta2( size_t n2, bool include = false ) const;
 284
 285         /// Returns true if the graph is connected
 286         bool isConnected() const;
 287
 288         /// Returns true if the graph is a tree, i.e., if it is singly connected and connected.
 289         /** This is equivalent to whether for each pair of vertices in the graph, there exists
 290          *  a unique path in the graph that starts at the first and ends at the second vertex.
 291          */
 292         bool isTree() const;
 293
 294         /// Stream to output stream os in graphviz .dot syntax
 295         void printDot( std::ostream& os ) const;
 296
 297         /// Checks internal consistency
 298         void check() const;
 299 };
 300
 301
 302 template<typename EdgeInputIterator>
 303 void BipartiteGraph::construct( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) {
 304     _nb1.clear();
 305     _nb1.resize( nr1 );
 306     _nb2.clear();
 307     _nb2.resize( nr2 );
 308
 309     for( EdgeInputIterator e = begin; e != end; e++ ) {
 310 #ifdef DAI_DEBUG
 311         addEdge( e->first, e->second, true );
 312 #else
 313         addEdge( e->first, e->second, false );
 314 #endif
 315     }
 316 }
 317
 318
 319 } // end of namespace dai
 320
 321
 322 #endif