/// Represents the neighborhood structure of nodes in an undirected, bipartite graph.
/** A bipartite graph has two types of nodes: type 1 and type 2. Edges can occur only between
- * nodes of different type. Nodes are indexed by an unsigned integer. If there are nr1()
- * nodes of type 1 and nr2() nodes of type 2, the nodes of type 1 are numbered
- * 0,1,2,...,nr1()-1 and the nodes of type 2 are numbered 0,1,2,...,nr2()-1. An edge
+ * nodes of different type. Nodes are indexed by an unsigned integer. If there are nrNodes1()
+ * nodes of type 1 and nrNodes2() nodes of type 2, the nodes of type 1 are numbered
+ * 0,1,2,...,nrNodes1()-1 and the nodes of type 2 are numbered 0,1,2,...,nrNodes2()-1. An edge
* between node \a n1 of type 1 and node \a n2 of type 2 is represented by a BipartiteGraph::Edge(\a n1,\a n2).
*
* A BipartiteGraph is implemented as a sparse adjacency list, i.e., it stores for each node a list of
/// Constructs BipartiteGraph from a range of edges.
/** \tparam EdgeInputIterator Iterator that iterates over instances of BipartiteGraph::Edge.
- * \param nr1 The number of nodes of type 1.
- * \param nr2 The number of nodes of type 2.
+ * \param nrNodes1 The number of nodes of type 1.
+ * \param nrNodes2 The number of nodes of type 2.
* \param begin Points to the first edge.
* \param end Points just beyond the last edge.
*/
template<typename EdgeInputIterator>
- BipartiteGraph( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) : _nb1(), _nb2() {
- construct( nr1, nr2, begin, end );
+ BipartiteGraph( size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end ) : _nb1(), _nb2() {
+ construct( nrNodes1, nrNodes2, begin, end );
}
//@}
//@{
/// (Re)constructs BipartiteGraph from a range of edges.
/** \tparam EdgeInputIterator Iterator that iterates over instances of BipartiteGraph::Edge.
- * \param nr1 The number of nodes of type 1.
- * \param nr2 The number of nodes of type 2.
+ * \param nrNodes1 The number of nodes of type 1.
+ * \param nrNodes2 The number of nodes of type 2.
* \param begin Points to the first edge.
* \param end Points just beyond the last edge.
*/
template<typename EdgeInputIterator>
- void construct( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end );
+ void construct( size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end );
/// Adds a node of type 1 without neighbors and returns the index of the added node.
- size_t add1() { _nb1.push_back( Neighbors() ); return _nb1.size() - 1; }
+ size_t addNode1() { _nb1.push_back( Neighbors() ); return _nb1.size() - 1; }
/// Adds a node of type 2 without neighbors and returns the index of the added node.
- size_t add2() { _nb2.push_back( Neighbors() ); return _nb2.size() - 1; }
+ size_t addNode2() { _nb2.push_back( Neighbors() ); return _nb2.size() - 1; }
+
+
+ /// Adds a node of type 1 without neighbors and returns the index of the added node.
+ /** \deprecated Please use dai::BipartiteGraph::addNode1() instead.
+ */
+ size_t add1() { return addNode1(); }
+
+ /// Adds a node of type 2 without neighbors and returns the index of the added node.
+ /** \deprecated Please use dai::BipartiteGraph::addNode2() instead.
+ */
+ size_t add2() { return addNode2(); }
/// Adds a node of type 1, with neighbors specified by a range of nodes of type 2.
/** \tparam NodeInputIterator Iterator that iterates over instances of \c size_t.
* \returns Index of the added node.
*/
template <typename NodeInputIterator>
- size_t add1( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
+ size_t addNode1( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
Neighbors nbs1new;
nbs1new.reserve( sizeHint );
size_t iter = 0;
for( NodeInputIterator it = begin; it != end; ++it ) {
- DAI_ASSERT( *it < nr2() );
+ DAI_ASSERT( *it < nrNodes2() );
Neighbor nb1new( iter, *it, nb2(*it).size() );
- Neighbor nb2new( nb2(*it).size(), nr1(), iter++ );
+ Neighbor nb2new( nb2(*it).size(), nrNodes1(), iter++ );
nbs1new.push_back( nb1new );
nb2( *it ).push_back( nb2new );
}
* \returns Index of the added node.
*/
template <typename NodeInputIterator>
- size_t add2( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
+ size_t addNode2( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
Neighbors nbs2new;
nbs2new.reserve( sizeHint );
size_t iter = 0;
for( NodeInputIterator it = begin; it != end; ++it ) {
- DAI_ASSERT( *it < nr1() );
+ DAI_ASSERT( *it < nrNodes1() );
Neighbor nb2new( iter, *it, nb1(*it).size() );
- Neighbor nb1new( nb1(*it).size(), nr2(), iter++ );
+ Neighbor nb1new( nb1(*it).size(), nrNodes2(), iter++ );
nbs2new.push_back( nb2new );
nb1( *it ).push_back( nb1new );
}
return _nb2.size() - 1;
}
+ /// Adds a node of type 1, with neighbors specified by a range of nodes of type 2.
+ /** \deprecated Please use dai::BipartiteGraph::addNode1( NodeInputIterator, NodeInputIterator, size_t) instead.
+ */
+ template <typename NodeInputIterator>
+ size_t add1( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
+ return addNode1( begin, end, sizeHint );
+ }
+
+ /// Adds a node of type 2, with neighbors specified by a range of nodes of type 1.
+ /** \deprecated Please use dai::BipartiteGraph::addNode2( NodeInputIterator, NodeInputIterator, size_t) instead.
+ */
+ template <typename NodeInputIterator>
+ size_t add2( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
+ return addNode2( begin, end, sizeHint );
+ }
+
/// Adds an edge between node \a n1 of type 1 and node \a n2 of type 2.
/** If \a check == \c true, only adds the edge if it does not exist already.
*/
/// \name Erasing nodes and edges
//@{
/// Removes node \a n1 of type 1 and all incident edges; indices of other nodes are changed accordingly.
- void erase1( size_t n1 );
+ void eraseNode1( size_t n1 );
+
+ /// Removes node \a n2 of type 2 and all incident edges; indices of other nodes are changed accordingly.
+ void eraseNode2( size_t n2 );
+
+ /// Removes node \a n1 of type 1 and all incident edges; indices of other nodes are changed accordingly.
+ /** \deprecated Please use dai::BipartiteGraph::eraseNode1(size_t) instead.
+ */
+ void erase1( size_t n1 ) { eraseNode1( n1 ); }
/// Removes node \a n2 of type 2 and all incident edges; indices of other nodes are changed accordingly.
- void erase2( size_t n2 );
+ /** \deprecated Please use dai::BipartiteGraph::eraseNode2(size_t) instead.
+ */
+ void erase2( size_t n2 ) { eraseNode2( n2 ); }
/// Removes edge between node \a n1 of type 1 and node \a n2 of type 2.
void eraseEdge( size_t n1, size_t n2 );
/// \name Queries
//@{
/// Returns number of nodes of type 1
- size_t nr1() const { return _nb1.size(); }
+ size_t nrNodes1() const { return _nb1.size(); }
+ /// Returns number of nodes of type 2
+ size_t nrNodes2() const { return _nb2.size(); }
+
+ /// Returns number of nodes of type 1
+ /** \deprecated Please use dai::BipartiteGraph::nrNodes1() instead.
+ */
+ size_t nr1() const { return nrNodes1(); }
+
/// Returns number of nodes of type 2
- size_t nr2() const { return _nb2.size(); }
+ /** \deprecated Please use dai::BipartiteGraph::nrNodes2() instead.
+ */
+ size_t nr2() const { return nrNodes2(); }
- /// Calculates the number of edges, time complexity: O(nr1())
+ /// Calculates the number of edges, time complexity: O(nrNodes1())
size_t nrEdges() const {
size_t sum = 0;
- for( size_t i1 = 0; i1 < nr1(); i1++ )
+ for( size_t i1 = 0; i1 < nrNodes1(); i1++ )
sum += nb1(i1).size();
return sum;
}
template<typename EdgeInputIterator>
-void BipartiteGraph::construct( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) {
+void BipartiteGraph::construct( size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end ) {
_nb1.clear();
- _nb1.resize( nr1 );
+ _nb1.resize( nrNodes1 );
_nb2.clear();
- _nb2.resize( nr2 );
+ _nb2.resize( nrNodes2 );
for( EdgeInputIterator e = begin; e != end; e++ ) {
#ifdef DAI_DEBUG
void BipartiteGraph::addEdge( size_t n1, size_t n2, bool check ) {
- DAI_ASSERT( n1 < nr1() );
- DAI_ASSERT( n2 < nr2() );
+ DAI_ASSERT( n1 < nrNodes1() );
+ DAI_ASSERT( n2 < nrNodes2() );
bool exists = false;
if( check ) {
// Check whether the edge already exists
}
-void BipartiteGraph::erase1( size_t n1 ) {
- DAI_ASSERT( n1 < nr1() );
+void BipartiteGraph::eraseNode1( size_t n1 ) {
+ DAI_ASSERT( n1 < nrNodes1() );
// Erase neighbor entry of node n1
_nb1.erase( _nb1.begin() + n1 );
// Adjust neighbor entries of nodes of type 2
- for( size_t n2 = 0; n2 < nr2(); n2++ ) {
+ for( size_t n2 = 0; n2 < nrNodes2(); n2++ ) {
for( size_t iter = 0; iter < nb2(n2).size(); ) {
Neighbor &m1 = nb2(n2, iter);
if( m1.node == n1 ) {
}
-void BipartiteGraph::erase2( size_t n2 ) {
- DAI_ASSERT( n2 < nr2() );
+void BipartiteGraph::eraseNode2( size_t n2 ) {
+ DAI_ASSERT( n2 < nrNodes2() );
// Erase neighbor entry of node n2
_nb2.erase( _nb2.begin() + n2 );
// Adjust neighbor entries of nodes of type 1
- for( size_t n1 = 0; n1 < nr1(); n1++ ) {
+ for( size_t n1 = 0; n1 < nrNodes1(); n1++ ) {
for( size_t iter = 0; iter < nb1(n1).size(); ) {
Neighbor &m2 = nb1(n1, iter);
if( m2.node == n2 ) {
void BipartiteGraph::eraseEdge( size_t n1, size_t n2 ) {
- DAI_ASSERT( n1 < nr1() );
- DAI_ASSERT( n2 < nr2() );
+ DAI_ASSERT( n1 < nrNodes1() );
+ DAI_ASSERT( n2 < nrNodes2() );
size_t iter;
// Search for edge among neighbors of n1
for( iter = 0; iter < nb1(n1).size(); iter++ )
bool BipartiteGraph::isConnected() const {
- if( nr1() == 0 ) {
+ if( nrNodes1() == 0 ) {
return true;
} else {
using namespace boost;
typedef pair<size_t, size_t> E;
// Copy graph structure into boostGraph object
- size_t N = nr1();
+ size_t N = nrNodes1();
vector<E> edges;
edges.reserve( nrEdges() );
- for( size_t n1 = 0; n1 < nr1(); n1++ )
+ for( size_t n1 = 0; n1 < nrNodes1(); n1++ )
foreach( const Neighbor &n2, nb1(n1) )
edges.push_back( E( n1, n2.node + N ) );
- boostGraph g( edges.begin(), edges.end(), nr1() + nr2() );
+ boostGraph g( edges.begin(), edges.end(), nrNodes1() + nrNodes2() );
// Construct connected components using Boost Graph Library
std::vector<int> component( num_vertices( g ) );
return (num_comp == 1);
/*
- std::vector<bool> incomponent1( nr1(), false );
- std::vector<bool> incomponent2( nr2(), false );
+ std::vector<bool> incomponent1( nrNodes1(), false );
+ std::vector<bool> incomponent2( nrNodes2(), false );
incomponent1[0] = true;
bool found_new_nodes;
found_new_nodes = false;
// For all nodes of type 2, check if they are connected with the (growing) component
- for( size_t n2 = 0; n2 < nr2(); n2++ )
+ for( size_t n2 = 0; n2 < nrNodes2(); n2++ )
if( !incomponent2[n2] ) {
foreach( const Neighbor &n1, nb2(n2) ) {
if( incomponent1[n1] ) {
}
// For all nodes of type 1, check if they are connected with the (growing) component
- for( size_t n1 = 0; n1 < nr1(); n1++ )
+ for( size_t n1 = 0; n1 < nrNodes1(); n1++ )
if( !incomponent1[n1] ) {
foreach( const Neighbor &n2, nb1(n1) ) {
if( incomponent2[n2] ) {
// Check if there are remaining nodes (not in the component)
bool all_connected = true;
- for( size_t n1 = 0; (n1 < nr1()) && all_connected; n1++ )
+ for( size_t n1 = 0; (n1 < nrNodes1()) && all_connected; n1++ )
if( !incomponent1[n1] )
all_connected = false;
- for( size_t n2 = 0; (n2 < nr2()) && all_connected; n2++ )
+ for( size_t n2 = 0; (n2 < nrNodes2()) && all_connected; n2++ )
if( !incomponent2[n2] )
all_connected = false;
size_t nr_1 = 0;
size_t nr_2 = 0;
- if( nr1() == 0 || nr2() == 0 )
+ if( nrNodes1() == 0 || nrNodes2() == 0 )
return true;
else {
levelType newLevel;
nr_1 += newLevel.ind1.size();
nr_2 += newLevel.ind2.size();
} while( ((newLevel.ind1.size() != 0) || (newLevel.ind2.size() != 0)) && !foundCycle );
- if( nr_1 == nr1() && nr_2 == nr2() && !foundCycle )
+ if( nr_1 == nrNodes1() && nr_2 == nrNodes2() && !foundCycle )
return true;
else
return false;
using namespace std;
os << "graph G {" << endl;
os << "node[shape=circle,width=0.4,fixedsize=true];" << endl;
- for( size_t n1 = 0; n1 < nr1(); n1++ )
+ for( size_t n1 = 0; n1 < nrNodes1(); n1++ )
os << "\tx" << n1 << ";" << endl;
os << "node[shape=box,width=0.3,height=0.3,fixedsize=true];" << endl;
- for( size_t n2 = 0; n2 < nr2(); n2++ )
+ for( size_t n2 = 0; n2 < nrNodes2(); n2++ )
os << "\ty" << n2 << ";" << endl;
- for( size_t n1 = 0; n1 < nr1(); n1++ )
+ for( size_t n1 = 0; n1 < nrNodes1(); n1++ )
foreach( const Neighbor &n2, nb1(n1) )
os << "\tx" << n1 << " -- y" << n2 << ";" << endl;
os << "}" << endl;
void BipartiteGraph::checkConsistency() const {
- size_t N1 = nr1();
- size_t N2 = nr2();
+ size_t N1 = nrNodes1();
+ size_t N2 = nrNodes2();
for( size_t n1 = 0; n1 < N1; n1++ ) {
size_t iter = 0;
foreach( const Neighbor &n2, nb1(n1) ) {