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 <vector>
  27 #include <algorithm>
  28 #include <boost/numeric/ublas/vector_sparse.hpp>
  29
  30
  31 namespace dai {
  32
  33
  34 /// A BipartiteGraph represents a graph with two types of nodes
  35 template <class T1, class T2> class BipartiteGraph {
  36     public:
  37         typedef std::pair<size_t,size_t>    _edge_t;
  38         typedef std::vector<size_t>         _nb_t;
  39         typedef _nb_t::const_iterator       _nb_cit;
  40
  41
  42     private:
  43         /// Vertices of first type
  44         std::vector<T1>                     _V1;
  45
  46         /// Vertices of second type
  47         std::vector<T2>                     _V2;
  48
  49         /// Edges, which are pairs (v1,v2) with v1 in _V1 and v2 in _V2
  50         std::vector<_edge_t>                _E12;
  51
  52         /// Conversion matrix that computes which index of _E12 corresponds to a vertex index pair (v1,v2)
  53         std::vector<boost::numeric::ublas::mapped_vector<size_t> > _E12ind;
  54
  55         /// Neighbour indices of vertices of first type
  56         std::vector<_nb_t>                  _nb1;
  57
  58         /// Neighbour indices of vertices of second type
  59         std::vector<_nb_t>                  _nb2;
  60
  61
  62     public:
  63         /// Default constructor
  64         BipartiteGraph<T1,T2> () {};
  65
  66         /// Copy constructor
  67         BipartiteGraph<T1,T2> ( const BipartiteGraph<T1,T2> & x ) : _V1(x._V1), _V2(x._V2), _E12(x._E12), _E12ind(x._E12ind), _nb1(x._nb1), _nb2(x._nb2) {};
  68
  69         /// Assignment operator
  70         BipartiteGraph<T1,T2> & operator=(const BipartiteGraph<T1,T2> & x) {
  71             if( this != &x ) {
  72                 _V1 =       x._V1;
  73                 _V2 =       x._V2;
  74                 _E12 =      x._E12;
  75                 _E12ind =   x._E12ind;
  76                 _nb1 =      x._nb1;
  77                 _nb2 =      x._nb2;
  78             }
  79             return *this;
  80         }
  81
  82         /// Provides read access to node of first type
  83         const T1 & V1( size_t i1 ) const { return _V1[i1]; }
  84         /// Provides full access to node of first type
  85         T1 & V1( size_t i1 ) { return _V1[i1]; }
  86         /// Provides read access to all nodes of first type
  87         const std::vector<T1> & V1s() const { return _V1; }
  88         /// Provides full access to all nodes of first type
  89         std::vector<T1> & V1s() { return _V1; }
  90
  91         /// Provides read access to node of second type
  92         const T2 & V2( size_t i2 ) const { return _V2[i2]; }
  93         /// Provides full access to node of second type
  94         T2 & V2( size_t i2 ) { return _V2[i2]; }
  95         /// Provides read access to all nodes of second type
  96         const std::vector<T2> & V2s() const { return _V2; }
  97         /// Provides full access to all nodes of second type
  98         std::vector<T2> & V2s() { return _V2; }
  99
 100         /// Provides read access to edge
 101         const _edge_t & edge(size_t ind) const { return _E12[ind]; }
 102         /// Provides full access to edge
 103         _edge_t & edge(size_t ind) { return _E12[ind]; }
 104         /// Provides read access to all edges
 105         const std::vector<_edge_t> & edges() const { return _E12; }
 106         /// Provides full access to all edges
 107         std::vector<_edge_t> & edges() { return _E12; }
 108         /// Returns number of edges
 109         size_t nr_edges() const { return _E12.size(); }
 110
 111         /// Provides read access to neighbours of node of first type
 112         const _nb_t & nb1( size_t i1 ) const { return _nb1[i1]; }
 113         /// Provides full access to neighbours of node of first type
 114         _nb_t & nb1( size_t i1 ) { return _nb1[i1]; }
 115
 116         /// Provides read access to neighbours of node of second type
 117         const _nb_t & nb2( size_t i2 ) const { return _nb2[i2]; }
 118         /// Provides full access to neighbours of node of second type
 119         _nb_t & nb2( size_t i2 ) { return _nb2[i2]; }
 120
 121         /// Converts the pair of indices (i1,i2) to the corresponding edge index
 122         size_t VV2E( const size_t i1, const size_t i2 ) const { return _E12ind[i1](i2); }
 123
 124
 125         /// Regenerates internal structures (_E12ind, _nb1 and _nb2) based upon _V1, _V2 and _E12
 126         void Regenerate() {
 127             // Calculate _nb1 and _nb2
 128
 129             // Start with empty vectors
 130             _nb1.clear();
 131             _nb1.resize(_V1.size());
 132             // Start with empty vectors
 133             _nb2.clear();
 134             _nb2.resize(_V2.size());
 135             // Each edge yields a neighbour pair
 136             for( std::vector<_edge_t>::const_iterator e = _E12.begin(); e != _E12.end(); e++ ) {
 137                 _nb1[e->first].push_back(e->second);
 138                 _nb2[e->second].push_back(e->first);
 139             }
 140             // Remove duplicates from _nb1
 141             for( size_t i1 = 0; i1 < _V1.size(); i1++ ) {
 142                 _nb_t::iterator new_end = unique(_nb1[i1].begin(), _nb1[i1].end());
 143                 _nb1[i1].erase( new_end, _nb1[i1].end() );
 144             }
 145             // Remove duplicates from _nb2
 146             for( size_t i2 = 0; i2 < _V2.size(); i2++ ) {
 147                 _nb_t::iterator new_end = unique(_nb2[i2].begin(), _nb2[i2].end());
 148                 _nb2[i2].erase( new_end, _nb2[i2].end() );
 149             }
 150
 151             // Calculate _E12ind
 152             _E12ind = std::vector<boost::numeric::ublas::mapped_vector<size_t> >(_V1.size(), boost::numeric::ublas::mapped_vector<size_t>(_V2.size()) );
 153             for( size_t k = 0; k < _E12.size(); k++ )
 154                 _E12ind[_E12[k].first](_E12[k].second) = k;
 155
 156         }
 157 };
 158
 159
 160 } // end of namespace dai
 161
 162
 163 #endif