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  *  each node has a vector of Neighbor entries, which is also known as a Neighbors type.
  42  */
  43 class BipartiteGraph {
  44     public:
  45         /// A Neighbor describes a neighboring node of some other node in a BipartiteGraph.
  46         /** Iterating over all neighbors of node n1 of type 1 can be done in the following way:
  47          *  \code
  48          *      foreach( const BipartiteGraph::Neighbor &n2, nb1(n1) ) {
  49          *          size_t _n2 = n2.iter;
  50          *          size_t _n1 = n2.dual;
  51          *          // n2 == n2.node;
  52          *          // The _n2'th neighbor of n1 is n2, and the _n1'th neighbor of n2 is n1:
  53          *          // nb1(n1)[_n2] == n2, nb2(n2)[_n1] == n1
  54          *      }
  55          *  \endcode
  56          */
  57         struct Neighbor {
  58             /// Corresponds to the index of this Neighbor entry in the vector of neighbors
  59             unsigned iter;
  60             /// Contains the number of the neighboring node
  61             unsigned node;
  62             /// Contains the "dual" iter
  63             unsigned dual;
  64             /// Cast to unsigned returns node member
  65             operator unsigned () const { return node; }
  66             /// Default constructor
  67             Neighbor() {}
  68             /// Constructor
  69             Neighbor( size_t iter, size_t node, size_t dual ) : iter(iter), node(node), dual(dual) {}
  70         };
  71
  72         /// Neighbors is a vector of Neighbor entries; each node has an associated Neighbors variable, which describes its neighbors.
  73         typedef std::vector<Neighbor> Neighbors;
  74
  75         /// 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.
  76         typedef std::pair<size_t,size_t> Edge;
  77
  78     private:
  79         /// _nb1 contains for each node of type 1 a vector of its neighbors
  80         std::vector<Neighbors> _nb1;
  81         /// _nb2 contains for each node of type 2 a vector of its neighbors
  82         std::vector<Neighbors> _nb2;
  83
  84         /// Used internally by isTree()
  85         struct levelType {
  86             std::vector<size_t> ind1;       // indices of vertices of type 1
  87             std::vector<size_t> ind2;       // indices of vertices of type 2
  88         };
  89
  90     public:
  91         /// Default constructor
  92         BipartiteGraph() : _nb1(), _nb2() {}
  93
  94         /// Copy constructor
  95         BipartiteGraph( const BipartiteGraph & x ) : _nb1(x._nb1), _nb2(x._nb2) {}
  96
  97         /// Assignment operator
  98         BipartiteGraph & operator=( const BipartiteGraph & x ) {
  99             if( this != &x ) {
 100                 _nb1 = x._nb1;
 101                 _nb2 = x._nb2;
 102             }
 103             return *this;
 104         }
 105
 106         /// Create bipartite graph from a range of edges.
 107         /** nr1 is the number of nodes of type 1, nr2 the number of nodes of type 2.
 108          *  The value_type of an EdgeInputIterator should be Edge.
 109          */
 110         template<typename EdgeInputIterator>
 111         void create( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end );
 112
 113         /// Construct bipartite graph from a range of edges.
 114         /** nr1 is the number of nodes of type 1, nr2 the number of nodes of type 2.
 115          *  The value_type of an EdgeInputIterator should be Edge.
 116          */
 117         template<typename EdgeInputIterator>
 118         BipartiteGraph( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) : _nb1( nr1 ), _nb2( nr2 ) {
 119             create( nr1, nr2, begin, end );
 120         }
 121
 122         /// Returns constant reference to the _i2'th neighbor of node i1 of type 1
 123         const Neighbor & nb1( size_t i1, size_t _i2 ) const {
 124 #ifdef DAI_DEBUG
 125             assert( i1 < _nb1.size() );
 126             assert( _i2 < _nb1[i1].size() );
 127 #endif
 128             return _nb1[i1][_i2];
 129         }
 130         /// Returns reference to the _i2'th neighbor of node i1 of type 1
 131         Neighbor & nb1( size_t i1, size_t _i2 ) {
 132 #ifdef DAI_DEBUG
 133             assert( i1 < _nb1.size() );
 134             assert( _i2 < _nb1[i1].size() );
 135 #endif
 136             return _nb1[i1][_i2];
 137         }
 138
 139         /// Returns constant reference to the _i1'th neighbor of node i2 of type 2
 140         const Neighbor & nb2( size_t i2, size_t _i1 ) const {
 141 #ifdef DAI_DEBUG
 142             assert( i2 < _nb2.size() );
 143             assert( _i1 < _nb2[i2].size() );
 144 #endif
 145             return _nb2[i2][_i1];
 146         }
 147         /// Returns reference to the _i1'th neighbor of node i2 of type 2
 148         Neighbor & nb2( size_t i2, size_t _i1 ) {
 149 #ifdef DAI_DEBUG
 150             assert( i2 < _nb2.size() );
 151             assert( _i1 < _nb2[i2].size() );
 152 #endif
 153             return _nb2[i2][_i1];
 154         }
 155
 156         /// Returns constant reference to all neighbors of node i1 of type 1
 157         const Neighbors & nb1( size_t i1 ) const {
 158 #ifdef DAI_DEBUG
 159             assert( i1 < _nb1.size() );
 160 #endif
 161             return _nb1[i1];
 162         }
 163         /// Returns reference to all neighbors of node of i1 type 1
 164         Neighbors & nb1( size_t i1 ) {
 165 #ifdef DAI_DEBUG
 166             assert( i1 < _nb1.size() );
 167 #endif
 168             return _nb1[i1];
 169         }
 170
 171         /// Returns constant reference to all neighbors of node i2 of type 2
 172         const Neighbors & nb2( size_t i2 ) const {
 173 #ifdef DAI_DEBUG
 174             assert( i2 < _nb2.size() );
 175 #endif
 176             return _nb2[i2];
 177         }
 178         /// Returns reference to all neighbors of node i2 of type 2
 179         Neighbors & nb2( size_t i2 ) {
 180 #ifdef DAI_DEBUG
 181             assert( i2 < _nb2.size() );
 182 #endif
 183             return _nb2[i2];
 184         }
 185
 186         /// Returns number of nodes of type 1
 187         size_t nr1() const { return _nb1.size(); }
 188         /// Returns number of nodes of type 2
 189         size_t nr2() const { return _nb2.size(); }
 190
 191         /// Calculates the number of edges, using O(nr1()) time
 192         size_t nrEdges() const {
 193             size_t sum = 0;
 194             for( size_t i1 = 0; i1 < nr1(); i1++ )
 195                 sum += nb1(i1).size();
 196             return sum;
 197         }
 198
 199         /// Add node of type 1 without neighbors.
 200         void add1() { _nb1.push_back( Neighbors() ); }
 201
 202         /// Add node of type 2 without neighbors.
 203         void add2() { _nb2.push_back( Neighbors() ); }
 204
 205         /// Add node of type 1 with neighbors specified by a range.
 206         /** The value_type of an NodeInputIterator should be a size_t, corresponding to
 207          *  the indices of nodes of type 2 that should become neighbors of the added node.
 208          *  For improved efficiency, the size of the range may be specified by sizeHint.
 209          */
 210         template <typename NodeInputIterator>
 211         void add1( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
 212             Neighbors nbs1new;
 213             nbs1new.reserve( sizeHint );
 214             size_t iter = 0;
 215             for( NodeInputIterator it = begin; it != end; ++it ) {
 216                 assert( *it < nr2() );
 217                 Neighbor nb1new( iter, *it, nb2(*it).size() );
 218                 Neighbor nb2new( nb2(*it).size(), nr1(), iter++ );
 219                 nbs1new.push_back( nb1new );
 220                 nb2( *it ).push_back( nb2new );
 221             }
 222             _nb1.push_back( nbs1new );
 223         }
 224
 225         /// Add node of type 2 with neighbors specified by a range.
 226         /** The value_type of an NodeInputIterator should be a size_t, corresponding to
 227          *  the indices of nodes of type 1 that should become neighbors of the added node.
 228          *  For improved efficiency, the size of the range may be specified by sizeHint.
 229          */
 230         template <typename NodeInputIterator>
 231         void add2( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
 232             Neighbors nbs2new;
 233             nbs2new.reserve( sizeHint );
 234             size_t iter = 0;
 235             for( NodeInputIterator it = begin; it != end; ++it ) {
 236                 assert( *it < nr1() );
 237                 Neighbor nb2new( iter, *it, nb1(*it).size() );
 238                 Neighbor nb1new( nb1(*it).size(), nr2(), iter++ );
 239                 nbs2new.push_back( nb2new );
 240                 nb1( *it ).push_back( nb1new );
 241             }
 242             _nb2.push_back( nbs2new );
 243         }
 244
 245         /// Remove node n1 of type 1 and all incident edges.
 246         void erase1( size_t n1 );
 247
 248         /// Remove node n2 of type 2 and all incident edges.
 249         void erase2( size_t n2 );
 250
 251         /// Add edge between node n1 of type 1 and node n2 of type 2.
 252         /** If check == true, only adds the edge if it does not exist already.
 253          */
 254         void addEdge( size_t n1, size_t n2, bool check = true ) {
 255             assert( n1 < nr1() );
 256             assert( n2 < nr2() );
 257             bool exists = false;
 258             if( check ) {
 259                 // Check whether the edge already exists
 260                 foreach( const Neighbor &nb2, nb1(n1) )
 261                     if( nb2 == n2 ) {
 262                         exists = true;
 263                         break;
 264                     }
 265             }
 266             if( !exists ) { // Add edge
 267                 Neighbor nb_1( _nb1[n1].size(), n2, _nb2[n2].size() );
 268                 Neighbor nb_2( nb_1.dual, n1, nb_1.iter );
 269                 _nb1[n1].push_back( nb_1 );
 270                 _nb2[n2].push_back( nb_2 );
 271             }
 272         }
 273
 274         /// Calculate second-order neighbors (i.e., neighbors of neighbors) of node n1 of type 1.
 275         /** If include == true, include n1 itself, otherwise exclude n1.
 276          */
 277         std::vector<size_t> delta1( size_t n1, bool include = false ) const;
 278
 279         /// Calculate second-order neighbors (i.e., neighbors of neighbors) of node n2 of type 2.
 280         /** If include == true, include n2 itself, otherwise exclude n2.
 281          */
 282         std::vector<size_t> delta2( size_t n2, bool include = false ) const;
 283
 284         /// Returns true if the graph is connected
 285         bool isConnected() const;
 286
 287         /// Returns true if the graph is a tree, i.e., if it is singly connected and connected.
 288         /** This is equivalent to whether for each pair of vertices in the graph, there exists
 289          *  a unique path in the graph that starts at the first and ends at the second vertex.
 290          */
 291         bool isTree() const;
 292
 293         /// Stream to output stream os in graphviz .dot syntax
 294         void display( std::ostream& os ) const;
 295
 296         /// Checks internal consistency
 297         void check() const;
 298 };
 299
 300
 301 template<typename EdgeInputIterator>
 302 void BipartiteGraph::create( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) {
 303     _nb1.clear();
 304     _nb1.resize( nr1 );
 305     _nb2.clear();
 306     _nb2.resize( nr2 );
 307
 308     for( EdgeInputIterator e = begin; e != end; e++ ) {
 309 #ifdef DAI_DEBUG
 310         addEdge( e->first, e->second, true );
 311 #else
 312         addEdge( e->first, e->second, false );
 313 #endif
 314     }
 315 }
 316
 317
 318 } // end of namespace dai
 319
 320
 321 #endif