Represents the neighborhood structure of nodes in a directed cyclic graph. More...

#include <dai/dag.h>

Public Member Functions
Constructors and destructors
	DAG ()
	Default constructor (creates an empty DAG). More...

	DAG (size_t nr)
	Constructs DAG with nr nodes and no edges. More...

template<typename EdgeInputIterator >
	DAG (size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check=true)
	Constructs DAG from a range of edges. More...

Accessors and mutators
const Neighbor &	pa (size_t n, size_t _p) const
	Returns constant reference to the _p 'th parent of node n. More...

Neighbor &	pa (size_t n, size_t _p)
	Returns reference to the _p 'th parent of node n. More...

const Neighbors &	pa (size_t n) const
	Returns constant reference to all parents of node n. More...

Neighbors &	pa (size_t n)
	Returns reference to all parents of node n. More...

const Neighbor &	ch (size_t n, size_t _c) const
	Returns constant reference to the _c 'th child of node n. More...

Neighbor &	ch (size_t n, size_t _c)
	Returns reference to the _c 'th child of node n. More...

const Neighbors &	ch (size_t n) const
	Returns constant reference to all children of node n. More...

Neighbors &	ch (size_t n)
	Returns reference to all children of node n. More...

Adding nodes and edges
template<typename EdgeInputIterator >
void	construct (size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check=true)
	(Re)constructs DAG from a range of edges. More...

size_t	addNode ()
	Adds a node without parents and children and returns the index of the added node. More...

template<typename NodeInputIterator >
size_t	addNode (NodeInputIterator begin, NodeInputIterator end, size_t sizeHint=0)
	Adds a node with parents specified by a range of nodes. More...

DAG &	addEdge (size_t n1, size_t n2, bool check=true)
	Adds an edge from node n1 and node n2. More...

Erasing nodes and edges
void	eraseNode (size_t n)
	Removes node n and all ingoing and outgoing edges; indices of other nodes are changed accordingly. More...

void	eraseEdge (size_t n1, size_t n2)
	Removes edge from node n1 to node n2. More...

Queries
size_t	nrNodes () const
	Returns number of nodes. More...

size_t	nrEdges () const
	Calculates the number of edges, time complexity: O(nrNodes()) More...

bool	hasEdge (size_t n1, size_t n2) const
	Returns true if the DAG contains an edge from node n1 and n2. More...

size_t	findPa (size_t n, size_t p)
	Returns the index of a given node p amongst the parents of n. More...

size_t	findCh (size_t n, size_t c)
	Returns the index of a given node c amongst the children of n. More...

SmallSet< size_t >	paSet (size_t n) const
	Returns parents of node n as a SmallSet<size_t>. More...

SmallSet< size_t >	chSet (size_t n) const
	Returns children of node n as a SmallSet<size_t>. More...

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 a to n (including n itself if inclusive == `true`) More...

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 from n to d (excluding n itself if inclusive == `true`) More...

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) More...

bool	isConnected () const
	Returns true if the DAG is connected. More...

void	checkConsistency () const
	Asserts internal consistency. More...

bool	operator== (const DAG &x) const
	Comparison operator which returns true if two DAGs are identical. More...

Private Attributes
std::vector< Neighbors >	_pa
	Contains for each node a vector of its parent nodes. More...

std::vector< Neighbors >	_ch
	Contains for each node a vector of its children nodes. More...

Input and output
void	printDot (std::ostream &os) const
	Writes a DAG to an output stream in GraphViz .dot syntax. More...

std::string	toString () const
	Formats a DAG as a string. More...

std::ostream &	operator<< (std::ostream &os, const DAG &g)
	Writes a DAG to an output stream. More...

Detailed Description

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 n1 to node n2 is represented by a Edge(n1,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.

Constructor & Destructor Documentation

dai::DAG::DAG ( )

inline

Default constructor (creates an empty DAG).

dai::DAG::DAG ( size_t nr )

inline

Constructs DAG with nr nodes and no edges.

template<typename EdgeInputIterator >

dai::DAG::DAG	(	size_t	nr,
		EdgeInputIterator	begin,
		EdgeInputIterator	end,
		bool	check = `true`
	)

inline

Constructs DAG from a range of edges.

Template Parameters

EdgeInputIterator Iterator that iterates over instances of Edge.

Parameters

nr	The number of nodes.
begin	Points to the first edge.
end	Points just beyond the last edge.
check	Whether to only add an edge if it does not exist already and if it does not introduce a cycle

Member Function Documentation

const Neighbor& dai::DAG::pa	(	size_t	n,
		size_t	_p
	)		const

inline

Returns constant reference to the _p 'th parent of node n.

Neighbor& dai::DAG::pa	(	size_t	n,
		size_t	_p
	)

inline

Returns reference to the _p 'th parent of node n.

const Neighbors& dai::DAG::pa ( size_t n ) const

inline

Returns constant reference to all parents of node n.

Neighbors& dai::DAG::pa ( size_t n )

inline

Returns reference to all parents of node n.

const Neighbor& dai::DAG::ch	(	size_t	n,
		size_t	_c
	)		const

inline

Returns constant reference to the _c 'th child of node n.

Neighbor& dai::DAG::ch	(	size_t	n,
		size_t	_c
	)

inline

Returns reference to the _c 'th child of node n.

const Neighbors& dai::DAG::ch ( size_t n ) const

inline

Returns constant reference to all children of node n.

Neighbors& dai::DAG::ch ( size_t n )

inline

Returns reference to all children of node n.

template<typename EdgeInputIterator >

void dai::DAG::construct	(	size_t	nr,
		EdgeInputIterator	begin,
		EdgeInputIterator	end,
		bool	check = `true`
	)

(Re)constructs DAG from a range of edges.

Template Parameters

EdgeInputIterator Iterator that iterates over instances of Edge.

Parameters

nr	The number of nodes.
begin	Points to the first edge.
end	Points just beyond the last edge.
check	Whether to only add an edge if it does not exist already and does not introduce a cycle.

size_t dai::DAG::addNode ( )

inline

Adds a node without parents and children and returns the index of the added node.

template<typename NodeInputIterator >

size_t dai::DAG::addNode	(	NodeInputIterator	begin,
		NodeInputIterator	end,
		size_t	sizeHint = `0`
	)

inline

Adds a node with parents specified by a range of nodes.

Template Parameters

NodeInputIterator Iterator that iterates over instances of size_t.

Parameters

begin	Points to the first index of the nodes that should become parents of the added node.
end	Points just beyond the last index of the nodes that should become parents of the added node.
sizeHint	For improved efficiency, the size of the range may be specified by sizeHint.

Returns: Index of the added node.

DAG & dai::DAG::addEdge	(	size_t	n1,
		size_t	n2,
		bool	check = `true`
	)

Adds an edge from node n1 and node n2.

If check == true, only adds the edge if it does not exist already and it would not introduce a cycle.

void dai::DAG::eraseNode ( size_t n )

Removes node n and all ingoing and outgoing edges; indices of other nodes are changed accordingly.

void dai::DAG::eraseEdge	(	size_t	n1,
		size_t	n2
	)

Removes edge from node n1 to node n2.

size_t dai::DAG::nrNodes ( ) const

inline

Returns number of nodes.

size_t dai::DAG::nrEdges ( ) const

inline

Calculates the number of edges, time complexity: O(nrNodes())

bool dai::DAG::hasEdge	(	size_t	n1,
		size_t	n2
	)		const

inline

Returns true if the DAG contains an edge from node n1 and n2.

Note: The time complexity is linear in the number of children of n1 or the number of parents of n2, whichever is smaller

size_t dai::DAG::findPa	(	size_t	n,
		size_t	p
	)

inline

Returns the index of a given node p amongst the parents of n.

Note: The time complexity is linear in the number of parents of n

Exceptions

OBJECT_NOT_FOUND if p is not a parent of n

size_t dai::DAG::findCh	(	size_t	n,
		size_t	c
	)

inline

Returns the index of a given node c amongst the children of n.

Note: The time complexity is linear in the number of children of n

Exceptions

OBJECT_NOT_FOUND if c is not a child n

SmallSet< size_t > dai::DAG::paSet ( size_t n ) const

Returns parents of node n as a SmallSet<size_t>.

SmallSet< size_t > dai::DAG::chSet ( size_t n ) const

Returns children of node n as a SmallSet<size_t>.

std::set< size_t > dai::DAG::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 a to n (including n itself if inclusive == true)

std::set< size_t > dai::DAG::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 from n to d (excluding n itself if inclusive == true)

bool dai::DAG::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)

bool dai::DAG::isConnected ( ) const

Returns true if the DAG is connected.

void dai::DAG::checkConsistency ( ) const

Asserts internal consistency.

bool dai::DAG::operator== ( const DAG & x ) const

inline

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., x has an edge from n1 to n2 if and only if *this has an edge from node n1 to n2).

void dai::DAG::printDot ( std::ostream & os ) const

Writes a DAG to an output stream in GraphViz .dot syntax.

std::string dai::DAG::toString ( ) const

inline

Formats a DAG as a string.

Friends And Related Function Documentation

std::ostream& operator<<	(	std::ostream &	os,
		const DAG &	g
	)

friend

Writes a DAG to an output stream.

Member Data Documentation

std::vector<Neighbors> dai::DAG::_pa

private

Contains for each node a vector of its parent nodes.

std::vector<Neighbors> dai::DAG::_ch

private

Contains for each node a vector of its children nodes.

The documentation for this class was generated from the following files:

include/dai/dag.h
src/dag.cpp

Public Member Functions

Private Attributes

Input and output

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation