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

#include <dai/bipgraph.h>

Classes
struct	levelType
	Used internally by isTree() More...

Public Member Functions
Constructors and destructors
	BipartiteGraph ()
	Default constructor (creates an empty bipartite graph) More...

	BipartiteGraph (size_t nr1, size_t nr2)
	Constructs BipartiteGraph with nr1 nodes of type 1, nr2 nodes of type 2 and no edges. More...

template<typename EdgeInputIterator >
	BipartiteGraph (size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end, bool check=true)
	Constructs BipartiteGraph from a range of edges. More...

Accessors and mutators
const Neighbor &	nb1 (size_t i1, size_t _i2) const
	Returns constant reference to the _i2 'th neighbor of node i1 of type 1. More...

Neighbor &	nb1 (size_t i1, size_t _i2)
	Returns reference to the _i2 'th neighbor of node i1 of type 1. More...

const Neighbor &	nb2 (size_t i2, size_t _i1) const
	Returns constant reference to the _i1 'th neighbor of node i2 of type 2. More...

Neighbor &	nb2 (size_t i2, size_t _i1)
	Returns reference to the _i1 'th neighbor of node i2 of type 2. More...

const Neighbors &	nb1 (size_t i1) const
	Returns constant reference to all neighbors of node i1 of type 1. More...

Neighbors &	nb1 (size_t i1)
	Returns reference to all neighbors of node i1 of type 1. More...

const Neighbors &	nb2 (size_t i2) const
	Returns constant reference to all neighbors of node i2 of type 2. More...

Neighbors &	nb2 (size_t i2)
	Returns reference to all neighbors of node i2 of type 2. More...

Adding nodes and edges
template<typename EdgeInputIterator >
void	construct (size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end, bool check=true)
	(Re)constructs BipartiteGraph from a range of edges. More...

size_t	addNode1 ()
	Adds a node of type 1 without neighbors and returns the index of the added node. More...

size_t	addNode2 ()
	Adds a node of type 2 without neighbors and returns the index of the added node. More...

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. More...

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. More...

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. More...

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. More...

void	eraseNode2 (size_t n2)
	Removes node n2 of type 2 and all incident edges; indices of other nodes are changed accordingly. More...

void	eraseEdge (size_t n1, size_t n2)
	Removes edge between node n1 of type 1 and node n2 of type 2. More...

Queries
size_t	nrNodes1 () const
	Returns number of nodes of type 1. More...

size_t	nrNodes2 () const
	Returns number of nodes of type 2. More...

size_t	nrEdges () const
	Calculates the number of edges, time complexity: O(nrNodes1()) More...

bool	hasEdge (size_t n1, size_t n2) const
	Returns true if the graph contains an edge between node n1 of type 1 and node n2 of type 2. More...

size_t	findNb1 (size_t n1, size_t n2)
	Returns the index of a given node n2 of type 2 amongst the neighbors of node n1 of type 1. More...

size_t	findNb2 (size_t n1, size_t n2)
	Returns the index of a given node n1 of type 1 amongst the neighbors of node n2 of type 2. More...

SmallSet< size_t >	nb1Set (size_t n1) const
	Returns neighbors of node n1 of type 1 as a SmallSet<size_t>. More...

SmallSet< size_t >	nb2Set (size_t n2) const
	Returns neighbors of node n2 of type 2 as a SmallSet<size_t>. More...

SmallSet< 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. More...

SmallSet< 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. More...

bool	isConnected () const
	Returns true if the graph is connected. More...

bool	isTree () const
	Returns true if the graph is a tree, i.e., if it is singly connected and connected. More...

bool	operator== (const BipartiteGraph &x) const
	Comparison operator which returns true if two graphs are identical. More...

void	checkConsistency () const
	Asserts internal consistency. More...

Private Attributes
std::vector< Neighbors >	_nb1
	Contains for each node of type 1 a vector of its neighbors. More...

std::vector< Neighbors >	_nb2
	Contains for each node of type 2 a vector of its neighbors. More...

Input and output
void	printDot (std::ostream &os) const
	Writes a BipartiteGraph to an output stream in GraphViz .dot syntax. More...

std::string	toString () const
	Formats a BipartiteGraph as a string. More...

std::ostream &	operator<< (std::ostream &os, const BipartiteGraph &g)
	Writes a BipartiteGraph to an output stream. 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 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.

Constructor & Destructor Documentation

dai::BipartiteGraph::BipartiteGraph ( )

inline

Default constructor (creates an empty bipartite graph)

dai::BipartiteGraph::BipartiteGraph	(	size_t	nr1,
		size_t	nr2
	)

inline

Constructs BipartiteGraph with nr1 nodes of type 1, nr2 nodes of type 2 and no edges.

template<typename EdgeInputIterator >

dai::BipartiteGraph::BipartiteGraph	(	size_t	nrNodes1,
		size_t	nrNodes2,
		EdgeInputIterator	begin,
		EdgeInputIterator	end,
		bool	check = `true`
	)

inline

Constructs BipartiteGraph from a range of edges.

Template Parameters

EdgeInputIterator Iterator that iterates over instances of 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.
check	Whether to only add an edge if it does not exist already.

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,
		bool	check = `true`
	)

(Re)constructs BipartiteGraph from a range of edges.

Template Parameters

EdgeInputIterator Iterator that iterates over instances of 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.
check	Whether to only add an edge if it does not exist already.

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.

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.

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

Examples:: example_bipgraph.cpp.

size_t dai::BipartiteGraph::nrNodes2 ( ) const

inline

Returns number of nodes of type 2.

size_t dai::BipartiteGraph::nrEdges ( ) const

inline

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

bool dai::BipartiteGraph::hasEdge	(	size_t	n1,
		size_t	n2
	)		const

inline

Returns true if the graph contains an edge between node n1 of type 1 and node n2 of type 2.

Note: The time complexity is linear in the number of neighbors of n1 or n2

size_t dai::BipartiteGraph::findNb1	(	size_t	n1,
		size_t	n2
	)

inline

Returns the index of a given node n2 of type 2 amongst the neighbors of node n1 of type 1.

Note: The time complexity is linear in the number of neighbors of n1

Exceptions

OBJECT_NOT_FOUND if n2 is not a neighbor of n1

size_t dai::BipartiteGraph::findNb2	(	size_t	n1,
		size_t	n2
	)

inline

Returns the index of a given node n1 of type 1 amongst the neighbors of node n2 of type 2.

Note: The time complexity is linear in the number of neighbors of n2

Exceptions

OBJECT_NOT_FOUND if n1 is not a neighbor of n2

SmallSet< size_t > dai::BipartiteGraph::nb1Set ( size_t n1 ) const

Returns neighbors of node n1 of type 1 as a SmallSet<size_t>.

SmallSet< size_t > dai::BipartiteGraph::nb2Set ( size_t n2 ) const

Returns neighbors of node n2 of type 2 as a SmallSet<size_t>.

SmallSet< 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.

Note: In libDAI versions 0.2.4 and earlier, this function used to return a std::vector<size_t>

SmallSet< 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.

Note: In libDAI versions 0.2.4 and earlier, this function used to return a std::vector<size_t>

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.

bool dai::BipartiteGraph::operator== ( const BipartiteGraph & x ) const

inline

Comparison operator which returns true if two graphs are identical.

Note: Two graphs are called identical if they have the same number of nodes of both types and the same edges (i.e., x has an edge between nodes n1 and n2 if and only if *this has an edge between nodes n1 and n2).

void dai::BipartiteGraph::checkConsistency ( ) const

Asserts internal consistency.

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

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

std::string dai::BipartiteGraph::toString ( ) const

inline

Formats a BipartiteGraph as a string.

Friends And Related Function Documentation

std::ostream& operator<<	(	std::ostream &	os,
		const BipartiteGraph &	g
	)

friend

Writes a BipartiteGraph to an output stream.

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:

include/dai/bipgraph.h
src/bipgraph.cpp

Classes

Public Member Functions

Private Attributes

Input and output

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation