libDAI
|
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... | |
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:
|
inline |
Default constructor.
|
inline |
Constructor that allows setting the values of the member variables.
|
inline |
Cast to size_t
returns node
member.
size_t dai::Neighbor::iter |
Corresponds to the index of this Neighbor entry in the vector of neighbors.
size_t dai::Neighbor::node |
Contains the absolute index of the neighboring node.
size_t dai::Neighbor::dual |
Contains the "dual" index (i.e., the index of this node in the Neighbors vector of the neighboring node)