[ VIGRA Homepage | Function Index | Class Index | Namespaces | File List | Main Page ]

details Graph Data Structures and Algorithms VIGRA

Classes

class  AdjacencyListGraph
 undirected adjacency list graph in the LEMON API More...
 
struct  AdjacencyListGraph::ArcMap< T >
 default arc map More...
 
struct  AdjacencyListGraph::EdgeMap< T >
 default edge map More...
 
class  GridGraph< N, DirectedTag >
 Define a grid graph in arbitrary dimensions. More...
 
struct  AdjacencyListGraph::NodeMap< T >
 default node map More...
 
class  ShortestPathDijkstra< GRAPH, WEIGHT_TYPE >
 shortest path computer More...
 

Typedefs

typedef detail::GenericArc
< index_type > 
Arc
 arc descriptor
 
typedef
detail_adjacency_list_graph::ArcIt
< GraphType > 
ArcIt
 arc iterator
 
typedef detail::GenericEdge
< index_type > 
Edge
 edge descriptor
 
typedef
detail_adjacency_list_graph::ItemIter
< GraphType, Edge > 
EdgeIt
 edge iterator
 
typedef
detail::GenericIncEdgeIt
< GraphType, NodeStorage,
InFlter > 
InArcIt
 incoming arc iterator
 
typedef
detail::GenericIncEdgeIt
< GraphType, NodeStorage,
IncFilter > 
IncEdgeIt
 incident edge iterator
 
typedef detail::GenericNode
< index_type > 
Node
 node descriptor
 
typedef
detail_adjacency_list_graph::ItemIter
< GraphType, Node > 
NodeIt
 node iterator
 
typedef
detail::GenericIncEdgeIt
< GraphType, NodeStorage,
OutFilter > 
OutArcIt
 outgoing arc iterator
 
typedef
detail::GenericIncEdgeIt
< GraphType, NodeStorage,
BackOutFilter > 
OutBackArcIt
 outgoing back arc iterator
 

Functions

 AdjacencyListGraph (const size_t nodes=0, const size_t edges=0)
 
Arc arcFromId (const index_type id) const
 Get arc descriptor for given node ID i (API: LEMON). Return Arc(lemon::INVALID) when the ID does not exist in this graph.
 
index_type arcNum () const
 Get the number of arcs in this graph (API: LEMON).
 
Node baseNode (const IncEdgeIt &iter) const
 Return the start node of the edge the given iterator is referring to (API: LEMON).
 
Node baseNode (const OutArcIt &iter) const
 Return the start node of the edge the given iterator is referring to (API: LEMON).
 
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, 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
 
Arc direct (const Edge &edge, const bool forward) const
 Create an arc for the given edge e, oriented along the edge's natural (forward = true) or reversed (forward = false) direction (API: LEMON).
 
Arc direct (const Edge &edge, const Node &node) const
 Create an arc for the given edge e oriented so that node n is the starting node of the arc (API: LEMON), or return lemon::INVALID if the edge is not incident to this node.
 
bool direction (const Arc &arc) const
 Return true when the arc is looking on the underlying edge in its natural (i.e. forward) direction, false otherwise (API: LEMON).
 
Edge edgeFromId (const index_type id) const
 Get edge descriptor for given node ID i (API: LEMON). Return Edge(lemon::INVALID) when the ID does not exist in this graph.
 
index_type edgeNum () const
 Get the number of edges in this graph (API: LEMON).
 
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
 
Arc findArc (const Node &u, const Node &v) const
 Get a descriptor for the arc connecting vertices u and v,
or lemon::INVALID if no such edge exists (API: LEMON).
 
Edge findEdge (const Node &a, const Node &b) const
 Get a descriptor for the edge connecting vertices u and v,
or lemon::INVALID if no such edge exists (API: LEMON).
 
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...
 
index_type id (const Node &node) const
 Get the ID for node desciptor v (API: LEMON).
 
index_type id (const Edge &edge) const
 Get the ID for edge desciptor v (API: LEMON).
 
index_type id (const Arc &arc) const
 Get the ID for arc desciptor v (API: LEMON).
 
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
 Get the maximum ID of any edge in arc graph (API: LEMON).
 
index_type maxEdgeId () const
 Get the maximum ID of any edge in this graph (API: LEMON).
 
index_type maxNodeId () const
 Get the maximum ID of any node in this graph (API: LEMON).
 
Node nodeFromId (const index_type id) const
 Get node descriptor for given node ID i (API: LEMON). Return Node(lemon::INVALID) when the ID does not exist in this graph.
 
index_type nodeNum () const
 Get the number of nodes in this graph (API: LEMON).
 
Node oppositeNode (Node const &n, const Edge &e) const
 Return the opposite node of the given node n along edge e (API: LEMON), or return lemon::INVALID if the edge is not incident to this node.
 
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 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...
 
Node runningNode (const IncEdgeIt &iter) const
 Return the end node of the edge the given iterator is referring to (API: LEMON).
 
Node runningNode (const OutArcIt &iter) const
 Return the end node of the edge the given iterator is referring to (API: LEMON).
 
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 (const Arc &arc) const
 Get the start node of the given arc a (API: LEMON).
 
Node target (const Arc &arc) const
 Get the end node of the given arc a (API: LEMON).
 
Node u (const Edge &edge) const
 Get the start node of the given edge e (API: LEMON,
the boost::graph API provides the free function boost::source(e, graph)).
 
Node v (const Edge &edge) const
 Get the end node of the given edge e (API: LEMON,
the boost::graph API provides the free function boost::target(e, graph)).
 

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.

See also the GridGraph additions to namespace boost.

Function Documentation

AdjacencyListGraph ( const size_t  nodes = 0,
const size_t  edges = 0 
)

construct

Parameters
nodes: reserve space for n nodes
edges: reserve space for n edges
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)
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,
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
[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 bevore 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 bevore 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 &  ragGtQt 
)

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

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.

© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de)
Heidelberg Collaboratory for Image Processing, University of Heidelberg, Germany

html generated using doxygen and Python
vigra 1.10.0 (Thu Jan 8 2015)