40#ifndef VIGRA_GRAPH_ALGORITHMS_HXX
41#define VIGRA_GRAPH_ALGORITHMS_HXX
52#include "graph_generalization.hxx"
53#include "multi_gridgraph.hxx"
54#include "priority_queue.hxx"
55#include "union_find.hxx"
56#include "adjacency_list_graph.hxx"
57#include "graph_maps.hxx"
63#include "functorexpression.hxx"
64#include "array_vector.hxx"
72 namespace detail_graph_algorithms{
73 template <
class GRAPH_MAP,
class COMPERATOR>
74 struct GraphItemCompare
77 GraphItemCompare(
const GRAPH_MAP & map,
const COMPERATOR & comperator)
79 comperator_(comperator){
84 bool operator()(
const KEY & a,
const KEY & b)
const{
85 return comperator_(map_[a],map_[b]);
88 const GRAPH_MAP & map_;
89 const COMPERATOR & comperator_;
97 template<
class GRAPH,
class WEIGHTS,
class COMPERATOR>
106 for(
typename GRAPH::EdgeIt e(g);e!=lemon::INVALID;++e){
116 template<
class G,
class A,
class B>
118 typename G::NodeIt iter(g);
119 while(iter!=lemon::INVALID){
126 template<
class G,
class A,
class B>
128 typename G::EdgeIt iter(g);
129 while(iter!=lemon::INVALID){
135 template<
class G,
class A,
class T>
137 typename G::NodeIt iter(g);
138 while(iter!=lemon::INVALID){
144 template<
class G,
class A,
class T>
146 typename G::EdgeIt iter(g);
147 while(iter!=lemon::INVALID){
163 class GRAPH_IN_NODE_LABEL_MAP
169 typename AdjacencyListGraph:: template EdgeMap< std::vector<typename GRAPH_IN::Edge> > &
affiliatedEdges,
170 const Int64 ignoreLabel=-1
173 typedef typename GraphMapTypeTraits<GRAPH_IN_NODE_LABEL_MAP>::Value LabelType;
184 const LabelType
l=labels[*iter];
185 if(ignoreLabel==-1 ||
static_cast<Int64>(
l)!=ignoreLabel)
191 const LabelType
lu = labels[
graphIn.u(edge)];
192 const LabelType
lv = labels[
graphIn.v(edge)];
193 if(
lu!=
lv && ( ignoreLabel==-1 || (
static_cast<Int64>(
lu)!=ignoreLabel &&
static_cast<Int64>(
lv)!=ignoreLabel) ) ){
203 const LabelType
lu = labels[
graphIn.u(edge)];
204 const LabelType
lv = labels[
graphIn.v(edge)];
206 if(
lu!=
lv && ( ignoreLabel==-1 || (
static_cast<Int64>(
lu)!=ignoreLabel &&
static_cast<Int64>(
lv)!=ignoreLabel) ) ){
216 template<
unsigned int DIM,
class DTAG,
class AFF_EDGES>
217 size_t affiliatedEdgesSerializationSize(
218 const GridGraph<DIM,DTAG> &,
219 const AdjacencyListGraph & rag,
220 const AFF_EDGES & affEdges
227 for(EdgeIt iter(rag); iter!=lemon::INVALID; ++iter){
230 size+=affEdges[e].size()*(DIM+1);
235 template<
class OUT_ITER,
unsigned int DIM,
class DTAG,
class AFF_EDGES>
236 void serializeAffiliatedEdges(
237 const GridGraph<DIM,DTAG> &,
238 const AdjacencyListGraph & rag,
239 const AFF_EDGES & affEdges,
247 for(EdgeIt iter(rag); iter!=lemon::INVALID; ++iter){
249 const Edge edge = *iter;
250 const size_t numAffEdge = affEdges[edge].size();
251 *outIter = numAffEdge; ++outIter;
253 for(
size_t i=0; i<numAffEdge; ++i){
254 const GEdge gEdge = affEdges[edge][i];
255 for(
size_t d=0; d<DIM+1; ++d){
256 *outIter = gEdge[d]; ++outIter;
262 template<
class IN_ITER,
unsigned int DIM,
class DTAG,
class AFF_EDGES>
263 void deserializeAffiliatedEdges(
264 const GridGraph<DIM,DTAG> &,
265 const AdjacencyListGraph & rag,
266 AFF_EDGES & affEdges,
275 affEdges.assign(rag);
277 for(EdgeIt iter(rag); iter!=lemon::INVALID; ++iter){
279 const Edge edge = *iter;
280 const size_t numAffEdge = *begin; ++begin;
282 for(
size_t i=0; i<numAffEdge; ++i){
284 for(
size_t d=0; d<DIM+1; ++d){
285 gEdge[d]=*begin; ++begin;
287 affEdges[edge].push_back(gEdge);
296 template<
class GRAPH,
class WEIGHT_TYPE>
301 typedef typename Graph::Node Node;
302 typedef typename Graph::NodeIt NodeIt;
303 typedef typename Graph::Edge Edge;
304 typedef typename Graph::OutArcIt OutArcIt;
308 typedef typename Graph:: template
NodeMap<Node> PredecessorsMap;
315 pq_(g.maxNodeId()+1),
333 template<
class WEIGHTS>
335 const Node &
target = lemon::INVALID,
338 this->initializeMaps(
source);
355 template<
class WEIGHTS>
356 void run(Node
const & start, Node
const & stop,
358 const Node &
target = lemon::INVALID,
362 "ShortestPathDijkstra::run(): source is not within ROI");
363 vigra_precondition(
target == lemon::INVALID ||
365 "ShortestPathDijkstra::run(): target is not within ROI");
366 this->initializeMaps(
source, start, stop);
376 template<
class WEIGHTS>
378 const Node &
target = lemon::INVALID,
381 this->reInitializeMaps(
source);
389 template<
class WEIGHTS,
class ITER>
392 const Node &
target = lemon::INVALID,
404 template<
class EFGE_WEIGHTS,
class NODE_WEIGHTS,
class ITER>
411 const Node &
target = lemon::INVALID,
433 return target_!=lemon::INVALID;
438 return discoveryOrder_;
459 template<
class WEIGHTS>
460 void runImpl(
const WEIGHTS & weights,
461 const Node &
target = lemon::INVALID,
462 WeightType
maxDistance=NumericTraits<WeightType>::max())
469 template<
class EDGE_WEIGHTS,
class NODE_WEIGHTS>
470 void runImplWithNodeWeights(
471 const EDGE_WEIGHTS & edgeWeights,
472 const NODE_WEIGHTS & nodeWeights,
473 const Node &
target = lemon::INVALID,
474 WeightType maxDistance=NumericTraits<WeightType>::max())
476 target_ = lemon::INVALID;
477 while(!pq_.
empty() ){
478 const Node topNode(graph_.nodeFromId(pq_.
top()));
479 if(distMap_[topNode] > maxDistance)
482 discoveryOrder_.push_back(topNode);
486 for(OutArcIt outArcIt(graph_,topNode);outArcIt!=lemon::INVALID;++outArcIt){
487 const Node otherNode = graph_.target(*outArcIt);
488 const size_t otherNodeId = graph_.id(otherNode);
489 const WeightType otherNodeWeight = nodeWeights[otherNode];
491 const Edge edge(*outArcIt);
492 const WeightType currentDist = distMap_[otherNode];
493 const WeightType alternativeDist = distMap_[topNode]+edgeWeights[edge]+otherNodeWeight;
494 if(alternativeDist<currentDist){
495 pq_.
push(otherNodeId,alternativeDist);
496 distMap_[otherNode]=alternativeDist;
497 predMap_[otherNode]=topNode;
500 else if(predMap_[otherNode]==lemon::INVALID){
501 const Edge edge(*outArcIt);
502 const WeightType initialDist = distMap_[topNode]+edgeWeights[edge]+otherNodeWeight;
503 if(initialDist<=maxDistance)
505 pq_.
push(otherNodeId,initialDist);
506 distMap_[otherNode]=initialDist;
507 predMap_[otherNode]=topNode;
512 while(!pq_.
empty() ){
513 const Node topNode(graph_.nodeFromId(pq_.
top()));
514 predMap_[topNode]=lemon::INVALID;
518 target_ = discoveryOrder_.
back();
522 void initializeMaps(Node
const &
source){
523 for(NodeIt n(graph_); n!=lemon::INVALID; ++n){
525 predMap_[node]=lemon::INVALID;
527 distMap_[
source]=
static_cast<WeightType
>(0.0);
529 discoveryOrder_.clear();
534 void initializeMaps(Node
const &
source,
535 Node
const & start, Node
const & stop)
537 Node left_border = min(start, Node(1)),
538 right_border = min(predMap_.shape()-stop, Node(1)),
539 DONT_TOUCH = Node(lemon::INVALID) - Node(1);
542 left_border, right_border, DONT_TOUCH);
543 predMap_.subarray(start, stop) = lemon::INVALID;
546 distMap_[
source]=
static_cast<WeightType
>(0.0);
547 discoveryOrder_.clear();
552 template <
class ITER>
553 void initializeMapsMultiSource(ITER
source, ITER source_end){
554 for(NodeIt n(graph_); n!=lemon::INVALID; ++n){
556 predMap_[node]=lemon::INVALID;
558 discoveryOrder_.clear();
561 distMap_[*
source]=
static_cast<WeightType
>(0.0);
565 source_=lemon::INVALID;
568 void reInitializeMaps(Node
const &
source){
569 for(
unsigned int n=0; n<discoveryOrder_.
size(); ++n){
570 predMap_[discoveryOrder_[n]]=lemon::INVALID;
572 distMap_[
source]=
static_cast<WeightType
>(0.0);
574 discoveryOrder_.clear();
579 const Graph & graph_;
581 PredecessorsMap predMap_;
582 DistanceMap distMap_;
583 DiscoveryOrder discoveryOrder_;
590 template<
class NODE,
class PREDECESSORS>
596 if(predecessors[target]==lemon::INVALID)
610 template<
class GRAPH,
class WEIGHTS,
class PREDECESSORS,
class DISTANCE,
class HEURSTIC>
613 const typename GRAPH::Node & source,
614 const typename GRAPH::Node & target,
622 typedef typename Graph::Edge Edge;
623 typedef typename Graph::Node Node;
624 typedef typename Graph::NodeIt NodeIt;
625 typedef typename Graph::OutArcIt OutArcIt;
626 typedef typename DISTANCE::value_type DistanceType;
631 for(NodeIt n(graph);n!=lemon::INVALID;++n){
634 distance[node]=std::numeric_limits<DistanceType>::infinity();
635 predecessors[node]=lemon::INVALID;
638 distance[source]=
static_cast<DistanceType
>(0.0);
670 const DistanceType
tenativeScore = distance[current] + weights[edge];
695 void shortestPathSegmentation(
697 const EDGE_WEIGHTS & edgeWeights,
698 const NODE_WEIGHTS & nodeWeights,
699 SEED_NODE_MAP & seeds
703 typedef typename Graph::Node Node;
704 typedef typename Graph::NodeIt NodeIt;
705 typedef WEIGHT_TYPE WeightType;
708 std::vector<Node> seededNodes;
709 for(NodeIt n(graph);n!=lemon::INVALID;++n){
713 seededNodes.push_back(node);
718 typedef ShortestPathDijkstra<Graph, WeightType> Sp;
719 typedef typename Sp::PredecessorsMap PredecessorsMap;
721 sp.runMultiSource(edgeWeights, nodeWeights, seededNodes.begin(), seededNodes.end());
722 const PredecessorsMap & predMap = sp.predecessors();
724 for(NodeIt n(graph);n!=lemon::INVALID;++n){
727 Node pred=predMap[node];
728 while(seeds[pred]==0){
731 seeds[node]=seeds[pred];
736 namespace detail_watersheds_segmentation{
738 struct RawPriorityFunctor{
739 template<
class LabelType,
class T>
740 T operator()(
const LabelType ,
const T priority)
const{
747 template<
class PRIORITY_TYPE,
class LABEL_TYPE>
748 struct CarvingFunctor{
749 CarvingFunctor(
const LABEL_TYPE backgroundLabel,
750 const PRIORITY_TYPE & factor,
751 const PRIORITY_TYPE & noPriorBelow
753 : backgroundLabel_(backgroundLabel),
755 noPriorBelow_(noPriorBelow){
757 PRIORITY_TYPE operator()(
const LABEL_TYPE label,
const PRIORITY_TYPE priority)
const{
758 if(priority>=noPriorBelow_)
759 return (label==backgroundLabel_ ? priority*factor_ : priority);
764 LABEL_TYPE backgroundLabel_;
765 PRIORITY_TYPE factor_;
766 PRIORITY_TYPE noPriorBelow_;
774 class PRIORITY_MANIP_FUNCTOR,
777 void edgeWeightedWatershedsSegmentationImpl(
779 const EDGE_WEIGHTS & edgeWeights,
781 PRIORITY_MANIP_FUNCTOR & priorManipFunctor,
785 typedef typename Graph::Edge Edge;
786 typedef typename Graph::Node Node;
787 typedef typename Graph::NodeIt NodeIt;
788 typedef typename Graph::OutArcIt OutArcIt;
790 typedef typename EDGE_WEIGHTS::Value WeightType;
791 typedef typename LABELS::Value LabelType;
793 typedef PriorityQueue<Edge,WeightType,true> PQ;
802 for(NodeIt n(g);n!=lemon::INVALID;++n){
804 if(labels[node]!=
static_cast<LabelType
>(0)){
805 for(OutArcIt a(g,node);a!=lemon::INVALID;++a){
807 const Node neigbour=g.target(*a);
809 if(labels[neigbour]==
static_cast<LabelType
>(0)){
810 const WeightType priority = priorManipFunctor(labels[node],edgeWeights[edge]);
811 pq.push(edge,priority);
821 const Edge edge = pq.top();
824 const Node u = g.u(edge);
825 const Node v = g.v(edge);
826 const LabelType lU = labels[u];
827 const LabelType lV = labels[v];
831 throw std::runtime_error(
"both have no labels");
833 else if(lU!=0 && lV!=0){
838 const Node unlabeledNode = lU==0 ? u : v;
839 const LabelType label = lU==0 ? lV : lU;
842 labels[unlabeledNode] = label;
845 for(OutArcIt a(g,unlabeledNode);a!=lemon::INVALID;++a){
846 const Edge otherEdge(*a);
847 const Node targetNode=g.target(*a);
848 if(labels[targetNode] == 0){
850 const WeightType priority = priorManipFunctor(label,edgeWeights[otherEdge]);
851 pq.push(otherEdge,priority);
870 template<
class GRAPH,
class EDGE_WEIGHTS,
class SEEDS,
class LABELS>
877 detail_watersheds_segmentation::RawPriorityFunctor
fPriority;
891 template<
class GRAPH,
class EDGE_WEIGHTS,
class SEEDS,
class LABELS>
901 typedef typename EDGE_WEIGHTS::Value WeightType;
902 typedef typename LABELS::Value LabelType;
915 template<
class GRAPH ,
class EDGE_WEIGHTS,
class NODE_SIZE,
class NODE_LABEL_MAP>
925 typedef typename Graph::Edge Edge;
926 typedef typename Graph::Node Node;
928 typedef typename EDGE_WEIGHTS::Value WeightType;
952 size_t nodeNum = graph.nodeNum();
959 const size_t rui =
ufdArray.findIndex(graph.id(graph.u(e)));
960 const size_t rvi =
ufdArray.findIndex(graph.id(graph.v(e)));
961 const Node
ru = graph.nodeFromId(
rui);
962 const Node
rv = graph.nodeFromId(
rvi);
969 const WeightType
tauRu =
static_cast<WeightType
>(
k)/
static_cast<WeightType
>(
sizeRu);
970 const WeightType
tauRv =
static_cast<WeightType
>(
k)/
static_cast<WeightType
>(
sizeRv);
1000 for(
typename GRAPH::NodeIt n(graph);n!=lemon::INVALID;++n){
1001 const Node node(*n);
1009 namespace detail_graph_smoothing{
1013 class NODE_FEATURES_IN,
1015 class WEIGHTS_TO_SMOOTH_FACTOR,
1016 class NODE_FEATURES_OUT
1018 void graphSmoothingImpl(
1020 const NODE_FEATURES_IN & nodeFeaturesIn,
1021 const EDGE_WEIGHTS & edgeWeights,
1022 WEIGHTS_TO_SMOOTH_FACTOR & weightsToSmoothFactor,
1023 NODE_FEATURES_OUT & nodeFeaturesOut
1026 typedef GRAPH Graph;
1027 typedef typename Graph::Edge Edge;
1028 typedef typename Graph::Node Node;
1029 typedef typename Graph::NodeIt NodeIt;
1030 typedef typename Graph::OutArcIt OutArcIt;
1032 typedef typename NODE_FEATURES_IN::Value NodeFeatureInValue;
1033 typedef typename NODE_FEATURES_OUT::Reference NodeFeatureOutRef;
1034 typedef typename EDGE_WEIGHTS::ConstReference SmoothFactorType;
1039 for(NodeIt n(g);n!=lemon::INVALID;++n){
1041 const Node node(*n);
1043 NodeFeatureInValue featIn = nodeFeaturesIn[node];
1044 NodeFeatureOutRef featOut = nodeFeaturesOut[node];
1047 float weightSum = 0.0;
1049 for(OutArcIt a(g,node);a!=lemon::INVALID;++a){
1050 const Edge edge(*a);
1051 const Node neigbour(g.target(*a));
1052 SmoothFactorType smoothFactor= weightsToSmoothFactor(edgeWeights[edge]);
1054 NodeFeatureInValue neighbourFeat = nodeFeaturesIn[neigbour];
1055 neighbourFeat*=smoothFactor;
1057 featOut = neighbourFeat;
1059 featOut += neighbourFeat;
1060 weightSum+=smoothFactor;
1064 featIn*=
static_cast<float>(degree);
1065 weightSum+=
static_cast<float>(degree);
1072 struct ExpSmoothFactor{
1073 ExpSmoothFactor(
const T lambda,
const T edgeThreshold,
const T scale)
1075 edgeThreshold_(edgeThreshold),
1078 T operator()(
const T weight){
1079 return weight> edgeThreshold_ ? 0 : std::exp(-1.0*lambda_*weight)*scale_;
1098 template<
class GRAPH,
class NODE_FEATURES_IN,
class EDGE_INDICATOR,
class NODE_FEATURES_OUT>
1108 detail_graph_smoothing::ExpSmoothFactor<float> functor(lambda,
edgeThreshold,scale);
1123 template<
class GRAPH,
class NODE_FEATURES_IN,
class EDGE_INDICATOR,
class NODE_FEATURES_OUT>
1136 iterations = std::max(
size_t(1),iterations);
1142 for(
size_t i=0;
i<iterations;++
i){
1158 template<
class GRAPH,
class NODE_MAP,
class EDGE_MAP>
1159 void nodeGtToEdgeGt(
1161 const NODE_MAP & nodeGt,
1162 const Int64 ignoreLabel,
1165 typedef typename GRAPH::Node Node;
1166 typedef typename GRAPH::EdgeIt EdgeIt;
1167 typedef typename GRAPH::Edge Edge;
1169 for(EdgeIt edgeIt(g); edgeIt!=lemon::INVALID; ++edgeIt){
1170 const Edge edge(*edgeIt);
1171 const Node u = g.u(edge);
1172 const Node v = g.v(edge);
1174 const Int64 lU =
static_cast<Int64>(nodeGt[u]);
1175 const Int64 lV =
static_cast<Int64>(nodeGt[v]);
1177 if(ignoreLabel==-1 || (lU!=ignoreLabel || lV!=ignoreLabel)){
1178 edgeGt[edge] = lU == lV ? 0 : 1;
1196 template<
class RAG,
class BASE_GRAPH,
class BASE_GRAPH_RAG_LABELS,
1197 class BASE_GRAPH_GT,
class RAG_GT,
class RAG_GT_QT>
1206 typedef typename BASE_GRAPH::Node BaseGraphNode;
1209 typedef typename RAG::Node
RagNode;
1211 typedef typename BASE_GRAPH_GT::Value
GtLabelType;
1215 typedef std::map<GtLabelType,UInt32>
MapType;
1216 typedef typename MapType::const_iterator
MapIter;
1267 template<
class RAGGRAPH,
class GRAPH,
class RAGEDGES,
unsigned int N,
class T>
1270 const GRAPH & graph,
1273 const typename RAGGRAPH::Node & node
1275 typedef typename GRAPH::Node Node;
1276 typedef typename GRAPH::Edge Edge;
1278 typedef typename RAGGRAPH::Edge
RagEdge;
1285 for (
RagOutArcIt iter(
rag, node); iter != lemon::INVALID; ++iter)
1299 coords = GraphDescriptorToMultiArrayIndex<GRAPH>::intrinsicNodeCoordinate(graph, u);
1303 coords = GraphDescriptorToMultiArrayIndex<GRAPH>::intrinsicNodeCoordinate(graph, v);
1307 vigra_precondition(
false,
"You should not come to this part of the code.");
1317 typedef typename std::set< NodeCoordinate >::iterator
setIter;
1338 template<
unsigned int N,
class DirectedTag,
1339 class NODEMAP,
class EDGEMAP,
class FUNCTOR>
1349 typedef typename Graph::Edge Edge;
1350 typedef typename Graph::EdgeIt EdgeIt;
1353 vigra_precondition(
nodeWeights.shape() == g.shape(),
1354 "edgeWeightsFromNodeWeights(): shape mismatch between graph and nodeWeights.");
1356 for (EdgeIt iter(g); iter!=lemon::INVALID; ++iter)
1358 const Edge edge(*iter);
1359 const CoordType
uCoord(g.u(edge));
1360 const CoordType
vCoord(g.v(edge));
1372 template<
unsigned int N,
class DirectedTag,
1373 class NODEMAP,
class EDGEMAP>
1376 const GridGraph<N, DirectedTag> & g,
1377 const NODEMAP & nodeWeights,
1378 EDGEMAP & edgeWeights,
1379 bool euclidean=
false)
1381 using namespace vigra::functor;
1406 typedef typename Graph::Edge Edge;
1407 typedef typename Graph::EdgeIt EdgeIt;
1411 "edgeWeightsFromInterpolatedImage(): interpolated shape must be shape*2-1");
1413 for (EdgeIt iter(g); iter!=lemon::INVALID; ++iter)
1415 const Edge edge(*iter);
1416 const CoordType
uCoord(g.u(edge));
1417 const CoordType
vCoord(g.v(edge));
1429 template<
class GRAPH>
1432 typedef typename GRAPH::Node Node;
1434 ThreeCycle(
const Node & a,
const Node & b,
const Node c){
1438 std::sort(nodes_, nodes_+3);
1440 bool operator < (
const ThreeCycle & other)
const{
1441 if(nodes_[0] < other.nodes_[0]){
1444 else if(nodes_[0] == other.nodes_[0]){
1445 if(nodes_[1] < other.nodes_[1]){
1448 else if(nodes_[1] == other.nodes_[1]){
1449 if(nodes_[2] < other.nodes_[2]){
1471 template<
class GRAPH>
1476 typedef typename GRAPH::Node Node;
1477 typedef typename GRAPH::Edge Edge;
1478 typedef typename GRAPH::EdgeIt EdgeIt;
1479 typedef typename GRAPH::OutArcIt OutArcIt;
1483 std::set< Cycle >
cycles;
1484 typedef typename std::set<Cycle>::const_iterator
SetIter;
1485 for (EdgeIt iter(g); iter!=lemon::INVALID; ++iter){
1486 const Edge edge(*iter);
1487 const Node u = g.u(edge);
1488 const Node v = g.v(edge);
1492 const Node w = g.target(*
outArcIt);
1494 const Edge e = g.findEdge(w,v);
1495 if(e != lemon::INVALID){
1506 const Cycle & c = *iter;
1507 for(
size_t j=0;
j<3; ++
j){
1514 template<
class GRAPH>
1515 void find3CyclesEdges(
1519 typedef typename GRAPH::Node Node;
1520 typedef typename GRAPH::Edge Edge;
1521 typedef typename GRAPH::EdgeIt EdgeIt;
1522 typedef typename GRAPH::OutArcIt OutArcIt;
1526 std::set< Cycle >
cycles;
1527 typedef typename std::set<Cycle>::const_iterator
SetIter;
1528 for (EdgeIt iter(g); iter!=lemon::INVALID; ++iter){
1529 const Edge edge(*iter);
1530 const Node u = g.u(edge);
1531 const Node v = g.v(edge);
1535 const Node w = g.target(*
outArcIt);
1537 const Edge e = g.findEdge(w,v);
1538 if(e != lemon::INVALID){
1549 const Cycle & c = *iter;
1550 const Node u = c.nodes_[0];
1551 const Node v = c.nodes_[1];
1552 const Node w = c.nodes_[2];
undirected adjacency list graph in the LEMON API
Definition adjacency_list_graph.hxx:228
detail_adjacency_list_graph::ItemIter< GraphType, Edge > EdgeIt
edge iterator
Definition adjacency_list_graph.hxx:253
detail::GenericEdge< index_type > Edge
edge descriptor
Definition adjacency_list_graph.hxx:249
size_type size() const
Definition array_vector.hxx:358
reference back()
Definition array_vector.hxx:321
const_reference top() const
get index with top priority
Definition priority_queue.hxx:490
void pop()
Remove the current top element.
Definition priority_queue.hxx:502
bool empty() const
check if the PQ is empty
Definition priority_queue.hxx:444
bool contains(const int i) const
check if i is an index on the PQ
Definition priority_queue.hxx:459
void push(const value_type i, const priority_type p)
Insert a index with a given priority.
Definition priority_queue.hxx:475
MultiArrayShape< N+1 >::type Edge
The edge descriptor (API: LEMON).
Definition multi_gridgraph.hxx:1592
Main MultiArray class containing the memory management.
Definition multi_array.hxx:2477
Class for a single RGB value.
Definition rgbvalue.hxx:128
shortest path computer
Definition graph_algorithms.hxx:297
WeightType distance(const Node &target) const
get the distance to a rarget node (after a call of run)
Definition graph_algorithms.hxx:452
void runMultiSource(const WEIGHTS &weights, ITER source_begin, ITER source_end, const Node &target=lemon::INVALID, WeightType maxDistance=NumericTraits< WeightType >::max())
run shortest path with given edge weights from multiple sources.
Definition graph_algorithms.hxx:391
void run(Node const &start, Node const &stop, const WEIGHTS &weights, const Node &source, const Node &target=lemon::INVALID, WeightType maxDistance=NumericTraits< WeightType >::max())
run shortest path in a region of interest of a GridGraph.
Definition graph_algorithms.hxx:356
ShortestPathDijkstra(const Graph &g)
\ brief constructor from graph
Definition graph_algorithms.hxx:313
const PredecessorsMap & predecessors() const
get the predecessors node map (after a call of run)
Definition graph_algorithms.hxx:442
const DiscoveryOrder & discoveryOrder() const
get an array with all visited nodes, sorted by distance from source
Definition graph_algorithms.hxx:437
const Graph & graph() const
get the graph
Definition graph_algorithms.hxx:419
const Node & target() const
get the target node
Definition graph_algorithms.hxx:427
const Node & source() const
get the source node
Definition graph_algorithms.hxx:423
void runMultiSource(const EFGE_WEIGHTS &edgeWeights, const NODE_WEIGHTS &nodeWeights, ITER source_begin, ITER source_end, const Node &target=lemon::INVALID, WeightType maxDistance=NumericTraits< WeightType >::max())
run shortest path with given edge weights from multiple sources.
Definition graph_algorithms.hxx:406
bool hasTarget() const
check if explicit target is given
Definition graph_algorithms.hxx:432
void run(const WEIGHTS &weights, const Node &source, const Node &target=lemon::INVALID, WeightType maxDistance=NumericTraits< WeightType >::max())
run shortest path given edge weights
Definition graph_algorithms.hxx:334
const DistanceMap & distances() const
get the distances node map (after a call of run)
Definition graph_algorithms.hxx:447
void reRun(const WEIGHTS &weights, const Node &source, const Node &target=lemon::INVALID, WeightType maxDistance=NumericTraits< WeightType >::max())
run shortest path again with given edge weights
Definition graph_algorithms.hxx:377
void init(Iterator i, Iterator end)
Definition tinyvector.hxx:708
size_type size() const
Definition tinyvector.hxx:913
iterator end()
Definition tinyvector.hxx:864
iterator begin()
Definition tinyvector.hxx:861
Class for fixed size vectors.
Definition tinyvector.hxx:1008
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 &)
Definition graph_algorithms.hxx:1198
void copyNodeMap(const G &g, const A &a, B &b)
copy a lemon node map
Definition graph_algorithms.hxx:117
detail::SelectIntegerType< 32, detail::UnsignedIntTypes >::type UInt32
32-bit unsigned int
Definition sized_int.hxx:183
void fillNodeMap(const G &g, A &a, const T &value)
fill a lemon node map
Definition graph_algorithms.hxx:136
bool allLessEqual(TinyVectorBase< V1, SIZE, D1, D2 > const &l, TinyVectorBase< V2, SIZE, D3, D4 > const &r)
pointwise less-equal
Definition tinyvector.hxx:1399
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
Definition graph_algorithms.hxx:165
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
Definition graph_algorithms.hxx:892
size_t pathLength(const NODE source, const NODE target, const PREDECESSORS &predecessors)
get the length in node units of a path
Definition graph_algorithms.hxx:591
FFTWComplex< R >::NormType norm(const FFTWComplex< R > &a)
norm (= magnitude)
Definition fftw3.hxx:1037
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
Definition graph_algorithms.hxx:1124
void copyEdgeMap(const G &g, const A &a, B &b)
copy a lemon edge map
Definition graph_algorithms.hxx:127
detail::SelectIntegerType< 64, detail::SignedIntTypes >::type Int64
64-bit signed int
Definition sized_int.hxx:177
void edgeSort(const GRAPH &g, const WEIGHTS &weights, const COMPERATOR &comperator, std::vector< typename GRAPH::Edge > &sortedEdges)
get a vector of Edge descriptors
Definition graph_algorithms.hxx:98
void fillEdgeMap(const G &g, A &a, const T &value)
fill a lemon edge map
Definition graph_algorithms.hxx:145
void edgeWeightedWatershedsSegmentation(const GRAPH &g, const EDGE_WEIGHTS &edgeWeights, const SEEDS &seeds, LABELS &labels)
edge weighted watersheds Segmentataion
Definition graph_algorithms.hxx:871
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
Definition graph_algorithms.hxx:916
bool allLess(TinyVectorBase< V1, SIZE, D1, D2 > const &l, TinyVectorBase< V2, SIZE, D3, D4 > const &r)
pointwise less-than
Definition tinyvector.hxx:1375
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.
Definition graph_algorithms.hxx:1268
void edgeWeightsFromInterpolatedImage(const GridGraph< N, DirectedTag > &g, const MultiArrayView< N, T > &interpolatedImage, EDGEMAP &edgeWeights, bool euclidean=false)
create edge weights from an interpolated image
Definition graph_algorithms.hxx:1399
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
Definition graph_algorithms.hxx:1099
void edgeWeightsFromNodeWeights(const GridGraph< N, DirectedTag > &g, const NODEMAP &nodeWeights, EDGEMAP &edgeWeights, bool euclidean, FUNCTOR const &func)
create edge weights from node weights
Definition graph_algorithms.hxx:1341
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.
Definition graph_algorithms.hxx:611
void initMultiArrayBorder(...)
Write values to the specified border values in the array.