dai::BipartiteGraph Class Reference

Represents the neighborhood structure of nodes in an undirected, bipartite graph. More...

#include <dai/bipgraph.h>

List of all members.

Public Types

typedef std::vector< NeighborNeighbors
 Describes the neighbors of some node.
typedef std::pair< size_t, size_t > Edge
 Represents an edge: an Edge(n1,n2) corresponds to the edge between node n1 of type 1 and node n2 of type 2.

Public Member Functions

Constructors and destructors
 BipartiteGraph ()
 Default constructor (creates an empty bipartite graph).
template<typename EdgeInputIterator>
 BipartiteGraph (size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end)
 Constructs BipartiteGraph from a range of edges.
Accessors and mutators
const Neighbornb1 (size_t i1, size_t _i2) const
 Returns constant reference to the _i2 'th neighbor of node i1 of type 1.
Neighbornb1 (size_t i1, size_t _i2)
 Returns reference to the _i2 'th neighbor of node i1 of type 1.
const Neighbornb2 (size_t i2, size_t _i1) const
 Returns constant reference to the _i1 'th neighbor of node i2 of type 2.
Neighbornb2 (size_t i2, size_t _i1)
 Returns reference to the _i1 'th neighbor of node i2 of type 2.
const Neighborsnb1 (size_t i1) const
 Returns constant reference to all neighbors of node i1 of type 1.
Neighborsnb1 (size_t i1)
 Returns reference to all neighbors of node i1 of type 1.
const Neighborsnb2 (size_t i2) const
 Returns constant reference to all neighbors of node i2 of type 2.
Neighborsnb2 (size_t i2)
 Returns reference to all neighbors of node i2 of type 2.
Adding nodes and edges
template<typename EdgeInputIterator>
void construct (size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end)
 (Re)constructs BipartiteGraph from a range of edges.
size_t addNode1 ()
 Adds a node of type 1 without neighbors and returns the index of the added node.
size_t addNode2 ()
 Adds a node of type 2 without neighbors and returns the index of the added node.
size_t add1 ()
 Adds a node of type 1 without neighbors and returns the index of the added node.
size_t add2 ()
 Adds a node of type 2 without neighbors and returns the index of the added node.
template<typename NodeInputIterator>
size_t addNode1 (NodeInputIterator begin, NodeInputIterator end, size_t sizeHint=0)
 Adds a node of type 1, with neighbors specified by a range of nodes of type 2.
template<typename NodeInputIterator>
size_t addNode2 (NodeInputIterator begin, NodeInputIterator end, size_t sizeHint=0)
 Adds a node of type 2, with neighbors specified by a range of nodes of type 1.
template<typename NodeInputIterator>
size_t add1 (NodeInputIterator begin, NodeInputIterator end, size_t sizeHint=0)
 Adds a node of type 1, with neighbors specified by a range of nodes of type 2.
template<typename NodeInputIterator>
size_t add2 (NodeInputIterator begin, NodeInputIterator end, size_t sizeHint=0)
 Adds a node of type 2, with neighbors specified by a range of nodes of type 1.
void addEdge (size_t n1, size_t n2, bool check=true)
 Adds an edge between node n1 of type 1 and node n2 of type 2.
Erasing nodes and edges
void eraseNode1 (size_t n1)
 Removes node n1 of type 1 and all incident edges; indices of other nodes are changed accordingly.
void eraseNode2 (size_t n2)
 Removes node n2 of type 2 and all incident edges; indices of other nodes are changed accordingly.
void erase1 (size_t n1)
 Removes node n1 of type 1 and all incident edges; indices of other nodes are changed accordingly.
void erase2 (size_t n2)
 Removes node n2 of type 2 and all incident edges; indices of other nodes are changed accordingly.
void eraseEdge (size_t n1, size_t n2)
 Removes edge between node n1 of type 1 and node n2 of type 2.
Queries
size_t nrNodes1 () const
 Returns number of nodes of type 1.
size_t nrNodes2 () const
 Returns number of nodes of type 2.
size_t nr1 () const
 Returns number of nodes of type 1.
size_t nr2 () const
 Returns number of nodes of type 2.
size_t nrEdges () const
 Calculates the number of edges, time complexity: O(nrNodes1()).
std::vector< size_t > delta1 (size_t n1, bool include=false) const
 Calculates second-order neighbors (i.e., neighbors of neighbors) of node n1 of type 1.
std::vector< size_t > delta2 (size_t n2, bool include=false) const
 Calculates second-order neighbors (i.e., neighbors of neighbors) of node n2 of type 2.
bool isConnected () const
 Returns true if the graph is connected.
bool isTree () const
 Returns true if the graph is a tree, i.e., if it is singly connected and connected.
void checkConsistency () const
 Checks internal consistency.
Input and output
void printDot (std::ostream &os) const
 Writes this BipartiteGraph to an output stream in GraphViz .dot syntax.

Private Attributes

std::vector< Neighbors_nb1
 Contains for each node of type 1 a vector of its neighbors.
std::vector< Neighbors_nb2
 Contains for each node of type 2 a vector of its neighbors.

Classes

struct  levelType
 Used internally by isTree(). More...
struct  Neighbor
 Describes the neighbor relationship of two nodes in a BipartiteGraph. More...


Detailed Description

Represents the neighborhood structure of nodes in an undirected, bipartite graph.

A bipartite graph has two types of nodes: type 1 and type 2. Edges can occur only between nodes of different type. Nodes are indexed by an unsigned integer. If there are nrNodes1() nodes of type 1 and nrNodes2() nodes of type 2, the nodes of type 1 are numbered 0,1,2,...,nrNodes1()-1 and the nodes of type 2 are numbered 0,1,2,...,nrNodes2()-1. An edge between node n1 of type 1 and node n2 of type 2 is represented by a BipartiteGraph::Edge(n1,n2).

A BipartiteGraph is implemented as a sparse adjacency list, i.e., it stores for each node a list of its neighboring nodes. More precisely: it stores for each node of type 1 a vector of Neighbor structures (accessible by the nb1() method) describing the neighboring nodes of type 2; similarly, for each node of type 2 it stores a vector of Neighbor structures (accessibly by the nb2() method) describing the neighboring nodes of type 1. Thus, each node has an associated variable of type BipartiteGraph::Neighbors, which is a vector of Neighbor structures, describing its neighboring nodes of the other type.

Idea:
Cache second-order neighborhoods in BipartiteGraph.
Examples:

example_bipgraph.cpp.


Member Typedef Documentation

Describes the neighbors of some node.

typedef std::pair<size_t,size_t> dai::BipartiteGraph::Edge

Represents an edge: an Edge(n1,n2) corresponds to the edge between node n1 of type 1 and node n2 of type 2.


Constructor & Destructor Documentation

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

Default constructor (creates an empty bipartite graph).

template<typename EdgeInputIterator>
dai::BipartiteGraph::BipartiteGraph ( size_t  nrNodes1,
size_t  nrNodes2,
EdgeInputIterator  begin,
EdgeInputIterator  end 
) [inline]

Constructs BipartiteGraph from a range of edges.

Template Parameters:
EdgeInputIterator Iterator that iterates over instances of BipartiteGraph::Edge.
Parameters:
nrNodes1 The number of nodes of type 1.
nrNodes2 The number of nodes of type 2.
begin Points to the first edge.
end Points just beyond the last edge.


Member Function Documentation

const Neighbor& dai::BipartiteGraph::nb1 ( size_t  i1,
size_t  _i2 
) const [inline]

Returns constant reference to the _i2 'th neighbor of node i1 of type 1.

Neighbor& dai::BipartiteGraph::nb1 ( size_t  i1,
size_t  _i2 
) [inline]

Returns reference to the _i2 'th neighbor of node i1 of type 1.

const Neighbor& dai::BipartiteGraph::nb2 ( size_t  i2,
size_t  _i1 
) const [inline]

Returns constant reference to the _i1 'th neighbor of node i2 of type 2.

Neighbor& dai::BipartiteGraph::nb2 ( size_t  i2,
size_t  _i1 
) [inline]

Returns reference to the _i1 'th neighbor of node i2 of type 2.

const Neighbors& dai::BipartiteGraph::nb1 ( size_t  i1  )  const [inline]

Returns constant reference to all neighbors of node i1 of type 1.

Neighbors& dai::BipartiteGraph::nb1 ( size_t  i1  )  [inline]

Returns reference to all neighbors of node i1 of type 1.

const Neighbors& dai::BipartiteGraph::nb2 ( size_t  i2  )  const [inline]

Returns constant reference to all neighbors of node i2 of type 2.

Neighbors& dai::BipartiteGraph::nb2 ( size_t  i2  )  [inline]

Returns reference to all neighbors of node i2 of type 2.

template<typename EdgeInputIterator>
void dai::BipartiteGraph::construct ( size_t  nrNodes1,
size_t  nrNodes2,
EdgeInputIterator  begin,
EdgeInputIterator  end 
) [inline]

(Re)constructs BipartiteGraph from a range of edges.

Template Parameters:
EdgeInputIterator Iterator that iterates over instances of BipartiteGraph::Edge.
Parameters:
nrNodes1 The number of nodes of type 1.
nrNodes2 The number of nodes of type 2.
begin Points to the first edge.
end Points just beyond the last edge.

size_t dai::BipartiteGraph::addNode1 (  )  [inline]

Adds a node of type 1 without neighbors and returns the index of the added node.

size_t dai::BipartiteGraph::addNode2 (  )  [inline]

Adds a node of type 2 without neighbors and returns the index of the added node.

size_t dai::BipartiteGraph::add1 (  )  [inline]

Adds a node of type 1 without neighbors and returns the index of the added node.

Deprecated:
Please use dai::BipartiteGraph::addNode1() instead.

size_t dai::BipartiteGraph::add2 (  )  [inline]

Adds a node of type 2 without neighbors and returns the index of the added node.

Deprecated:
Please use dai::BipartiteGraph::addNode2() instead.

template<typename NodeInputIterator>
size_t dai::BipartiteGraph::addNode1 ( NodeInputIterator  begin,
NodeInputIterator  end,
size_t  sizeHint = 0 
) [inline]

Adds a node of type 1, with neighbors specified by a range of nodes of type 2.

Template Parameters:
NodeInputIterator Iterator that iterates over instances of size_t.
Parameters:
begin Points to the first index of the nodes of type 2 that should become neighbors of the added node.
end Points just beyond the last index of the nodes of type 2 that should become neighbors of the added node.
sizeHint For improved efficiency, the size of the range may be specified by sizeHint.
Returns:
Index of the added node.

template<typename NodeInputIterator>
size_t dai::BipartiteGraph::addNode2 ( NodeInputIterator  begin,
NodeInputIterator  end,
size_t  sizeHint = 0 
) [inline]

Adds a node of type 2, with neighbors specified by a range of nodes of type 1.

Template Parameters:
NodeInputIterator Iterator that iterates over instances of size_t.
Parameters:
begin Points to the first index of the nodes of type 1 that should become neighbors of the added node.
end Points just beyond the last index of the nodes of type 1 that should become neighbors of the added node.
sizeHint For improved efficiency, the size of the range may be specified by sizeHint.
Returns:
Index of the added node.

template<typename NodeInputIterator>
size_t dai::BipartiteGraph::add1 ( NodeInputIterator  begin,
NodeInputIterator  end,
size_t  sizeHint = 0 
) [inline]

Adds a node of type 1, with neighbors specified by a range of nodes of type 2.

Deprecated:
Please use dai::BipartiteGraph::addNode1( NodeInputIterator, NodeInputIterator, size_t) instead.

template<typename NodeInputIterator>
size_t dai::BipartiteGraph::add2 ( NodeInputIterator  begin,
NodeInputIterator  end,
size_t  sizeHint = 0 
) [inline]

Adds a node of type 2, with neighbors specified by a range of nodes of type 1.

Deprecated:
Please use dai::BipartiteGraph::addNode2( NodeInputIterator, NodeInputIterator, size_t) instead.

void dai::BipartiteGraph::addEdge ( size_t  n1,
size_t  n2,
bool  check = true 
)

Adds an edge between node n1 of type 1 and node n2 of type 2.

If check == true, only adds the edge if it does not exist already.

void dai::BipartiteGraph::eraseNode1 ( size_t  n1  ) 

Removes node n1 of type 1 and all incident edges; indices of other nodes are changed accordingly.

void dai::BipartiteGraph::eraseNode2 ( size_t  n2  ) 

Removes node n2 of type 2 and all incident edges; indices of other nodes are changed accordingly.

void dai::BipartiteGraph::erase1 ( size_t  n1  )  [inline]

Removes node n1 of type 1 and all incident edges; indices of other nodes are changed accordingly.

Deprecated:
Please use dai::BipartiteGraph::eraseNode1(size_t) instead.

void dai::BipartiteGraph::erase2 ( size_t  n2  )  [inline]

Removes node n2 of type 2 and all incident edges; indices of other nodes are changed accordingly.

Deprecated:
Please use dai::BipartiteGraph::eraseNode2(size_t) instead.

void dai::BipartiteGraph::eraseEdge ( size_t  n1,
size_t  n2 
)

Removes edge between node n1 of type 1 and node n2 of type 2.

size_t dai::BipartiteGraph::nrNodes1 (  )  const [inline]

Returns number of nodes of type 1.

size_t dai::BipartiteGraph::nrNodes2 (  )  const [inline]

Returns number of nodes of type 2.

size_t dai::BipartiteGraph::nr1 (  )  const [inline]

Returns number of nodes of type 1.

Deprecated:
Please use dai::BipartiteGraph::nrNodes1() instead.

size_t dai::BipartiteGraph::nr2 (  )  const [inline]

Returns number of nodes of type 2.

Deprecated:
Please use dai::BipartiteGraph::nrNodes2() instead.

size_t dai::BipartiteGraph::nrEdges (  )  const [inline]

Calculates the number of edges, time complexity: O(nrNodes1()).

std::vector< size_t > dai::BipartiteGraph::delta1 ( size_t  n1,
bool  include = false 
) const

Calculates second-order neighbors (i.e., neighbors of neighbors) of node n1 of type 1.

If include == true, includes n1 itself, otherwise excludes n1.

std::vector< size_t > dai::BipartiteGraph::delta2 ( size_t  n2,
bool  include = false 
) const

Calculates second-order neighbors (i.e., neighbors of neighbors) of node n2 of type 2.

If include == true, includes n2 itself, otherwise excludes n2.

bool dai::BipartiteGraph::isConnected (  )  const

Returns true if the graph is connected.

bool dai::BipartiteGraph::isTree (  )  const

Returns true if the graph is a tree, i.e., if it is singly connected and connected.

void dai::BipartiteGraph::checkConsistency (  )  const

Checks internal consistency.

void dai::BipartiteGraph::printDot ( std::ostream &  os  )  const

Writes this BipartiteGraph to an output stream in GraphViz .dot syntax.


Member Data Documentation

std::vector<Neighbors> dai::BipartiteGraph::_nb1 [private]

Contains for each node of type 1 a vector of its neighbors.

std::vector<Neighbors> dai::BipartiteGraph::_nb2 [private]

Contains for each node of type 2 a vector of its neighbors.


The documentation for this class was generated from the following files:

Generated on Thu Feb 11 12:26:02 2010 for libDAI by  doxygen 1.5.5