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 /// Remove node of type 1 and all incident edges.
  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 /// Remove node of type 2 and all incident edges.
  59 void BipartiteGraph::erase2( size_t n2 ) {
  60     assert( n2 < nr2() );
  61     // Erase neighbor entry of node n2
  62     _nb2.erase( _nb2.begin() + n2 );
  63     // Adjust neighbor entries of nodes of type 1
  64     for( size_t n1 = 0; n1 < nr1(); n1++ ) {
  65         for( size_t iter = 0; iter < nb1(n1).size(); ) {
  66             Neighbor &m2 = nb1(n1, iter);
  67             if( m2.node == n2 ) {
  68                 // delete this entry, because it points to the deleted node
  69                 nb1(n1).erase( nb1(n1).begin() + iter );
  70             } else if( m2.node > n2 ) {
  71                 // update this entry and the corresponding dual of the neighboring node of type 2
  72                 m2.iter = iter;
  73                 m2.node--;
  74                 nb2( m2.node, m2.dual ).dual = iter;
  75                 iter++;
  76             } else {
  77                 // skip
  78                 iter++;
  79             }
  80         }
  81     }
  82 }
  83
  84
  85 /// Calculate second-order neighbors (i.e., neighbors of neighbors) of node n1 of type 1.
  86 /** If include == true, include n1 itself, otherwise exclude n1.
  87  */
  88 std::vector<size_t> BipartiteGraph::delta1( size_t n1, bool include ) const {
  89     std::vector<size_t> result;
  90     foreach( const Neighbor &n2, nb1(n1) )
  91         foreach( const Neighbor &m1, nb2(n2) )
  92             if( include || (m1 != n1) )
  93                 result.push_back( m1 );
  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 /// Calculate second-order neighbors (i.e., neighbors of neighbors) of node n2 of type 2.
 102 /** If include == true, include n2 itself, otherwise exclude n2.
 103  */
 104 std::vector<size_t> BipartiteGraph::delta2( size_t n2, bool include ) const {
 105     std::vector<size_t> result;
 106     foreach( const Neighbor &n1, nb2(n2) )
 107         foreach( const Neighbor &m2, nb1(n1) )
 108             if( include || (m2 != n2) )
 109                 result.push_back( m2 );
 110     // remove duplicates
 111     std::vector<size_t>::iterator it = std::unique( result.begin(), result.end() );
 112     result.erase( it, result.end() );
 113     return result;
 114 }
 115
 116
 117 /// Returns true if the graph is connected
 118 bool BipartiteGraph::isConnected() const {
 119     if( nr1() == 0 ) {
 120         return true;
 121     } else {
 122         std::vector<bool> incomponent1( nr1(), false );
 123         std::vector<bool> incomponent2( nr2(), false );
 124
 125         incomponent1[0] = true;
 126         bool found_new_nodes;
 127         do {
 128             found_new_nodes = false;
 129
 130             // For all nodes of type 2, check if they are connected with the (growing) component
 131             for( size_t n2 = 0; n2 < nr2(); n2++ )
 132                 if( !incomponent2[n2] ) {
 133                     foreach( const Neighbor &n1, nb2(n2) ) {
 134                         if( incomponent1[n1] ) {
 135                             found_new_nodes = true;
 136                             incomponent2[n2] = true;
 137                             break;
 138                         }
 139                     }
 140                 }
 141
 142             // For all nodes of type 1, check if they are connected with the (growing) component
 143             for( size_t n1 = 0; n1 < nr1(); n1++ )
 144                 if( !incomponent1[n1] ) {
 145                     foreach( const Neighbor &n2, nb1(n1) ) {
 146                         if( incomponent2[n2] ) {
 147                             found_new_nodes = true;
 148                             incomponent1[n1] = true;
 149                             break;
 150                         }
 151                     }
 152                 }
 153         } while( found_new_nodes );
 154
 155         // Check if there are remaining nodes (not in the component)
 156         bool all_connected = true;
 157         for( size_t n1 = 0; (n1 < nr1()) && all_connected; n1++ )
 158             if( !incomponent1[n1] )
 159                 all_connected = false;
 160         for( size_t n2 = 0; (n2 < nr2()) && all_connected; n2++ )
 161             if( !incomponent2[n2] )
 162                 all_connected = false;
 163
 164         return all_connected;
 165     }
 166 }
 167
 168
 169 /// Returns true if the graph is a tree, i.e., if it is singly connected and connected.
 170 /** This is equivalent to whether for each pair of vertices in the graph, there exists
 171  *  a unique path in the graph that starts at the first and ends at the second vertex.
 172  */
 173 bool BipartiteGraph::isTree() const {
 174     using namespace std;
 175     vector<levelType> levels;
 176
 177     bool foundCycle = false;
 178     size_t nr_1 = 0;
 179     size_t nr_2 = 0;
 180
 181     if( nr1() == 0 || nr2() == 0 )
 182         return true;
 183     else {
 184         levelType newLevel;
 185         do {
 186             newLevel.ind1.clear();
 187             newLevel.ind2.clear();
 188             if( levels.size() == 0 ) {
 189                 size_t n1 = 0;
 190                 // add n1 to ind1
 191                 newLevel.ind1 = vector<size_t>( 1, n1 );
 192                 // add all neighbors of n1 to ind2
 193                 newLevel.ind2.reserve( nb1(n1).size() );
 194                 foreach( const Neighbor &n2, nb1(n1) )
 195                     newLevel.ind2.push_back( n2 );
 196             } else {
 197                 const levelType &prevLevel = levels.back();
 198                 // build newLevel.ind1
 199                 foreach( size_t n2, prevLevel.ind2 ) { // for all n2 in the previous level
 200                     foreach( const Neighbor &n1, nb2(n2) ) { // for all neighbors n1 of n2
 201                         if( find( prevLevel.ind1.begin(), prevLevel.ind1.end(), n1 ) == prevLevel.ind1.end() ) { // n1 not in previous level
 202                             if( find( newLevel.ind1.begin(), newLevel.ind1.end(), n1 ) != newLevel.ind1.end() )
 203                                 foundCycle = true; // n1 already in new level: we found a cycle
 204                             else
 205                                 newLevel.ind1.push_back( n1 ); // add n1 to new level
 206                         }
 207                         if( foundCycle )
 208                             break;
 209                     }
 210                     if( foundCycle )
 211                         break;
 212                 }
 213                 // build newLevel.ind2
 214                 foreach( size_t n1, newLevel.ind1 ) { // for all n1 in this level
 215                     foreach( const Neighbor &n2, nb1(n1) ) { // for all neighbors n2 of n1
 216                         if( find( prevLevel.ind2.begin(), prevLevel.ind2.end(), n2 ) == prevLevel.ind2.end() ) { // n2 not in previous level
 217                             if( find( newLevel.ind2.begin(), newLevel.ind2.end(), n2 ) != newLevel.ind2.end() )
 218                                 foundCycle = true; // n2 already in new level: we found a cycle
 219                             else
 220                                 newLevel.ind2.push_back( n2 ); // add n2 to new level
 221                         }
 222                         if( foundCycle )
 223                             break;
 224                     }
 225                     if( foundCycle )
 226                         break;
 227                 }
 228             }
 229             levels.push_back( newLevel );
 230             nr_1 += newLevel.ind1.size();
 231             nr_2 += newLevel.ind2.size();
 232         } while( ((newLevel.ind1.size() != 0) || (newLevel.ind2.size() != 0)) && !foundCycle );
 233         if( nr_1 == nr1() && nr_2 == nr2() && !foundCycle )
 234             return true;
 235         else
 236             return false;
 237     }
 238 }
 239
 240
 241 /// Stream to output stream os in graphviz .dot syntax
 242 void BipartiteGraph::display( std::ostream& os ) const {
 243     using namespace std;
 244     os << "graph G {" << endl;
 245     os << "node[shape=circle,width=0.4,fixedsize=true];" << endl;
 246     for( size_t n1 = 0; n1 < nr1(); n1++ )
 247         os << "\tx" << n1 << ";" << endl;
 248     os << "node[shape=box,width=0.3,height=0.3,fixedsize=true];" << endl;
 249     for( size_t n2 = 0; n2 < nr2(); n2++ )
 250         os << "\ty" << n2 << ";" << endl;
 251     for( size_t n1 = 0; n1 < nr1(); n1++ )
 252         foreach( const Neighbor &n2, nb1(n1) )
 253             os << "\tx" << n1 << " -- y" << n2 << ";" << endl;
 254     os << "}" << endl;
 255 }
 256
 257
 258 /// Checks internal consistency
 259 void BipartiteGraph::check() const {
 260     size_t N1 = nr1();
 261     size_t N2 = nr2();
 262     for( size_t n1 = 0; n1 < N1; n1++ ) {
 263         size_t iter = 0;
 264         foreach( const Neighbor &n2, nb1(n1) ) {
 265             assert( n2.iter == iter );
 266             assert( n2.node < N2 );
 267             assert( n2.dual < nb2(n2).size() );
 268             assert( nb2(n2, n2.dual) == n1 );
 269             iter++;
 270         }
 271     }
 272     for( size_t n2 = 0; n2 < N2; n2++ ) {
 273         size_t iter = 0;
 274         foreach( const Neighbor &n1, nb2(n2) ) {
 275             assert( n1.iter == iter );
 276             assert( n1.node < N1 );
 277             assert( n1.dual < nb1(n1).size() );
 278             assert( nb1(n1, n1.dual) == n2 );
 279             iter++;
 280         }
 281     }
 282 }
 283
 284
 285 } // end of namespace dai