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

#include <dai/graph.h>

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

	GraphAL (size_t nr)
	Constructs GraphAL with nr nodes and no edges. More...

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

Accessors and mutators
const Neighbor &	nb (size_t n1, size_t _n2) const
	Returns constant reference to the _n2 'th neighbor of node n1. More...

Neighbor &	nb (size_t n1, size_t _n2)
	Returns reference to the _n2 'th neighbor of node n1. More...

const Neighbors &	nb (size_t n) const
	Returns constant reference to all neighbors of node n. More...

Neighbors &	nb (size_t n)
	Returns reference to all neighbors of node n. More...

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

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

template<typename NodeInputIterator >
size_t	addNode (NodeInputIterator begin, NodeInputIterator end, size_t sizeHint=0)
	Adds a node, with neighbors specified by a range of nodes. More...

GraphAL &	addEdge (size_t n1, size_t n2, bool check=true)
	Adds an edge between node n1 and node n2. More...

Erasing nodes and edges
void	eraseNode (size_t n)
	Removes node n 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 and node n2. More...

Queries
size_t	nrNodes () const
	Returns number of nodes. More...

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

bool	hasEdge (size_t n1, size_t n2) const
	Returns true if the graph contains an edge between nodes n1 and n2. More...

size_t	findNb (size_t n1, size_t n2)
	Returns the index of a given node n2 amongst the neighbors of n1. More...

SmallSet< size_t >	nbSet (size_t n) const
	Returns neighbors of node n as a SmallSet<size_t>. 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...

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

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

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

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

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

std::ostream &	operator<< (std::ostream &os, const GraphAL &g)
	Writes a GraphAL to an output stream. More...

Detailed Description

Represents the neighborhood structure of nodes in an undirected graph.

A graph has nodes connected by edges. Nodes are indexed by an unsigned integer. If there are nrNodes() nodes, they are numbered 0,1,2,...,nrNodes()-1. An edge between node n1 and node n2 is represented by a Edge(n1,n2).

GraphAL is implemented as a sparse adjacency list, i.e., it stores for each node a list of its neighboring nodes. The list of neighboring nodes is implemented as a vector of Neighbor structures (accessible by the nb() method). Thus, each node has an associated variable of type GraphAL::Neighbors, which is a vector of Neighbor structures, describing its neighboring nodes.

Constructor & Destructor Documentation

dai::GraphAL::GraphAL ( )

inline

Default constructor (creates an empty graph).

dai::GraphAL::GraphAL ( size_t nr )

inline

Constructs GraphAL with nr nodes and no edges.

template<typename EdgeInputIterator >

dai::GraphAL::GraphAL	(	size_t	nr,
		EdgeInputIterator	begin,
		EdgeInputIterator	end,
		bool	check = `true`
	)

inline

Constructs GraphAL from a range of edges.

Template Parameters

EdgeInputIterator Iterator that iterates over instances of Edge.

Parameters

nr	The number of nodes.
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::GraphAL::nb	(	size_t	n1,
		size_t	_n2
	)		const

inline

Returns constant reference to the _n2 'th neighbor of node n1.

Neighbor& dai::GraphAL::nb	(	size_t	n1,
		size_t	_n2
	)

inline

Returns reference to the _n2 'th neighbor of node n1.

const Neighbors& dai::GraphAL::nb ( size_t n ) const

inline

Returns constant reference to all neighbors of node n.

Neighbors& dai::GraphAL::nb ( size_t n )

inline

Returns reference to all neighbors of node n.

template<typename EdgeInputIterator >

void dai::GraphAL::construct	(	size_t	nr,
		EdgeInputIterator	begin,
		EdgeInputIterator	end,
		bool	check = `true`
	)

(Re)constructs GraphAL from a range of edges.

Template Parameters

EdgeInputIterator Iterator that iterates over instances of Edge.

Parameters

nr	The number of nodes.
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::GraphAL::addNode ( )

inline

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

template<typename NodeInputIterator >

size_t dai::GraphAL::addNode	(	NodeInputIterator	begin,
		NodeInputIterator	end,
		size_t	sizeHint = `0`
	)

inline

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

Template Parameters

NodeInputIterator Iterator that iterates over instances of size_t.

Parameters

begin	Points to the first index of the nodes that should become neighbors of the added node.
end	Points just beyond the last index of the nodes 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.

GraphAL & dai::GraphAL::addEdge	(	size_t	n1,
		size_t	n2,
		bool	check = `true`
	)

Adds an edge between node n1 and node n2.

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

void dai::GraphAL::eraseNode ( size_t n )

Removes node n and all incident edges; indices of other nodes are changed accordingly.

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

Removes edge between node n1 and node n2.

size_t dai::GraphAL::nrNodes ( ) const

inline

Returns number of nodes.

size_t dai::GraphAL::nrEdges ( ) const

inline

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

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

inline

Returns true if the graph contains an edge between nodes n1 and n2.

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

size_t dai::GraphAL::findNb	(	size_t	n1,
		size_t	n2
	)

inline

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

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

SmallSet< size_t > dai::GraphAL::nbSet ( size_t n ) const

Returns neighbors of node n as a SmallSet<size_t>.

bool dai::GraphAL::isConnected ( ) const

Returns true if the graph is connected.

bool dai::GraphAL::isTree ( ) const

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

void dai::GraphAL::checkConsistency ( ) const

Asserts internal consistency.

bool dai::GraphAL::operator== ( const GraphAL & 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 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::GraphAL::printDot ( std::ostream & os ) const

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

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

inline

Formats a GraphAL as a string.

Friends And Related Function Documentation

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

friend

Writes a GraphAL to an output stream.

Member Data Documentation

std::vector<Neighbors> dai::GraphAL::_nb

private

Contains for each node a vector of its neighbors.

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

include/dai/graph.h
src/graph.cpp

Public Member Functions

Private Attributes

Input and output

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation