/* This file is part of libDAI - http://www.libdai.org/
*
* libDAI is licensed under the terms of the GNU General Public License version
* 2, or (at your option) any later version. libDAI is distributed without any
* warranty. See the file COPYING for more details.
*
* Copyright (C) 2010 Joris Mooij [joris dot mooij at libdai dot org]
*/
/// \file
/// \brief Defines the DAG class, which represents a directed acyclic graph
#ifndef __defined_libdai_dag_h
#define __defined_libdai_dag_h
#include
#include
#include
#include
#include
#include
namespace dai {
/// Represents the neighborhood structure of nodes in a directed cyclic graph.
/** A directed cyclic graph has nodes connected by directed edges, such that there is no
* directed cycle of edges n1->n2->n3->...->n1. Nodes are indexed by an unsigned integer.
* If there are nrNodes() nodes, they are numbered 0,1,2,...,nrNodes()-1. An edge
* from node \a n1 to node \a n2 is represented by a DAG::Edge(\a n1,\a n2).
*
* DAG is implemented as a sparse adjacency list, i.e., it stores for each node a list of
* its parents and a list of its children. Both lists are implemented as a vector of Neighbor
* structures (accessible by the pa() and ch() methods). Thus, each node has two associated
* variables of type DAG::Neighbors, which are vectors of Neighbor structures, describing their
* parent and children nodes.
*/
class DAG {
public:
/// Describes the parent/child relationship of two nodes in a DAG.
/** Sometimes we want to do an action, such as sending a
* message, for all edges in a graph. However, most graphs
* will be sparse, so we need some way of storing a set of
* the neighbors of a node, which is both fast and
* memory-efficient. We also need to be able to go between
* viewing node \a a as a neighbor of node \a b, and node \a b
* as a neighbor of node \a a. The Neighbor struct solves
* both of these problems. Each node has two lists of neighbors
* (a list of parents and a list of children), stored as a
* std::vector<\link Neighbor \endlink>, and extra information
* is included in the Neighbor struct which allows us to access
* a node as a neighbor of its neighbor (the \c dual member),
* i.e., as a child of its parent or as a parent of its child.
*
* By convention, variable identifiers naming indices into a
* vector of neighbors are prefixed with an underscore ("_").
* The neighbor list which they point into is then understood
* from context. For example, `pa(i,_j)` gives the
* \a _j 'th parent of node \a i, and `ch(k,_l)`
* gives the \a _l 'th child of node \a k.
* Here, \a i and \a k are "absolute" indexes of nodes \a i and \a k,
* but \a _j and \a _k are understood as "relative" indexes
* within the list `pa(i)` of parents of \a i and the
* list of children `ch(k)` of \a k. The
* absolute index of \a _j, which would be called \a j, can be
* recovered from the \c node member: `j = pa(i,_j).node`.
* Similarly, the absolute index of \a _l, which would be called
* \a l, can be recovered from the \c node member:
* `l = ch(k,_l).node`.
* The \c iter member gives the relative index \a _j or \a _l,
* and the \c dual member gives the "dual" relative index, i.e.,
* the index of \a i in \a j 's children list or the index of
* \a k in \a l 's parent list.
*
* \code
* Neighbor p = pa(i,_j);
* p.node == j &&
* p.iter == _j &&
* ch(p.node,p.dual).node == i
*
* Neighbor c = ch(k,_l);
* c.node == l &&
* c.iter == _l &&
* pa(c.node,c.dual).node == k
* \endcode
*
* There is no cheap way to transform a pair of absolute node
* indices \a i and \a j into a Neighbor structure relative
* to one of the nodes. Such a feature has never yet been
* found to be necessary. Iteration over edges can always be
* accomplished using the Neighbor lists, and by writing
* functions that accept relative indices:
* \code
* for( size_t i = 0; i < nrNodes(); ++i )
* foreach( const Neighbor &j, ch(i) )
* assert( hasEdge( i, j ) );
* \endcode
*/
struct Neighbor {
/// Corresponds to the index of this Neighbor entry in the vector of neighbors
size_t iter;
/// Contains the number of the neighboring node
size_t node;
/// Contains the "dual" iter
size_t dual;
/// Default constructor
Neighbor() {}
/// Constructor that sets the Neighbor members according to the parameters
Neighbor( size_t iter, size_t node, size_t dual ) : iter(iter), node(node), dual(dual) {}
/// Cast to \c size_t returns \c node member
operator size_t () const { return node; }
};
/// Type for storing the parents/children of some node.
typedef std::vector Neighbors;
/// Represents a directed edge: an Edge(\a n1,\a n2) corresponds to the edge from node \a n1 to node \a n2.
typedef std::pair Edge;
private:
/// Contains for each node a vector of its parent nodes
std::vector _pa;
/// Contains for each node a vector of its children nodes
std::vector _ch;
public:
/// \name Constructors and destructors
//@{
/// Default constructor (creates an empty DAG).
DAG() : _pa(), _ch() {}
/// Constructs DAG with \a nr nodes and no edges.
DAG( size_t nr ) : _pa( nr ), _ch( nr ) {}
/// Constructs DAG from a range of edges.
/** \tparam EdgeInputIterator Iterator that iterates over instances of DAG::Edge.
* \param nr The number of nodes.
* \param begin Points to the first edge.
* \param end Points just beyond the last edge.
* \param check Whether to only add an edge if it does not exist already and
* if it does not introduce a cycle
*/
template
DAG( size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check=true ) : _pa(), _ch() {
construct( nr, begin, end, check );
}
//@}
/// \name Accessors and mutators
//@{
/// Returns constant reference to the \a _p 'th parent of node \a n
const Neighbor& pa( size_t n, size_t _p ) const {
DAI_DEBASSERT( n < _pa.size() );
DAI_DEBASSERT( _p < _pa[n].size() );
return _pa[n][_p];
}
/// Returns reference to the \a _p 'th parent of node \a n
Neighbor& pa( size_t n, size_t _p ) {
DAI_DEBASSERT( n < _pa.size() );
DAI_DEBASSERT( _p < _pa[n].size() );
return _pa[n][_p];
}
/// Returns constant reference to all parents of node \a n
const Neighbors& pa( size_t n ) const {
DAI_DEBASSERT( n < _pa.size() );
return _pa[n];
}
/// Returns reference to all parents of node \a n
Neighbors& pa( size_t n ) {
DAI_DEBASSERT( n < _pa.size() );
return _pa[n];
}
/// Returns constant reference to the \a _c 'th child of node \a n
const Neighbor& ch( size_t n, size_t _c ) const {
DAI_DEBASSERT( n < _ch.size() );
DAI_DEBASSERT( _c < _ch[n].size() );
return _ch[n][_c];
}
/// Returns reference to the \a _c 'th child of node \a n
Neighbor& ch( size_t n, size_t _c ) {
DAI_DEBASSERT( n < _ch.size() );
DAI_DEBASSERT( _c < _ch[n].size() );
return _ch[n][_c];
}
/// Returns constant reference to all children of node \a n
const Neighbors& ch( size_t n ) const {
DAI_DEBASSERT( n < _ch.size() );
return _ch[n];
}
/// Returns reference to all children of node \a n
Neighbors& ch( size_t n ) {
DAI_DEBASSERT( n < _ch.size() );
return _ch[n];
}
//@}
/// \name Adding nodes and edges
//@{
/// (Re)constructs DAG from a range of edges.
/** \tparam EdgeInputIterator Iterator that iterates over instances of DAG::Edge.
* \param nr The number of nodes.
* \param begin Points to the first edge.
* \param end Points just beyond the last edge.
* \param check Whether to only add an edge if it does not exist already and does not introduce a cycle.
*/
template
void construct( size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check=true );
/// Adds a node without parents and children and returns the index of the added node.
size_t addNode() {
_pa.push_back( Neighbors() );
_ch.push_back( Neighbors() );
return _pa.size() - 1;
}
/// Adds a node with parents specified by a range of nodes.
/** \tparam NodeInputIterator Iterator that iterates over instances of \c size_t.
* \param begin Points to the first index of the nodes that should become parents of the added node.
* \param end Points just beyond the last index of the nodes that should become parents of the added node.
* \param sizeHint For improved efficiency, the size of the range may be specified by \a sizeHint.
* \returns Index of the added node.
*/
template
size_t addNode( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint=0 ) {
Neighbors newparents;
newparents.reserve( sizeHint );
size_t iter = 0;
for( NodeInputIterator it = begin; it != end; ++it ) {
DAI_ASSERT( *it < nrNodes() );
Neighbor newparent( iter, *it, ch(*it).size() );
Neighbor newchild( ch(*it).size(), nrNodes(), iter++ );
newparents.push_back( newparent );
ch( *it ).push_back( newchild );
}
_pa.push_back( newparents );
_ch.push_back( Neighbors() );
return _pa.size() - 1;
}
/// Adds an edge from node \a n1 and node \a n2.
/** If \a check == \c true, only adds the edge if it does not exist already and it would not introduce a cycle.
*/
DAG& addEdge( size_t n1, size_t n2, bool check=true );
//@}
/// \name Erasing nodes and edges
//@{
/// Removes node \a n and all ingoing and outgoing edges; indices of other nodes are changed accordingly.
void eraseNode( size_t n );
/// Removes edge from node \a n1 to node \a n2.
void eraseEdge( size_t n1, size_t n2 );
//@}
/// \name Queries
//@{
/// Returns number of nodes
size_t nrNodes() const {
DAI_DEBASSERT( _pa.size() == _ch.size() );
return _pa.size();
}
/// Calculates the number of edges, time complexity: O(nrNodes())
size_t nrEdges() const {
size_t sum = 0;
for( size_t i = 0; i < _pa.size(); i++ )
sum += _pa[i].size();
return sum;
}
/// Returns true if the DAG contains an edge from node \a n1 and \a n2
/** \note The time complexity is linear in the number of children of \a n1 or the number of parents of \a n2, whichever is smaller
*/
bool hasEdge( size_t n1, size_t n2 ) const {
if( ch(n1).size() < pa(n2).size() ) {
for( size_t _n2 = 0; _n2 < ch(n1).size(); _n2++ )
if( ch( n1, _n2 ) == n2 )
return true;
} else {
for( size_t _n1 = 0; _n1 < pa(n2).size(); _n1++ )
if( pa( n2, _n1 ) == n1 )
return true;
}
return false;
}
/// Returns the index of a given node \a p amongst the parents of \a n
/** \note The time complexity is linear in the number of parents of \a n
* \throw OBJECT_NOT_FOUND if \a p is not a parent of \a n
*/
size_t findPa( size_t n, size_t p ) {
for( size_t _p = 0; _p < pa(n).size(); _p++ )
if( pa( n, _p ) == p )
return _p;
DAI_THROW(OBJECT_NOT_FOUND);
return pa(n).size();
}
/// Returns the index of a given node \a c amongst the children of \a n
/** \note The time complexity is linear in the number of children of \a n
* \throw OBJECT_NOT_FOUND if \a c is not a child \a n
*/
size_t findCh( size_t n, size_t c ) {
for( size_t _c = 0; _c < ch(n).size(); _c++ )
if( ch( n, _c ) == c )
return _c;
DAI_THROW(OBJECT_NOT_FOUND);
return ch(n).size();
}
/// Returns parents of node \a n as a SmallSet.
SmallSet paSet( size_t n ) const;
/// Returns children of node \a n as a SmallSet.
SmallSet 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 ancestors( 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)
std::set descendants( size_t n ) 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 true if the DAG is connected
bool isConnected() const;
/// Asserts internal consistency
void checkConsistency() const;
/// Comparison operator which returns true if two DAGs are identical
/** \note Two DAGs are called identical if they have the same number
* of nodes and the same edges (i.e., \a x has an edge from \a n1 to \a n2
* if and only if \c *this has an edge from node \a n1 to \a n2).
*/
bool operator==( const DAG& x ) const {
if( nrNodes() != x.nrNodes() )
return false;
for( size_t n1 = 0; n1 < nrNodes(); n1++ ) {
if( pa(n1).size() != x.pa(n1).size() )
return false;
foreach( const Neighbor &n2, pa(n1) )
if( !x.hasEdge( n2, n1 ) )
return false;
foreach( const Neighbor &n2, x.pa(n1) )
if( !hasEdge( n2, n1 ) )
return false;
}
return true;
}
//@}
/// \name Input and output
//@{
/// Writes this DAG to an output stream in GraphViz .dot syntax
void printDot( std::ostream& os ) const;
/// Writes this DAG to an output stream
friend std::ostream& operator<<( std::ostream& os, const DAG& g ) {
g.printDot( os );
return os;
}
//@}
};
template
void DAG::construct( size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check ) {
_pa.clear();
_pa.resize( nr );
_ch.clear();
_ch.resize( nr );
for( EdgeInputIterator e = begin; e != end; e++ )
addEdge( e->first, e->second, check );
}
} // end of namespace dai
#endif