lti::adjacencyGraph< N, W, D, F, E > Class Template Reference

Adjacency Graph. More...

#include <ltiAdjacencyGraph.h>

Inheritance diagram for lti::adjacencyGraph< N, W, D, F, E >:

[legend]

Collaboration diagram for lti::adjacencyGraph< N, W, D, F, E >:

[legend]

List of all members.

Classes
class	const_edge_iterator
	The graph const_iterator iterates on all nodes in a read-only fashion. More...
class	const_iterator
	The graph const_iterator iterates on all nodes in a read-only fashion. More...
class	edge_iterator
	The edge iterator iterates on all outgoing edges of a node. More...
class	entry_type
	Entry type used in the sparse matrix representing the affinity matrix. More...
class	iterator
	The graph iterator iterates on all nodes. More...
Public Types
Type definitions

typedef W	weight_type
typedef int	id_type
typedef std::pair< id_type, id_type >	node_pair
typedef N	node_type
typedef N	value_type
typedef D	edge_data_type
typedef E	edge_traits
typedef F	weight_functor
Public Member Functions
	adjacencyGraph ()
	adjacencyGraph (const int number, const node_type &nodeData=node_type())
	adjacencyGraph (const adjacencyGraph< N, W, D, F, E > &other)
bool	clear ()
bool	empty () const
virtual const char *	getTypeName () const
virtual bool	write (ioHandler &handler, const bool complete=true) const
virtual bool	read (ioHandler &handler, const bool complete=true)
bool	checkConsistency () const
Iterators

const_iterator	begin () const
iterator	begin ()
const_iterator	end () const
iterator	end ()
edge_iterator	begin (const id_type startNode)
edge_iterator	end (const id_type startNode)
const_edge_iterator	begin (const id_type startNode) const
const_edge_iterator	end (const id_type startNode) const
Node operations

bool	isNodeIdValid (const id_type id) const
const node_type &	getNodeData (const id_type id) const
node_type &	getNodeData (const id_type id)
node_type &	setNodeData (const id_type id, const node_type &data)
id_type	insertNode (const node_type &nodeData=node_type())
bool	insertNodes (const int number, const node_type &nodeData=node_type())
bool	removeNode (const id_type id)
id_type	mergeNodes (const id_type first, const id_type second)
id_type	mergeNodes (const node_pair &edge)
id_type	topologicalMerge (const id_type first, const id_type second)
id_type	topologicalMerge (const node_pair &edge)
int	numberEdges (const id_type node) const
bool	resize (const int number, const node_type &nodeData=node_type())
int	size () const
int	totalAdjacentNodes () const
int	totalEdges () const
id_type	lastValidId () const
Edge related methods

const weight_type &	getEdgeWeight (const id_type a, const id_type b) const
const weight_type &	getEdgeWeight (const node_pair &edge) const
const weight_type &	getEdgeWeight (const edge_iterator &it) const
const weight_type &	getEdgeWeight (const const_edge_iterator &it) const
bool	updateEdgeWeight (const id_type a, const id_type b, const weight_type &weight)
bool	updateEdgeWeight (const node_pair &edges, const weight_type &weight)
bool	updateEdgeWeight (const edge_iterator &it, const weight_type &weight)
bool	updateEdgeWeight (const id_type a, const id_type b)
bool	updateEdgeWeight (const node_pair &edges)
bool	updateEdgeWeight (const edge_iterator &it)
bool	setEdgeData (const id_type a, const id_type b, const edge_data_type &data)
bool	setEdgeData (const node_pair &edges, const edge_data_type &data)
bool	setEdgeData (const edge_iterator &it, const edge_data_type &data)
const edge_data_type &	getEdgeData (const id_type a, const id_type b) const
const edge_data_type &	getEdgeData (const node_pair &edges) const
edge_data_type &	getEdgeData (const id_type a, const id_type b)
edge_data_type &	getEdgeData (const node_pair &edges)
bool	getLowestWeightEdge (id_type &a, id_type &b, weight_type &weight) const
bool	getLowestWeightEdge (node_pair &edge, weight_type &weight) const
id_type	getOtherNode (const edge_iterator &it) const
id_type	getOtherNode (const const_edge_iterator &it) const
node_pair	getEdge (const edge_iterator &it) const
node_pair	getEdge (const const_edge_iterator &it) const
bool	insertEdge (const id_type first, const id_type second, const edge_data_type &init=edge_data_type())
bool	insertEdge (const node_pair &nodes, const edge_data_type &init=edge_data_type())
bool	insertEdge (const id_type first, const id_type second, const edge_data_type &init12, const edge_data_type &init21)
bool	insertEdge (const node_pair &nodes, const edge_data_type &init12, const edge_data_type &init21)
bool	insertWeightedEdge (const id_type first, const id_type second, const edge_data_type &init12, const weight_type &weight12, const edge_data_type &init21, const weight_type &weight21)
bool	insertWeightedEdge (const node_pair &nodes, const edge_data_type &init12, const weight_type &weight12, const edge_data_type &init21, const weight_type &weight21)
edge_data_type &	forceTopologicalEdge (const node_pair &nodes)
edge_data_type &	forceTopologicalEdge (const id_type first, const id_type second)
bool	removeEdge (const id_type first, const id_type second)
bool	removeEdge (const node_pair &nodes)
bool	removeEdge (const edge_iterator &edge)
weight_type	computeEdgeWeight (const id_type a, const id_type b) const
weight_type	computeEdgeWeight (const node_pair &edge) const
weight_type	computeEdgeWeight (const edge_iterator &it) const
weight_type	computeEdgeWeight (const const_edge_iterator &it) const
bool	recomputeAllWeights ()
Weight computation functor

const weight_functor &	getWeightFunctor () const
void	setWeightFunctor (const weight_functor &ftor)
Copy methods

adjacencyGraph< N, W, D, F, E > &	copy (const adjacencyGraph< N, W, D, F, E > &other)
adjacencyGraph< N, W, D, F, E > &	operator= (const adjacencyGraph< N, W, D, F, E > &other)
virtual mathObject *	clone () const
Protected Types
Protected type definitions

typedef priorityQueue < weight_type, node_pair >	queue_type
typedef std::map< id_type, entry_type >	row_type
typedef std::vector< row_type >	adjacency_type
typedef std::vector< std::pair < int, node_type > >	nodes_type
Protected Member Functions
bool	fixEntryIterators ()
bool	insertWeightedEdgeProt (const id_type first, const id_type second, const edge_data_type &init12, const weight_type &weight12, const edge_data_type &init21, const weight_type &weight21)
id_type	getNodeId (const typename entry_type::entry_iterator &it) const
Protected Attributes
adjacency_type	adjacency
nodes_type	nodes
queue_type	distances
id_type	firstValidNodeIndex
id_type	lastValidNodeIndex
int	freeElements
weight_functor	theWeightFunctor

Detailed Description

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>
class lti::adjacencyGraph< N, W, D, F, E >

Adjacency Graph.

An adjacency graph is a set of nodes and edges linking nodes. Each node can contain some data (of type N). Each edge contains also some data (of type D) and a weight (of type W).

The adjacency property between two nodes is symmetrical, i.e. if A is adjacent to B, then B is adjacent to A. However, the weights and data of the edges from A-to-B or B-to-A not necessarily have to be the same. This means that an adjacency graph ensures always two edges between two nodes. Furthermore, a node can never be adjacent to itself.

Several methods are provided to merge nodes, insert other ones, insert edges to connect nodes, and update the data of existing nodes or edges.

This class can be used for example to represent an adjacency graph of all regions in an image partition. The main data structure is an affinity matrix: an usually sparse matrix encoding the weight of the edges between the nodes of a graph.

A second property of this class is that it is possible to access in O(1) the edge of the graph with the smallest weight, even if you change the weights of the edges during the use of the graph.

Merging two nodes implies updating the weights of the edges in the neighborhood of the new merged node, and the data object of the node. For this reason this class needs a function object to compute weight_type weight_function(const N&,const N&,const D&) const which computes the weight of an edge as a function of the two linked nodes and the information chunk stored in the edge itself. Of course, if you want, you can avoid the mergeNodes() method and set the weight of your graph by yourself. For this last case there is also a topologicalMerge() method, that won't recompute anything, not even the new node's data.

Template parameters

The required template types are the following:

Type N specifies the node information type. Each node gets an own identification id which is always an integer greater or equal zero. With it, you can get or set the node's data (of type N). The type name of N is node_type. Following are the requirements for this type N:
- The operator=(const N&) to copy another node's data.
- The operator+= to merge the contents of two nodes.
- Overload of the global function lti::read(ioHandler&,N)
- Overload of the global function lti::write(ioHandler&,const N&)
The weight type W with following interface
- operator= to copy other weights
- operator< that allows to define an order of weight_type elements
- operator== to compare equality
- operator!= to compare inequality
- Overload of the global function lti::read(ioHandler&,W&)
- Overload of the global function lti::write(ioHandler&,const W&) This type is usually just float or double. Its name is weight_type
The edge data type D, which allows to describe additional information about the edge. This information is used together with the nodes information in the computation of the edge's weight. It can describe for example the number of pixels in the border between two regions. This type (named edge_data_type) must support
- operator+=(const D& other) to combine the information of another edge.
- Overload of the global function lti::read(ioHandler&,D&)
- Overload of the global function lti::write(ioHandler&,const D&)
The weight computation functor F is a small class with the implementation of the operator() with following interface: W operator()(const N& first,const N& second,const D& data) const The graph provides methods to get a const reference to the internal instance of this functor or to set the internal instance. This allow the computation of the weights to use some additional data. If this functors must have a state, you should implement the assignment operator=(), which will be used by the method setWeightFunctor() This type has the name weight_functor
Type E specifies the edge traits. It must provide following interface:
- A static constant attribute E::Invalid of type W which will represent an invalid edge. Since the weights usually represent similarities or distances between nodes, they are usually zero or possitive. Therefore, usual invalid flags are negative constants.
- A static constant boolean attribute E::Symmetric, which is true if the weights are symmetric, i.e. if weight(A,B) == weight(B,A), or false otherwise. The name of this type is edge_traits

Please note that for all standard types (int, float, double, etc.) and most all types in the lti namespace, the lti::read and lti::write functions are already implemented.

Since each node is identified by an unique id of type id_type, the edges can be uniquely specified by a pair of id_type elements.

Symmetric edges

The use of a symmetric edge type (edge_traits::Symmetric == true) have several implications:

The computation of the weight occurs only once for the given edge (a,b) and (b,a) will get the same value.
Only the lower diagonal affinity matrix will be stored, to save some space.

Iterators

You can use the iterators and edge_iterators to iterate on the graph nodes or the node's outgoing edges respectively.

The iterators visit only valid nodes, and allow you to access the data of the node in the usual way (operator*), but you can also get the id of the visited node with the method id().

The edge_iterators allow to access the data of an edge. Using several methods of the graph class, you can also efficiently access other information like the nodes linked by the pointed edge, or the weight assigned to the edge.

IO

The adjacency graphs are mathObjects, and therefore are serializable. If you want to edit the written files, you need to know the syntax therein. A file contains four data blocks:

The size of the data structure, which is always greater or equal the number of nodes.
The nodes list containing for each node two elements: the node's id and the data of the node.
A boolean indicating if the saved data belongs to a symmetric graph or not.
The edge list containing for each edge three elements: the edge as pair of node ids, the edge's weight, the edge's data

You can find another more general weighted graph representation in the class lti::weightedGraph.

See also:: lti::weightedGragh; lti::adjacencyGraphEdge,lti::adjacencyGraphNode

Member Typedef Documentation

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

typedef std::vector< row_type > lti::adjacencyGraph< N, W, D, F, E >::adjacency_type [protected]

Type for (sparse) adjacency matrix of complex elements.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

typedef D lti::adjacencyGraph< N, W, D, F, E >::edge_data_type

Type for additional edge information (besides the weight).

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

typedef E lti::adjacencyGraph< N, W, D, F, E >::edge_traits

Edge traits type containing the Symmetric and Invalid constants.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

typedef int lti::adjacencyGraph< N, W, D, F, E >::id_type

Type for the identification key of the nodes.

All nodes in a graph have consecutive indices. When a node is removed, its index can be (and will be) reused, so that you should take care not to use "obsoleted" indices, because they could bring you to a new node you didn't want.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

typedef std::pair<id_type,id_type> lti::adjacencyGraph< N, W, D, F, E >::node_pair

The edge type contains two adjacent nodes "first" and "second".

The edge direction is always from first to second.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

typedef N lti::adjacencyGraph< N, W, D, F, E >::node_type

Type of the nodes.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

typedef std::vector< std::pair<int,node_type> > lti::adjacencyGraph< N, W, D, F, E >::nodes_type [protected]

Type used to contain the nodes' data and a flag indicating how many outgoing edges can be found in the node.

This number will be negative if the node has been deleted.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

typedef priorityQueue<weight_type, node_pair> lti::adjacencyGraph< N, W, D, F, E >::queue_type [protected]

Priority queue type used.

The priority queue keeps the edges sorted in increasing order by their weights.

The weight_type is used as key to sort the elements, the point type is used to indicate the source and destination nodes (y source, x destination),

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

typedef std::map<id_type,entry_type> lti::adjacencyGraph< N, W, D, F, E >::row_type [protected]

The row of the affinity matrix contains for one specific node, all nodes to which an edge exists.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

typedef N lti::adjacencyGraph< N, W, D, F, E >::value_type

Type of the nodes.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

typedef F lti::adjacencyGraph< N, W, D, F, E >::weight_functor

Type of the functor implementing the weight computation functor.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

typedef W lti::adjacencyGraph< N, W, D, F, E >::weight_type

Type of the weight of the edges.

It provides with following interface

operator= to copy other weights
operator<
operator== to compare equality
operator!= to compare inequality

Constructor & Destructor Documentation

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

lti::adjacencyGraph< N, W, D, F, E >::adjacencyGraph ( )

default constructor

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

lti::adjacencyGraph< N, W, D, F, E >::adjacencyGraph	(	const int	number,
		const node_type &	nodeData = `node_type()`
	)

Construct a graph with the given number of nodes, each one initialized with the given data.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

lti::adjacencyGraph< N, W, D, F, E >::adjacencyGraph ( const adjacencyGraph< N, W, D, F, E > & other )

copy constructor

Member Function Documentation

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

const_edge_iterator lti::adjacencyGraph< N, W, D, F, E >::begin ( const id_type startNode ) const

Get edge iterator to the first outgoing edge of the given start node.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

edge_iterator lti::adjacencyGraph< N, W, D, F, E >::begin ( const id_type startNode )

Get edge iterator to the first outgoing edge of the given start node.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

iterator lti::adjacencyGraph< N, W, D, F, E >::begin ( )

Return an iterator to the first valid node of the graph.

The use of the iterators is similar to the iterators of the Standard Template Library (STL). If you need to iterate on all nodes of a graph, you can use following code:

   int tmp,accu;                        // a temporal variable
   lti::adjacencyGraph myGraph(10);     // a graph with 10 elements
   lti::adjacencyGraph::iterator it,eit;

   for (it=myGraph.begin(),eit=myGraph.end(); it!=eit ; ++it) {
     // get the id of the nodes
     lti::adjacencyGraph::id_type theId = it.id();
     // do something with the graph id
   }

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

const_iterator lti::adjacencyGraph< N, W, D, F, E >::begin ( ) const

Return a const_iterator to the first valid node of the graph.

Note that you can not change the values of the graph's nodes when you use a const_iterator. See also begin()

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

bool lti::adjacencyGraph< N, W, D, F, E >::checkConsistency ( ) const

Check Graph Consistency.

This method is for debug purposes only.

If everything is ok, this should by equivalent to true. But if some bug decided to live here, it can produce a false, which shouldn't ever happen!

Don't ever rely on this method to do anything, since it will be removed as soon as we are sure, everything works. In other words, this method is already deprecated!

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

bool lti::adjacencyGraph< N, W, D, F, E >::clear ( )

Remove all nodes and edges from the graph.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

virtual mathObject* lti::adjacencyGraph< N, W, D, F, E >::clone ( ) const [virtual]

returns a copy of this object

Implements lti::mathObject.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

weight_type lti::adjacencyGraph< N, W, D, F, E >::computeEdgeWeight ( const const_edge_iterator & it ) const

Call the E::weight() method to compute the weight an edge from a to b should have, considering the node and edges current data.

Please note that if you just want to get the current weight of an edge, the getEdgeWeight methods are much much faster (they don't compute anything, but just return a previously set or computed weight value).

For this method, you should check if a and b are valid ids or your program may crash!

Note that after topological node merges or topogical edge insertions the weight values of edges can be edge_traits::Invalid. Therefore, this method is provided to compute them, without changing anything.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

weight_type lti::adjacencyGraph< N, W, D, F, E >::computeEdgeWeight ( const edge_iterator & it ) const

Call the E::weight() method to compute the weight an edge from a to b should have, considering the node and edges current data.

Please note that if you just want to get the current weight of an edge, the getEdgeWeight methods are much much faster (they don't compute anything, but just return a previously set or computed weight value).

For this method, you should check if a and b are valid ids or your program may crash!

Note that after topological node merges or topogical edge insertions the weight values of edges can be edge_traits::Invalid. Therefore, this method is provided to compute them, without changing anything.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

weight_type lti::adjacencyGraph< N, W, D, F, E >::computeEdgeWeight ( const node_pair & edge ) const

Call the E::weight() method to compute the weight an edge from a to b should have, considering the node and edges current data.

Please note that if you just want to get the current weight of an edge, the getEdgeWeight methods are much much faster (they don't compute anything, but just return a previously set or computed weight value).

For this method, you should check if a and b are valid ids or your program may crash!

Note that after topological node merges or topogical edge insertions the weight values of edges can be edge_traits::Invalid. Therefore, this method is provided to compute them, without changing anything.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

weight_type lti::adjacencyGraph< N, W, D, F, E >::computeEdgeWeight	(	const id_type	a,
		const id_type	b
	)			const

Call the E::weight() method to compute the weight an edge from a to b should have, considering the node and edges current data.

Please note that if you just want to get the current weight of an edge, the getEdgeWeight methods are much much faster (they don't compute anything, but just return a previously set or computed weight value).

For this method, you should check if a and b are valid ids or your program may crash!

Note that after topological node merges or topogical edge insertions the weight values of edges can be edge_traits::Invalid. Therefore, this method is provided to compute them, without changing anything.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

adjacencyGraph<N,W,D,F,E>& lti::adjacencyGraph< N, W, D, F, E >::copy ( const adjacencyGraph< N, W, D, F, E > & other )

copy the other adjacency matrix

Reimplemented from lti::ioObject.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

bool lti::adjacencyGraph< N, W, D, F, E >::empty ( ) const [inline]

Check if the graph is empty, i.e.

if it has no nodes.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

const_edge_iterator lti::adjacencyGraph< N, W, D, F, E >::end ( const id_type startNode ) const

Get edge iterator to the end of the outgoing edge list for the given start node.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

edge_iterator lti::adjacencyGraph< N, W, D, F, E >::end ( const id_type startNode )

Get edge iterator to the end of the outgoing edge list for the given start node.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

iterator lti::adjacencyGraph< N, W, D, F, E >::end ( )

returns last index as an iterator For an example see begin()

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

const_iterator lti::adjacencyGraph< N, W, D, F, E >::end ( ) const

returns last index as a const iterator.

For an example see begin()

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

bool lti::adjacencyGraph< N, W, D, F, E >::fixEntryIterators ( ) [protected]

After copying or loading a graph, the "complement" interators in the entries of the matrix are invalid.

This method ensures consistency

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

edge_data_type& lti::adjacencyGraph< N, W, D, F, E >::forceTopologicalEdge	(	const id_type	first,
		const id_type	second
	)

Return a reference to the given edge's data, or create the edge pair if it didn't exist and return the reference to the created data.

The created edge will not have an associated weight, to save the time of computing the weight and administrating it in the corresponding sorted data structure.

This method is useful for complex graph operations, which need to build first the graph structure and compute in a second stage all weights and set them at once with the method TODO. Avoiding an unnecessary preliminar weight computation and the unnecessary sorting of such weight permits to save lots of time.

Of course, this method can also be (ab)used to create simple non-weighted bidirectional adjacency graphs if you need to analyze only topological features of an adjacency problem.

You can later assign a weight to the edges with the updateEdgeWeight methods.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

edge_data_type& lti::adjacencyGraph< N, W, D, F, E >::forceTopologicalEdge ( const node_pair & nodes )

Return a reference to the given edge's data, or create the edge pair if it didn't exist and return the reference to the created data.

The created edge will not have an associated weight, to save the time of computing the weight and administrating it in the corresponding sorted data structure.

This method is useful for complex graph operations, which need to build first the graph structure and compute in a second stage all weights and set them at once with the method TODO. Avoiding an unnecessary preliminar weight computation and the unnecessary sorting of such weight permits to save lots of time.

Of course, this method can also be (ab)used to create simple non-weighted bidirectional adjacency graphs if you need to analyze only topological features of an adjacency problem.

You can later assign a weight to the edges with the updateEdgeWeight methods.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

node_pair lti::adjacencyGraph< N, W, D, F, E >::getEdge ( const const_edge_iterator & it ) const

Get edge as node_pair pointed by the given iterator.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

node_pair lti::adjacencyGraph< N, W, D, F, E >::getEdge ( const edge_iterator & it ) const

Get edge as node_pair pointed by the given iterator.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

edge_data_type& lti::adjacencyGraph< N, W, D, F, E >::getEdgeData ( const node_pair & edges )

Get a writable reference to the data object of the edge.

If you have an edge_iterator, remember that you can get the edge data dereferencing it, i.e. if iter is your iterator, then (*iter) is the edge's data.

Parameters:

edges

pair of nodes (a=edges.first,b=edges.second)

Returns:: read-only reference to the data. If the edge didn't exist expect unpredictable behaviour!

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

edge_data_type& lti::adjacencyGraph< N, W, D, F, E >::getEdgeData	(	const id_type	a,
		const id_type	b
	)

Get a writable reference to the data object of the edge.

If you have an edge_iterator, remember that you can get the edge data dereferencing it, i.e. if iter is your iterator, then (*iter) is the edge's data.

Parameters:

	a	first node
	b	second node

Returns:: read-only reference to the data. If the edge didn't exist expect unpredictable behaviour!

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

const edge_data_type& lti::adjacencyGraph< N, W, D, F, E >::getEdgeData ( const node_pair & edges ) const

Get a read-only reference to the data object of the edge.

If you have a const_edge_iterator, remember that you can get the edge data dereferencing it, i.e. if iter is your iterator, then (*iter) is the edge's data.

Parameters:

edges

pair of nodes (a=edges.first,b=edges.second)

Returns:: read-only reference to the data. If the edge didn't exist expect unpredictable behaviour!

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

const edge_data_type& lti::adjacencyGraph< N, W, D, F, E >::getEdgeData	(	const id_type	a,
		const id_type	b
	)			const

Get a read-only reference to the data object of the edge.

If you have a const_edge_iterator, remember that you can get the edge data dereferencing it, i.e. if iter is your iterator, then (*iter) is the edge's data.

Parameters:

	a	first node
	b	second node

Returns:: read-only reference to the data. If the edge didn't exist expect unpredictable behaviour!

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

const weight_type& lti::adjacencyGraph< N, W, D, F, E >::getEdgeWeight ( const const_edge_iterator & it ) const

Get edge weight.

Please remember that getEdgeWeight(a,b) is not necessarily the same than getEdgeWeight(b,a). This depends on the definition of the function E::weight()

Parameters:

it

iterator to the edge

Returns:: the weith of the edge or edge_traits::Invalid if edge does not exist

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

const weight_type& lti::adjacencyGraph< N, W, D, F, E >::getEdgeWeight ( const edge_iterator & it ) const

Get edge weight.

Please remember that getEdgeWeight(a,b) is not necessarily the same than getEdgeWeight(b,a). This depends on the definition of the function E::weight()

Parameters:

it

iterator to the edge

Returns:: the weight of the edge or edge_traits::Invalid if it is a topological edge, without associated weight

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

const weight_type& lti::adjacencyGraph< N, W, D, F, E >::getEdgeWeight ( const node_pair & edge ) const

Get edge weight.

Please remember that getEdgeWeight(a,b) is not necessarily the same than getEdgeWeight(b,a). This depends on the definition of the function E::weight()

Parameters:

edge

the pair of nodes describing an edge.

Returns:: the weight of the edge or edge_traits::Invalid if edge does not exist or is a topological edge, without associated weight.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

const weight_type& lti::adjacencyGraph< N, W, D, F, E >::getEdgeWeight	(	const id_type	a,
		const id_type	b
	)			const

Get edge weight.

Please remember that getEdgeWeight(a,b) is not necessarily the same than getEdgeWeight(b,a). This depends on the definition of the function object of type weight_functor

Parameters:

	a	first node
	b	second node

Returns:: the weight of the edge or edge_traits::Invalid if edge does not exist

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

bool lti::adjacencyGraph< N, W, D, F, E >::getLowestWeightEdge	(	node_pair &	edge,
		weight_type &	weight
	)			const

Get pair of nodes with the lowest valid edge weight.

Parameters:

	edge	the edge contains both nodes
	weight	weight of the edge

Returns:: true if graph not empty, false otherwise (in which case the three parameters will be left untouched).

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

bool lti::adjacencyGraph< N, W, D, F, E >::getLowestWeightEdge	(	id_type &	a,
		id_type &	b,
		weight_type &	weight
	)			const

Get edge with the lowest weight in the graph.

Parameters:

	a	first node
	b	second node
	weight	weight of the edge

Returns:: true if graph not empty, false otherwise (in which case the three parameters will be left untouched.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

node_type& lti::adjacencyGraph< N, W, D, F, E >::getNodeData ( const id_type id )

Return the data contained in the node with the given id.

You must ensure that the given id is valid. If it is not, an assertion will be thrown in debug modus, or some problems will occur in release modus (segmentation fault or similar).

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

const node_type& lti::adjacencyGraph< N, W, D, F, E >::getNodeData ( const id_type id ) const

Return the data contained in the node with the given id.

You must ensure that the given id is valid. If it is not, an assertion will be thrown in debug modus, or some problems will occur in release modus (segmentation fault or similar).

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

id_type lti::adjacencyGraph< N, W, D, F, E >::getNodeId ( const typename entry_type::entry_iterator & it ) const [protected]

Get the id of the node corresponding to the given iterator.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

id_type lti::adjacencyGraph< N, W, D, F, E >::getOtherNode ( const const_edge_iterator & it ) const

Get the id of the node at the other side of the edge pointed by the given iterator.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

id_type lti::adjacencyGraph< N, W, D, F, E >::getOtherNode ( const edge_iterator & it ) const

Get the id of the node at the other side of the edge pointed by the given iterator.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

virtual const char* lti::adjacencyGraph< N, W, D, F, E >::getTypeName ( ) const [virtual]

returns the name of this class

Reimplemented from lti::mathObject.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

const weight_functor& lti::adjacencyGraph< N, W, D, F, E >::getWeightFunctor ( ) const

Get a read-only reference to the internal weight computation functor of type weight_functor (template parameter F).

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

bool lti::adjacencyGraph< N, W, D, F, E >::insertEdge	(	const node_pair &	nodes,
		const edge_data_type &	init12,
		const edge_data_type &	init21
	)

Insert an edge between the first and second nodes, identified by their ids.

The data of each

The weight of both edges (first->second, second->first) will be computed from the data of both nodes and the given edge data, using the function E::weight().

Parameters:

	nodes	the first and second nodes, which identify the edge
	init12	initial data for the first to second edge.
	init21	initial data for the second to first edge.

Returns:: true if edge could be set successfully inserted, false otherwise (for example, if one or both ids are invalid, or if the edge already existed).

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

bool lti::adjacencyGraph< N, W, D, F, E >::insertEdge	(	const id_type	first,
		const id_type	second,
		const edge_data_type &	init12,
		const edge_data_type &	init21
	)

Insert an edge between the first and second nodes, identified by their ids.

The weight of both edges (first->second, second->first) will be computed from the data of both nodes and the given edge data, using the function E::weight().

Parameters:

	first	id of the first node (source one).
	second	id of the second node (destination one).
	init12	initial data for the first to second edge.
	init21	initial data for the second to first edge.

Returns:: true if edge could be set successfully inserted, false otherwise (for example, if one or both ids are invalid, or if the edge already existed).

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

bool lti::adjacencyGraph< N, W, D, F, E >::insertEdge	(	const node_pair &	nodes,
		const edge_data_type &	init = `edge_data_type()`
	)

Insert an edge between the first and second nodes, identified by their ids.

The edge is assumed symmetrical, so that an edge with the same data type will be inserted between the second and the first nodes.

The weight of both edges (first->second, second->first) will be computed from the data of both nodes and the given edge data, using the function E::weight().

Parameters:

	nodes	the first and second nodes, which identify the edge
	init	initial data set for the edge.

Returns:: true if edge could be set successfully inserted, false otherwise (for example, if one or both ids are invalid, or if the edge already existed).

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

bool lti::adjacencyGraph< N, W, D, F, E >::insertEdge	(	const id_type	first,
		const id_type	second,
		const edge_data_type &	init = `edge_data_type()`
	)

Insert an edge between the first and second nodes, identified by their ids.

The edge is assumed symmetrical, so that an edge with the same data type will be inserted between the second and the first nodes.

The weight of both edges (first->second, second->first) will be computed from the data of both nodes and the given edge data, using the function E::weight().

Parameters:

	first	id of the first node (source one).
	second	id of the second node (destination one).
	init	initial data set for the edge.

Returns:: true if edge could be set successfully inserted, false otherwise (for example, if one or both ids are invalid, or if the edge already existed).

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

id_type lti::adjacencyGraph< N, W, D, F, E >::insertNode ( const node_type & nodeData = node_type() )

Insert a node in the graph with the given data.

Parameters:

nodeData

data to be included in the new node. If not given, a default object will be created.

Returns:: an identification key for the new inserted node.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

bool lti::adjacencyGraph< N, W, D, F, E >::insertNodes	(	const int	number,
		const node_type &	nodeData = `node_type()`
	)

Insert the given number of nodes in the graphs, all having copies of the same data object.

Parameters:

	number	number of nodes to be inserted.
	nodeData	data to be included in the new nodes. If omitted, a default object will be created.

Returns:: true if successful, false otherwise.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

bool lti::adjacencyGraph< N, W, D, F, E >::insertWeightedEdge	(	const node_pair &	nodes,
		const edge_data_type &	init12,
		const weight_type &	weight12,
		const edge_data_type &	init21,
		const weight_type &	weight21
	)

Insert an edge between the first and second nodes, identified by their ids.

The data of each

Parameters:

	nodes	the first and second nodes, which identify the edge
	init12	initial data for the first to second edge.
	weight12	weight of the edge between nodes.first and nodes.second
	init21	initial data for the second to first edge.
	weight21	weight of the edge between nodes.second and nodes.first

Returns:: true if edge could be set successfully inserted, false otherwise (for example, if one or both ids are invalid, or if the edge already existed).

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

bool lti::adjacencyGraph< N, W, D, F, E >::insertWeightedEdge	(	const id_type	first,
		const id_type	second,
		const edge_data_type &	init12,
		const weight_type &	weight12,
		const edge_data_type &	init21,
		const weight_type &	weight21
	)

Insert an edge between the first and second nodes, identified by their ids.

Parameters:

	first	id of the first node (source one).
	second	id of the second node (destination one).
	init12	initial data for the first to second edge.
	weight12	weight of the edge between first and second
	init21	initial data for the second to first edge.
	weight21	weight of the edge between second and first

Returns:: true if edge could be set successfully inserted, false otherwise (for example, if one or both ids are invalid, or if the edge already existed).

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

bool lti::adjacencyGraph< N, W, D, F, E >::insertWeightedEdgeProt	(	const id_type	first,
		const id_type	second,
		const edge_data_type &	init12,
		const weight_type &	weight12,
		const edge_data_type &	init21,
		const weight_type &	weight21
	)			`[protected]`

Insert an edge between the first and second nodes, identified by their ids.

This method assumes the validity of the first and second ids, and therefore is protected!

Parameters:

	first	id of the first node (source one).
	second	id of the second node (destination one).
	init12	initial data for the first to second edge.
	weight12	weight of the edge between first and second
	init21	initial data for the second to first edge.
	weight21	weight of the edge between second and first

Returns:: true if edge could be set successfully inserted, false otherwise (for example, if one or both ids are invalid, or if the edge already existed).

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

bool lti::adjacencyGraph< N, W, D, F, E >::isNodeIdValid ( const id_type id ) const

Check if the given id is a valid one.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

id_type lti::adjacencyGraph< N, W, D, F, E >::lastValidId ( ) const

Return the largest valid node id (or negative if the graph is empty).

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

id_type lti::adjacencyGraph< N, W, D, F, E >::mergeNodes ( const node_pair & edge )

Merge two nodes.

See also:: mergeNodes(const id_type,const id_type)

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

id_type lti::adjacencyGraph< N, W, D, F, E >::mergeNodes	(	const id_type	first,
		const id_type	second
	)

Merge the two given nodes.

Topological merge of the two given nodes.

The difference of this method with topologicalMerge is that besides ensuring a topological merge, the data of the merged edges and nodes is updated. Consider for instance the following graph with nodes A,B,w,x,y,z and edges Ax,Az,Aw,AB,Bw,By:

 x---A---B---y
     |\  |
     | \ |
     z   w

The merge of A and B results in

 x---A---y
     |\  
     | \ 
     z   w

Here, the new weight of Aw is computed using the operator+= of the weight_type type, which in this case does an update of:

the node information of A (which is the combination of the previous node data A and B). For this task, the N type must provide the operator+=.
the edge weights between A and its old neighbors x, z and w, the additional information update of the edge Aw, which now encompasses the old Aw and Bw, and the weights to the new neighbor y. The update of edge information assumes that the data_type provides the operator+=.

Parameters:

	first	one of the two nodes to be merged.
	second	the node to be merged with the first one.

Returns:: the id of the new merged node. This will usually be the id of the first node. If one of the ids does not exist, a negative id will be returned.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

int lti::adjacencyGraph< N, W, D, F, E >::numberEdges ( const id_type node ) const

Return the number of outgoing edges for the given node.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

adjacencyGraph<N,W,D,F,E>& lti::adjacencyGraph< N, W, D, F, E >::operator= ( const adjacencyGraph< N, W, D, F, E > & other )

copy the other adjacency matrix

Reimplemented from lti::ioObject.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

virtual bool lti::adjacencyGraph< N, W, D, F, E >::read	(	ioHandler &	handler,
		const bool	complete = `true`
	)			`[virtual]`

read the parameters from the given ioHandler

Parameters:

	handler	the ioHandler to be used
	complete	if true (the default) the enclosing begin/end will be also written, otherwise only the data block will be written.

Returns:: true if write was successful

Reimplemented from lti::mathObject.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

bool lti::adjacencyGraph< N, W, D, F, E >::recomputeAllWeights ( )

This method uses the data in the nodes and the edges to recompute all graph weights.

It is more efficient than recomputing the weights one by one, since the sorting of the weights can occur at once, and not iteratively.

If the graph is symmetric, only the bottom diagonal affinity matrix will be used, i.e. only the edges (a,b) with a>b will be considered to the computations and the results will also be assigned to (b,a).

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

bool lti::adjacencyGraph< N, W, D, F, E >::removeEdge ( const edge_iterator & edge )

Remove the edge between the given two nodes.

In order to ensure the adjacency graph consistency not only the first-to-second edge will be removed, but also the second-to-first one.

Parameters:

edge

edge_iterator pointing to the edge to be removed.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

bool lti::adjacencyGraph< N, W, D, F, E >::removeEdge ( const node_pair & nodes )

Remove the edge between the given two nodes.

In order to ensure the adjacency graph consistency not only the first-to-second edge will be removed, but also the second-to-first one.

Parameters:

nodes

first and second node ids, which identify the edge

Returns:: true if edge could be deleted. false if some problem occurred, for example if the ids are not valid, or the edge didn't exist.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

bool lti::adjacencyGraph< N, W, D, F, E >::removeEdge	(	const id_type	first,
		const id_type	second
	)

Remove the edge between the given two nodes.

In order to ensure the adjacency graph consistency not only the first-to-second edge will be removed, but also the second-to-first one.

Parameters:

	first	id of the first node (source one).
	second	id of the second node (destination one).

Returns:: true if edge could be deleted. false if some problem occurred, for example if the ids are not valid, or the edge didn't exist.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

bool lti::adjacencyGraph< N, W, D, F, E >::removeNode ( const id_type id )

Remove the node and all edges from/to it.

Parameters:

id

identification key for the node to be removed.

Returns:: true if node could be deleted. false if some problem occurred, for example if the id is not valid.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

bool lti::adjacencyGraph< N, W, D, F, E >::resize	(	const int	number,
		const node_type &	nodeData = `node_type()`
	)

Remove all nodes and edges from the graph and insert the given number of nodes, without any edges.

This method ensures that the ids for the nodes lie between zero and number-1.

Parameters:

	number	number of nodes the graph must have.
	nodeData	data to be included in all nodes. If omitted, a default data object will be created.

Returns:: true if successful, false otherwise.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

bool lti::adjacencyGraph< N, W, D, F, E >::setEdgeData	(	const edge_iterator &	it,
		const edge_data_type &	data
	)

Change the data of the given edge.

This method updates the data of the edge (a,b).

If the constant E::Symmetric is true, then also the data of the edge (b,a) is updated.

Parameters:

	it	iterator to the edge
	data	new data for the edge.

Returns:: true if update successful, or false if the edge didn't exist.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

bool lti::adjacencyGraph< N, W, D, F, E >::setEdgeData	(	const node_pair &	edges,
		const edge_data_type &	data
	)

Change the data of the given edge.

This method updates the data of the edge (a,b).

If the constant E::Symmetric is true, then also the data of the edge (b,a) is updated.

Parameters:

	edges	pair of nodes (a=edges.first,b=edges.second)
	data	new data for the edge.

Returns:: true if update successful, or false if the edge didn't exist.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

bool lti::adjacencyGraph< N, W, D, F, E >::setEdgeData	(	const id_type	a,
		const id_type	b,
		const edge_data_type &	data
	)

Change the data of the given edge.

This method updates the data of the edge (a,b).

If the constant E::Symmetric is true, then also the data of the edge (b,a) is updated.

Parameters:

	a	first node
	b	second node
	data	new data for the edge.

Returns:: true if update successful, or false if the edge didn't exist.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

node_type& lti::adjacencyGraph< N, W, D, F, E >::setNodeData	(	const id_type	id,
		const node_type &	data
	)

Change the data in a given node.

You must ensure that the given id is valid. If it is not, an assertion will be thrown in debug modus, or some problems will occur in release modus (segmentation fault or similar).

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

void lti::adjacencyGraph< N, W, D, F, E >::setWeightFunctor ( const weight_functor & ftor )

Set a the functor to be used to compute the weights.

This method assumes that the weight_functor implements the operator=(), even the default implementation or a specialized one.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

int lti::adjacencyGraph< N, W, D, F, E >::size ( ) const

Return the number of nodes of this graph.

This value needs to be computed, and therefore takes a little bit time.

This value counts all nodes, independently if they are connected to other nodes or not. In an adjacency graph, isolated nodes can exist, but they do not make much sence, since they are not adjacent to anything. Hence, Many algorithms require instead the number returned by totalAdjacentNodes().

See also:: totalAdjacentNodes();

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

id_type lti::adjacencyGraph< N, W, D, F, E >::topologicalMerge ( const node_pair & edge )

Merge two nodes.

See also:: topologicalMerge(const id_type,const id_type)

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

id_type lti::adjacencyGraph< N, W, D, F, E >::topologicalMerge	(	const id_type	first,
		const id_type	second
	)

Topological merge of the two given nodes.

The difference of this method with mergeNodes is that it only ensures that the topology of the merge node is kept. Consider the following graph with nodes A,B,w,x,y,z and edges Ax,Az,Aw,AB,Bw and By:

 x---A---B---y
     |\  |
     | \ |
     z   w

The merge of A and B results in

 x---A---y
     |\  
     | \ 
     z   w

Here, the weight of Aw is kept and the weight of A remain unchainged.

Parameters:

	first	one of the two nodes to be merged.
	second	the node to be merged with the first one.

Returns:: the id of the new merged node. This will usually be the id of the first node. If one of the ids does not exist, a negative id will be returned.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

int lti::adjacencyGraph< N, W, D, F, E >::totalAdjacentNodes ( ) const

Return the number of nodes of this graph, that are connected to at least another node.

Note that this value is always less or equal the size().

This value needs to be computed, and therefore, takes a little bit time.

In an adjacency graph, isolated nodes can exist, but they do not make much sence, since they are not adjacent to anyone. Many algorithm require instead the number of nodes that are adjacent to something, which is exactly what this method computes.

See also:: size();

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

int lti::adjacencyGraph< N, W, D, F, E >::totalEdges ( ) const

Return the total number of edges of this graph.

This value needs to be computed, and therefore takes a little bit time.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

bool lti::adjacencyGraph< N, W, D, F, E >::updateEdgeWeight ( const edge_iterator & it )

Change the weight of the given edge.

This method updates the weigth of the edge (a,b) to the one computed by the E::weight() method.

If the constant E::Symmetric is true, then also the weight of the edge (b,a) is updated.

Parameters:

it

iterator to the edge

Returns:: true if update successful, or false if the edge didn't exist.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

bool lti::adjacencyGraph< N, W, D, F, E >::updateEdgeWeight ( const node_pair & edges )

Change the weight of the given edge.

This method updates the weigth of the edge (a,b) to the one computed by the E::weight() method.

If the constant E::Symmetric is true, then also the weight of the edge (b,a) is updated.

Parameters:

edges

pair of nodes (a=edges.first,b=edges.second)

Returns:: true if update successful, or false if the edge didn't exist.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

bool lti::adjacencyGraph< N, W, D, F, E >::updateEdgeWeight	(	const id_type	a,
		const id_type	b
	)

Recompute the weight of the given edge.

This method updates the weigth of the edge (a,b) to the one computed by the E::weight() method.

If the constant E::Symmetric is true, then also the weight of the edge (b,a) is updated.

Parameters:

	a	first node
	b	second node

Returns:: true if update successful, or false if the edge didn't exist.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

bool lti::adjacencyGraph< N, W, D, F, E >::updateEdgeWeight	(	const edge_iterator &	it,
		const weight_type &	weight
	)

Change the weight of the given edge.

This method updates the weigth of the edge (a,b).

If the constant E::Symmetric is true, then also the weight of the edge (b,a) is updated.

Parameters:

	it	iterator to the edge
	weight	new weight for the edge.

Returns:: true if update successful, or false if the edge didn't exist.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

bool lti::adjacencyGraph< N, W, D, F, E >::updateEdgeWeight	(	const node_pair &	edges,
		const weight_type &	weight
	)

Change the weight of the given edge.

This method updates the weigth of the edge (a,b).

If the constant E::Symmetric is true, then also the weight of the edge (b,a) is updated.

Parameters:

	edges	pair of nodes (a=edges.first,b=edges.second)
	weight	new weight for the edge.

Returns:: true if update successful, or false if the edge didn't exist.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

bool lti::adjacencyGraph< N, W, D, F, E >::updateEdgeWeight	(	const id_type	a,
		const id_type	b,
		const weight_type &	weight
	)

Change the weight of the given edge.

This method updates the weigth of the edge (a,b).

If the constant E::Symmetric is true, then also the weight of the edge (b,a) is updated.

Parameters:

	a	first node
	b	second node
	weight	new weight for the edge.

Returns:: true if update successful, or false if the edge didn't exist.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

virtual bool lti::adjacencyGraph< N, W, D, F, E >::write	(	ioHandler &	handler,
		const bool	complete = `true`
	)			const `[virtual]`

write the parameters in the given ioHandler

The adjacency graphs are mathObjects, and therefore are serializable. If you want to edit the written files, you need to know the syntax therein. A file contains four data blocks:

The size of the data structure, which is always greater or equal to the number of nodes.
The nodes list containing for each node two elements: the node's id and the data of the node.
A boolean indicating if the saved data belongs to a symmetric graph or not.
The edge list containing for each one three elements: the edge as pair of node ids, the edge's weight, the edge's data

Parameters:

	handler	the ioHandler to be used
	complete	if true (the default) the enclosing begin/end will be also written, otherwise only the data block will be written.

Returns:: true if write was successful

Reimplemented from lti::mathObject.

Member Data Documentation

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

adjacency_type lti::adjacencyGraph< N, W, D, F, E >::adjacency [protected]

adjacency matrix

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

queue_type lti::adjacencyGraph< N, W, D, F, E >::distances [protected]

priority queue ordered by the distances.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

id_type lti::adjacencyGraph< N, W, D, F, E >::firstValidNodeIndex [protected]

first valid vector index

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

int lti::adjacencyGraph< N, W, D, F, E >::freeElements [protected]

Number of elements in the nodes vector that has been freed.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

id_type lti::adjacencyGraph< N, W, D, F, E >::lastValidNodeIndex [protected]

first valid vector index

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

nodes_type lti::adjacencyGraph< N, W, D, F, E >::nodes [protected]

The nodes.

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>

weight_functor lti::adjacencyGraph< N, W, D, F, E >::theWeightFunctor [protected]

The one and only instance of E, used to compute the weights between two nodes.

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

ltiAdjacencyGraph.h

lti::adjacencyGraph< N, W, D, F, E > Class Template Reference

Classes

Public Types

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Detailed Description

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>> class lti::adjacencyGraph< N, W, D, F, E >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<class N, class W = float, class D = int, class F = adjacencyGraphVoidWeightFunction<N,W,D>, class E = symmetricEdgeTraits<W>>
class lti::adjacencyGraph< N, W, D, F, E >