src/bipgraph.cpp

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