[ VIGRA Homepage | Function Index | Class Index | Namespaces | File List | Main Page ]
![]() |
Graph Data Structures and Algorithms | ![]() |
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) ). | |
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
.
AdjacencyListGraph | ( | const size_t | nodes = 0 , |
const size_t | edges = 0 |
||
) |
construct
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
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
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
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
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
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
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
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
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) |
html generated using doxygen and Python
|