include/dai/bipgraph.h

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