src/bipgraph.cpp

   1 /*  This file is part of libDAI - http://www.libdai.org/
   2  *
   3  *  libDAI is licensed under the terms of the GNU General Public License version
   4  *  2, or (at your option) any later version. libDAI is distributed without any
   5  *  warranty. See the file COPYING for more details.
   6  *
   7  *  Copyright (C) 2006-2009  Joris Mooij  [joris dot mooij at libdai dot org]
   8  *  Copyright (C) 2006-2007  Radboud University Nijmegen, The Netherlands
   9  */
  10
  11
  12 #include <dai/bipgraph.h>
  13
  14
  15 namespace dai {
  16
  17
  18 using namespace std;
  19
  20
  21 void BipartiteGraph::erase1( size_t n1 ) {
  22     assert( n1 < nr1() );
  23     // Erase neighbor entry of node n1
  24     _nb1.erase( _nb1.begin() + n1 );
  25     // Adjust neighbor entries of nodes of type 2
  26     for( size_t n2 = 0; n2 < nr2(); n2++ ) {
  27         for( size_t iter = 0; iter < nb2(n2).size(); ) {
  28             Neighbor &m1 = nb2(n2, iter);
  29             if( m1.node == n1 ) {
  30                 // delete this entry, because it points to the deleted node
  31                 nb2(n2).erase( nb2(n2).begin() + iter );
  32             } else if( m1.node > n1 ) {
  33                 // update this entry and the corresponding dual of the neighboring node of type 1
  34                 m1.iter = iter;
  35                 m1.node--;
  36                 nb1( m1.node, m1.dual ).dual = iter;
  37                 iter++;
  38             } else {
  39                 // skip
  40                 iter++;
  41             }
  42         }
  43     }
  44 }
  45
  46
  47 void BipartiteGraph::erase2( size_t n2 ) {
  48     assert( n2 < nr2() );
  49     // Erase neighbor entry of node n2
  50     _nb2.erase( _nb2.begin() + n2 );
  51     // Adjust neighbor entries of nodes of type 1
  52     for( size_t n1 = 0; n1 < nr1(); n1++ ) {
  53         for( size_t iter = 0; iter < nb1(n1).size(); ) {
  54             Neighbor &m2 = nb1(n1, iter);
  55             if( m2.node == n2 ) {
  56                 // delete this entry, because it points to the deleted node
  57                 nb1(n1).erase( nb1(n1).begin() + iter );
  58             } else if( m2.node > n2 ) {
  59                 // update this entry and the corresponding dual of the neighboring node of type 2
  60                 m2.iter = iter;
  61                 m2.node--;
  62                 nb2( m2.node, m2.dual ).dual = iter;
  63                 iter++;
  64             } else {
  65                 // skip
  66                 iter++;
  67             }
  68         }
  69     }
  70 }
  71
  72
  73 std::vector<size_t> BipartiteGraph::delta1( size_t n1, bool include ) const {
  74     // get all second-order neighbors
  75     std::vector<size_t> result;
  76     foreach( const Neighbor &n2, nb1(n1) )
  77         foreach( const Neighbor &m1, nb2(n2) )
  78             if( include || (m1 != n1) )
  79                 result.push_back( m1 );
  80     // remove duplicates
  81     std::vector<size_t>::iterator it = std::unique( result.begin(), result.end() );
  82     result.erase( it, result.end() );
  83     return result;
  84 }
  85
  86
  87 std::vector<size_t> BipartiteGraph::delta2( size_t n2, bool include ) const {
  88     // store all second-order neighbors
  89     std::vector<size_t> result;
  90     foreach( const Neighbor &n1, nb2(n2) )
  91         foreach( const Neighbor &m2, nb1(n1) )
  92             if( include || (m2 != n2) )
  93                 result.push_back( m2 );
  94     // remove duplicates
  95     std::vector<size_t>::iterator it = std::unique( result.begin(), result.end() );
  96     result.erase( it, result.end() );
  97     return result;
  98 }
  99
 100
 101 bool BipartiteGraph::isConnected() const {
 102     // TODO: use BGL, like:
 103     // std::vector<int> component( num_vertices( g ) );
 104     // int num_comp = connected_components( g, make_iterator_property_map(component.begin(), get(vertex_index, g)) );
 105     if( nr1() == 0 ) {
 106         return true;
 107     } else {
 108         std::vector<bool> incomponent1( nr1(), false );
 109         std::vector<bool> incomponent2( nr2(), false );
 110
 111         incomponent1[0] = true;
 112         bool found_new_nodes;
 113         do {
 114             found_new_nodes = false;
 115
 116             // For all nodes of type 2, check if they are connected with the (growing) component
 117             for( size_t n2 = 0; n2 < nr2(); n2++ )
 118                 if( !incomponent2[n2] ) {
 119                     foreach( const Neighbor &n1, nb2(n2) ) {
 120                         if( incomponent1[n1] ) {
 121                             found_new_nodes = true;
 122                             incomponent2[n2] = true;
 123                             break;
 124                         }
 125                     }
 126                 }
 127
 128             // For all nodes of type 1, check if they are connected with the (growing) component
 129             for( size_t n1 = 0; n1 < nr1(); n1++ )
 130                 if( !incomponent1[n1] ) {
 131                     foreach( const Neighbor &n2, nb1(n1) ) {
 132                         if( incomponent2[n2] ) {
 133                             found_new_nodes = true;
 134                             incomponent1[n1] = true;
 135                             break;
 136                         }
 137                     }
 138                 }
 139         } while( found_new_nodes );
 140
 141         // Check if there are remaining nodes (not in the component)
 142         bool all_connected = true;
 143         for( size_t n1 = 0; (n1 < nr1()) && all_connected; n1++ )
 144             if( !incomponent1[n1] )
 145                 all_connected = false;
 146         for( size_t n2 = 0; (n2 < nr2()) && all_connected; n2++ )
 147             if( !incomponent2[n2] )
 148                 all_connected = false;
 149
 150         return all_connected;
 151     }
 152 }
 153
 154
 155 bool BipartiteGraph::isTree() const {
 156     using namespace std;
 157     vector<levelType> levels;
 158
 159     bool foundCycle = false;
 160     size_t nr_1 = 0;
 161     size_t nr_2 = 0;
 162
 163     if( nr1() == 0 || nr2() == 0 )
 164         return true;
 165     else {
 166         levelType newLevel;
 167         do {
 168             newLevel.ind1.clear();
 169             newLevel.ind2.clear();
 170             if( levels.size() == 0 ) {
 171                 size_t n1 = 0;
 172                 // add n1 to ind1
 173                 newLevel.ind1 = vector<size_t>( 1, n1 );
 174                 // add all neighbors of n1 to ind2
 175                 newLevel.ind2.reserve( nb1(n1).size() );
 176                 foreach( const Neighbor &n2, nb1(n1) )
 177                     newLevel.ind2.push_back( n2 );
 178             } else {
 179                 const levelType &prevLevel = levels.back();
 180                 // build newLevel.ind1
 181                 foreach( size_t n2, prevLevel.ind2 ) { // for all n2 in the previous level
 182                     foreach( const Neighbor &n1, nb2(n2) ) { // for all neighbors n1 of n2
 183                         if( find( prevLevel.ind1.begin(), prevLevel.ind1.end(), n1 ) == prevLevel.ind1.end() ) { // n1 not in previous level
 184                             if( find( newLevel.ind1.begin(), newLevel.ind1.end(), n1 ) != newLevel.ind1.end() )
 185                                 foundCycle = true; // n1 already in new level: we found a cycle
 186                             else
 187                                 newLevel.ind1.push_back( n1 ); // add n1 to new level
 188                         }
 189                         if( foundCycle )
 190                             break;
 191                     }
 192                     if( foundCycle )
 193                         break;
 194                 }
 195                 // build newLevel.ind2
 196                 foreach( size_t n1, newLevel.ind1 ) { // for all n1 in this level
 197                     foreach( const Neighbor &n2, nb1(n1) ) { // for all neighbors n2 of n1
 198                         if( find( prevLevel.ind2.begin(), prevLevel.ind2.end(), n2 ) == prevLevel.ind2.end() ) { // n2 not in previous level
 199                             if( find( newLevel.ind2.begin(), newLevel.ind2.end(), n2 ) != newLevel.ind2.end() )
 200                                 foundCycle = true; // n2 already in new level: we found a cycle
 201                             else
 202                                 newLevel.ind2.push_back( n2 ); // add n2 to new level
 203                         }
 204                         if( foundCycle )
 205                             break;
 206                     }
 207                     if( foundCycle )
 208                         break;
 209                 }
 210             }
 211             levels.push_back( newLevel );
 212             nr_1 += newLevel.ind1.size();
 213             nr_2 += newLevel.ind2.size();
 214         } while( ((newLevel.ind1.size() != 0) || (newLevel.ind2.size() != 0)) && !foundCycle );
 215         if( nr_1 == nr1() && nr_2 == nr2() && !foundCycle )
 216             return true;
 217         else
 218             return false;
 219     }
 220 }
 221
 222
 223 void BipartiteGraph::printDot( std::ostream& os ) const {
 224     using namespace std;
 225     os << "graph G {" << endl;
 226     os << "node[shape=circle,width=0.4,fixedsize=true];" << endl;
 227     for( size_t n1 = 0; n1 < nr1(); n1++ )
 228         os << "\tx" << n1 << ";" << endl;
 229     os << "node[shape=box,width=0.3,height=0.3,fixedsize=true];" << endl;
 230     for( size_t n2 = 0; n2 < nr2(); n2++ )
 231         os << "\ty" << n2 << ";" << endl;
 232     for( size_t n1 = 0; n1 < nr1(); n1++ )
 233         foreach( const Neighbor &n2, nb1(n1) )
 234             os << "\tx" << n1 << " -- y" << n2 << ";" << endl;
 235     os << "}" << endl;
 236 }
 237
 238
 239 void BipartiteGraph::check() const {
 240     size_t N1 = nr1();
 241     size_t N2 = nr2();
 242     for( size_t n1 = 0; n1 < N1; n1++ ) {
 243         size_t iter = 0;
 244         foreach( const Neighbor &n2, nb1(n1) ) {
 245             assert( n2.iter == iter );
 246             assert( n2.node < N2 );
 247             assert( n2.dual < nb2(n2).size() );
 248             assert( nb2(n2, n2.dual) == n1 );
 249             iter++;
 250         }
 251     }
 252     for( size_t n2 = 0; n2 < N2; n2++ ) {
 253         size_t iter = 0;
 254         foreach( const Neighbor &n1, nb2(n2) ) {
 255             assert( n1.iter == iter );
 256             assert( n1.node < N1 );
 257             assert( n1.dual < nb1(n1).size() );
 258             assert( nb1(n1, n1.dual) == n2 );
 259             iter++;
 260         }
 261     }
 262 }
 263
 264
 265 } // end of namespace dai