Graph Data Structures and Algorithms

Classes

class AdjacencyListGraph

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

class GridGraph< N, DirectedTag >

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

class ShortestPathDijkstra< GRAPH, WEIGHT_TYPE >

shortest path computer More...

Functions

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

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

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 &ragGtQt)

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.

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

◆ edgeSort()

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

◆ makeRegionAdjacencyGraph()

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)

◆ edgeWeightedWatershedsSegmentation()

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)

◆ carvingSegmentation()

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)

◆ felzenszwalbSegmentation()

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

◆ graphSmoothing()

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

◆ recursiveGraphSmoothing()

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

◆ projectGroundTruth()

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 &	ragGtQt
	)

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

◆ ragFindEdges()

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

◆ edgeWeightsFromNodeWeights()

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)

◆ edgeWeightsFromInterpolatedImage()

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.

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

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

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

Functions
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

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

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 &ragGtQt)

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.