include/dai/bipgraph.h

   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 /// \file
  24 /// \brief Defines BipartiteGraph class
  25
  26
  27 #ifndef __defined_libdai_bipgraph_h
  28 #define __defined_libdai_bipgraph_h
  29
  30
  31 #include <ostream>
  32 #include <vector>
  33 #include <cassert>
  34 #include <algorithm>
  35 #include <dai/util.h>
  36
  37
  38 namespace dai {
  39
  40
  41 /// Represents the neighborhood structure of nodes in a bipartite graph.
  42 /** A bipartite graph has two types of nodes: type 1 and type 2. Edges can occur only between
  43  *  nodes of different type. Nodes are indexed by an unsigned integer. If there are nr1()
  44  *  nodes of type 1 and nr2() nodes of type 2, the nodes of type 1 are numbered
  45  *  0,1,2,...,nr1()-1 and the nodes of type 2 are numbered 0,1,2,...,nr2()-1. An edge
  46  *  between node \a n1 of type 1 and node \a n2 of type 2 is represented by a BipartiteGraph::Edge(\a n1,\a n2).
  47  *
  48  *  A BipartiteGraph is implemented as a sparse adjacency list, i.e., it stores for each node a list of
  49  *  its neighboring nodes. In particular, it stores for each node of type 1 a vector of Neighbor structures
  50  *  (accessible by the nb1() method) describing the neighboring nodes of type 2; similarly, for each node
  51  *  of type 2 it stores a vector of Neighbor structures (accessibly by the nb2() method) describing the
  52  *  neighboring nodes of type 1.
  53  *  Thus, each node has an associated variable of type BipartiteGraph::Neighbors, which is a vector of
  54  *  Neighbor structures, describing its neighboring nodes of the other type.
  55  *  \idea Cache second-order neighborhoods in BipartiteGraph.
  56  */
  57 class BipartiteGraph {
  58     public:
  59         /// Describes a neighboring node of some other node in a BipartiteGraph.
  60         /** A Neighbor structure has three members: \a iter, \a node and \a dual. The \a
  61          *  node member is the most important member: it contains the index of the neighboring node. The \a iter
  62          *  member is useful for iterating over neighbors, and contains the index of this Neighbor entry in the
  63          *  corresponding BipartiteGraph::Neighbors variable. The \a dual member is useful to find the dual Neighbor
  64          *  element: a pair of neighboring nodes can be either specified as a node of type 1 and a neighbor of type
  65          *  2, or as a node of type 2 and a neighbor of type 1; the \a dual member contains the index of the dual
  66          *  Neighbor element (see the example for another explanation of the dual member).
  67          */
  68         struct Neighbor {
  69             /// Corresponds to the index of this Neighbor entry in the vector of neighbors
  70             size_t iter;
  71             /// Contains the number of the neighboring node
  72             size_t node;
  73             /// Contains the "dual" iter
  74             size_t dual;
  75
  76             /// Default constructor
  77             Neighbor() {}
  78             /// Constructor that sets the Neighbor members according to the parameters
  79             Neighbor( size_t iter, size_t node, size_t dual ) : iter(iter), node(node), dual(dual) {}
  80
  81             /// Cast to size_t returns node member
  82             operator size_t () const { return node; }
  83         };
  84
  85         /// Describes the neighbors of some node.
  86         typedef std::vector<Neighbor> Neighbors;
  87
  88         /// Represents an edge: an Edge(\a n1,\a n2) corresponds to the edge between node \a n1 of type 1 and node \a n2 of type 2.
  89         typedef std::pair<size_t,size_t> Edge;
  90
  91     private:
  92         /// Contains for each node of type 1 a vector of its neighbors
  93         std::vector<Neighbors> _nb1;
  94
  95         /// Contains for each node of type 2 a vector of its neighbors
  96         std::vector<Neighbors> _nb2;
  97
  98         /// Used internally by isTree()
  99         struct levelType {
 100             std::vector<size_t> ind1;       // indices of nodes of type 1
 101             std::vector<size_t> ind2;       // indices of nodes of type 2
 102         };
 103
 104     public:
 105         /// Default constructor (creates an empty bipartite graph)
 106         BipartiteGraph() : _nb1(), _nb2() {}
 107
 108         /// Constructs BipartiteGraph from a range of edges.
 109         /** \tparam EdgeInputIterator Iterator that iterates over instances of BipartiteGraph::Edge.
 110          *  \param nr1 The number of nodes of type 1.
 111          *  \param nr2 The number of nodes of type 2.
 112          *  \param begin Points to the first edge.
 113          *  \param end Points just beyond the last edge.
 114          */
 115         template<typename EdgeInputIterator>
 116         BipartiteGraph( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) : _nb1( nr1 ), _nb2( nr2 ) {
 117             construct( nr1, nr2, begin, end );
 118         }
 119
 120         /// (Re)constructs BipartiteGraph from a range of edges.
 121         /** \tparam EdgeInputIterator Iterator that iterates over instances of BipartiteGraph::Edge.
 122          *  \param nr1 The number of nodes of type 1.
 123          *  \param nr2 The number of nodes of type 2.
 124          *  \param begin Points to the first edge.
 125          *  \param end Points just beyond the last edge.
 126          */
 127         template<typename EdgeInputIterator>
 128         void construct( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end );
 129
 130         /// Returns constant reference to the _i2'th neighbor of node i1 of type 1
 131         const Neighbor & nb1( size_t i1, size_t _i2 ) const {
 132 #ifdef DAI_DEBUG
 133             assert( i1 < _nb1.size() );
 134             assert( _i2 < _nb1[i1].size() );
 135 #endif
 136             return _nb1[i1][_i2];
 137         }
 138         /// Returns reference to the _i2'th neighbor of node i1 of type 1
 139         Neighbor & nb1( size_t i1, size_t _i2 ) {
 140 #ifdef DAI_DEBUG
 141             assert( i1 < _nb1.size() );
 142             assert( _i2 < _nb1[i1].size() );
 143 #endif
 144             return _nb1[i1][_i2];
 145         }
 146
 147         /// Returns constant reference to the _i1'th neighbor of node i2 of type 2
 148         const Neighbor & nb2( size_t i2, size_t _i1 ) const {
 149 #ifdef DAI_DEBUG
 150             assert( i2 < _nb2.size() );
 151             assert( _i1 < _nb2[i2].size() );
 152 #endif
 153             return _nb2[i2][_i1];
 154         }
 155         /// Returns reference to the _i1'th neighbor of node i2 of type 2
 156         Neighbor & nb2( size_t i2, size_t _i1 ) {
 157 #ifdef DAI_DEBUG
 158             assert( i2 < _nb2.size() );
 159             assert( _i1 < _nb2[i2].size() );
 160 #endif
 161             return _nb2[i2][_i1];
 162         }
 163
 164         /// Returns constant reference to all neighbors of node i1 of type 1
 165         const Neighbors & nb1( size_t i1 ) const {
 166 #ifdef DAI_DEBUG
 167             assert( i1 < _nb1.size() );
 168 #endif
 169             return _nb1[i1];
 170         }
 171         /// Returns reference to all neighbors of node of i1 type 1
 172         Neighbors & nb1( size_t i1 ) {
 173 #ifdef DAI_DEBUG
 174             assert( i1 < _nb1.size() );
 175 #endif
 176             return _nb1[i1];
 177         }
 178
 179         /// Returns constant reference to all neighbors of node i2 of type 2
 180         const Neighbors & nb2( size_t i2 ) const {
 181 #ifdef DAI_DEBUG
 182             assert( i2 < _nb2.size() );
 183 #endif
 184             return _nb2[i2];
 185         }
 186         /// Returns reference to all neighbors of node i2 of type 2
 187         Neighbors & nb2( size_t i2 ) {
 188 #ifdef DAI_DEBUG
 189             assert( i2 < _nb2.size() );
 190 #endif
 191             return _nb2[i2];
 192         }
 193
 194         /// Returns number of nodes of type 1
 195         size_t nr1() const { return _nb1.size(); }
 196         /// Returns number of nodes of type 2
 197         size_t nr2() const { return _nb2.size(); }
 198
 199         /// Calculates the number of edges, time complexity: O(nr1())
 200         size_t nrEdges() const {
 201             size_t sum = 0;
 202             for( size_t i1 = 0; i1 < nr1(); i1++ )
 203                 sum += nb1(i1).size();
 204             return sum;
 205         }
 206
 207         /// Adds a node of type 1 without neighbors.
 208         void add1() { _nb1.push_back( Neighbors() ); }
 209
 210         /// Adds a node of type 2 without neighbors.
 211         void add2() { _nb2.push_back( Neighbors() ); }
 212
 213         /// Adds a node of type 1, with neighbors specified by a range of nodes of type 2.
 214         /** \tparam NodeInputIterator Iterator that iterates over instances of size_t.
 215          *  \param begin Points to the first index of the nodes of type 2 that should become neighbors of the added node.
 216          *  \param end Points just beyond the last index of the nodes of type 2 that should become neighbors of the added node.
 217          *  \param sizeHint For improved efficiency, the size of the range may be specified by sizeHint.
 218          */
 219         template <typename NodeInputIterator>
 220         void add1( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
 221             Neighbors nbs1new;
 222             nbs1new.reserve( sizeHint );
 223             size_t iter = 0;
 224             for( NodeInputIterator it = begin; it != end; ++it ) {
 225                 assert( *it < nr2() );
 226                 Neighbor nb1new( iter, *it, nb2(*it).size() );
 227                 Neighbor nb2new( nb2(*it).size(), nr1(), iter++ );
 228                 nbs1new.push_back( nb1new );
 229                 nb2( *it ).push_back( nb2new );
 230             }
 231             _nb1.push_back( nbs1new );
 232         }
 233
 234         /// Adds a node of type 2, with neighbors specified by a range of nodes of type 1.
 235         /** \tparam NodeInputIterator Iterator that iterates over instances of size_t.
 236          *  \param begin Points to the first index of the nodes of type 1 that should become neighbors of the added node.
 237          *  \param end Points just beyond the last index of the nodes of type 1 that should become neighbors of the added node.
 238          *  \param sizeHint For improved efficiency, the size of the range may be specified by sizeHint.
 239          */
 240         template <typename NodeInputIterator>
 241         void add2( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
 242             Neighbors nbs2new;
 243             nbs2new.reserve( sizeHint );
 244             size_t iter = 0;
 245             for( NodeInputIterator it = begin; it != end; ++it ) {
 246                 assert( *it < nr1() );
 247                 Neighbor nb2new( iter, *it, nb1(*it).size() );
 248                 Neighbor nb1new( nb1(*it).size(), nr2(), iter++ );
 249                 nbs2new.push_back( nb2new );
 250                 nb1( *it ).push_back( nb1new );
 251             }
 252             _nb2.push_back( nbs2new );
 253         }
 254
 255         /// Removes node n1 of type 1 and all incident edges.
 256         void erase1( size_t n1 );
 257
 258         /// Removes node n2 of type 2 and all incident edges.
 259         void erase2( size_t n2 );
 260
 261         /// Adds an edge between node n1 of type 1 and node n2 of type 2.
 262         /** If check == true, only adds the edge if it does not exist already.
 263          */
 264         void addEdge( size_t n1, size_t n2, bool check = true ) {
 265             assert( n1 < nr1() );
 266             assert( n2 < nr2() );
 267             bool exists = false;
 268             if( check ) {
 269                 // Check whether the edge already exists
 270                 foreach( const Neighbor &nb2, nb1(n1) )
 271                     if( nb2 == n2 ) {
 272                         exists = true;
 273                         break;
 274                     }
 275             }
 276             if( !exists ) { // Add edge
 277                 Neighbor nb_1( _nb1[n1].size(), n2, _nb2[n2].size() );
 278                 Neighbor nb_2( nb_1.dual, n1, nb_1.iter );
 279                 _nb1[n1].push_back( nb_1 );
 280                 _nb2[n2].push_back( nb_2 );
 281             }
 282         }
 283
 284         /// Calculates second-order neighbors (i.e., neighbors of neighbors) of node n1 of type 1.
 285         /** If include == true, includes n1 itself, otherwise excludes n1.
 286          */
 287         std::vector<size_t> delta1( size_t n1, bool include = false ) const;
 288
 289         /// Calculates second-order neighbors (i.e., neighbors of neighbors) of node n2 of type 2.
 290         /** If include == true, includes n2 itself, otherwise excludes n2.
 291          */
 292         std::vector<size_t> delta2( size_t n2, bool include = false ) const;
 293
 294         /// Returns true if the graph is connected
 295         /** \todo Should be optimized by invoking boost::graph library
 296          */
 297         bool isConnected() const;
 298
 299         /// Returns true if the graph is a tree, i.e., if it is singly connected and connected.
 300         bool isTree() const;
 301
 302         /// Writes this BipartiteGraph to an output stream in GraphViz .dot syntax
 303         void printDot( std::ostream& os ) const;
 304
 305     private:
 306         /// Checks internal consistency
 307         void check() const;
 308 };
 309
 310
 311 template<typename EdgeInputIterator>
 312 void BipartiteGraph::construct( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) {
 313     _nb1.clear();
 314     _nb1.resize( nr1 );
 315     _nb2.clear();
 316     _nb2.resize( nr2 );
 317
 318     for( EdgeInputIterator e = begin; e != end; e++ ) {
 319 #ifdef DAI_DEBUG
 320         addEdge( e->first, e->second, true );
 321 #else
 322         addEdge( e->first, e->second, false );
 323 #endif
 324     }
 325 }
 326
 327
 328 } // end of namespace dai
 329
 330
 331 /** \example example_bipgraph.cpp
 332  *  This example deals with the following bipartite graph:
 333  *  \dot
 334  *  graph example {
 335  *    ordering=out;
 336  *    subgraph cluster_type1 {
 337  *      node[shape=circle,width=0.4,fixedsize=true,style=filled];
 338  *      12 [label="2"];
 339  *      11 [label="1"];
 340  *      10 [label="0"];
 341  *    }
 342  *    subgraph cluster_type2 {
 343  *      node[shape=polygon,regular=true,sides=4,width=0.4,fixedsize=true,style=filled];
 344  *      21 [label="1"];
 345  *      20 [label="0"];
 346  *    }
 347  *    10 -- 20;
 348  *    11 -- 20;
 349  *    12 -- 20;
 350  *    11 -- 21;
 351  *    12 -- 21;
 352  *  }
 353  *  \enddot
 354  *  It has three nodes of type 1 (drawn as circles) and two nodes of type 2 (drawn as rectangles).
 355  *  Node 0 of type 1 has only one neighbor (node 0 of type 2), but node 0 of type 2 has three neighbors (nodes 0,1,2 of type 1).
 356  *  The example code shows how to construct a BipartiteGraph object representing this bipartite graph and
 357  *  how to iterate over nodes and their neighbors.
 358  *
 359  *  \section Output
 360  *  \verbinclude examples/example_bipgraph.out
 361  *
 362  *  \section Source
 363  */
 364
 365
 366 #endif