|
libDAI
|
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). | |
| DAG (size_t nr) | |
| Constructs DAG with nr nodes and no edges. | |
| template<typename EdgeInputIterator > | |
| DAG (size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check=true) | |
| Constructs DAG from a range of edges. | |
Accessors and mutators | |
| const Neighbor & | pa (size_t n, size_t _p) const |
| Returns constant reference to the _p 'th parent of node n. | |
| Neighbor & | pa (size_t n, size_t _p) |
| Returns reference to the _p 'th parent of node n. | |
| const Neighbors & | pa (size_t n) const |
| Returns constant reference to all parents of node n. | |
| Neighbors & | pa (size_t n) |
| Returns reference to all parents of node n. | |
| const Neighbor & | ch (size_t n, size_t _c) const |
| Returns constant reference to the _c 'th child of node n. | |
| Neighbor & | ch (size_t n, size_t _c) |
| Returns reference to the _c 'th child of node n. | |
| const Neighbors & | ch (size_t n) const |
| Returns constant reference to all children of node n. | |
| Neighbors & | ch (size_t n) |
| Returns reference to all children of node n. | |
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. | |
| size_t | addNode () |
| Adds a node without parents and children and returns the index of the added node. | |
| 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. | |
| DAG & | addEdge (size_t n1, size_t n2, bool check=true) |
| Adds an edge from node n1 and node n2. | |
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. | |
| void | eraseEdge (size_t n1, size_t n2) |
| Removes edge from node n1 to node n2. | |
Queries | |
| size_t | nrNodes () const |
| Returns number of nodes. | |
| size_t | nrEdges () const |
| Calculates the number of edges, time complexity: O(nrNodes()) | |
| bool | hasEdge (size_t n1, size_t n2) const |
| Returns true if the DAG contains an edge from node n1 and n2. | |
| size_t | findPa (size_t n, size_t p) |
| Returns the index of a given node p amongst the parents of n. | |
| size_t | findCh (size_t n, size_t c) |
| Returns the index of a given node c amongst the children of n. | |
| SmallSet< size_t > | paSet (size_t n) const |
| Returns parents of node n as a SmallSet<size_t>. | |
| SmallSet< size_t > | chSet (size_t n) const |
| Returns children of node n as a SmallSet<size_t>. | |
| std::set< size_t > | ancestors (size_t n) 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 (excluding n itself) | |
| std::set< size_t > | descendants (size_t n) 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) | |
| 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) | |
| bool | isConnected () const |
| Returns true if the DAG is connected. | |
| void | checkConsistency () const |
| Asserts internal consistency. | |
| bool | operator== (const DAG &x) const |
| Comparison operator which returns true if two DAGs are identical. | |
Private Attributes | |
| std::vector< Neighbors > | _pa |
| Contains for each node a vector of its parent nodes. | |
| std::vector< Neighbors > | _ch |
| Contains for each node a vector of its children nodes. | |
Input and output | |
| void | printDot (std::ostream &os) const |
| Writes this DAG to an output stream in GraphViz .dot syntax. | |
| std::ostream & | operator<< (std::ostream &os, const DAG &g) |
| Writes this DAG to an output stream. | |
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.
| 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.
| dai::DAG::DAG | ( | size_t | nr, |
| EdgeInputIterator | begin, | ||
| EdgeInputIterator | end, | ||
| bool | check = true |
||
| ) | [inline] |
Constructs DAG from a range of edges.
| EdgeInputIterator | Iterator that iterates over instances of Edge. |
| 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 |
| 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.
| void dai::DAG::construct | ( | size_t | nr, |
| EdgeInputIterator | begin, | ||
| EdgeInputIterator | end, | ||
| bool | check = true |
||
| ) |
(Re)constructs DAG from a range of edges.
| EdgeInputIterator | Iterator that iterates over instances of Edge. |
| 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.
| 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.
| NodeInputIterator | Iterator that iterates over instances of size_t. |
| 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. |
| 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.
| 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.
| 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.
| 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 | ) | 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 (excluding n itself)
Returns the set of ancestors of node n, i.e., all nodes m such that there exists a directed path from m to n (excluding n itself)
| std::set< size_t > dai::DAG::descendants | ( | size_t | n | ) | 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)
Returns the set of descendants of node n, i.e., all nodes m such that there exists a directed path from n to m (excluding n itself)
| 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.
*this has an edge from node n1 to n2). | void dai::DAG::printDot | ( | std::ostream & | os | ) | const |
Writes this DAG to an output stream in GraphViz .dot syntax.
| std::ostream& operator<< | ( | std::ostream & | os, |
| const DAG & | g | ||
| ) | [friend] |
Writes this DAG to an output stream.
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.
1.7.4