dai::BipartiteGraph::Neighbor Struct Reference

Describes the neighbor relationship of two nodes in a BipartiteGraph. More...

#include <dai/bipgraph.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 neighbor relationship of two nodes in a BipartiteGraph.

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 a list of neighbors, 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).

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:

  void BP::calcNewMessage( size_t i, size_t _I )

Here, i is the "absolute" index of node i, but _I is understood as a "relative" index, giving node I 's entry in nb1(i). The corresponding Neighbor structure can be accessed as nb1(i,_I) or nb1(i)[_I]. The absolute index of _I, which would be called I, can be recovered from the node member: nb1(i,_I).node. The iter member gives the relative index _I, and the dual member gives the "dual" relative index, i.e., the index of i in I 's neighbor list.

  Neighbor n = nb1(i,_I);
  n.node == I &&
  n.iter == _I &&
  nb2(n.node,n.dual).node == i

In a FactorGraph, the nodes of type 1 represent variables, and the nodes of type 2 represent factors. For convenience, nb1() is called FactorGraph::nbV(), and nb2() is called FactorGraph::nbF().

There is no easy way to transform a pair of absolute node indices i and I 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 < nrVars(); ++i )
      foreach( const Neighbor &I, nbV(i) )
          calcNewMessage( i, I.iter );
Examples:

example_bipgraph.cpp.


Constructor & Destructor Documentation

dai::BipartiteGraph::Neighbor::Neighbor (  )  [inline]

Default constructor.

dai::BipartiteGraph::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::BipartiteGraph::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.

Examples:
example_bipgraph.cpp.

Contains the number of the neighboring node.

Examples:
example_bipgraph.cpp.

Contains the "dual" iter.

Examples:
example_bipgraph.cpp.

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