13 #ifndef __defined_libdai_dag_h
14 #define __defined_libdai_dag_h
44 std::vector<Neighbors>
_pa;
47 std::vector<Neighbors>
_ch;
52 DAG() : _pa(), _ch() {}
56 DAG(
size_t nr ) : _pa( nr ), _ch( nr ) {}
66 template<
typename EdgeInputIterator>
67 DAG(
size_t nr, EdgeInputIterator begin, EdgeInputIterator end,
bool check=
true ) : _pa(), _ch() {
74 const Neighbor&
pa(
size_t n,
size_t _p )
const {
132 template<
typename EdgeInputIterator>
133 void construct(
size_t nr, EdgeInputIterator begin, EdgeInputIterator end,
bool check=
true );
139 return _pa.size() - 1;
149 template <
typename NodeInputIterator>
150 size_t addNode( NodeInputIterator begin, NodeInputIterator end,
size_t sizeHint=0 ) {
152 newparents.reserve( sizeHint );
154 for( NodeInputIterator it = begin; it != end; ++it ) {
156 Neighbor newparent( iter, *it,
ch(*it).size() );
158 newparents.push_back( newparent );
159 ch( *it ).push_back( newchild );
161 _pa.push_back( newparents );
163 return _pa.size() - 1;
169 DAG&
addEdge(
size_t n1,
size_t n2,
bool check=
true );
192 for(
size_t i = 0; i < _pa.size(); i++ )
193 sum += _pa[i].size();
201 if(
ch(n1).size() <
pa(n2).size() ) {
202 for(
size_t _n2 = 0; _n2 <
ch(n1).size(); _n2++ )
203 if(
ch( n1, _n2 ) == n2 )
206 for(
size_t _n1 = 0; _n1 <
pa(n2).size(); _n1++ )
207 if(
pa( n2, _n1 ) == n1 )
218 for(
size_t _p = 0; _p <
pa(n).size(); _p++ )
219 if(
pa( n, _p ) == p )
221 DAI_THROW(OBJECT_NOT_FOUND);
230 for(
size_t _c = 0; _c <
ch(n).size(); _c++ )
231 if(
ch( n, _c ) == c )
233 DAI_THROW(OBJECT_NOT_FOUND);
244 std::set<size_t>
ancestors(
size_t n,
bool inclusive )
const;
247 std::set<size_t>
descendants(
size_t n,
bool inclusive )
const;
266 for(
size_t n1 = 0; n1 <
nrNodes(); n1++ ) {
267 if(
pa(n1).size() != x.
pa(n1).size() )
282 void printDot( std::ostream& os )
const;
293 std::stringstream ss;
301 template<
typename EdgeInputIterator>
302 void DAG::construct(
size_t nr, EdgeInputIterator begin, EdgeInputIterator end,
bool check ) {
308 for( EdgeInputIterator e = begin; e != end; e++ )
309 addEdge( e->first, e->second, check );
Represents the neighborhood structure of nodes in a directed cyclic graph.
Definition: dag.h:41
std::vector< Neighbor > Neighbors
Describes the set of neighbors of some node in a graph.
Definition: graph.h:92
bool isConnected() const
Returns true if the DAG is connected.
Definition: dag.cpp:199
bool hasEdge(size_t n1, size_t n2) const
Returns true if the DAG contains an edge from node n1 and n2.
Definition: dag.h:200
void eraseEdge(size_t n1, size_t n2)
Removes edge from node n1 to node n2.
Definition: dag.cpp:83
const Neighbors & pa(size_t n) const
Returns constant reference to all parents of node n.
Definition: dag.h:88
SmallSet< size_t > chSet(size_t n) const
Returns children of node n as a SmallSet.
Definition: dag.cpp:124
std::set< size_t > ancestors(size_t n, bool inclusive) const
Returns the set of ancestors of node n, i.e., all nodes a such that there exists a directed path from...
Definition: dag.cpp:133
Neighbors & pa(size_t n)
Returns reference to all parents of node n.
Definition: dag.h:93
size_t addNode(NodeInputIterator begin, NodeInputIterator end, size_t sizeHint=0)
Adds a node with parents specified by a range of nodes.
Definition: dag.h:150
void construct(size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check=true)
(Re)constructs DAG from a range of edges.
Definition: dag.h:302
const Neighbors & ch(size_t n) const
Returns constant reference to all children of node n.
Definition: dag.h:112
std::vector< Neighbors > _pa
Contains for each node a vector of its parent nodes.
Definition: dag.h:44
DAG(size_t nr)
Constructs DAG with nr nodes and no edges.
Definition: dag.h:56
size_t findCh(size_t n, size_t c)
Returns the index of a given node c amongst the children of n.
Definition: dag.h:229
void checkConsistency() const
Asserts internal consistency.
Definition: dag.cpp:254
size_t nrEdges() const
Calculates the number of edges, time complexity: O(nrNodes())
Definition: dag.h:190
SmallSet< size_t > paSet(size_t n) const
Returns parents of node n as a SmallSet.
Definition: dag.cpp:116
DAG & addEdge(size_t n1, size_t n2, bool check=true)
Adds an edge from node n1 and node n2.
Definition: dag.cpp:18
Neighbor & pa(size_t n, size_t _p)
Returns reference to the _p 'th parent of node n.
Definition: dag.h:81
bool operator==(const DAG &x) const
Comparison operator which returns true if two DAGs are identical.
Definition: dag.h:263
std::string toString() const
Formats a DAG as a string.
Definition: dag.h:292
#define bforeach
An alias to the BOOST_FOREACH macro from the boost::bforeach library.
Definition: util.h:48
size_t findPa(size_t n, size_t p)
Returns the index of a given node p amongst the parents of n.
Definition: dag.h:217
std::vector< Neighbors > _ch
Contains for each node a vector of its children nodes.
Definition: dag.h:47
bool existsDirectedPath(size_t n1, size_t n2) const
Returns whether there exists a directed path from node n1 to node n2 (which may consist of zero edges...
Definition: dag.cpp:180
Defines the Exception class and macros for throwing exceptions and doing assertions.
Neighbors & ch(size_t n)
Returns reference to all children of node n.
Definition: dag.h:117
Defines general utility functions and adds an abstraction layer for platform-dependent functionality...
void eraseNode(size_t n)
Removes node n and all ingoing and outgoing edges; indices of other nodes are changed accordingly...
Definition: dag.cpp:43
Defines the GraphAL class, which represents an undirected graph as an adjacency list.
Defines the SmallSet<> class, which represents a set (optimized for a small number of elements)...
Describes the neighbor relationship of two nodes in a graph.
Definition: graph.h:73
DAG()
Default constructor (creates an empty DAG).
Definition: dag.h:53
size_t addNode()
Adds a node without parents and children and returns the index of the added node. ...
Definition: dag.h:136
friend std::ostream & operator<<(std::ostream &os, const DAG &g)
Writes a DAG to an output stream.
Definition: dag.h:286
Namespace for libDAI.
Definition: alldai.cpp:16
void printDot(std::ostream &os) const
Writes a DAG to an output stream in GraphViz .dot syntax.
Definition: dag.cpp:242
#define DAI_ASSERT(condition)
Assertion mechanism, similar to the standard assert() macro. It is always active, even if NDEBUG is d...
Definition: exceptions.h:60
#define DAI_DEBASSERT(x)
Assertion mechanism similar to DAI_ASSERT which is only active if DAI_DEBUG is defined.
Definition: exceptions.h:65
Neighbor & ch(size_t n, size_t _c)
Returns reference to the _c 'th child of node n.
Definition: dag.h:105
const Neighbor & ch(size_t n, size_t _c) const
Returns constant reference to the _c 'th child of node n.
Definition: dag.h:99
size_t nrNodes() const
Returns number of nodes.
Definition: dag.h:184
const Neighbor & pa(size_t n, size_t _p) const
Returns constant reference to the _p 'th parent of node n.
Definition: dag.h:75
std::set< size_t > descendants(size_t n, bool inclusive) const
Returns the set of descendants of node n, i.e., all nodes d such that there exists a directed path fr...
Definition: dag.cpp:157
DAG(size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check=true)
Constructs DAG from a range of edges.
Definition: dag.h:67