src/graph.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-2010  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/graph.h>
  13 #include <dai/weightedgraph.h>
  14 #include <boost/graph/adjacency_list.hpp>
  15 #include <boost/graph/connected_components.hpp>
  16
  17
  18 namespace dai {
  19
  20
  21 using namespace std;
  22
  23
  24 void GraphAL::addEdge( size_t n1, size_t n2, bool check ) {
  25     DAI_ASSERT( n1 < nrNodes() );
  26     DAI_ASSERT( n2 < nrNodes() );
  27     bool exists = false;
  28     if( check ) {
  29         // Check whether the edge already exists
  30         foreach( const Neighbor &n, nb(n1) )
  31             if( n == n2 ) {
  32                 exists = true;
  33                 break;
  34             }
  35     }
  36     if( !exists ) { // Add edge
  37         Neighbor nb_1( nb(n1).size(), n2, nb(n2).size() );
  38         Neighbor nb_2( nb_1.dual, n1, nb_1.iter );
  39         nb(n1).push_back( nb_1 );
  40         nb(n2).push_back( nb_2 );
  41     }
  42 }
  43
  44
  45 void GraphAL::eraseNode( size_t n ) {
  46     DAI_ASSERT( n < nrNodes() );
  47     // Erase neighbor entry of node n
  48     _nb.erase( _nb.begin() + n );
  49     // Adjust neighbor entries of nodes
  50     for( size_t n2 = 0; n2 < nrNodes(); n2++ ) {
  51         for( size_t iter = 0; iter < nb(n2).size(); ) {
  52             Neighbor &m = nb(n2, iter);
  53             if( m.node == n ) {
  54                 // delete this entry, because it points to the deleted node
  55                 nb(n2).erase( nb(n2).begin() + iter );
  56             } else if( m.node > n ) {
  57                 // update this entry and the corresponding dual of the neighboring node
  58                 m.iter = iter;
  59                 m.node--;
  60                 nb( m.node, m.dual ).dual = iter;
  61                 iter++;
  62             } else {
  63                 // skip
  64                 iter++;
  65             }
  66         }
  67     }
  68 }
  69
  70
  71 void GraphAL::eraseEdge( size_t n1, size_t n2 ) {
  72     DAI_ASSERT( n1 < nrNodes() );
  73     DAI_ASSERT( n2 < nrNodes() );
  74     size_t iter;
  75     // Search for edge among neighbors of n1
  76     for( iter = 0; iter < nb(n1).size(); iter++ )
  77         if( nb(n1, iter).node == n2 ) {
  78             // Remove it
  79             nb(n1).erase( nb(n1).begin() + iter );
  80             break;
  81         }
  82     // Change the iter and dual values of the subsequent neighbors
  83     for( ; iter < nb(n1).size(); iter++ ) {
  84         Neighbor &m = nb( n1, iter );
  85         m.iter = iter;
  86         nb( m.node, m.dual ).dual = iter;
  87     }
  88     // Search for edge among neighbors of n2
  89     for( iter = 0; iter < nb(n2).size(); iter++ )
  90         if( nb(n2, iter).node == n1 ) {
  91             // Remove it
  92             nb(n2).erase( nb(n2).begin() + iter );
  93             break;
  94         }
  95     // Change the iter and node values of the subsequent neighbors
  96     for( ; iter < nb(n2).size(); iter++ ) {
  97         Neighbor &m = nb( n2, iter );
  98         m.iter = iter;
  99         nb( m.node, m.dual ).dual = iter;
 100     }
 101 }
 102
 103
 104 bool GraphAL::isConnected() const {
 105     if( nrNodes() == 0 ) {
 106         return true;
 107     } else {
 108         std::vector<bool> incomponent( nrNodes(), false );
 109
 110         incomponent[0] = true;
 111         bool found_new_nodes;
 112         do {
 113             found_new_nodes = false;
 114
 115             // For all nodes, check if they are connected with the (growing) component
 116             for( size_t n1 = 0; n1 < nrNodes(); n1++ )
 117                 if( !incomponent[n1] ) {
 118                     foreach( const Neighbor &n2, nb(n1) ) {
 119                         if( incomponent[n2] ) {
 120                             found_new_nodes = true;
 121                             incomponent[n1] = true;
 122                             break;
 123                         }
 124                     }
 125                 }
 126         } while( found_new_nodes );
 127
 128         // Check if there are remaining nodes (not in the component)
 129         bool all_connected = true;
 130         for( size_t n1 = 0; (n1 < nrNodes()) && all_connected; n1++ )
 131             if( !incomponent[n1] )
 132                 all_connected = false;
 133
 134         return all_connected;
 135
 136         // BGL implementation is slower...
 137     /*  using namespace boost;
 138         typedef adjacency_list< vecS, vecS, undirectedS, property<vertex_distance_t, int> > boostGraphAL;
 139         typedef pair<size_t, size_t> E;
 140
 141         // Copy graph structure into boostGraphAL object
 142         vector<E> edges;
 143         edges.reserve( nrEdges() );
 144         for( size_t n1 = 0; n1 < nrNodes(); n1++ )
 145             foreach( const Neighbor &n2, nb(n1) )
 146                 if( n1 < n2 )
 147                     edges.push_back( E( n1, n2 ) );
 148         boostGraphAL g( edges.begin(), edges.end(), nrNodes() );
 149
 150         // Construct connected components using Boost GraphAL Library
 151         std::vector<int> component( num_vertices( g ) );
 152         int num_comp = connected_components( g, make_iterator_property_map(component.begin(), get(vertex_index, g)) );
 153
 154         return (num_comp == 1);
 155     */
 156     }
 157 }
 158
 159
 160 bool GraphAL::isTree() const {
 161     using namespace std;
 162     vector<levelType> levels;
 163
 164     bool foundCycle = false;
 165     size_t Nr = 0;
 166
 167     if( nrNodes() == 0 )
 168         return true;
 169     else {
 170         levelType newLevel;
 171         do {
 172             newLevel.clear();
 173             if( levels.size() == 0 ) {
 174                 size_t n1 = 0;
 175                 // add n1
 176                 newLevel = vector<size_t>( 1, n1 );
 177             } else {
 178                 const levelType &prevLevel = levels.back();
 179                 // build newLevel
 180                 foreach( size_t n2, prevLevel ) { // for all n2 in the previous level
 181                     foreach( const Neighbor &n1, nb(n2) ) { // for all neighbors n1 of n2
 182                         if( find( prevLevel.begin(), prevLevel.end(), n1 ) == prevLevel.end() ) { // n1 not in previous level
 183                             if( find( newLevel.begin(), newLevel.end(), n1 ) != newLevel.end() )
 184                                 foundCycle = true; // n1 already in new level: we found a cycle
 185                             else
 186                                 newLevel.push_back( n1 ); // add n1 to new level
 187                         }
 188                         if( foundCycle )
 189                             break;
 190                     }
 191                     if( foundCycle )
 192                         break;
 193                 }
 194             }
 195             levels.push_back( newLevel );
 196             Nr += newLevel.size();
 197         } while( (newLevel.size() != 0) && !foundCycle );
 198         if( Nr == nrNodes() && !foundCycle )
 199             return true;
 200         else
 201             return false;
 202     }
 203 }
 204
 205
 206 void GraphAL::printDot( std::ostream& os ) const {
 207     using namespace std;
 208     os << "graph G {" << endl;
 209     os << "node[shape=circle,width=0.4,fixedsize=true];" << endl;
 210     for( size_t n = 0; n < nrNodes(); n++ )
 211         os << "\tx" << n << ";" << endl;
 212     for( size_t n1 = 0; n1 < nrNodes(); n1++ )
 213         foreach( const Neighbor &n2, nb(n1) )
 214             os << "\tx" << n1 << " -- y" << n2 << ";" << endl;
 215     os << "}" << endl;
 216 }
 217
 218
 219 void GraphAL::checkConsistency() const {
 220     size_t N = nrNodes();
 221     for( size_t n1 = 0; n1 < N; n1++ ) {
 222         size_t iter = 0;
 223         foreach( const Neighbor &n2, nb(n1) ) {
 224             DAI_ASSERT( n2.iter == iter );
 225             DAI_ASSERT( n2.node < N );
 226             DAI_ASSERT( n2.dual < nb(n2).size() );
 227             DAI_ASSERT( nb(n2, n2.dual) == n1 );
 228             iter++;
 229         }
 230     }
 231     for( size_t n2 = 0; n2 < N; n2++ ) {
 232         size_t iter = 0;
 233         foreach( const Neighbor &n1, nb(n2) ) {
 234             DAI_ASSERT( n1.iter == iter );
 235             DAI_ASSERT( n1.node < N );
 236             DAI_ASSERT( n1.dual < nb(n1).size() );
 237             DAI_ASSERT( nb(n1, n1.dual) == n2 );
 238             iter++;
 239         }
 240     }
 241 }
 242
 243
 244 GraphAL createGraphFull( size_t N ) {
 245     GraphAL result( N );
 246     for( size_t i = 0; i < N; i++ )
 247         for( size_t j = i+1; j < N; j++ )
 248             result.addEdge( i, j, false );
 249     return result;
 250 }
 251
 252
 253 GraphAL createGraphGrid( size_t n1, size_t n2, bool periodic ) {
 254     GraphAL result( n1*n2 );
 255     for( size_t i1 = 0; i1 < n1; i1++ )
 256         for( size_t i2 = 0; i2 < n2; i2++ ) {
 257             if( i1+1 < n1 || periodic )
 258                 result.addEdge( i1*n2 + i2, ((i1+1)%n1)*n2 + i2, n1 <= 2 );
 259             if( i2+1 < n2 || periodic )
 260                 result.addEdge( i1*n2 + i2, i1*n2 + ((i2+1)%n2), n2 <= 2 );
 261         }
 262     return result;
 263 }
 264
 265
 266 GraphAL createGraphGrid3D( size_t n1, size_t n2, size_t n3, bool periodic ) {
 267     GraphAL result( n1*n2*n3 );
 268     for( size_t i1 = 0; i1 < n1; i1++ )
 269         for( size_t i2 = 0; i2 < n2; i2++ )
 270             for( size_t i3 = 0; i3 < n3; i3++ ) {
 271                 if( i1+1 < n1 || periodic )
 272                     result.addEdge( i1*n2*n3 + i2*n3 + i3, ((i1+1)%n1)*n2*n3 + i2*n3 + i3, n1 <= 2 );
 273                 if( i2+1 < n2 || periodic )
 274                     result.addEdge( i1*n2*n3 + i2*n3 + i3, i1*n2*n3 + ((i2+1)%n2)*n3 + i3, n2 <= 2 );
 275                 if( i3+1 < n2 || periodic )
 276                     result.addEdge( i1*n2*n3 + i2*n3 + i3, i1*n2*n3 + i2*n3 + ((i3+1)%n3), n3 <= 2 );
 277             }
 278     return result;
 279 }
 280
 281
 282 GraphAL createGraphLoop( size_t N ) {
 283     GraphAL result( N );
 284     for( size_t i = 0; i < N; i++ )
 285         result.addEdge( i, (i+1)%N, N <= 2 );
 286     return result;
 287 }
 288
 289
 290 GraphAL createGraphTree( size_t N ) {
 291     GraphAL result( N );
 292     for( size_t i = 1; i < N; i++ ) {
 293         size_t j = rnd_int( 0, i-1 );
 294         result.addEdge( i, j, false );
 295     }
 296     return result;
 297 }
 298
 299
 300 GraphAL createGraphRegular( size_t N, size_t d ) {
 301     GraphEL g = RandomDRegularGraph( N, d );
 302     return GraphAL( N, g.begin(), g.end() );
 303 }
 304
 305
 306 } // end of namespace dai