Graph Data Structures and Algorithms

Classes

class AdjacencyListGraph

undirected adjacency list graph in the LEMON API More...

class BinaryForest

BinaryForest stores a collection of rooted binary trees. More...

class ClusteringOptions

Options object for hierarchical clustering. More...

class GridGraph< N, DirectedTag >

Define a grid graph in arbitrary dimensions. More...

class ShortestPathDijkstra< GRAPH, WEIGHT_TYPE >

shortest path computer More...

Functions

Arc addArc (Node const &u, Node const &v)

Add a new arc from node u to node v. The arc ID is 2*id(u) if v is the left child of u, 2*id(u)+1 otherwise.

Node addNode ()

Add a new node (its node ID will be selected automatically).

Arc arcFromId (index_type const &id) const

Get arc descriptor for id.

BinaryForest ()

Create an empty forest.

template<class GRAPH , class EDGE_WEIGHTS , class SEEDS , class LABELS >

void carvingSegmentation (const GRAPH &g, const EDGE_WEIGHTS &edgeWeights, const SEEDS &seeds, const typename LABELS::Value backgroundLabel, const typename EDGE_WEIGHTS::Value backgroundBias, const typename EDGE_WEIGHTS::Value noPriorBelow, LABELS &labels)

edge weighted watersheds Segmentataion More...

template<class G , class A , class B >

void copyEdgeMap (const G &g, const A &a, B &b)

copy a lemon edge map

template<class G , class A , class B >

void copyNodeMap (const G &g, const A &a, B &b)

copy a lemon node map

template<class GRAPH , class WEIGHTS , class COMPERATOR >

void edgeSort (const GRAPH &g, const WEIGHTS &weights, const COMPERATOR &comperator, std::vector< typename GRAPH::Edge > &sortedEdges)

get a vector of Edge descriptors More...

template<class GRAPH , class EDGE_WEIGHTS , class SEEDS , class LABELS >

void edgeWeightedWatershedsSegmentation (const GRAPH &g, const EDGE_WEIGHTS &edgeWeights, const SEEDS &seeds, LABELS &labels)

edge weighted watersheds Segmentataion More...

template<unsigned int N, class DirectedTag , class T , class EDGEMAP >

void edgeWeightsFromInterpolatedImage (const GridGraph< N, DirectedTag > &g, const MultiArrayView< N, T > &interpolatedImage, EDGEMAP &edgeWeights, bool euclidean=false)

create edge weights from an interpolated image More...

template<unsigned int N, class DirectedTag , class NODEMAP , class EDGEMAP , class FUNCTOR >

void edgeWeightsFromNodeWeights (const GridGraph< N, DirectedTag > &g, const NODEMAP &nodeWeights, EDGEMAP &edgeWeights, bool euclidean, FUNCTOR const &func)

create edge weights from node weights More...

template<class GRAPH , class EDGE_WEIGHTS , class NODE_SIZE , class NODE_LABEL_MAP >

void felzenszwalbSegmentation (const GRAPH &graph, const EDGE_WEIGHTS &edgeWeights, const NODE_SIZE &nodeSizes, float k, NODE_LABEL_MAP &nodeLabeling, const int nodeNumStopCond=-1)

edge weighted watersheds Segmentataion More...

template<class G , class A , class T >

void fillEdgeMap (const G &g, A &a, const T &value)

fill a lemon edge map

template<class G , class A , class T >

void fillNodeMap (const G &g, A &a, const T &value)

fill a lemon node map

Node getChild (Node const &node, size_t i=0) const

Get child number i of node. Returns the left child if i=0, the right child if i=1, and lemon::INVALID for other values of i or when the respective is undefined.

Node getNode (size_t i) const

Create node cescriptor for ID i, or lemon::INVALID if i is not a valid ID.

Node getParent (Node const &node, size_t i=0) const

Get the parent node descriptor of node, or lemon::INVALID if node is a root or i is non-zero.

Node getRoot (size_t i=0) const

Get the root node descriptor of tree i in the forest, or lemon::INVALID if i is invalid.

template<class GRAPH , class NODE_FEATURES_IN , class EDGE_INDICATOR , class NODE_FEATURES_OUT >

void graphSmoothing (const GRAPH &g, const NODE_FEATURES_IN &nodeFeaturesIn, const EDGE_INDICATOR &edgeIndicator, const float lambda, const float edgeThreshold, const float scale, NODE_FEATURES_OUT &nodeFeaturesOut)

smooth node features of a graph More...

template<... >

void hierarchicalClustering (...)

Reduce the number of nodes in a graph by iteratively contracting the cheapest edge. More...

index_type id (Node const &node) const

Get ID for node descriptor node.

index_type id (Arc const &arc) const

Get ID for arc descriptor arc.

size_t inDegree (Node const &node) const

Return the number of incoming edges of node. 0 for a root node, 1 otherwise.

template<class GRAPH_IN , class GRAPH_IN_NODE_LABEL_MAP >

void makeRegionAdjacencyGraph (GRAPH_IN graphIn, GRAPH_IN_NODE_LABEL_MAP labels, AdjacencyListGraph &rag, typename AdjacencyListGraph::template EdgeMap< std::vector< typename GRAPH_IN::Edge > > &affiliatedEdges, const Int64 ignoreLabel=-1)

make a region adjacency graph from a graph and labels w.r.t. that graph More...

index_type maxArcId () const

Return the highest possible arc ID (equivalent to 2*maxNodeId() + 1).

index_type maxNodeId () const

Return the highest existing node ID.

size_t merge (BinaryForest const &other)

Merge two forests and increase the IDs of other to avoid ID clashes. The function returns the offset that has been added to these IDs.

Node nodeFromId (index_type const &id) const

Get node descriptor for id.

size_t numArcs () const

Return the number of arcs. Always less than maxArcId() because not all arcs actually exist.

size_t numChildren (Node const &node) const

Return the number of children of node (equivalent to outDegree()).

size_t numNodes () const

Return the number of nodes (equivalent to maxNodeId()+1).

size_t numParents (Node const &node) const

Return the number of parents of node (equivalent to inDegree()).

size_t numRoots () const

Return the number of trees in the forest.

size_t outDegree (Node const &node) const

Return the number of outgoing edges of node. 0 for a leaf node, 1 or 2 otherwise.

template<class NODE , class PREDECESSORS >

size_t pathLength (const NODE source, const NODE target, const PREDECESSORS &predecessors)

get the length in node units of a path

template<class RAG , class BASE_GRAPH , class BASE_GRAPH_RAG_LABELS , class BASE_GRAPH_GT , class RAG_GT , class RAG_GT_QT >

void projectGroundTruth (const RAG &rag, const BASE_GRAPH &baseGraph, const BASE_GRAPH_RAG_LABELS &baseGraphRagLabels, const BASE_GRAPH_GT &baseGraphGt, RAG_GT &ragGt, RAG_GT_QT &)

template<class RAGGRAPH , class GRAPH , class RAGEDGES , unsigned int N, class T >

MultiArray< 2, MultiArrayIndex > ragFindEdges (const RAGGRAPH &rag, const GRAPH &graph, const RAGEDGES &affiliatedEdges, MultiArrayView< N, T > labelsArray, const typename RAGGRAPH::Node &node)

Find indices of points on the edges. More...

template<class GRAPH , class NODE_FEATURES_IN , class EDGE_INDICATOR , class NODE_FEATURES_OUT >

void recursiveGraphSmoothing (const GRAPH &g, const NODE_FEATURES_IN &nodeFeaturesIn, const EDGE_INDICATOR &edgeIndicator, const float lambda, const float edgeThreshold, const float scale, size_t iterations, NODE_FEATURES_OUT &nodeFeaturesBuffer, NODE_FEATURES_OUT &nodeFeaturesOut)

smooth node features of a graph More...

template<class GRAPH , class WEIGHTS , class PREDECESSORS , class DISTANCE , class HEURSTIC >

void shortestPathAStar (const GRAPH &graph, const typename GRAPH::Node &source, const typename GRAPH::Node &target, const WEIGHTS &weights, PREDECESSORS &predecessors, DISTANCE &distance, const HEURSTIC &heuristic)

Astar Shortest path search.

Node source (Arc const &arc) const

Find start node of arc.

Node target (Arc const &arc) const

Find end node of arc.

bool valid (Node const &node) const

Check if node exists.

bool valid (Arc const &arc) const

Check if arc exists.

Detailed Description

Graph algorithms and the underlying graph data structures (e.g. GridGraph and AdjacencyListGraph) implementing the APIs of the boost::graph and LEMON libraries.

Function Documentation

void vigra::edgeSort	(	const GRAPH &	g,
		const WEIGHTS &	weights,
		const COMPERATOR &	comperator,
		std::vector< typename GRAPH::Edge > &	sortedEdges
	)

get a vector of Edge descriptors

Sort the Edge descriptors given weights and a comperator

void vigra::makeRegionAdjacencyGraph	(	GRAPH_IN	graphIn,
		GRAPH_IN_NODE_LABEL_MAP	labels,
		AdjacencyListGraph &	rag,
		typename AdjacencyListGraph::template EdgeMap< std::vector< typename GRAPH_IN::Edge > > &	affiliatedEdges,
		const Int64	ignoreLabel = `-1`
	)

make a region adjacency graph from a graph and labels w.r.t. that graph

Parameters

	graphIn	: input graph
	labels	: labels w.r.t. graphIn
[out]	rag	: region adjacency graph
[out]	affiliatedEdges	: a vector of edges of graphIn for each edge in rag
	ignoreLabel	: optional label to ignore (default: -1 means no label will be ignored)

Examples:: graph_agglomerative_clustering.cxx.

void vigra::edgeWeightedWatershedsSegmentation	(	const GRAPH &	g,
		const EDGE_WEIGHTS &	edgeWeights,
		const SEEDS &	seeds,
		LABELS &	labels
	)

edge weighted watersheds Segmentataion

Parameters

	g	input graph
	edgeWeights	: edge weights / edge indicator
	seeds	: seed must be non empty!
[out]	labels	: resulting nodeLabeling (not necessarily dense)

void vigra::carvingSegmentation	(	const GRAPH &	g,
		const EDGE_WEIGHTS &	edgeWeights,
		const SEEDS &	seeds,
		const typename LABELS::Value	backgroundLabel,
		const typename EDGE_WEIGHTS::Value	backgroundBias,
		const typename EDGE_WEIGHTS::Value	noPriorBelow,
		LABELS &	labels
	)

edge weighted watersheds Segmentataion

Parameters

	g	input graph
	edgeWeights	: edge weights / edge indicator
	seeds	: seed must be non empty!
	backgroundLabel	: which label is background
	backgroundBias	: bias for background
	noPriorBelow	: don't bias the background if edge indicator is below this value
[out]	labels	: resulting nodeLabeling (not necessarily dense)

void vigra::felzenszwalbSegmentation	(	const GRAPH &	graph,
		const EDGE_WEIGHTS &	edgeWeights,
		const NODE_SIZE &	nodeSizes,
		float	k,
		NODE_LABEL_MAP &	nodeLabeling,
		const int	nodeNumStopCond = `-1`
	)

edge weighted watersheds Segmentataion

Parameters

	graph	input graph
	edgeWeights	: edge weights / edge indicator
	nodeSizes	: size of each node
	k	: free parameter of felzenszwalb algorithm
[out]	nodeLabeling	: nodeLabeling (not necessarily dense)
	nodeNumStopCond	: optional stopping condition

void vigra::graphSmoothing	(	const GRAPH &	g,
		const NODE_FEATURES_IN &	nodeFeaturesIn,
		const EDGE_INDICATOR &	edgeIndicator,
		const float	lambda,
		const float	edgeThreshold,
		const float	scale,
		NODE_FEATURES_OUT &	nodeFeaturesOut
	)

smooth node features of a graph

Parameters

	g	: input graph
	nodeFeaturesIn	: input node features which should be smoothed
	edgeIndicator	: edge indicator to indicate over which edges one should smooth
	lambda	: scale edge indicator by lambda before taking negative exponent
	edgeThreshold	: edge threshold
	scale	: how much smoothing should be applied
[out]	nodeFeaturesOut	: smoothed node features

void vigra::recursiveGraphSmoothing	(	const GRAPH &	g,
		const NODE_FEATURES_IN &	nodeFeaturesIn,
		const EDGE_INDICATOR &	edgeIndicator,
		const float	lambda,
		const float	edgeThreshold,
		const float	scale,
		size_t	iterations,
		NODE_FEATURES_OUT &	nodeFeaturesBuffer,
		NODE_FEATURES_OUT &	nodeFeaturesOut
	)

smooth node features of a graph

Parameters

	g	: input graph
	nodeFeaturesIn	: input node features which should be smoothed
	edgeIndicator	: edge indicator to indicate over which edges one should smooth
	lambda	: scale edge indicator by lambda before taking negative exponent
	edgeThreshold	: edge threshold
	scale	: how much smoothing should be applied
	iterations	: how often should this algorithm be called recursively
[out]	nodeFeaturesBuffer	: preallocated(!) buffer to store node features temp.
[out]	nodeFeaturesOut	: smoothed node features

void vigra::projectGroundTruth	(	const RAG &	rag,
		const BASE_GRAPH &	baseGraph,
		const BASE_GRAPH_RAG_LABELS &	baseGraphRagLabels,
		const BASE_GRAPH_GT &	baseGraphGt,
		RAG_GT &	ragGt,
		RAG_GT_QT &
	)

project ground truth from a base graph, to a region adjacency graph.

MultiArray<2, MultiArrayIndex> vigra::ragFindEdges	(	const RAGGRAPH &	rag,
		const GRAPH &	graph,
		const RAGEDGES &	affiliatedEdges,
		MultiArrayView< N, T >	labelsArray,
		const typename RAGGRAPH::Node &	node
	)

Find indices of points on the edges.

Parameters

rag	: Region adjacency graph of the labels array
graph	: Graph of labels array
affiliatedEdges	: The affiliated edges of the region adjacency graph
labelsArray	: The label image
node	: The node (of the region adjacency graph), whose edges shall be found

void vigra::edgeWeightsFromNodeWeights	(	const GridGraph< N, DirectedTag > &	g,
		const NODEMAP &	nodeWeights,
		EDGEMAP &	edgeWeights,
		bool	euclidean,
		FUNCTOR const &	func
	)

create edge weights from node weights

Parameters

	g	: input graph
	nodeWeights	: node property map holding node weights
[out]	edgeWeights	: resulting edge weights
	euclidean	: if 'true', multiply the computed weights with the Euclidean distance between the edge's end nodes (default: 'false')
	func	: binary function that computes the edge weight from the weights of the edge's end nodes (default: take the average)

void vigra::edgeWeightsFromInterpolatedImage	(	const GridGraph< N, DirectedTag > &	g,
		const MultiArrayView< N, T > &	interpolatedImage,
		EDGEMAP &	edgeWeights,
		bool	euclidean = `false`
	)

create edge weights from an interpolated image

Parameters

	g	: input graph
	interpolatedImage	: interpolated image
[out]	edgeWeights	: edge weights
	euclidean	: if 'true', multiply the weights with the Euclidean distance between the edge's end nodes (default: 'false')

For each edge, the function reads the weight from interpolatedImage[u+v], where u and v are the coordinates of the edge's end points.

void vigra::hierarchicalClustering ( ... )

Reduce the number of nodes in a graph by iteratively contracting the cheapest edge.

Declarations:

namespace vigra {
    template <class GRAPH,
              class EDGE_WEIGHT_MAP,  class EDGE_LENGTH_MAP,
              class NODE_FEATURE_MAP, class NOSE_SIZE_MAP,
              class NODE_LABEL_MAP>
    void
    hierarchicalClustering(GRAPH const & graph,
                           EDGE_WEIGHT_MAP const & edgeWeights, EDGE_LENGTH_MAP const & edgeLengths,
                           NODE_FEATURE_MAP const & nodeFeatures, NOSE_SIZE_MAP const & nodeSizes,
                           NODE_LABEL_MAP & labelMap,
                           ClusteringOptions options = ClusteringOptions());
}

Hierarchical clustering is a simple and versatile image segmentation algorithm that typically operates either directly on the pixels (e.g. on a vigra::GridGraph) or on a region adjacency graph over suitable superpixels (e.g. on an vigra::AdjacencyListGraph). The graph is passed to the function in its first argument. After clustering is completed, the parameter labelMap contains a mapping from original node IDs to the ID of the cluster each node belongs to. Cluster IDs correspond to the ID of an arbitrarily chosen representative node within each cluster, i.e. they form a sparse subset of the original IDs.

Properties of the graph's edges and nodes are provided in the property maps edgeWeights, edgeLengths, nodeFeatures, and nodeSizes. These maps are indexed by edge or node ID and return the corresponding feature. Features must by arithmetic scalars or, in case of node features, scalars or vectors of scalars (precisely: objects that provide begin() and end() to create an STL range). Edge weights are typically derived from an edge indicator such as the gradient magnitude, and node features are either the responses of a filter family (when clustering on the pixel grid), or region statistics as computed by Feature Accumulators (when clustering on superpixels).

In each step, the algorithm merges the two nodes $u$ and $v$ whose cluster distance is smallest, where the cluster distance is defined as

$d_{uv} = \left( (1-\beta) w_{uv} + \beta || f_u - f_v ||_M \right) \cdot \frac{2}{s_u^{-\omega} + s_v^{-\omega}}$

with $w_{uv}$ denoting the weight of edge $uv$ , $f_u$ and $f_v$ being the node features (possibly vectors to be compared with metric $M$ ), and $s_u$ and $s_v$ the corresponding node sizes. The metric is defined in the option object by calling vigra::ClusteringOptions::nodeFeatureMetric() and must be selected from the tags defined in vigra::metrics::MetricType.

The parameters $0 \le \beta \le 1$ and $0 \le \omega \le 1$ control the relative influence of the inputs: With $\beta = 0$ , the node features are ignored, whereas with $\beta = 1$ the edge weights are ignored. Similarly, with $\omega = 0$ , the node size is ignored, whereas with $\omega = 1$ , cluster distances are scaled by the harmonic mean of the cluster sizes, making the merging of small clusters more favorable. The parameters are defined in the option object by calling vigra::ClusteringOptions::nodeFeatureImportance() and vigra::ClusteringOptions::sizeImportance() respectively.

After each merging step, the features of the resulting cluster $z$ and the weights of its outgoing edges are updated by mean of the corresponding properties of the original clusters $u$ and $v$ , weighted by the respective node sizes $s_z$ and edge lengths $l_{zy}$ :

$\begin{eqnarray*} s_z & = & s_u + s_v \\ f_z & = & \frac{s_u f_u + s_v f_v}{s_z} \\ l_{zy} & = & l_{uy} + l_{vy} \textrm{ for all nodes }y\textrm{ connected to }u\textrm{ or }v \\ w_{zy} & = & \frac{l_{uy} w_{uy} + l_{vy} w_{vy}}{l_{zy}} \end{eqnarray*}$

Clustering normally stops when only one cluster remains. This default can be overridden by the option object parameters vigra::ClusteringOptions::minRegionCount() and vigra::ClusteringOptions::maxMergeDistance() to stop at a particular number of clusters or a particular cluster distance respectively.

Usage:

#include <vigra/hierarchical_clustering.hxx>
Namespace: vigra

A fully worked example can be found in graph_agglomerative_clustering.cxx

Examples:: graph_agglomerative_clustering.cxx.

Classes
class	AdjacencyListGraph
	undirected adjacency list graph in the LEMON API More...

class	BinaryForest
	BinaryForest stores a collection of rooted binary trees. More...

class	ClusteringOptions
	Options object for hierarchical clustering. More...

class	GridGraph< N, DirectedTag >
	Define a grid graph in arbitrary dimensions. More...

class	ShortestPathDijkstra< GRAPH, WEIGHT_TYPE >
	shortest path computer More...

Functions
Arc	addArc (Node const &u, Node const &v)
	Add a new arc from node u to node v. The arc ID is `2id(u)` if v is the left child of u, `2id(u)+1` otherwise.

Node	addNode ()
	Add a new node (its node ID will be selected automatically).

Arc	arcFromId (index_type const &id) const
	Get arc descriptor for id.

	BinaryForest ()
	Create an empty forest.

template<class GRAPH , class EDGE_WEIGHTS , class SEEDS , class LABELS >
void	carvingSegmentation (const GRAPH &g, const EDGE_WEIGHTS &edgeWeights, const SEEDS &seeds, const typename LABELS::Value backgroundLabel, const typename EDGE_WEIGHTS::Value backgroundBias, const typename EDGE_WEIGHTS::Value noPriorBelow, LABELS &labels)
	edge weighted watersheds Segmentataion More...

template<class G , class A , class B >
void	copyEdgeMap (const G &g, const A &a, B &b)
	copy a lemon edge map

template<class G , class A , class B >
void	copyNodeMap (const G &g, const A &a, B &b)
	copy a lemon node map

template<class GRAPH , class WEIGHTS , class COMPERATOR >
void	edgeSort (const GRAPH &g, const WEIGHTS &weights, const COMPERATOR &comperator, std::vector< typename GRAPH::Edge > &sortedEdges)
	get a vector of Edge descriptors More...

template<class GRAPH , class EDGE_WEIGHTS , class SEEDS , class LABELS >
void	edgeWeightedWatershedsSegmentation (const GRAPH &g, const EDGE_WEIGHTS &edgeWeights, const SEEDS &seeds, LABELS &labels)
	edge weighted watersheds Segmentataion More...

template<unsigned int N, class DirectedTag , class T , class EDGEMAP >
void	edgeWeightsFromInterpolatedImage (const GridGraph< N, DirectedTag > &g, const MultiArrayView< N, T > &interpolatedImage, EDGEMAP &edgeWeights, bool euclidean=false)
	create edge weights from an interpolated image More...

template<unsigned int N, class DirectedTag , class NODEMAP , class EDGEMAP , class FUNCTOR >
void	edgeWeightsFromNodeWeights (const GridGraph< N, DirectedTag > &g, const NODEMAP &nodeWeights, EDGEMAP &edgeWeights, bool euclidean, FUNCTOR const &func)
	create edge weights from node weights More...

template<class GRAPH , class EDGE_WEIGHTS , class NODE_SIZE , class NODE_LABEL_MAP >
void	felzenszwalbSegmentation (const GRAPH &graph, const EDGE_WEIGHTS &edgeWeights, const NODE_SIZE &nodeSizes, float k, NODE_LABEL_MAP &nodeLabeling, const int nodeNumStopCond=-1)
	edge weighted watersheds Segmentataion More...

template<class G , class A , class T >
void	fillEdgeMap (const G &g, A &a, const T &value)
	fill a lemon edge map

template<class G , class A , class T >
void	fillNodeMap (const G &g, A &a, const T &value)
	fill a lemon node map

Node	getChild (Node const &node, size_t i=0) const
	Get child number i of node. Returns the left child if `i=0`, the right child if `i=1`, and `lemon::INVALID` for other values of i or when the respective is undefined.

Node	getNode (size_t i) const
	Create node cescriptor for ID i, or `lemon::INVALID` if i is not a valid ID.

Node	getParent (Node const &node, size_t i=0) const
	Get the parent node descriptor of node, or `lemon::INVALID` if node is a root or i is non-zero.

Node	getRoot (size_t i=0) const
	Get the root node descriptor of tree i in the forest, or `lemon::INVALID` if i is invalid.

template<class GRAPH , class NODE_FEATURES_IN , class EDGE_INDICATOR , class NODE_FEATURES_OUT >
void	graphSmoothing (const GRAPH &g, const NODE_FEATURES_IN &nodeFeaturesIn, const EDGE_INDICATOR &edgeIndicator, const float lambda, const float edgeThreshold, const float scale, NODE_FEATURES_OUT &nodeFeaturesOut)
	smooth node features of a graph More...

template<... >
void	hierarchicalClustering (...)
	Reduce the number of nodes in a graph by iteratively contracting the cheapest edge. More...

index_type	id (Node const &node) const
	Get ID for node descriptor node.

index_type	id (Arc const &arc) const
	Get ID for arc descriptor arc.

size_t	inDegree (Node const &node) const
	Return the number of incoming edges of node. `0` for a root node, `1` otherwise.

template<class GRAPH_IN , class GRAPH_IN_NODE_LABEL_MAP >
void	makeRegionAdjacencyGraph (GRAPH_IN graphIn, GRAPH_IN_NODE_LABEL_MAP labels, AdjacencyListGraph &rag, typename AdjacencyListGraph::template EdgeMap< std::vector< typename GRAPH_IN::Edge > > &affiliatedEdges, const Int64 ignoreLabel=-1)
	make a region adjacency graph from a graph and labels w.r.t. that graph More...

index_type	maxArcId () const
	Return the highest possible arc ID (equivalent to `2*maxNodeId() + 1`).

index_type	maxNodeId () const
	Return the highest existing node ID.

size_t	merge (BinaryForest const &other)
	Merge two forests and increase the IDs of other to avoid ID clashes. The function returns the offset that has been added to these IDs.

Node	nodeFromId (index_type const &id) const
	Get node descriptor for id.

size_t	numArcs () const
	Return the number of arcs. Always less than `maxArcId()` because not all arcs actually exist.

size_t	numChildren (Node const &node) const
	Return the number of children of node (equivalent to `outDegree()`).

size_t	numNodes () const
	Return the number of nodes (equivalent to `maxNodeId()+1`).

size_t	numParents (Node const &node) const
	Return the number of parents of node (equivalent to `inDegree()`).

size_t	numRoots () const
	Return the number of trees in the forest.

size_t	outDegree (Node const &node) const
	Return the number of outgoing edges of node. `0` for a leaf node, `1` or `2` otherwise.

template<class NODE , class PREDECESSORS >
size_t	pathLength (const NODE source, const NODE target, const PREDECESSORS &predecessors)
	get the length in node units of a path

template<class RAG , class BASE_GRAPH , class BASE_GRAPH_RAG_LABELS , class BASE_GRAPH_GT , class RAG_GT , class RAG_GT_QT >
void	projectGroundTruth (const RAG &rag, const BASE_GRAPH &baseGraph, const BASE_GRAPH_RAG_LABELS &baseGraphRagLabels, const BASE_GRAPH_GT &baseGraphGt, RAG_GT &ragGt, RAG_GT_QT &)

template<class RAGGRAPH , class GRAPH , class RAGEDGES , unsigned int N, class T >
MultiArray< 2, MultiArrayIndex >	ragFindEdges (const RAGGRAPH &rag, const GRAPH &graph, const RAGEDGES &affiliatedEdges, MultiArrayView< N, T > labelsArray, const typename RAGGRAPH::Node &node)
	Find indices of points on the edges. More...

template<class GRAPH , class NODE_FEATURES_IN , class EDGE_INDICATOR , class NODE_FEATURES_OUT >
void	recursiveGraphSmoothing (const GRAPH &g, const NODE_FEATURES_IN &nodeFeaturesIn, const EDGE_INDICATOR &edgeIndicator, const float lambda, const float edgeThreshold, const float scale, size_t iterations, NODE_FEATURES_OUT &nodeFeaturesBuffer, NODE_FEATURES_OUT &nodeFeaturesOut)
	smooth node features of a graph More...

template<class GRAPH , class WEIGHTS , class PREDECESSORS , class DISTANCE , class HEURSTIC >
void	shortestPathAStar (const GRAPH &graph, const typename GRAPH::Node &source, const typename GRAPH::Node &target, const WEIGHTS &weights, PREDECESSORS &predecessors, DISTANCE &distance, const HEURSTIC &heuristic)
	Astar Shortest path search.

Node	source (Arc const &arc) const
	Find start node of arc.

Node	target (Arc const &arc) const
	Find end node of arc.

bool	valid (Node const &node) const
	Check if node exists.

bool	valid (Arc const &arc) const
	Check if arc exists.