git HEAD
--------
+* Fixed regression in SWIG interface caused by new build system (thanks to Benjamin Mumm for reporting this)
+* Added 'inclusive' argument to DAG::ancestors() and DAG::descendants()
* [Julien Rebetez] added FactorGraph::printDot() to SWIG interface
* Build system: optional compilation targets are now set in include/dai/dai_config.h instead of Makefile.ALL
* Workaround for bug in Boost Graph Library version 1.54 ("The graph may not contain an edge with negative weight") by not using Prim's minimum spanning tree algorithm anymore
/// Returns children of node \a n as a SmallSet<size_t>.
SmallSet<size_t> chSet( size_t n ) const;
- /// Returns the set of ancestors of node \a n, i.e., all nodes \a a such that there exists a directed path from \a a to \a n (excluding \a n itself)
- std::set<size_t> ancestors( size_t n ) const;
+ /// Returns the set of ancestors of node \a n, i.e., all nodes \a a such that there exists a directed path from \a a to \a n (including \a n itself if \a inclusive == \c true)
+ std::set<size_t> ancestors( size_t n, bool inclusive ) const;
- /// Returns the set of descendants of node \a n, i.e., all nodes \a d such that there exists a directed path from \a n to \a d (excluding \a n itself)
- std::set<size_t> descendants( size_t n ) const;
+ /// Returns the set of descendants of node \a n, i.e., all nodes \a d such that there exists a directed path from \a n to \a d (excluding \a n itself if \a inclusive == \c true)
+ std::set<size_t> descendants( size_t n, bool inclusive ) const;
/// Returns whether there exists a directed path from node \a n1 to node \a n2 (which may consist of zero edges)
bool existsDirectedPath( size_t n1, size_t n2 ) const;
}
-/// Returns the set of ancestors of node \a n, i.e., all nodes \a m such that there exists a directed path from \a m to \a n (excluding \a n itself)
-std::set<size_t> DAG::ancestors( size_t n ) const {
+/// Returns the set of ancestors of node \a n, i.e., all nodes \a a such that there exists a directed path from \a a to \a n (including \a n itself if \a inclusive == \c true)
+std::set<size_t> DAG::ancestors( size_t n, bool inclusive ) const {
set<size_t> anc;
+ if( inclusive )
+ anc.insert( n );
set<size_t> curParents;
curParents.insert( n );
}
-/// Returns the set of descendants of node \a n, i.e., all nodes \a m such that there exists a directed path from \a n to \a m (excluding \a n itself)
-std::set<size_t> DAG::descendants( size_t n ) const {
+/// Returns the set of descendants of node \a n, i.e., all nodes \a d such that there exists a directed path from \a n to \a d (excluding \a n itself if \a inclusive == \c true)
+std::set<size_t> DAG::descendants( size_t n, bool inclusive ) const {
set<size_t> desc;
+ if( inclusive )
+ desc.insert( n );
set<size_t> curChildren;
curChildren.insert( n );
%include "std_vector.i"
%template(IntVector) std::vector<size_t>;
//%include "std_set.i" /* for python */
+%include "../include/dai/dai_config.h"
%{
#include "../include/dai/alldai.h"
BOOST_CHECK( G.existsDirectedPath( 3, 3 ) );
std::set<size_t> s;
+ std::set<size_t> ss;
G.addNode();
G.addEdge( 3, 4 );
G.addNode();
G.addEdge( 1, 4 );
G.addEdge( 1, 5 );
- BOOST_CHECK( G.descendants( 4 ) == s );
- BOOST_CHECK( G.descendants( 5 ) == s );
+ BOOST_CHECK( G.descendants( 4, false ) == s ); ss = s; ss.insert( 4 ); BOOST_CHECK( G.descendants( 4, true ) == ss );
+ BOOST_CHECK( G.descendants( 5, false ) == s ); ss = s; ss.insert( 5 ); BOOST_CHECK( G.descendants( 5, true ) == ss );
s.insert( 4 );
- BOOST_CHECK( G.descendants( 3 ) == s );
+ BOOST_CHECK( G.descendants( 3, false ) == s ); ss = s; ss.insert( 3 ); BOOST_CHECK( G.descendants( 3, true ) == ss );
s.insert( 5 );
- BOOST_CHECK( G.descendants( 1 ) == s );
+ BOOST_CHECK( G.descendants( 1, false ) == s ); ss = s; ss.insert( 1 ); BOOST_CHECK( G.descendants( 1, true ) == ss );
s.erase( 5 );
s.insert( 3 );
- BOOST_CHECK( G.descendants( 2 ) == s );
+ BOOST_CHECK( G.descendants( 2, false ) == s ); ss = s; ss.insert( 2 ); BOOST_CHECK( G.descendants( 2, true ) == ss );
s.insert( 1 );
s.insert( 5 );
- BOOST_CHECK( G.descendants( 0 ) == s );
+ BOOST_CHECK( G.descendants( 0, false ) == s ); ss = s; ss.insert( 0 ); BOOST_CHECK( G.descendants( 0, true ) == ss );
s.clear();
- BOOST_CHECK( G.ancestors( 0 ) == s );
- BOOST_CHECK( G.ancestors( 2 ) == s );
+ BOOST_CHECK( G.ancestors( 0, false ) == s ); ss = s; ss.insert( 0 ); BOOST_CHECK( G.ancestors( 0, true ) == ss );
+ BOOST_CHECK( G.ancestors( 2, false ) == s ); ss = s; ss.insert( 2 ); BOOST_CHECK( G.ancestors( 2, true ) == ss );
s.insert( 0 );
- BOOST_CHECK( G.ancestors( 1 ) == s );
+ BOOST_CHECK( G.ancestors( 1, false ) == s ); ss = s; ss.insert( 1 ); BOOST_CHECK( G.ancestors( 1, true ) == ss );
s.insert( 2 );
- BOOST_CHECK( G.ancestors( 3 ) == s );
+ BOOST_CHECK( G.ancestors( 3, false ) == s ); ss = s; ss.insert( 3 ); BOOST_CHECK( G.ancestors( 3, true ) == ss );
s.erase( 2 );
s.insert( 1 );
- BOOST_CHECK( G.ancestors( 5 ) == s );
+ BOOST_CHECK( G.ancestors( 5, false ) == s ); ss = s; ss.insert( 5 ); BOOST_CHECK( G.ancestors( 5, true ) == ss );
s.insert( 2 );
s.insert( 3 );
- BOOST_CHECK( G.ancestors( 4 ) == s );
+ BOOST_CHECK( G.ancestors( 4, false ) == s ); ss = s; ss.insert( 4 ); BOOST_CHECK( G.ancestors( 4, true ) == ss );
}