src/bipgraph.cpp

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