38 #ifndef VIGRA_HIERARCHICAL_CLUSTERING_HXX
39 #define VIGRA_HIERARCHICAL_CLUSTERING_HXX
48 #include "priority_queue.hxx"
49 #include "metrics.hxx"
50 #include "merge_graph_adaptor.hxx"
58 namespace cluster_operators{
62 class EDGE_INDICATOR_MAP,
69 typedef EdgeWeightedUcm<
79 typedef typename EDGE_INDICATOR_MAP::Value ValueType;
80 typedef ValueType WeightType;
81 typedef MERGE_GRAPH MergeGraph;
82 typedef typename MergeGraph::Graph Graph;
83 typedef typename Graph::Edge BaseGraphEdge;
84 typedef typename Graph::Node BaseGraphNode;
85 typedef typename MergeGraph::Edge Edge;
86 typedef typename MergeGraph::Node Node;
87 typedef typename MergeGraph::EdgeIt EdgeIt;
88 typedef typename MergeGraph::NodeIt NodeIt;
89 typedef typename MergeGraph::IncEdgeIt IncEdgeIt;
90 typedef typename MergeGraph::index_type index_type;
91 typedef MergeGraphItemHelper<MergeGraph,Edge> EdgeHelper;
92 typedef MergeGraphItemHelper<MergeGraph,Node> NodeHelper;
94 typedef typename MergeGraph::MergeNodeCallBackType MergeNodeCallBackType;
95 typedef typename MergeGraph::MergeEdgeCallBackType MergeEdgeCallBackType;
96 typedef typename MergeGraph::EraseEdgeCallBackType EraseEdgeCallBackType;
98 typedef typename EDGE_INDICATOR_MAP::Reference EdgeIndicatorReference;
101 MergeGraph & mergeGraph,
102 EDGE_INDICATOR_MAP edgeIndicatorMap,
103 EDGE_SIZE_MAP edgeSizeMap,
104 NODE_SIZE_MAP nodeSizeMap,
105 MIN_WEIGHT_MAP minWeightEdgeMap,
106 const ValueType wardness=1.0
108 : mergeGraph_(mergeGraph),
109 edgeIndicatorMap_(edgeIndicatorMap),
110 edgeSizeMap_(edgeSizeMap),
111 nodeSizeMap_(nodeSizeMap),
112 minWeightEdgeMap_(minWeightEdgeMap),
113 pq_(mergeGraph.maxEdgeId()+1),
116 MergeNodeCallBackType cbMn(MergeNodeCallBackType:: template from_method<SelfType,&SelfType::mergeNodes>(
this));
117 MergeEdgeCallBackType cbMe(MergeEdgeCallBackType:: template from_method<SelfType,&SelfType::mergeEdges>(
this));
118 EraseEdgeCallBackType cbEe(EraseEdgeCallBackType:: template from_method<SelfType,&SelfType::eraseEdge>(
this));
120 mergeGraph_.registerMergeNodeCallBack(cbMn);
121 mergeGraph_.registerMergeEdgeCallBack(cbMe);
122 mergeGraph_.registerEraseEdgeCallBack(cbEe);
124 for(EdgeIt e(mergeGraph_);e!=lemon::INVALID;++e){
125 const Edge
edge = *e;
126 const BaseGraphEdge graphEdge=EdgeHelper::itemToGraphItem(mergeGraph_,edge);
127 const index_type edgeId = mergeGraph_.id(edge);
128 const ValueType currentWeight = this->getEdgeWeight(edge);
129 pq_.push(edgeId,currentWeight);
130 minWeightEdgeMap_[graphEdge]=currentWeight;
134 void setWardness(
const float w){
141 MergeNodeCallBackType cbMn(MergeNodeCallBackType:: template from_method<SelfType,&SelfType::mergeNodes>(
this));
142 MergeEdgeCallBackType cbMe(MergeEdgeCallBackType:: template from_method<SelfType,&SelfType::mergeEdges>(
this));
143 EraseEdgeCallBackType cbEe(EraseEdgeCallBackType:: template from_method<SelfType,&SelfType::eraseEdge>(
this));
145 mergeGraph_.registerMergeNodeCallBack(cbMn);
146 mergeGraph_.registerMergeEdgeCallBack(cbMe);
147 mergeGraph_.registerEraseEdgeCallBack(cbEe);
150 for(EdgeIt e(mergeGraph_);e!=lemon::INVALID;++e){
151 const Edge edge = *e;
152 const BaseGraphEdge graphEdge=EdgeHelper::itemToGraphItem(mergeGraph_,edge);
153 const index_type edgeId = mergeGraph_.id(edge);
154 const ValueType currentWeight = this->getEdgeWeight(edge);
155 pq_.push(edgeId,currentWeight);
156 minWeightEdgeMap_[graphEdge]=currentWeight;
161 void mergeEdges(
const Edge & a,
const Edge & b){
163 const BaseGraphEdge aa=EdgeHelper::itemToGraphItem(mergeGraph_,a);
164 const BaseGraphEdge bb=EdgeHelper::itemToGraphItem(mergeGraph_,b);
165 EdgeIndicatorReference va=edgeIndicatorMap_[aa];
166 EdgeIndicatorReference vb=edgeIndicatorMap_[bb];
167 va*=edgeSizeMap_[aa];
168 vb*=edgeSizeMap_[bb];
171 edgeSizeMap_[aa]+=edgeSizeMap_[bb];
172 va/=(edgeSizeMap_[aa]);
173 vb/=edgeSizeMap_[bb];
175 pq_.deleteItem(b.id());
179 void mergeNodes(
const Node & a,
const Node & b){
180 const BaseGraphNode aa=NodeHelper::itemToGraphItem(mergeGraph_,a);
181 const BaseGraphNode bb=NodeHelper::itemToGraphItem(mergeGraph_,b);
182 nodeSizeMap_[aa]+=nodeSizeMap_[bb];
186 void eraseEdge(
const Edge & edge){
190 pq_.deleteItem(edge.id());
194 const Node newNode = mergeGraph_.inactiveEdgesNode(edge);
198 for (IncEdgeIt e(mergeGraph_,newNode);e!=lemon::INVALID;++e)
201 const Edge incEdge(*e);
204 const BaseGraphEdge incGraphEdge = EdgeHelper::itemToGraphItem(mergeGraph_,incEdge);
209 const ValueType newWeight = getEdgeWeight(incEdge);
212 pq_.push(incEdge.id(),newWeight);
213 minWeightEdgeMap_[incGraphEdge]=newWeight;
220 Edge contractionEdge(){
221 index_type minLabel = pq_.top();
222 while(mergeGraph_.hasEdgeId(minLabel)==
false){
223 eraseEdge(Edge(minLabel));
224 minLabel = pq_.top();
226 return Edge(minLabel);
230 WeightType contractionWeight(){
231 index_type minLabel = pq_.top();
232 while(mergeGraph_.hasEdgeId(minLabel)==
false){
233 eraseEdge(Edge(minLabel));
234 minLabel = pq_.top();
236 return pq_.topPriority();
242 MergeGraph & mergeGraph(){
248 index_type minLabel = pq_.top();
249 while(mergeGraph_.hasEdgeId(minLabel)==
false){
250 eraseEdge(Edge(minLabel));
251 minLabel = pq_.top();
253 return mergeGraph_.edgeNum()==0 || mergeGraph_.nodeNum()==1;
257 ValueType getEdgeWeight(
const Edge & e){
259 const Node u = mergeGraph_.u(e);
260 const Node v = mergeGraph_.v(e);
262 const BaseGraphEdge ee=EdgeHelper::itemToGraphItem(mergeGraph_,e);
263 const BaseGraphNode uu=NodeHelper::itemToGraphItem(mergeGraph_,u);
264 const BaseGraphNode vv=NodeHelper::itemToGraphItem(mergeGraph_,v);
266 const float sizeU = nodeSizeMap_[uu] ;
267 const float sizeV = nodeSizeMap_[vv] ;
269 const ValueType wardFac = 2.0 / ( 1.0/std::pow(sizeU,wardness_) + 1/std::pow(sizeV,wardness_) );
272 const ValueType fromEdgeIndicator = edgeIndicatorMap_[ee];
273 const ValueType totalWeight = fromEdgeIndicator*wardFac;
278 MergeGraph & mergeGraph_;
279 EDGE_INDICATOR_MAP edgeIndicatorMap_;
280 EDGE_SIZE_MAP edgeSizeMap_;
281 NODE_SIZE_MAP nodeSizeMap_;
282 MIN_WEIGHT_MAP minWeightEdgeMap_;
284 ValueType wardness_;;
318 class EDGE_INDICATOR_MAP,
320 class NODE_FEATURE_MAP,
322 class MIN_WEIGHT_MAP,
339 typedef typename EDGE_INDICATOR_MAP::Value ValueType;
340 typedef ValueType WeightType;
341 typedef MERGE_GRAPH MergeGraph;
342 typedef typename MergeGraph::Graph Graph;
343 typedef typename Graph::Edge BaseGraphEdge;
344 typedef typename Graph::Node BaseGraphNode;
345 typedef typename MergeGraph::Edge Edge;
346 typedef typename MergeGraph::Node Node;
347 typedef typename MergeGraph::EdgeIt EdgeIt;
348 typedef typename MergeGraph::NodeIt NodeIt;
349 typedef typename MergeGraph::IncEdgeIt IncEdgeIt;
350 typedef typename MergeGraph::index_type index_type;
351 typedef MergeGraphItemHelper<MergeGraph,Edge> EdgeHelper;
352 typedef MergeGraphItemHelper<MergeGraph,Node> NodeHelper;
355 typedef typename EDGE_INDICATOR_MAP::Reference EdgeIndicatorReference;
356 typedef typename NODE_FEATURE_MAP::Reference NodeFeatureReference;
359 MergeGraph & mergeGraph,
360 EDGE_INDICATOR_MAP edgeIndicatorMap,
361 EDGE_SIZE_MAP edgeSizeMap,
362 NODE_FEATURE_MAP nodeFeatureMap,
363 NODE_SIZE_MAP nodeSizeMap,
364 MIN_WEIGHT_MAP minWeightEdgeMap,
365 NODE_LABEL_MAP nodeLabelMap,
366 const ValueType beta,
368 const ValueType wardness=static_cast<ValueType>(1.0),
369 const ValueType
gamma = static_cast<ValueType>(10000000.0),
370 const ValueType sameLabelMultiplier = static_cast<ValueType>(0.8)
372 : mergeGraph_(mergeGraph),
373 edgeIndicatorMap_(edgeIndicatorMap),
374 edgeSizeMap_(edgeSizeMap),
375 nodeFeatureMap_(nodeFeatureMap),
376 nodeSizeMap_(nodeSizeMap),
377 minWeightEdgeMap_(minWeightEdgeMap),
378 nodeLabelMap_(nodeLabelMap),
379 pq_(mergeGraph.maxEdgeId()+1),
383 sameLabelMultiplier_(sameLabelMultiplier),
386 typedef typename MergeGraph::MergeNodeCallBackType MergeNodeCallBackType;
387 typedef typename MergeGraph::MergeEdgeCallBackType MergeEdgeCallBackType;
388 typedef typename MergeGraph::EraseEdgeCallBackType EraseEdgeCallBackType;
391 MergeNodeCallBackType cbMn(MergeNodeCallBackType:: template from_method<SelfType,&SelfType::mergeNodes>(
this));
392 MergeEdgeCallBackType cbMe(MergeEdgeCallBackType:: template from_method<SelfType,&SelfType::mergeEdges>(
this));
393 EraseEdgeCallBackType cbEe(EraseEdgeCallBackType:: template from_method<SelfType,&SelfType::eraseEdge>(
this));
395 mergeGraph_.registerMergeNodeCallBack(cbMn);
396 mergeGraph_.registerMergeEdgeCallBack(cbMe);
397 mergeGraph_.registerEraseEdgeCallBack(cbEe);
401 for(EdgeIt e(mergeGraph);e!=lemon::INVALID;++e){
402 const Edge edge = *e;
403 const BaseGraphEdge graphEdge=EdgeHelper::itemToGraphItem(mergeGraph_,edge);
404 const index_type edgeId = mergeGraph_.id(edge);
405 const ValueType currentWeight = this->getEdgeWeight(edge);
406 pq_.
push(edgeId,currentWeight);
407 minWeightEdgeMap_[graphEdge]=currentWeight;
415 const BaseGraphEdge aa=EdgeHelper::itemToGraphItem(mergeGraph_,a);
416 const BaseGraphEdge bb=EdgeHelper::itemToGraphItem(mergeGraph_,b);
417 EdgeIndicatorReference va=edgeIndicatorMap_[aa];
418 EdgeIndicatorReference vb=edgeIndicatorMap_[bb];
419 va*=edgeSizeMap_[aa];
420 vb*=edgeSizeMap_[bb];
424 edgeSizeMap_[aa]+=edgeSizeMap_[bb];
425 va/=(edgeSizeMap_[aa]);
426 vb/=edgeSizeMap_[bb];
433 const BaseGraphNode aa=NodeHelper::itemToGraphItem(mergeGraph_,a);
434 const BaseGraphNode bb=NodeHelper::itemToGraphItem(mergeGraph_,b);
435 NodeFeatureReference va=nodeFeatureMap_[aa];
436 NodeFeatureReference vb=nodeFeatureMap_[bb];
437 va*=nodeSizeMap_[aa];
438 vb*=nodeSizeMap_[bb];
440 nodeSizeMap_[aa]+=nodeSizeMap_[bb];
441 va/=(nodeSizeMap_[aa]);
442 vb/=nodeSizeMap_[bb];
446 const UInt32 labelA = nodeLabelMap_[aa];
447 const UInt32 labelB = nodeLabelMap_[bb];
449 if(labelA!=0 && labelB!=0 && labelA!=labelB){
450 throw std::runtime_error(
"both nodes have labels");
453 const UInt32 newLabel = std::max(labelA, labelB);
454 nodeLabelMap_[aa] = newLabel;
467 const Node newNode = mergeGraph_.inactiveEdgesNode(edge);
472 for (IncEdgeIt e(mergeGraph_,newNode);e!=lemon::INVALID;++e){
475 const Edge incEdge(*e);
478 const BaseGraphEdge incGraphEdge = EdgeHelper::itemToGraphItem(mergeGraph_,incEdge);
483 const ValueType newWeight = getEdgeWeight(incEdge);
489 pq_.
push(incEdge.id(),newWeight);
490 minWeightEdgeMap_[incGraphEdge]=newWeight;
498 index_type minLabel = pq_.
top();
499 while(mergeGraph_.hasEdgeId(minLabel)==
false){
501 minLabel = pq_.
top();
503 return Edge(minLabel);
508 index_type minLabel = pq_.
top();
509 while(mergeGraph_.hasEdgeId(minLabel)==
false){
511 minLabel = pq_.
top();
525 index_type minLabel = pq_.
top();
526 while(mergeGraph_.hasEdgeId(minLabel)==
false){
528 minLabel = pq_.
top();
536 ValueType getEdgeWeight(
const Edge & e){
538 const Node u = mergeGraph_.u(e);
539 const Node v = mergeGraph_.v(e);
541 const BaseGraphEdge ee=EdgeHelper::itemToGraphItem(mergeGraph_,e);
542 const BaseGraphNode uu=NodeHelper::itemToGraphItem(mergeGraph_,u);
543 const BaseGraphNode vv=NodeHelper::itemToGraphItem(mergeGraph_,v);
545 const float sizeU = nodeSizeMap_[uu];
546 const float sizeV = nodeSizeMap_[vv];
549 const ValueType wardFac = 2.0 / ( 1.0/std::pow(sizeU,wardness_) + 1/std::pow(sizeV,wardness_) );
551 const ValueType fromEdgeIndicator = edgeIndicatorMap_[ee];
552 ValueType fromNodeDist = metric_(nodeFeatureMap_[uu],nodeFeatureMap_[vv]);
553 ValueType totalWeight = ((1.0-beta_)*fromEdgeIndicator + beta_*fromNodeDist)*wardFac;
556 const UInt32 labelA = nodeLabelMap_[uu];
557 const UInt32 labelB = nodeLabelMap_[vv];
559 if(labelA!=0 && labelB!=0){
560 if(labelA == labelB){
561 totalWeight*=sameLabelMultiplier_;
564 totalWeight += gamma_;
571 MergeGraph & mergeGraph_;
572 EDGE_INDICATOR_MAP edgeIndicatorMap_;
573 EDGE_SIZE_MAP edgeSizeMap_;
574 NODE_FEATURE_MAP nodeFeatureMap_;
575 NODE_SIZE_MAP nodeSizeMap_;
576 MIN_WEIGHT_MAP minWeightEdgeMap_;
577 NODE_LABEL_MAP nodeLabelMap_;
582 ValueType sameLabelMultiplier_;
583 metrics::Metric<float> metric_;
603 const size_t nodeNumStopCond = 1,
604 const bool buildMergeTree =
false,
606 : nodeNumStopCond_ (nodeNumStopCond)
607 , maxMergeWeight_(NumericTraits<double>::max())
608 , nodeFeatureImportance_(0.5)
609 , sizeImportance_(1.0)
611 , buildMergeTreeEncoding_(buildMergeTree)
621 nodeNumStopCond_ = count;
631 maxMergeWeight_ = val;
644 vigra_precondition(0.0 <= val && val <= 1.0,
645 "ClusteringOptions::nodePropertyImportance(val): 0 <= val <= 1 required.");
646 nodeFeatureImportance_ = val;
660 vigra_precondition(0.0 <= val && val <= 1.0,
661 "ClusteringOptions::sizeImportance(val): 0 <= val <= 1 required.");
662 sizeImportance_ = val;
675 nodeFeatureMetric_ = metric;
681 buildMergeTreeEncoding_ = val;
695 size_t nodeNumStopCond_;
696 double maxMergeWeight_;
697 double nodeFeatureImportance_;
698 double sizeImportance_;
700 bool buildMergeTreeEncoding_;
705 template<
class CLUSTER_OPERATOR>
706 class HierarchicalClusteringImpl
709 typedef CLUSTER_OPERATOR ClusterOperator;
710 typedef typename ClusterOperator::MergeGraph MergeGraph;
711 typedef typename MergeGraph::Graph Graph;
712 typedef typename Graph::Edge BaseGraphEdge;
713 typedef typename Graph::Node BaseGraphNode;
714 typedef typename MergeGraph::Edge Edge;
715 typedef typename MergeGraph::Node Node;
716 typedef typename CLUSTER_OPERATOR::WeightType ValueType;
717 typedef typename MergeGraph::index_type MergeGraphIndexType;
719 typedef ClusteringOptions Parameter;
723 const MergeGraphIndexType a,
724 const MergeGraphIndexType b,
725 const MergeGraphIndexType r,
728 a_(a),b_(b),r_(r),w_(w){
730 MergeGraphIndexType a_;
731 MergeGraphIndexType b_;
732 MergeGraphIndexType r_;
736 typedef std::vector<MergeItem> MergeTreeEncoding;
739 HierarchicalClusteringImpl(
740 ClusterOperator & clusterOperator,
741 const Parameter & parameter = Parameter()
744 clusterOperator_(clusterOperator),
746 mergeGraph_(clusterOperator_.mergeGraph()),
747 graph_(mergeGraph_.graph()),
748 timestamp_(graph_.maxNodeId()+1),
750 timeStampIndexToMergeIndex_(),
751 mergeTreeEndcoding_()
753 if(param_.buildMergeTreeEncoding_){
756 mergeTreeEndcoding_.reserve(graph_.nodeNum()*2);
757 toTimeStamp_.resize(graph_.maxNodeId()+1);
758 timeStampIndexToMergeIndex_.resize(graph_.maxNodeId()+1);
759 for(MergeGraphIndexType nodeId=0;nodeId<=mergeGraph_.maxNodeId();++nodeId){
760 toTimeStamp_[nodeId]=nodeId;
772 while(mergeGraph_.nodeNum()>param_.nodeNumStopCond_ && mergeGraph_.edgeNum()>0 && !clusterOperator_.done()){
774 const Edge edgeToRemove = clusterOperator_.contractionEdge();
775 if(param_.buildMergeTreeEncoding_){
776 const MergeGraphIndexType uid = mergeGraph_.id(mergeGraph_.u(edgeToRemove));
777 const MergeGraphIndexType vid = mergeGraph_.id(mergeGraph_.v(edgeToRemove));
778 const ValueType w = clusterOperator_.contractionWeight();
780 mergeGraph_.contractEdge( edgeToRemove);
781 const MergeGraphIndexType aliveNodeId = mergeGraph_.hasNodeId(uid) ? uid : vid;
782 const MergeGraphIndexType deadNodeId = aliveNodeId==vid ? uid : vid;
783 timeStampIndexToMergeIndex_[timeStampToIndex(timestamp_)]=mergeTreeEndcoding_.size();
784 mergeTreeEndcoding_.push_back(MergeItem( toTimeStamp_[aliveNodeId],toTimeStamp_[deadNodeId],timestamp_,w));
785 toTimeStamp_[aliveNodeId]=timestamp_;
791 mergeGraph_.contractEdge( edgeToRemove );
793 if(param_.verbose_ && mergeGraph_.nodeNum()%1==0){
794 std::cout<<
"\rNodes: "<<std::setw(10)<<mergeGraph_.nodeNum()<<std::flush;
803 const MergeTreeEncoding & mergeTreeEndcoding()
const{
804 return mergeTreeEndcoding_;
807 template<
class EDGE_MAP>
808 void ucmTransform(EDGE_MAP & edgeMap)
const{
809 typedef typename Graph::EdgeIt BaseGraphEdgeIt;
811 for(BaseGraphEdgeIt iter(graph()); iter!=lemon::INVALID; ++iter ){
812 const BaseGraphEdge edge=*iter;
813 edgeMap[
edge] = edgeMap[mergeGraph().reprGraphEdge(edge)];
818 template<
class OUT_ITER>
819 size_t leafNodeIds(
const MergeGraphIndexType treeNodeId, OUT_ITER begin)
const{
820 if(treeNodeId<=graph_.maxNodeId()){
827 std::queue<MergeGraphIndexType> queue;
828 queue.push(treeNodeId);
830 while(!queue.empty()){
832 const MergeGraphIndexType
id = queue.front();
834 const MergeGraphIndexType mergeIndex = timeStampToMergeIndex(
id);
835 const MergeGraphIndexType ab[]= { mergeTreeEndcoding_[mergeIndex].a_, mergeTreeEndcoding_[mergeIndex].b_};
837 for(
size_t i=0;i<2;++i){
838 if(ab[i]<=graph_.maxNodeId()){
853 const Graph & graph()
const{
858 const MergeGraph & mergeGraph()
const{
863 const MergeGraphIndexType reprNodeId(
const MergeGraphIndexType
id)
const{
864 return mergeGraph_.reprNodeId(
id);
868 MergeGraphIndexType timeStampToIndex(
const MergeGraphIndexType timestamp)
const{
869 return timestamp- graph_.maxNodeId();
873 MergeGraphIndexType timeStampToMergeIndex(
const MergeGraphIndexType timestamp)
const{
874 return timeStampIndexToMergeIndex_[timeStampToIndex(timestamp)];
877 ClusterOperator & clusterOperator_;
879 MergeGraph & mergeGraph_;
880 const Graph & graph_;
885 MergeGraphIndexType timestamp_;
886 std::vector<MergeGraphIndexType> toTimeStamp_;
887 std::vector<MergeGraphIndexType> timeStampIndexToMergeIndex_;
889 MergeTreeEncoding mergeTreeEndcoding_;
990 template <
class GRAPH,
991 class EDGE_WEIGHT_MAP,
class EDGE_LENGTH_MAP,
992 class NODE_FEATURE_MAP,
class NOSE_SIZE_MAP,
993 class NODE_LABEL_MAP>
996 EDGE_WEIGHT_MAP
const & edgeWeights, EDGE_LENGTH_MAP
const & edgeLengths,
997 NODE_FEATURE_MAP
const & nodeFeatures, NOSE_SIZE_MAP
const & nodeSizes,
998 NODE_LABEL_MAP & labelMap,
999 ClusteringOptions options = ClusteringOptions())
1001 typedef typename NODE_LABEL_MAP::Value LabelType;
1002 typedef MergeGraphAdaptor<GRAPH> MergeGraph;
1003 typedef typename GRAPH::template EdgeMap<float> EdgeUltrametric;
1004 typedef typename GRAPH::template NodeMap<LabelType> NodeSeeds;
1006 MergeGraph mergeGraph(graph);
1011 EdgeUltrametric edgeUltrametric(graph);
1012 NodeSeeds nodeSeeds(graph);
1016 typedef cluster_operators::EdgeWeightNodeFeatures<
1026 MergeOperator mergeOperator(mergeGraph,
1027 edgeWeights, edgeLengths,
1028 nodeFeatures, nodeSizes,
1029 edgeUltrametric, nodeSeeds,
1030 options.nodeFeatureImportance_,
1031 options.nodeFeatureMetric_,
1032 options.sizeImportance_,
1033 options.maxMergeWeight_);
1035 typedef HierarchicalClusteringImpl<MergeOperator> Clustering;
1037 Clustering clustering(mergeOperator, options);
1038 clustering.cluster();
1040 for(
typename GRAPH::NodeIt node(graph); node != lemon::INVALID; ++node)
1042 labelMap[*node] = mergeGraph.reprNodeId(graph.id(*node));
1050 #endif // VIGRA_HIERARCHICAL_CLUSTERING_HXX
This Cluster Operator is a MONSTER. It can really do a lot.
Definition: hierarchical_clustering.hxx:325
MergeGraph & mergeGraph()
get a reference to the merge
Definition: hierarchical_clustering.hxx:519
ClusteringOptions & minRegionCount(size_t count)
Definition: hierarchical_clustering.hxx:619
priority_type topPriority() const
get top priority
Definition: priority_queue.hxx:496
ClusteringOptions & sizeImportance(double val)
Definition: hierarchical_clustering.hxx:658
ClusteringOptions & maxMergeDistance(double val)
Definition: hierarchical_clustering.hxx:629
ClusteringOptions & verbose(bool val=true)
Definition: hierarchical_clustering.hxx:689
Manhattan distance (L1 norm)
Definition: metrics.hxx:236
Options object for hierarchical clustering.
Definition: hierarchical_clustering.hxx:598
ClusteringOptions & nodeFeatureImportance(double val)
Definition: hierarchical_clustering.hxx:642
void push(const value_type i, const priority_type p)
Insert a index with a given priority.
Definition: priority_queue.hxx:475
MetricType
Tags to select a metric for vector distance computation.
Definition: metrics.hxx:229
doxygen_overloaded_function(template<...> void separableConvolveBlockwise) template< unsigned int N
Separated convolution on ChunkedArrays.
WeightType contractionWeight()
get the edge weight of the edge which should be contracted next
Definition: hierarchical_clustering.hxx:507
void hierarchicalClustering(...)
Reduce the number of nodes in a graph by iteratively contracting the cheapest edge.
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=static_cast< ValueType >(1.0), const ValueType gamma=static_cast< ValueType >(10000000.0), const ValueType sameLabelMultiplier=static_cast< ValueType >(0.8))
construct cluster operator
Definition: hierarchical_clustering.hxx:358
void mergeEdges(const Edge &a, const Edge &b)
will be called via callbacks from mergegraph
Definition: hierarchical_clustering.hxx:413
void eraseEdge(const Edge &edge)
will be called via callbacks from mergegraph
Definition: hierarchical_clustering.hxx:459
double gamma(double x)
The gamma function.
Definition: mathutil.hxx:1577
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
ClusteringOptions & nodeFeatureMetric(metrics::MetricType metric)
Definition: hierarchical_clustering.hxx:673
void mergeNodes(const Node &a, const Node &b)
will be called via callbacks from mergegraph
Definition: hierarchical_clustering.hxx:432
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
Edge contractionEdge()
get the edge which should be contracted next
Definition: hierarchical_clustering.hxx:497