38 #ifndef VIGRA_HIERARCHICAL_CLUSTERING_HXX
39 #define VIGRA_HIERARCHICAL_CLUSTERING_HXX
48 #include "priority_queue.hxx"
49 #include "metrics.hxx"
53 namespace cluster_operators{
57 class EDGE_INDICATOR_MAP,
64 typedef EdgeWeightedUcm<
74 typedef typename EDGE_INDICATOR_MAP::Value ValueType;
75 typedef ValueType WeightType;
76 typedef MERGE_GRAPH MergeGraph;
77 typedef typename MergeGraph::Graph Graph;
78 typedef typename Graph::Edge BaseGraphEdge;
79 typedef typename Graph::Node BaseGraphNode;
80 typedef typename MergeGraph::Edge Edge;
81 typedef typename MergeGraph::Node Node;
82 typedef typename MergeGraph::EdgeIt EdgeIt;
83 typedef typename MergeGraph::NodeIt NodeIt;
84 typedef typename MergeGraph::IncEdgeIt IncEdgeIt;
85 typedef typename MergeGraph::index_type index_type;
86 typedef MergeGraphItemHelper<MergeGraph,Edge> EdgeHelper;
87 typedef MergeGraphItemHelper<MergeGraph,Node> NodeHelper;
89 typedef typename MergeGraph::MergeNodeCallBackType MergeNodeCallBackType;
90 typedef typename MergeGraph::MergeEdgeCallBackType MergeEdgeCallBackType;
91 typedef typename MergeGraph::EraseEdgeCallBackType EraseEdgeCallBackType;
93 typedef typename EDGE_INDICATOR_MAP::Reference EdgeIndicatorReference;
96 MergeGraph & mergeGraph,
97 EDGE_INDICATOR_MAP edgeIndicatorMap,
98 EDGE_SIZE_MAP edgeSizeMap,
99 NODE_SIZE_MAP nodeSizeMap,
100 MIN_WEIGHT_MAP minWeightEdgeMap,
101 const ValueType wardness=1.0
103 : mergeGraph_(mergeGraph),
104 edgeIndicatorMap_(edgeIndicatorMap),
105 edgeSizeMap_(edgeSizeMap),
106 nodeSizeMap_(nodeSizeMap),
107 minWeightEdgeMap_(minWeightEdgeMap),
108 pq_(mergeGraph.maxEdgeId()+1),
111 MergeNodeCallBackType cbMn(MergeNodeCallBackType:: template from_method<SelfType,&SelfType::mergeNodes>(
this));
112 MergeEdgeCallBackType cbMe(MergeEdgeCallBackType:: template from_method<SelfType,&SelfType::mergeEdges>(
this));
113 EraseEdgeCallBackType cbEe(EraseEdgeCallBackType:: template from_method<SelfType,&SelfType::eraseEdge>(
this));
115 mergeGraph_.registerMergeNodeCallBack(cbMn);
116 mergeGraph_.registerMergeEdgeCallBack(cbMe);
117 mergeGraph_.registerEraseEdgeCallBack(cbEe);
119 for(EdgeIt e(mergeGraph_);e!=lemon::INVALID;++e){
120 const Edge
edge = *e;
121 const BaseGraphEdge graphEdge=EdgeHelper::itemToGraphItem(mergeGraph_,edge);
122 const index_type edgeId = mergeGraph_.id(edge);
123 const ValueType currentWeight = this->getEdgeWeight(edge);
124 pq_.push(edgeId,currentWeight);
125 minWeightEdgeMap_[graphEdge]=currentWeight;
129 void setWardness(
const float w){
136 MergeNodeCallBackType cbMn(MergeNodeCallBackType:: template from_method<SelfType,&SelfType::mergeNodes>(
this));
137 MergeEdgeCallBackType cbMe(MergeEdgeCallBackType:: template from_method<SelfType,&SelfType::mergeEdges>(
this));
138 EraseEdgeCallBackType cbEe(EraseEdgeCallBackType:: template from_method<SelfType,&SelfType::eraseEdge>(
this));
140 mergeGraph_.registerMergeNodeCallBack(cbMn);
141 mergeGraph_.registerMergeEdgeCallBack(cbMe);
142 mergeGraph_.registerEraseEdgeCallBack(cbEe);
145 for(EdgeIt e(mergeGraph_);e!=lemon::INVALID;++e){
146 const Edge edge = *e;
147 const BaseGraphEdge graphEdge=EdgeHelper::itemToGraphItem(mergeGraph_,edge);
148 const index_type edgeId = mergeGraph_.id(edge);
149 const ValueType currentWeight = this->getEdgeWeight(edge);
150 pq_.push(edgeId,currentWeight);
151 minWeightEdgeMap_[graphEdge]=currentWeight;
156 void mergeEdges(
const Edge & a,
const Edge & b){
158 const BaseGraphEdge aa=EdgeHelper::itemToGraphItem(mergeGraph_,a);
159 const BaseGraphEdge bb=EdgeHelper::itemToGraphItem(mergeGraph_,b);
160 EdgeIndicatorReference va=edgeIndicatorMap_[aa];
161 EdgeIndicatorReference vb=edgeIndicatorMap_[bb];
162 va*=edgeSizeMap_[aa];
163 vb*=edgeSizeMap_[bb];
166 edgeSizeMap_[aa]+=edgeSizeMap_[bb];
167 va/=(edgeSizeMap_[aa]);
168 vb/=edgeSizeMap_[bb];
170 pq_.deleteItem(b.id());
174 void mergeNodes(
const Node & a,
const Node & b){
175 const BaseGraphNode aa=NodeHelper::itemToGraphItem(mergeGraph_,a);
176 const BaseGraphNode bb=NodeHelper::itemToGraphItem(mergeGraph_,b);
177 nodeSizeMap_[aa]+=nodeSizeMap_[bb];
181 void eraseEdge(
const Edge & edge){
185 pq_.deleteItem(edge.id());
189 const Node newNode = mergeGraph_.inactiveEdgesNode(edge);
193 for (IncEdgeIt e(mergeGraph_,newNode);e!=lemon::INVALID;++e)
196 const Edge incEdge(*e);
199 const BaseGraphEdge incGraphEdge = EdgeHelper::itemToGraphItem(mergeGraph_,incEdge);
204 const ValueType newWeight = getEdgeWeight(incEdge);
207 pq_.push(incEdge.id(),newWeight);
208 minWeightEdgeMap_[incGraphEdge]=newWeight;
215 Edge contractionEdge(){
216 index_type minLabel = pq_.top();
217 while(mergeGraph_.hasEdgeId(minLabel)==
false){
218 eraseEdge(Edge(minLabel));
219 minLabel = pq_.top();
221 return Edge(minLabel);
225 WeightType contractionWeight(){
226 index_type minLabel = pq_.top();
227 while(mergeGraph_.hasEdgeId(minLabel)==
false){
228 eraseEdge(Edge(minLabel));
229 minLabel = pq_.top();
231 return pq_.topPriority();
237 MergeGraph & mergeGraph(){
243 index_type minLabel = pq_.top();
244 while(mergeGraph_.hasEdgeId(minLabel)==
false){
245 eraseEdge(Edge(minLabel));
246 minLabel = pq_.top();
248 return mergeGraph_.edgeNum()==0 || mergeGraph_.nodeNum()==1;
252 ValueType getEdgeWeight(
const Edge & e){
254 const Node u = mergeGraph_.u(e);
255 const Node v = mergeGraph_.v(e);
257 const size_t dU = mergeGraph_.degree(u);
258 const size_t dV = mergeGraph_.degree(u);
259 const BaseGraphEdge ee=EdgeHelper::itemToGraphItem(mergeGraph_,e);
260 const BaseGraphNode uu=NodeHelper::itemToGraphItem(mergeGraph_,u);
261 const BaseGraphNode vv=NodeHelper::itemToGraphItem(mergeGraph_,v);
263 const float sizeU = nodeSizeMap_[uu] ;
264 const float sizeV = nodeSizeMap_[vv] ;
266 const ValueType wardFac = 2.0 / ( 1.0/std::pow(sizeU,wardness_) + 1/std::pow(sizeV,wardness_) );
269 const ValueType fromEdgeIndicator = edgeIndicatorMap_[ee];
270 const ValueType totalWeight = fromEdgeIndicator*wardFac;
275 MergeGraph & mergeGraph_;
276 EDGE_INDICATOR_MAP edgeIndicatorMap_;
277 EDGE_SIZE_MAP edgeSizeMap_;
278 NODE_SIZE_MAP nodeSizeMap_;
279 MIN_WEIGHT_MAP minWeightEdgeMap_;
281 ValueType wardness_;;
315 class EDGE_INDICATOR_MAP,
317 class NODE_FEATURE_MAP,
319 class MIN_WEIGHT_MAP,
336 typedef typename EDGE_INDICATOR_MAP::Value ValueType;
337 typedef ValueType WeightType;
338 typedef MERGE_GRAPH MergeGraph;
339 typedef typename MergeGraph::Graph Graph;
340 typedef typename Graph::Edge BaseGraphEdge;
341 typedef typename Graph::Node BaseGraphNode;
342 typedef typename MergeGraph::Edge Edge;
343 typedef typename MergeGraph::Node Node;
344 typedef typename MergeGraph::EdgeIt EdgeIt;
345 typedef typename MergeGraph::NodeIt NodeIt;
346 typedef typename MergeGraph::IncEdgeIt IncEdgeIt;
347 typedef typename MergeGraph::index_type index_type;
348 typedef MergeGraphItemHelper<MergeGraph,Edge> EdgeHelper;
349 typedef MergeGraphItemHelper<MergeGraph,Node> NodeHelper;
352 typedef typename EDGE_INDICATOR_MAP::Reference EdgeIndicatorReference;
353 typedef typename NODE_FEATURE_MAP::Reference NodeFeatureReference;
356 MergeGraph & mergeGraph,
357 EDGE_INDICATOR_MAP edgeIndicatorMap,
358 EDGE_SIZE_MAP edgeSizeMap,
359 NODE_FEATURE_MAP nodeFeatureMap,
360 NODE_SIZE_MAP nodeSizeMap,
361 MIN_WEIGHT_MAP minWeightEdgeMap,
362 NODE_LABEL_MAP nodeLabelMap,
363 const ValueType beta,
364 const metrics::MetricType metricType,
365 const ValueType wardness=1.0,
366 const ValueType
gamma = 10000000.0,
367 const ValueType sameLabelMultiplier = 0.8
369 : mergeGraph_(mergeGraph),
370 edgeIndicatorMap_(edgeIndicatorMap),
371 edgeSizeMap_(edgeSizeMap),
372 nodeFeatureMap_(nodeFeatureMap),
373 nodeSizeMap_(nodeSizeMap),
374 minWeightEdgeMap_(minWeightEdgeMap),
375 nodeLabelMap_(nodeLabelMap),
376 pq_(mergeGraph.maxEdgeId()+1),
380 sameLabelMultiplier_(sameLabelMultiplier),
383 typedef typename MergeGraph::MergeNodeCallBackType MergeNodeCallBackType;
384 typedef typename MergeGraph::MergeEdgeCallBackType MergeEdgeCallBackType;
385 typedef typename MergeGraph::EraseEdgeCallBackType EraseEdgeCallBackType;
388 MergeNodeCallBackType cbMn(MergeNodeCallBackType:: template from_method<SelfType,&SelfType::mergeNodes>(
this));
389 MergeEdgeCallBackType cbMe(MergeEdgeCallBackType:: template from_method<SelfType,&SelfType::mergeEdges>(
this));
390 EraseEdgeCallBackType cbEe(EraseEdgeCallBackType:: template from_method<SelfType,&SelfType::eraseEdge>(
this));
392 mergeGraph_.registerMergeNodeCallBack(cbMn);
393 mergeGraph_.registerMergeEdgeCallBack(cbMe);
394 mergeGraph_.registerEraseEdgeCallBack(cbEe);
398 for(EdgeIt e(mergeGraph);e!=lemon::INVALID;++e){
399 const Edge edge = *e;
400 const BaseGraphEdge graphEdge=EdgeHelper::itemToGraphItem(mergeGraph_,edge);
401 const index_type edgeId = mergeGraph_.id(edge);
402 const ValueType currentWeight = this->getEdgeWeight(edge);
403 pq_.
push(edgeId,currentWeight);
404 minWeightEdgeMap_[graphEdge]=currentWeight;
412 const BaseGraphEdge aa=EdgeHelper::itemToGraphItem(mergeGraph_,a);
413 const BaseGraphEdge bb=EdgeHelper::itemToGraphItem(mergeGraph_,b);
414 EdgeIndicatorReference va=edgeIndicatorMap_[aa];
415 EdgeIndicatorReference vb=edgeIndicatorMap_[bb];
416 va*=edgeSizeMap_[aa];
417 vb*=edgeSizeMap_[bb];
421 edgeSizeMap_[aa]+=edgeSizeMap_[bb];
422 va/=(edgeSizeMap_[aa]);
423 vb/=edgeSizeMap_[bb];
430 const BaseGraphNode aa=NodeHelper::itemToGraphItem(mergeGraph_,a);
431 const BaseGraphNode bb=NodeHelper::itemToGraphItem(mergeGraph_,b);
432 NodeFeatureReference va=nodeFeatureMap_[aa];
433 NodeFeatureReference vb=nodeFeatureMap_[bb];
434 va*=nodeSizeMap_[aa];
435 vb*=nodeSizeMap_[bb];
437 nodeSizeMap_[aa]+=nodeSizeMap_[bb];
438 va/=(nodeSizeMap_[aa]);
439 vb/=nodeSizeMap_[bb];
443 const UInt32 labelA = nodeLabelMap_[aa];
444 const UInt32 labelB = nodeLabelMap_[bb];
446 if(labelA!=0 && labelB!=0 && labelA!=labelB){
447 throw std::runtime_error(
"both nodes have labels");
450 const UInt32 newLabel = std::max(labelA, labelB);
451 nodeLabelMap_[aa] = newLabel;
464 const Node newNode = mergeGraph_.inactiveEdgesNode(edge);
469 for (IncEdgeIt e(mergeGraph_,newNode);e!=lemon::INVALID;++e){
472 const Edge incEdge(*e);
475 const BaseGraphEdge incGraphEdge = EdgeHelper::itemToGraphItem(mergeGraph_,incEdge);
480 const ValueType newWeight = getEdgeWeight(incEdge);
486 pq_.
push(incEdge.id(),newWeight);
487 minWeightEdgeMap_[incGraphEdge]=newWeight;
495 index_type minLabel = pq_.
top();
496 while(mergeGraph_.hasEdgeId(minLabel)==
false){
498 minLabel = pq_.
top();
500 return Edge(minLabel);
505 index_type minLabel = pq_.
top();
506 while(mergeGraph_.hasEdgeId(minLabel)==
false){
508 minLabel = pq_.
top();
522 index_type minLabel = pq_.
top();
523 while(mergeGraph_.hasEdgeId(minLabel)==
false){
525 minLabel = pq_.
top();
533 ValueType getEdgeWeight(
const Edge & e){
535 const Node u = mergeGraph_.u(e);
536 const Node v = mergeGraph_.v(e);
538 const size_t dU = mergeGraph_.degree(u);
539 const size_t dV = mergeGraph_.degree(u);
540 const BaseGraphEdge ee=EdgeHelper::itemToGraphItem(mergeGraph_,e);
541 const BaseGraphNode uu=NodeHelper::itemToGraphItem(mergeGraph_,u);
542 const BaseGraphNode vv=NodeHelper::itemToGraphItem(mergeGraph_,v);
544 const float sizeU = nodeSizeMap_[uu];
545 const float sizeV = nodeSizeMap_[vv];
548 const ValueType wardFac = 2.0 / ( 1.0/std::pow(sizeU,wardness_) + 1/std::pow(sizeV,wardness_) );
550 const ValueType fromEdgeIndicator = edgeIndicatorMap_[ee];
551 ValueType fromNodeDist = metric_(nodeFeatureMap_[uu],nodeFeatureMap_[vv]);
552 ValueType totalWeight = ((1.0-beta_)*fromEdgeIndicator + beta_*fromNodeDist)*wardFac;
555 const UInt32 labelA = nodeLabelMap_[uu];
556 const UInt32 labelB = nodeLabelMap_[vv];
558 if(labelA!=0 && labelB!=0){
559 if(labelA == labelB){
560 totalWeight*=sameLabelMultiplier_;
563 totalWeight += gamma_;
570 MergeGraph & mergeGraph_;
571 EDGE_INDICATOR_MAP edgeIndicatorMap_;
572 EDGE_SIZE_MAP edgeSizeMap_;
573 NODE_FEATURE_MAP nodeFeatureMap_;
574 NODE_SIZE_MAP nodeSizeMap_;
575 MIN_WEIGHT_MAP minWeightEdgeMap_;
576 NODE_LABEL_MAP nodeLabelMap_;
581 ValueType sameLabelMultiplier_;
582 metrics::Metric<float> metric_;
592 template<
class CLUSTER_OPERATOR>
596 typedef CLUSTER_OPERATOR ClusterOperator;
597 typedef typename ClusterOperator::MergeGraph MergeGraph;
598 typedef typename MergeGraph::Graph Graph;
599 typedef typename Graph::Edge BaseGraphEdge;
600 typedef typename Graph::Node BaseGraphNode;
601 typedef typename MergeGraph::Edge Edge;
602 typedef typename MergeGraph::Node Node;
603 typedef typename CLUSTER_OPERATOR::WeightType ValueType;
604 typedef typename MergeGraph::index_type MergeGraphIndexType;
608 const size_t nodeNumStopCond = 1,
609 const bool buildMergeTree =
true,
610 const bool verbose =
false
612 : nodeNumStopCond_ (nodeNumStopCond),
613 buildMergeTreeEncoding_(buildMergeTree),
616 size_t nodeNumStopCond_;
617 bool buildMergeTreeEncoding_;
623 const MergeGraphIndexType a,
624 const MergeGraphIndexType b,
625 const MergeGraphIndexType r,
628 a_(a),b_(b),r_(r),w_(w){
630 MergeGraphIndexType a_;
631 MergeGraphIndexType b_;
632 MergeGraphIndexType r_;
636 typedef std::vector<MergeItem> MergeTreeEncoding;
640 ClusterOperator & clusterOperator,
641 const Parameter & parameter = Parameter()
644 clusterOperator_(clusterOperator),
646 mergeGraph_(clusterOperator_.mergeGraph()),
647 graph_(mergeGraph_.
graph()),
648 timestamp_(graph_.maxNodeId()+1),
650 timeStampIndexToMergeIndex_(),
651 mergeTreeEndcoding_()
653 if(param_.buildMergeTreeEncoding_){
656 mergeTreeEndcoding_.reserve(graph_.nodeNum()*2);
657 toTimeStamp_.resize(graph_.maxNodeId()+1);
658 timeStampIndexToMergeIndex_.resize(graph_.maxNodeId()+1);
659 for(MergeGraphIndexType nodeId=0;nodeId<=mergeGraph_.maxNodeId();++nodeId){
660 toTimeStamp_[nodeId]=nodeId;
672 while(mergeGraph_.nodeNum()>param_.nodeNumStopCond_ && mergeGraph_.edgeNum()>0 && !clusterOperator_.done()){
674 const Edge edgeToRemove = clusterOperator_.contractionEdge();
675 if(param_.buildMergeTreeEncoding_){
676 const MergeGraphIndexType uid = mergeGraph_.id(mergeGraph_.u(edgeToRemove));
677 const MergeGraphIndexType vid = mergeGraph_.id(mergeGraph_.v(edgeToRemove));
678 const ValueType w = clusterOperator_.contractionWeight();
680 mergeGraph_.contractEdge( edgeToRemove);
681 const MergeGraphIndexType aliveNodeId = mergeGraph_.hasNodeId(uid) ? uid : vid;
682 const MergeGraphIndexType deadNodeId = aliveNodeId==vid ? uid : vid;
683 timeStampIndexToMergeIndex_[timeStampToIndex(timestamp_)]=mergeTreeEndcoding_.size();
684 mergeTreeEndcoding_.push_back(MergeItem( toTimeStamp_[aliveNodeId],toTimeStamp_[deadNodeId],timestamp_,w));
685 toTimeStamp_[aliveNodeId]=timestamp_;
691 mergeGraph_.contractEdge( edgeToRemove );
693 if(param_.verbose_ && mergeGraph_.nodeNum()%1==0){
694 std::cout<<
"\rNodes: "<<std::setw(10)<<mergeGraph_.nodeNum()<<std::flush;
704 return mergeTreeEndcoding_;
707 template<
class EDGE_MAP>
708 void ucmTransform(EDGE_MAP & edgeMap)
const{
709 typedef typename Graph::EdgeIt BaseGraphEdgeIt;
711 for(BaseGraphEdgeIt iter(
graph()); iter!=lemon::INVALID; ++iter ){
712 const BaseGraphEdge edge=*iter;
718 template<
class OUT_ITER>
719 size_t leafNodeIds(
const MergeGraphIndexType treeNodeId, OUT_ITER begin)
const{
720 if(treeNodeId<=graph_.maxNodeId()){
727 std::queue<MergeGraphIndexType> queue;
728 queue.push(treeNodeId);
730 while(!queue.empty()){
732 const MergeGraphIndexType
id = queue.front();
734 const MergeGraphIndexType mergeIndex = timeStampToMergeIndex(
id);
735 const MergeGraphIndexType ab[]= { mergeTreeEndcoding_[mergeIndex].a_, mergeTreeEndcoding_[mergeIndex].b_};
737 for(
size_t i=0;i<2;++i){
738 if(ab[i]<=graph_.maxNodeId()){
763 const MergeGraphIndexType
reprNodeId(
const MergeGraphIndexType
id)
const{
764 return mergeGraph_.reprNodeId(
id);
768 MergeGraphIndexType timeStampToIndex(
const MergeGraphIndexType timestamp)
const{
769 return timestamp- graph_.maxNodeId();
773 MergeGraphIndexType timeStampToMergeIndex(
const MergeGraphIndexType timestamp)
const{
774 return timeStampIndexToMergeIndex_[timeStampToIndex(timestamp)];
777 ClusterOperator & clusterOperator_;
779 MergeGraph & mergeGraph_;
780 const Graph & graph_;
785 MergeGraphIndexType timestamp_;
786 std::vector<MergeGraphIndexType> toTimeStamp_;
787 std::vector<MergeGraphIndexType> timeStampIndexToMergeIndex_;
789 MergeTreeEncoding mergeTreeEndcoding_;
797 #endif // VIGRA_HIERARCHICAL_CLUSTERING_HXX
This Cluster Operator is a MONSTER. It can really do a lot.
Definition: hierarchical_clustering.hxx:322
MergeGraph & mergeGraph()
get a reference to the merge
Definition: hierarchical_clustering.hxx:516
const MergeGraphIndexType reprNodeId(const MergeGraphIndexType id) const
get the representative node id
Definition: hierarchical_clustering.hxx:763
priority_type topPriority() const
get top priority
Definition: priority_queue.hxx:496
const MergeGraph & mergeGraph() const
get the merge graph
Definition: hierarchical_clustering.hxx:758
EdgeWeightNodeFeatures(MergeGraph &mergeGraph, EDGE_INDICATOR_MAP edgeIndicatorMap, EDGE_SIZE_MAP edgeSizeMap, NODE_FEATURE_MAP nodeFeatureMap, NODE_SIZE_MAP nodeSizeMap, MIN_WEIGHT_MAP minWeightEdgeMap, NODE_LABEL_MAP nodeLabelMap, const ValueType beta, const metrics::MetricType metricType, const ValueType wardness=1.0, const ValueType gamma=10000000.0, const ValueType sameLabelMultiplier=0.8)
construct cluster operator
Definition: hierarchical_clustering.hxx:355
void push(const value_type i, const priority_type p)
Insert a index with a given priority.
Definition: priority_queue.hxx:475
WeightType contractionWeight()
get the edge weight of the edge which should be contracted next
Definition: hierarchical_clustering.hxx:504
size_t leafNodeIds(const MergeGraphIndexType treeNodeId, OUT_ITER begin) const
get the node id's which are the leafes of a treeNodeId
Definition: hierarchical_clustering.hxx:719
void mergeEdges(const Edge &a, const Edge &b)
will be called via callbacks from mergegraph
Definition: hierarchical_clustering.hxx:410
void eraseEdge(const Edge &edge)
will be called via callbacks from mergegraph
Definition: hierarchical_clustering.hxx:456
HierarchicalClustering(ClusterOperator &clusterOperator, const Parameter ¶meter=Parameter())
construct HierarchicalClustering from clusterOperator and an optional parameter object ...
Definition: hierarchical_clustering.hxx:639
double gamma(double x)
The gamma function.
Definition: mathutil.hxx:1570
std::pair< typename vigra::GridGraph< N, DirectedTag >::edge_descriptor, bool > edge(typename vigra::GridGraph< N, DirectedTag >::vertex_descriptor const &u, typename vigra::GridGraph< N, DirectedTag >::vertex_descriptor const &v, vigra::GridGraph< N, DirectedTag > const &g)
Return the pair (edge_descriptor, true) when an edge between vertices u and v exists, or (lemon::INVALID, false) otherwise (API: boost).
Definition: multi_gridgraph.hxx:2990
void deleteItem(const value_type i)
deleqte the priority associated with index i
Definition: priority_queue.hxx:516
void mergeNodes(const Node &a, const Node &b)
will be called via callbacks from mergegraph
Definition: hierarchical_clustering.hxx:429
do hierarchical clustering with a given cluster operator
Definition: hierarchical_clustering.hxx:593
detail::SelectIntegerType< 32, detail::UnsignedIntTypes >::type UInt32
32-bit unsigned int
Definition: sized_int.hxx:183
const_reference top() const
get index with top priority
Definition: priority_queue.hxx:490
void cluster()
start the clustering
Definition: hierarchical_clustering.hxx:669
const MergeTreeEncoding & mergeTreeEndcoding() const
get the encoding of the merge tree
Definition: hierarchical_clustering.hxx:703
Edge contractionEdge()
get the edge which should be contracted next
Definition: hierarchical_clustering.hxx:494
const Graph & graph() const
get the graph the merge graph is based on
Definition: hierarchical_clustering.hxx:753