Describes the parent/child relationship of two nodes in a DAG. More...
#include <dai/dag.h>
Public Member Functions | |
Neighbor () | |
Default constructor. | |
Neighbor (size_t iter, size_t node, size_t dual) | |
Constructor that sets the Neighbor members according to the parameters. | |
operator size_t () const | |
Cast to size_t returns node member. | |
Public Attributes | |
size_t | iter |
Corresponds to the index of this Neighbor entry in the vector of neighbors. | |
size_t | node |
Contains the number of the neighboring node. | |
size_t | dual |
Contains the "dual" iter. |
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 as a neighbor of node b, and node b as a neighbor of node 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<Neighbor>, and extra information is included in the Neighbor struct which allows us to access a node as a neighbor of its neighbor (the 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 _j 'th parent of node i, and ch(k,_l)
gives the _l 'th child of node k. Here, i and k are "absolute" indexes of nodes i and k, but _j and _k are understood as "relative" indexes within the list pa(i)
of parents of i and the list of children ch(k)
of k. The absolute index of _j, which would be called j, can be recovered from the node
member: j = pa(i,_j).node
. Similarly, the absolute index of _l, which would be called l, can be recovered from the node
member: l = ch(k,_l).node
. The iter
member gives the relative index _j or _l, and the dual
member gives the "dual" relative index, i.e., the index of i in j 's children list or the index of k in l 's parent list.
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
There is no cheap way to transform a pair of absolute node indices i and 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:
for( size_t i = 0; i < nrNodes(); ++i ) foreach( const Neighbor &j, ch(i) ) assert( hasEdge( i, j ) );
dai::DAG::Neighbor::Neighbor | ( | ) | [inline] |
Default constructor.
dai::DAG::Neighbor::Neighbor | ( | size_t | iter, | |
size_t | node, | |||
size_t | dual | |||
) | [inline] |
Constructor that sets the Neighbor members according to the parameters.
dai::DAG::Neighbor::operator size_t | ( | ) | const [inline] |
Cast to size_t
returns node
member.
size_t dai::DAG::Neighbor::iter |
Corresponds to the index of this Neighbor entry in the vector of neighbors.
size_t dai::DAG::Neighbor::node |
Contains the number of the neighboring node.
size_t dai::DAG::Neighbor::dual |
Contains the "dual" iter.