- Fixed bug in BipartiteGraph::eraseNode1()
- Fixed bug in BipartiteGraph::eraseNode2()
- Fixed bug in BipartiteGraph::isTree()
+ - Added BipartiteGraph::hasEdge()
+ - Added BipartiteGraph::findNb1()
+ - Added BipartiteGraph::findNb2()
+ - BipartiteGraph::delta1() and BipartiteGraph::delta2() now
+ return a SmallSet<size_t> instead of a vector<size_t>
* Improved GraphAL code:
- Fixed bug in GraphAL::nrEdges()
- Fixed bug in GraphAL::addEdge()
- Fixed bug in createGraphGrid3D()
- Fixed bug in createGraphRegular()
- Added GraphAL::hasEdge(size_t,size_t)
+* Improved SmallSet code:
+ - The sizeHint argument of the iterator constructor
+ SmallSet::SmallSet( TIterator begin, TIterator end, size_t sizeHint=0 )
+ no longer has a default value in order to avoid confusion with the
+ SmallSet::SmallSet( const T &t1, const T &t2 )
+ constructor.
* Removed RandomDRegularGraph()
* Compressed Makefile
* Added unit tests for Var, SmallSet, VarSet, Graph, BipartiteGraph
#include <vector>
#include <algorithm>
#include <dai/util.h>
+#include <dai/smallset.h>
#include <dai/exceptions.h>
return sum;
}
+ /// Returns true if the graph contains an edge between node \a n1 of type 1 and node \a n2 of type 2.
+ /** \note The time complexity is linear in the number of neighbors of \a n1 or \a n2
+ */
+ bool hasEdge( size_t n1, size_t n2 ) {
+ if( nb1(n1).size() < nb2(n2).size() ) {
+ for( size_t _n2 = 0; _n2 < nb1(n1).size(); _n2++ )
+ if( nb1( n1, _n2 ) == n2 )
+ return true;
+ } else {
+ for( size_t _n1 = 0; _n1 < nb2(n2).size(); _n1++ )
+ if( nb2( n2, _n1 ) == n1 )
+ return true;
+ }
+ return false;
+ }
+
+ /// Returns the index of a given node \a n2 of type 2 amongst the neighbors of node \a n1 of type 1
+ /** \note The time complexity is linear in the number of neighbors of \a n1
+ * \throw OBJECT_NOT_FOUND if \a n2 is not a neighbor of \a n1
+ */
+ size_t findNb1( size_t n1, size_t n2 ) {
+ for( size_t _n2 = 0; _n2 < nb1(n1).size(); _n2++ )
+ if( nb1( n1, _n2 ) == n2 )
+ return _n2;
+ DAI_THROW(OBJECT_NOT_FOUND);
+ return nb1(n1).size();
+ }
+
+ /// Returns the index of a given node \a n1 of type 1 amongst the neighbors of node \a n2 of type 2
+ /** \note The time complexity is linear in the number of neighbors of \a n2
+ * \throw OBJECT_NOT_FOUND if \a n1 is not a neighbor of \a n2
+ */
+ size_t findNb2( size_t n1, size_t n2 ) {
+ for( size_t _n1 = 0; _n1 < nb2(n2).size(); _n1++ )
+ if( nb2( n2, _n1 ) == n1 )
+ return _n1;
+ DAI_THROW(OBJECT_NOT_FOUND);
+ return nb2(n2).size();
+ }
+
/// Calculates second-order neighbors (i.e., neighbors of neighbors) of node \a n1 of type 1.
/** If \a include == \c true, includes \a n1 itself, otherwise excludes \a n1.
*/
- std::vector<size_t> delta1( size_t n1, bool include = false ) const;
+ SmallSet<size_t> delta1( size_t n1, bool include = false ) const;
/// Calculates second-order neighbors (i.e., neighbors of neighbors) of node \a n2 of type 2.
/** If \a include == \c true, includes \a n2 itself, otherwise excludes \a n2.
*/
- std::vector<size_t> delta2( size_t n2, bool include = false ) const;
+ SmallSet<size_t> delta2( size_t n2, bool include = false ) const;
/// Returns true if the graph is connected
bool isConnected() const;
}
/// Returns true if the graph contains an edge between nodes \a n1 and \a n2
- /** \note The time complexity is linear in the number of neighbors of \a n1
+ /** \note The time complexity is linear in the number of neighbors of \a n1 or \a n2
*/
bool hasEdge( size_t n1, size_t n2 ) {
- for( size_t _n2 = 0; _n2 < nb(n1).size(); _n2++ )
- if( nb( n1, _n2 ) == n2 )
- return true;
+ if( nb(n1).size() < nb(n2).size() ) {
+ for( size_t _n2 = 0; _n2 < nb(n1).size(); _n2++ )
+ if( nb( n1, _n2 ) == n2 )
+ return true;
+ } else {
+ for( size_t _n1 = 0; _n1 < nb(n2).size(); _n1++ )
+ if( nb( n2, _n1 ) == n1 )
+ return true;
+ }
return false;
}
* \param sizeHint For efficiency, the number of elements can be speficied by \a sizeHint.
*/
template <typename TIterator>
- SmallSet( TIterator begin, TIterator end, size_t sizeHint=0 ) {
+ SmallSet( TIterator begin, TIterator end, size_t sizeHint ) {
_elements.reserve( sizeHint );
_elements.insert( _elements.begin(), begin, end );
std::sort( _elements.begin(), _elements.end() );
}
-std::vector<size_t> BipartiteGraph::delta1( size_t n1, bool include ) const {
+SmallSet<size_t> BipartiteGraph::delta1( size_t n1, bool include ) const {
// get all second-order neighbors
- std::vector<size_t> result;
+ SmallSet<size_t> result;
foreach( const Neighbor &n2, nb1(n1) )
foreach( const Neighbor &m1, nb2(n2) )
if( include || (m1 != n1) )
- result.push_back( m1 );
- // remove duplicates
- std::vector<size_t>::iterator it = std::unique( result.begin(), result.end() );
- result.erase( it, result.end() );
+ result |= m1;
return result;
}
-std::vector<size_t> BipartiteGraph::delta2( size_t n2, bool include ) const {
+SmallSet<size_t> BipartiteGraph::delta2( size_t n2, bool include ) const {
// store all second-order neighbors
- std::vector<size_t> result;
+ SmallSet<size_t> result;
foreach( const Neighbor &n1, nb2(n2) )
foreach( const Neighbor &m2, nb1(n1) )
if( include || (m2 != n2) )
- result.push_back( m2 );
- // remove duplicates
- std::vector<size_t>::iterator it = std::unique( result.begin(), result.end() );
- result.erase( it, result.end() );
+ result |= m2;
return result;
}
size_t eliminationCost_MinNeighbors( const ClusterGraph &cl, size_t i ) {
- std::vector<size_t> id_n = cl.G.delta1( i );
- return id_n.size();
+ return cl.G.delta1( i ).size();
}
size_t eliminationCost_MinWeight( const ClusterGraph &cl, size_t i ) {
- std::vector<size_t> id_n = cl.G.delta1( i );
+ SmallSet<size_t> id_n = cl.G.delta1( i );
size_t cost = 1;
- for( size_t _i = 0; _i < id_n.size(); _i++ )
- cost *= cl.vars[id_n[_i]].states();
+ for( SmallSet<size_t>::const_iterator it = id_n.begin(); it != id_n.end(); it++ )
+ cost *= cl.vars[*it].states();
return cost;
}
size_t eliminationCost_MinFill( const ClusterGraph &cl, size_t i ) {
- std::vector<size_t> id_n = cl.G.delta1( i );
+ SmallSet<size_t> id_n = cl.G.delta1( i );
size_t cost = 0;
// for each unordered pair {i1,i2} adjacent to n
- for( size_t _i1 = 0; _i1 < id_n.size(); _i1++ )
- for( size_t _i2 = _i1 + 1; _i2 < id_n.size(); _i2++ ) {
- // if i1 and i2 are not adjacent, eliminating n would make them adjacent
- if( !cl.adj(id_n[_i1], id_n[_i2]) )
- cost++;
- }
+ for( SmallSet<size_t>::const_iterator it1 = id_n.begin(); it1 != id_n.end(); it1++ )
+ for( SmallSet<size_t>::const_iterator it2 = it1; it2 != id_n.end(); it2++ )
+ if( it1 != it2 ) {
+ // if i1 and i2 are not adjacent, eliminating n would make them adjacent
+ if( !cl.adj(*it1, *it2) )
+ cost++;
+ }
return cost;
}
size_t eliminationCost_WeightedMinFill( const ClusterGraph &cl, size_t i ) {
- std::vector<size_t> id_n = cl.G.delta1( i );
+ SmallSet<size_t> id_n = cl.G.delta1( i );
size_t cost = 0;
// for each unordered pair {i1,i2} adjacent to n
- for( size_t _i1 = 0; _i1 < id_n.size(); _i1++ )
- for( size_t _i2 = _i1 + 1; _i2 < id_n.size(); _i2++ ) {
- // if i1 and i2 are not adjacent, eliminating n would make them adjacent
- if( !cl.adj(id_n[_i1], id_n[_i2]) )
- cost += cl.vars[id_n[_i1]].states() * cl.vars[id_n[_i2]].states();
- }
+ for( SmallSet<size_t>::const_iterator it1 = id_n.begin(); it1 != id_n.end(); it1++ )
+ for( SmallSet<size_t>::const_iterator it2 = it1; it2 != id_n.end(); it2++ )
+ if( it1 != it2 ) {
+ // if i1 and i2 are not adjacent, eliminating n would make them adjacent
+ if( !cl.adj(*it1, *it2) )
+ cost += cl.vars[*it1].states() * cl.vars[*it2].states();
+ }
return cost;
}
}
+BOOST_AUTO_TEST_CASE( RandomAddEraseTest ) {
+ // check adding and erasing nodes and edges randomly
+ BipartiteGraph G;
+ for( size_t maxN1 = 2; maxN1 < 10; maxN1++ )
+ for( size_t maxN2 = 2; maxN2 < 10; maxN2++ )
+ for( size_t repeats = 0; repeats < 100000; repeats++ ) {
+ size_t action = rnd( 5 );
+ size_t N1 = G.nrNodes1();
+ size_t N2 = G.nrNodes2();
+ size_t M = G.nrEdges();
+ size_t maxM = N1 * N2;
+ if( action == 0 ) {
+ // add node
+ if( rnd( 2 ) == 0 ) {
+ // add node of type 1
+ if( N1 < maxN1 )
+ G.addNode1();
+ } else {
+ // add node of type 2
+ if( N2 < maxN2 )
+ G.addNode2();
+ }
+ } else if( action == 1 ) {
+ // erase node
+ if( rnd( 2 ) == 0 ) {
+ // erase node of type 1
+ if( N1 > 0 )
+ G.eraseNode1( rnd( N1 ) );
+ } else {
+ // erase node of type 2
+ if( N2 > 0 )
+ G.eraseNode2( rnd( N2 ) );
+ }
+ } else if( action == 2 || action == 3 ) {
+ // add edge
+ if( N1 >= 1 && N2 >= 1 && M < maxM ) {
+ size_t n1 = 0;
+ size_t n2 = 0;
+ if( rnd( 2 ) == 0 ) {
+ do {
+ n1 = rnd( N1 );
+ } while( G.nb1(n1).size() >= N2 );
+ do {
+ n2 = rnd( N2 );
+ } while( G.hasEdge( n1, n2 ) );
+ } else {
+ do {
+ n2 = rnd( N2 );
+ } while( G.nb2(n2).size() >= N1 );
+ do {
+ n1 = rnd( N1 );
+ } while( G.hasEdge( n1, n2 ) );
+ }
+ G.addEdge( n1, n2 );
+ }
+ } else if( action == 4 ) {
+ // erase edge
+ if( M > 0 ) {
+ size_t n1 = 0;
+ size_t n2 = 0;
+ if( rnd( 2 ) == 0 ) {
+ do {
+ n1 = rnd( N1 );
+ } while( G.nb1(n1).size() == 0 );
+ do {
+ n2 = rnd( N2 );
+ } while( !G.hasEdge( n1, n2 ) );
+ } else {
+ do {
+ n2 = rnd( N2 );
+ } while( G.nb2(n2).size() == 0 );
+ do {
+ n1 = rnd( N1 );
+ } while( !G.hasEdge( n1, n2 ) );
+ }
+ G.eraseEdge( n1, n2 );
+ }
+ }
+ G.checkConsistency();
+ }
+}
+
+
BOOST_AUTO_TEST_CASE( QueriesTest ) {
// check queries which have not been tested in another test case
typedef BipartiteGraph::Edge Edge;
std::vector<Edge> edges;
- edges.push_back( Edge( 0, 0 ) );
edges.push_back( Edge( 0, 1 ) );
edges.push_back( Edge( 1, 1 ) );
+ edges.push_back( Edge( 0, 0 ) );
BipartiteGraph G( 3, 2, edges.begin(), edges.end() );
G.checkConsistency();
- std::vector<size_t> v;
- std::vector<size_t> v0; v0.push_back(0);
- std::vector<size_t> v1; v1.push_back(1);
- std::vector<size_t> v01; v01.push_back(0); v01.push_back(1);
- BOOST_CHECK( G.delta1( 0, true ) == v01 );
- BOOST_CHECK( G.delta1( 1, true ) == v01 );
- BOOST_CHECK( G.delta1( 2, true ) == v );
- BOOST_CHECK( G.delta2( 0, true ) == v01 );
- BOOST_CHECK( G.delta2( 1, true ) == v01 );
- BOOST_CHECK( G.delta1( 0, false ) == v1 );
- BOOST_CHECK( G.delta1( 1, false ) == v0 );
- BOOST_CHECK( G.delta1( 2, false ) == v );
- BOOST_CHECK( G.delta2( 0, false ) == v1 );
- BOOST_CHECK( G.delta2( 1, false ) == v0 );
+ SmallSet<size_t> v;
+ SmallSet<size_t> v0( 0 );
+ SmallSet<size_t> v1( 1 );
+ SmallSet<size_t> v01( 0, 1 );
+ BOOST_CHECK_EQUAL( G.delta1( 0, true ), v01 );
+ BOOST_CHECK_EQUAL( G.delta1( 1, true ), v01 );
+ BOOST_CHECK_EQUAL( G.delta1( 2, true ), v );
+ BOOST_CHECK_EQUAL( G.delta2( 0, true ), v01 );
+ BOOST_CHECK_EQUAL( G.delta2( 1, true ), v01 );
+ BOOST_CHECK_EQUAL( G.delta1( 0, false ), v1 );
+ BOOST_CHECK_EQUAL( G.delta1( 1, false ), v0 );
+ BOOST_CHECK_EQUAL( G.delta1( 2, false ), v );
+ BOOST_CHECK_EQUAL( G.delta2( 0, false ), v1 );
+ BOOST_CHECK_EQUAL( G.delta2( 1, false ), v0 );
+ BOOST_CHECK( G.hasEdge( 0, 0 ) );
+ BOOST_CHECK( G.hasEdge( 0, 1 ) );
+ BOOST_CHECK( G.hasEdge( 1, 1 ) );
+ BOOST_CHECK( !G.hasEdge( 1, 0 ) );
+ BOOST_CHECK( !G.hasEdge( 2, 0 ) );
+ BOOST_CHECK( !G.hasEdge( 2, 1 ) );
+ BOOST_CHECK_EQUAL( G.findNb1( 0, 0 ), 1 );
+ BOOST_CHECK_EQUAL( G.findNb1( 0, 1 ), 0 );
+ BOOST_CHECK_EQUAL( G.findNb1( 1, 1 ), 0 );
+ BOOST_CHECK_EQUAL( G.findNb2( 0, 0 ), 0 );
+ BOOST_CHECK_EQUAL( G.findNb2( 0, 1 ), 0 );
+ BOOST_CHECK_EQUAL( G.findNb2( 1, 1 ), 1 );
}
}
+BOOST_AUTO_TEST_CASE( RandomAddEraseTest ) {
+ // check adding and erasing nodes and edges randomly
+ GraphAL G;
+ for( size_t maxN = 2; maxN < 50; maxN++ )
+ for( size_t repeats = 0; repeats < 10000; repeats++ ) {
+ size_t action = rnd( 5 );
+ size_t N = G.nrNodes();
+ size_t M = G.nrEdges();
+ size_t maxM = N * (N - 1) / 2;
+ if( action == 0 ) {
+ // add node
+ if( N < maxN )
+ G.addNode();
+ } else if( action == 1 ) {
+ // erase node
+ if( N > 0 )
+ G.eraseNode( rnd( N ) );
+ } else if( action == 2 || action == 3 ) {
+ // add edge
+ if( N >= 2 && M < maxM ) {
+ size_t n1 = 0;
+ do {
+ n1 = rnd( N );
+ } while( G.nb(n1).size() >= N - 1 );
+ size_t n2 = 0;
+ do {
+ n2 = rnd( N );
+ } while( G.hasEdge( n1, n2 ) );
+ G.addEdge( n1, n2 );
+ }
+ } else if( action == 4 ) {
+ // erase edge
+ if( M > 0 ) {
+ size_t n1 = 0;
+ do {
+ n1 = rnd( N );
+ } while( G.nb(n1).size() == 0 );
+ size_t n2 = 0;
+ do {
+ n2 = rnd( N );
+ } while( !G.hasEdge( n1, n2 ) );
+ G.eraseEdge( n1, n2 );
+ }
+ }
+ G.checkConsistency();
+ }
+}
+
+
BOOST_AUTO_TEST_CASE( QueriesAndCreationTest ) {
// check queries and createGraph* functions
BOOST_CHECK( !y.contains( 5 ) );
BOOST_CHECK( y.contains( 1 ) );
+ SmallSet<size_t> u( 0, 1 );
+ BOOST_CHECK( !u.empty() );
+ BOOST_CHECK_EQUAL( u.size(), 2 );
+ BOOST_CHECK( !u.contains( 2 ) );
+ BOOST_CHECK( u.contains( 1 ) );
+ BOOST_CHECK( u.contains( 0 ) );
+
SmallSet<double> z( 1.0, 2.0 );
BOOST_CHECK_EQUAL( z.size(), 2 );
BOOST_CHECK( !z.contains( 5.0 ) );
a.push_back( 4 );
a.push_back( 3 );
a.push_back( 2 );
- SmallSet<double> w( a.begin(), a.end() );
+ SmallSet<double> w( a.begin(), a.end(), a.size() );
BOOST_CHECK_EQUAL( w.size(), 4 );
BOOST_CHECK( w.contains( 1 ) );
BOOST_CHECK( w.contains( 2 ) );
projects / libdai.git / commitdiff