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

#include <dai/graph.h>

Public Member Functions
	Neighbor ()
	Default constructor. More...

	Neighbor (size_t iter, size_t node, size_t dual)
	Constructor that allows setting the values of the member variables. More...

	operator size_t () const
	Cast to `size_t` returns `node` member. More...

Public Attributes
size_t	iter
	Corresponds to the index of this Neighbor entry in the vector of neighbors. More...

size_t	node
	Contains the absolute index of the neighboring node. More...

size_t	dual
	Contains the "dual" index (i.e., the index of this node in the Neighbors vector of the neighboring node) More...

Detailed Description

Describes the neighbor relationship of two nodes in a graph.

Most graphs that libDAI deals with are sparse. Therefore, a fast and memory-efficient way of representing the structure of a sparse graph is needed. A frequently used operation that also needs to be fast is switching 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.

Most sparse graphs in libDAI are represented by storing for each node in the graph the set of its neighbors. In practice, this set of neighbors is stored using the Neighbors type, which is simply a std::vector<Neighbor>. The Neighbor struct contains the label of the neighboring node (the node member) and additional information which allows to access a node as a neighbor of its neighbor (the dual member). For convenience, each Neighbor structure also stores its index in the Neighbors vector that it is part of (the iter 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 the context.

Let us denote the _j 'th neighbor of node i by nb(i,_j), which is of the Neighbor type. Here, i is the "absolute" index of node i, but _j is understood as a "relative" index, giving node j 's entry in the Neighbors nb(i) of node i. The absolute index of _j, which would be denoted j, can be recovered from the node member, nb(i,_j).node. The iter member nb(i,_j).iter gives the relative index _j, and the dual member nb(i,_j).dual gives the "dual" relative index, i.e., the index of i in j 's neighbor list.

Iteration over edges can be easily accomplished:

for( size_t i = 0; i < nrNodes(); ++i ) {
    size_t _j = 0;
    bforeach( const Neighbor &j, nb(i) ) {
        assert( j == nb(i,j.iter) );
        assert( nb(j.node,j.dual).node == i );
        assert( _j = j.iter );
        _j++;
    }
}