dai::DAG::Neighbor Struct Reference

Describes the parent/child relationship of two nodes in a DAG. More...

#include <dai/dag.h>

List of all members.

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.

Detailed Description

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 ) );

Constructor & Destructor Documentation

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.


Member Function Documentation

dai::DAG::Neighbor::operator size_t (  )  const [inline]

Cast to size_t returns node member.


Member Data Documentation

Corresponds to the index of this Neighbor entry in the vector of neighbors.

Contains the number of the neighboring node.

Contains the "dual" iter.


The documentation for this struct was generated from the following file:
Generated on Sun May 9 16:51:33 2010 for libDAI by  doxygen 1.6.3