168 value_type firstRep()
const{
171 value_type lastRep()
const{
176 const_iterator begin()
const{
182 const_iterator end()
const{
183 return ConstRepIter<T>(*
this,lastRep_+1);
187 const_iterator iteratorAt(
const value_type & rep)
const{
189 return ConstRepIter<T>(*
this,rep);
191 return ConstRepIter<T>(*
this,lastRep_+1);
194 bool isErased(
const value_type & value)
const{
195 return jumpVec_[value].first == -1 && jumpVec_[value].second == -1;
198 void eraseElement(
const value_type & value,
const bool reduceSize=
true){
199 const T notRep=value;
200 const T jumpMinus = jumpVec_[notRep].first;
201 const T jumpPlus = jumpVec_[notRep].second;
204 const T nextRep = notRep+jumpPlus;
206 jumpVec_[nextRep].first=0;
208 else if(jumpPlus==0){
210 const T prevRep = notRep-jumpMinus;
212 jumpVec_[prevRep].second=0;
216 const T nextRep = notRep+jumpPlus;
217 const T prevRep = notRep-jumpMinus;
218 jumpVec_[nextRep].first+=jumpVec_[notRep].first;
219 jumpVec_[prevRep].second+=jumpVec_[notRep].second;
224 jumpVec_[notRep].first =-1;
225 jumpVec_[notRep].second =-1;
229 std::vector<value_type> parents_;
230 std::vector<value_type> ranks_;
231 std::vector< std::pair< vigra::Int64, vigra::Int64> > jumpVec_;
232 value_type firstRep_;
234 value_type numberOfElements_;
235 value_type numberOfSets_;
246template<
class GRAPH,
class ITEM>
247struct MergeGraphItemHelper;
250struct MergeGraphItemHelper<MG,typename MG::Edge>{
251 typedef typename MG::Graph Graph;
252 typedef typename MG::index_type index_type ;
253 typedef typename MG::Edge Item;
254 typedef typename Graph::Edge GraphItem;
255 typedef typename MG::EdgeIt ItemIt;
258 static index_type maxItemId(
const MG & g){
259 return g.maxEdgeId();
261 static index_type itemNum(
const MG & g){
265 static GraphItem itemToGraphItem(
const MG & g,
const Item & item){
266 const index_type
id = g.id(item);
267 return g.graph().edgeFromId(
id);
272struct MergeGraphItemHelper<MG,typename MG::Node>{
273 typedef typename MG::Graph Graph;
274 typedef typename MG::index_type index_type ;
275 typedef typename MG::Node Item;
276 typedef typename Graph::Node GraphItem;
277 typedef typename MG::NodeIt ItemIt;
280 static index_type maxItemId(
const MG & g){
281 return g.maxNodeId();
283 static index_type itemNum(
const MG & g){
286 static GraphItem itemToGraphItem(
const MG & g,
const Item & item){
287 const index_type
id = g.id(item);
288 return g.graph().nodeFromId(
id);
293template<
class MERGE_GRAPH>
294class MergeGraphNodeIt
295:
public ForwardIteratorFacade<MergeGraphNodeIt<MERGE_GRAPH>,typename MERGE_GRAPH::Node,true>{
297 typedef MERGE_GRAPH Graph;
298 typedef typename Graph::Node Node;
300 MergeGraphNodeIt(
const lemon::Invalid & = lemon::INVALID)
306 MergeGraphNodeIt(
const Graph & g)
308 nodeIdIt_(g.nodeUfd_.begin()),
311 MergeGraphNodeIt(
const Graph & g,
const Node & node)
313 nodeIdIt_(g.nodeUfd_.iteratorAt(g.id(node))),
318 return graph_==NULL || nodeIdIt_==graph_->nodeUfd_.end();
321 return graph_!=NULL && nodeIdIt_==graph_->nodeUfd_.begin();
324 friend class vigra::IteratorFacadeCoreAccess;
327 bool equal(
const MergeGraphNodeIt<MERGE_GRAPH> & other)
const{
328 return (isEnd()&&other.isEnd()) || nodeIdIt_==other.nodeIdIt_;
330 void increment(){++nodeIdIt_;}
331 const Node & dereference()
const{
332 node_=Node(*nodeIdIt_);
336 const Graph * graph_;
337 typename Graph::NodeIdIt nodeIdIt_;
342template<
class MERGE_GRAPH>
343class MergeGraphEdgeIt
344:
public ForwardIteratorFacade<MergeGraphEdgeIt<MERGE_GRAPH>,typename MERGE_GRAPH::Edge,true>{
346 typedef MERGE_GRAPH Graph;
347 typedef typename Graph::Edge Edge;
349 MergeGraphEdgeIt(
const lemon::Invalid & = lemon::INVALID)
354 MergeGraphEdgeIt(
const Graph & g)
356 edgeIdIt_(g.edgeUfd_.begin()),
360 MergeGraphEdgeIt(
const Graph & g,
const Edge & node)
362 edgeIdIt_(g.edgeUfd_.iteratorAt(g.id(node))),
366 return graph_==NULL || edgeIdIt_==graph_->edgeUfd_.end();
369 return graph_!=NULL && edgeIdIt_==graph_->edgeUfd_.begin();
372 friend class vigra::IteratorFacadeCoreAccess;
375 bool equal(
const MergeGraphEdgeIt<MERGE_GRAPH> & other)
const{
376 return (isEnd()&&other.isEnd()) || edgeIdIt_==other.edgeIdIt_;
381 const Edge & dereference()
const{
382 edge_=Edge(*edgeIdIt_);
386 const Graph * graph_;
387 typename Graph::EdgeIdIt edgeIdIt_;
394:
public ForwardIteratorFacade<
395 MergeGraphArcIt<GRAPH>,typename GRAPH::Arc,true
400 typedef typename Graph::Arc Arc;
401 typedef typename Graph::Edge Edge;
402 typedef typename Graph::EdgeIt EdgeIt;
403 MergeGraphArcIt(
const lemon::Invalid = lemon::INVALID )
410 MergeGraphArcIt(
const GRAPH & g )
414 veryEnd_( g.edgeNum()==0 ? true : false),
418 MergeGraphArcIt(
const GRAPH & g ,
const Arc & arc )
420 pos_(g,arc.edgeId()),
421 inFirstHalf_(g.id(arc)<=g.maxEdgeId()),
426 friend class vigra::IteratorFacadeCoreAccess;
428 return veryEnd_ || graph_==NULL;
432 return graph_!=NULL && veryEnd_==
false && pos_ == EdgeIt(*graph_);
438 if(pos_ == lemon::INVALID ) {
439 pos_ = EdgeIt(*graph_);
446 if(pos_ == lemon::INVALID){
454 bool equal(MergeGraphArcIt
const& other)
const{
457 isEnd()==other.isEnd() &&
458 inFirstHalf_==other.inFirstHalf_
460 (isEnd() || graph_==NULL || pos_==other.pos_ )
465 const Arc & dereference()
const {
467 arc_ = graph_->direct(*pos_,inFirstHalf_);
472 const GRAPH * graph_;
482template<
class NODE,
class EDGE>
483class MergeGraphCallbacks{
486 typedef delegate2<void ,const NODE & ,const NODE &> MergeNodeCallBackType;
487 typedef delegate2<void ,const EDGE & ,const EDGE &> MergeEdgeCallBackType;
488 typedef delegate1<void ,const EDGE &> EraseEdgeCallBackType;
490 MergeGraphCallbacks(){}
492 void registerMergeNodeCallBack(MergeNodeCallBackType f){
493 mergeNodeCallbacks_.push_back(f);
495 void registerMergeEdgeCallBack(MergeEdgeCallBackType f){
496 mergeEdgeCallbacks_.push_back(f);
498 void registerEraseEdgeCallBack(EraseEdgeCallBackType f){
499 eraseEdgeCallbacks_.push_back(f);
503 void callMergeNodeCallbacks(
const NODE & a,
const NODE & b){
504 for(
size_t i=0;i<mergeNodeCallbacks_.size();++i)
505 mergeNodeCallbacks_[i](a,b);
507 void callMergeEdgeCallbacks(
const EDGE & a,
const EDGE & b){
508 for(
size_t i=0;i<mergeEdgeCallbacks_.size();++i)
509 mergeEdgeCallbacks_[i](a,b);
511 void callEraseEdgeCallbacks(
const EDGE & a){
512 for(
size_t i=0;i<eraseEdgeCallbacks_.size();++i)
513 eraseEdgeCallbacks_[i](a);
515 void clearCallbacks(){
516 mergeNodeCallbacks_.clear();
517 mergeEdgeCallbacks_.clear();
518 eraseEdgeCallbacks_.clear();
521 std::vector<MergeNodeCallBackType> mergeNodeCallbacks_;
522 std::vector<MergeEdgeCallBackType> mergeEdgeCallbacks_;
523 std::vector<EraseEdgeCallBackType> eraseEdgeCallbacks_;
533:
public MergeGraphCallbacks<
534 detail::GenericNode<vigra::Int64> ,
535 detail::GenericEdge<vigra::Int64>
542 typedef IdType index_type;
546 typedef detail::GenericNode<index_type> Node;
547 typedef detail::GenericEdge<index_type> Edge;
548 typedef detail::GenericArc<index_type> Arc;
551 typedef typename Graph::Node GraphNode;
552 typedef typename Graph::Edge GraphEdge;
553 typedef typename Graph::Node GraphArc;
560 typedef detail::GenericNodeImpl<index_type,false > NodeStorage;
561 typedef detail::GenericEdgeImpl<index_type > EdgeStorage;
567 typedef std::map<vigra::UInt64 , std::vector<IdType> > DoubleMap;
572 typedef detail::NeighborNodeFilter<MergeGraphType> NnFilter;
573 typedef detail::IncEdgeFilter<MergeGraphType> IncFilter;
574 typedef detail::IsInFilter<MergeGraphType> InFlter;
575 typedef detail::IsOutFilter<MergeGraphType> OutFilter;
580 typedef detail::GenericIncEdgeIt<MergeGraphType,NodeStorage,NnFilter > NeighborNodeIt;
581 typedef detail::GenericIncEdgeIt<MergeGraphType,NodeStorage,IncFilter > IncEdgeIt;
582 typedef detail::GenericIncEdgeIt<MergeGraphType,NodeStorage,InFlter > InArcIt;
583 typedef detail::GenericIncEdgeIt<MergeGraphType,NodeStorage,OutFilter > OutArcIt;
588 struct EdgeMap : DenseEdgeReferenceMap<MergeGraphType,T> {
600 struct NodeMap : DenseNodeReferenceMap<MergeGraphType,T> {
612 struct ArcMap : DenseArcReferenceMap<MergeGraphType,T> {
634 size_t edgeNum()
const;
635 size_t nodeNum()
const;
636 size_t arcNum()
const;
638 IdType maxEdgeId()
const;
639 IdType maxNodeId()
const;
640 IdType maxArcId()
const;
653 Edge edgeFromId(
const IdType index)
const;
654 Node nodeFromId(
const IdType index)
const;
655 Arc arcFromId(
const IdType index)
const;
662 bool hasEdgeId(
const IdType edgeIndex)
const;
663 bool hasNodeId(
const IdType
nodeIndex)
const;
664 bool hasArcId(
const IdType
arcId)
const{
665 return hasEdgeId(arcFromId(
arcId).edgeId());
669 Edge findEdge(
const Node & a,
const Node & b)
const;
670 Arc findArc(
const Node & u,
const Node & v)
const;
673 IdType id(
const Edge & edge)
const;
674 IdType id(
const Node & node)
const;
675 IdType id(
const Arc &
arc)
const;
678 size_t degree(
const Node & node)
const;
682 Node u(
const Edge & edge)
const;
683 Node v(
const Edge & edge)
const;
685 Node source(
const Arc &
arc)
const{
686 if(
arc!=lemon::INVALID)
687 return direction(
arc) ? u(Edge(
arc)) : v(Edge(
arc));
689 return Node(lemon::INVALID);
691 Node target(
const Arc &
arc)
const{
692 if(
arc!=lemon::INVALID)
693 return direction(
arc) ? v(Edge(
arc)) : u(Edge(
arc));
695 return Node(lemon::INVALID);
700 IdType reprEdgeId(
const IdType edgeIndex)
const;
701 IdType reprNodeId(
const IdType
nodeIndex)
const;
702 bool stateOfInitalEdge(
const IdType
initalEdge)
const;
704 void contractEdge(
const Edge & edge);
707 Node oppositeNode(Node
const &n,
const Edge &e)
const {
708 const Node
uNode = u(e);
709 const Node
vNode = v(e);
710 if(
id(
uNode)==
id(n)){
713 else if(
id(
vNode)==
id(n)){
717 return Node(lemon::INVALID);
722 Arc direct(
const Edge & edge,
const bool forward)
const{
723 if(edge!=lemon::INVALID){
725 return Arc(
id(edge),
id(edge));
727 return Arc(
id(edge)+(maxEdgeId()+1),
id(edge));
730 return Arc(lemon::INVALID);
733 Arc direct(
const Edge & edge,
const Node & node)
const{
735 return direct(edge,
true);
736 else if(v(edge)==node)
737 return direct(edge,
false);
739 return Arc(lemon::INVALID);
742 bool direction(
const Arc &
arc)
const{
743 return arc.id()==
arc.edgeId();
748 GraphEdge reprGraphEdge(
const GraphEdge & edge)
const{
749 return graph_.edgeFromId(reprEdgeId(graph_.id(edge)));
751 GraphNode reprGraphNode(
const GraphNode & node)
const{
752 return graph_.nodeFromId(reprNodeId(graph_.id(node)));
756 Edge reprEdge(
const GraphEdge & edge)
const{
757 return edgeFromId(reprEdgeId(graph_.id(edge)));
759 Node reprNode(
const GraphNode & node)
const{
760 return nodeFromId(reprNodeId(graph_.id(node)));
763 const Graph & graph()
const{
766 const Graph & graph(){
771 Node inactiveEdgesNode(
const Edge edge)
const{
772 return reprNodeId(graphUId(
id(edge)));
774 size_t maxDegree()
const{
776 for(NodeIt it(*
this);it!=lemon::INVALID;++it){
777 std::max(
md,
size_t( degree(*it) ) );
786 template<
class G,
class NIMPL,
class FILT>
787 friend class detail::GenericIncEdgeIt;
790 friend struct detail::NeighborNodeFilter;
792 friend struct detail::IncEdgeFilter;
794 friend struct detail::BackEdgeFilter;
796 friend struct detail::IsOutFilter;
798 friend struct detail::IsInFilter;
803 Edge edgeFromIdUnsave(
const IdType index)
const;
805 index_type uId(
const index_type edgeId)
const;
806 index_type vId(
const index_type edgeId)
const;
807 index_type graphUId(
const index_type edgeId)
const;
808 index_type graphVId(
const index_type edgeId)
const;
811 const NodeStorage & nodeImpl(
const Node & node)
const{
812 return nodeVector_[id(node)];
814 NodeStorage & nodeImpl(
const Node & node){
815 return nodeVector_[id(node)];
819 const GRAPH & graph_;
823 std::vector< NodeStorage > nodeVector_;
825 size_t nDoubleEdges_;
826 std::vector<std::pair<index_type,index_type> > doubleEdges_;
832: MergeGraphCallbacks<Node,Edge >(),
834 nodeUfd_(graph.maxNodeId()+1),
835 edgeUfd_(graph.maxEdgeId()+1),
836 nodeVector_(graph.maxNodeId()+1),
838 doubleEdges_(graph_.edgeNum()/2 +1)
845 nodeVector_[possibleNodeId].id_ = possibleNodeId;
848 for(index_type possibleEdgeId = 0 ; possibleEdgeId <= graph_.maxEdgeId(); ++possibleEdgeId){
849 const GraphEdge possibleEdge(graph_.edgeFromId(possibleEdgeId));
850 if(possibleEdge==lemon::INVALID){
851 edgeUfd_.eraseElement(possibleEdgeId);
854 const index_type guid = graphUId(possibleEdgeId);
855 const index_type gvid = graphVId(possibleEdgeId);
856 nodeVector_[ guid ].insert(gvid,possibleEdgeId);
857 nodeVector_[ gvid ].insert(guid,possibleEdgeId);
865void MergeGraphAdaptor<GRAPH>::reset (){
867 nodeUfd_.reset(graph_.maxNodeId()+1),
868 edgeUfd_.reset(graph_.maxEdgeId()+1),
870 this->clearCallbacks();
900inline typename MergeGraphAdaptor<GRAPH>::Edge
901MergeGraphAdaptor<GRAPH>::findEdge (
902 const typename MergeGraphAdaptor<GRAPH>::Node & a,
903 const typename MergeGraphAdaptor<GRAPH>::Node & b
907 std::pair<index_type,bool> res = nodeVector_[id(a)].findEdge(
id(b));
909 return Edge(res.first);
912 return Edge(lemon::INVALID);
916inline typename MergeGraphAdaptor<GRAPH>::Arc
917MergeGraphAdaptor<GRAPH>::findArc (
918 const typename MergeGraphAdaptor<GRAPH>::Node & uNode,
919 const typename MergeGraphAdaptor<GRAPH>::Node & vNode
922 if(edge==lemon::INVALID)
923 return Arc(lemon::INVALID);
925 return direct(edge,u(edge)==
uNode);
930inline typename MergeGraphAdaptor<GRAPH>::Node
931MergeGraphAdaptor<GRAPH>::u(
const Edge & edge)
const{
932 return nodeFromId(uId(
id(edge)));
936inline typename MergeGraphAdaptor<GRAPH>::Node
937MergeGraphAdaptor<GRAPH>::v(
const Edge & edge)
const{
938 return nodeFromId(vId(
id(edge)));
942inline typename MergeGraphAdaptor<GRAPH>::index_type
943MergeGraphAdaptor<GRAPH>::uId(
const index_type edgeId)
const{
944 return reprNodeId(graphUId(edgeId));
948inline typename MergeGraphAdaptor<GRAPH>::index_type
949MergeGraphAdaptor<GRAPH>::vId(
const index_type edgeId)
const{
950 return reprNodeId(graphVId(edgeId));
956inline typename MergeGraphAdaptor<GRAPH>::index_type
957MergeGraphAdaptor<GRAPH>::graphUId(
const index_type edgeId)
const{
958 return graph_.id(graph_.u(graph_.edgeFromId(edgeId)));
962inline typename MergeGraphAdaptor<GRAPH>::index_type
963MergeGraphAdaptor<GRAPH>::graphVId(
const index_type edgeId)
const{
964 return graph_.id(graph_.v(graph_.edgeFromId(edgeId)));
969inline typename MergeGraphAdaptor<GRAPH>::IdType
970MergeGraphAdaptor<GRAPH>::maxEdgeId()
const {
971 return static_cast<index_type
>(edgeUfd_.lastRep());
974inline typename MergeGraphAdaptor<GRAPH>::IdType
975MergeGraphAdaptor<GRAPH>::maxNodeId()
const {
976 return static_cast<index_type
>(nodeUfd_.lastRep());
980inline typename MergeGraphAdaptor<GRAPH>::IdType
981MergeGraphAdaptor<GRAPH>::maxArcId()
const {
982 return maxEdgeId()*2 +1 ;
989inline typename MergeGraphAdaptor<GRAPH>::IdType
990MergeGraphAdaptor<GRAPH>::id(
991 const typename MergeGraphAdaptor<GRAPH>::Edge & edge
997inline typename MergeGraphAdaptor<GRAPH>::IdType
998MergeGraphAdaptor<GRAPH>::id(
999 const typename MergeGraphAdaptor<GRAPH>::Node & node
1004template<
class GRAPH>
1005inline typename MergeGraphAdaptor<GRAPH>::IdType
1006MergeGraphAdaptor<GRAPH>::id(
1007 const typename MergeGraphAdaptor<GRAPH>::Arc & arc
1015template<
class GRAPH>
1017MergeGraphAdaptor<GRAPH>::degree(
1018 typename MergeGraphAdaptor<GRAPH>::Node
const & node
1020 return static_cast<size_t>( nodeVector_[id(node)].edgeNum() );
1025template<
class GRAPH>
1026inline typename MergeGraphAdaptor<GRAPH>::EdgeIdIt
1027MergeGraphAdaptor<GRAPH>::edgeIdsBegin()
const{
1028 return edgeUfd_.begin();
1031template<
class GRAPH>
1032inline typename MergeGraphAdaptor<GRAPH>::EdgeIdIt
1033MergeGraphAdaptor<GRAPH>::edgeIdsEnd()
const{
1034 return edgeUfd_.end();
1038template<
class GRAPH>
1039inline typename MergeGraphAdaptor<GRAPH>::NodeIdIt
1040MergeGraphAdaptor<GRAPH>::nodeIdsBegin()
const{
1041 return nodeUfd_.begin();
1044template<
class GRAPH>
1045inline typename MergeGraphAdaptor<GRAPH>::NodeIdIt
1046MergeGraphAdaptor<GRAPH>::nodeIdsEnd()
const{
1047 return nodeUfd_.end();
1051template<
class GRAPH>
1052inline typename MergeGraphAdaptor<GRAPH>::Edge
1053MergeGraphAdaptor<GRAPH>::edgeFromIdUnsave(
1054 const typename MergeGraphAdaptor<GRAPH>::IdType index
1059template<
class GRAPH>
1060inline typename MergeGraphAdaptor<GRAPH>::Edge
1061MergeGraphAdaptor<GRAPH>::edgeFromId(
1062 const typename MergeGraphAdaptor<GRAPH>::IdType index
1064 if (hasEdgeId(index))
1067 return Edge(lemon::INVALID);
1070template<
class GRAPH>
1071inline typename MergeGraphAdaptor<GRAPH>::Node
1072MergeGraphAdaptor<GRAPH>::nodeFromId(
1073 const typename MergeGraphAdaptor<GRAPH>::IdType index
1075 if(hasNodeId(index))
1078 return Node(lemon::INVALID);
1081template<
class GRAPH>
1082inline typename MergeGraphAdaptor<GRAPH>::Arc
1083MergeGraphAdaptor<GRAPH>::arcFromId(
1084 const typename MergeGraphAdaptor<GRAPH>::IdType index
1086 if(index<=maxEdgeId( ))
1087 return Arc(index,index);
1089 return Arc(index, index-maxEdgeId() -1);
1092template<
class GRAPH>
1094MergeGraphAdaptor<GRAPH>::hasEdgeId(
1095 const typename MergeGraphAdaptor<GRAPH>::IdType edgeIndex
1097 if(edgeIndex<=maxEdgeId() && !edgeUfd_.isErased(edgeIndex)){
1113template<
class GRAPH>
1115MergeGraphAdaptor<GRAPH>::hasNodeId(
1116 const typename MergeGraphAdaptor<GRAPH>::IdType nodeIndex
1122template<
class GRAPH>
1123inline typename MergeGraphAdaptor<GRAPH>::IdType
1124MergeGraphAdaptor<GRAPH>::reprEdgeId(
1125 const typename MergeGraphAdaptor<GRAPH>::IdType edgeIndex
1127 return edgeUfd_.find(edgeIndex);
1130template<
class GRAPH>
1131inline typename MergeGraphAdaptor<GRAPH>::IdType
1132MergeGraphAdaptor<GRAPH>::reprNodeId(
1133 const typename MergeGraphAdaptor<GRAPH>::IdType nodeIndex
1138template<
class GRAPH>
1139inline bool MergeGraphAdaptor<GRAPH>::stateOfInitalEdge(
1140 const typename MergeGraphAdaptor<GRAPH>::IdType initalEdge
1148template<
class GRAPH>
1149inline size_t MergeGraphAdaptor<GRAPH>::nodeNum()
const{
1150 return nodeUfd_.numberOfSets();
1153template<
class GRAPH>
1154inline size_t MergeGraphAdaptor<GRAPH>::arcNum()
const{
1158template<
class GRAPH>
1159inline size_t MergeGraphAdaptor<GRAPH>::edgeNum()
const{
1160 return edgeUfd_.numberOfSets();
1163template<
class GRAPH>
1164void MergeGraphAdaptor<GRAPH>::contractEdge(
1165 const typename MergeGraphAdaptor<GRAPH>::Edge & toDeleteEdge
1176 typename NodeStorage::AdjIt iter=nodeVector_[
notNewNodeRep].adjacencyBegin();
1177 typename NodeStorage::AdjIt
end =nodeVector_[
notNewNodeRep].adjacencyEnd();
1180 for(;iter!=
end;++iter){
1190 edgeUfd_.merge(iter->edgeId(),
found.first);
1192 const index_type
edgeA = iter->edgeId();
1194 const index_type
edgeR = edgeUfd_.find(
edgeA);
1207 doubleEdges_[nDoubleEdges_]=std::pair<index_type,index_type>(
edgeR,
edgeNR );
1235 for(
size_t de=0;
de<nDoubleEdges_;++
de){
1236 this->callMergeEdgeCallbacks(Edge(doubleEdges_[
de].first),Edge(doubleEdges_[
de].second));
1246namespace merge_graph_detail {
1255 numberOfElements_(0),
1267 const value_type& size
1274 numberOfElements_(size),
1277 for(T
j=0;
j<size; ++
j) {
1278 parents_[
static_cast<SizeTType
>(
j)] =
j;
1281 jumpVec_.front().first=0;
1282 jumpVec_.front().second=1;
1283 for(T
j=1;
j<size-1;++
j){
1284 jumpVec_[
j].first =1;
1285 jumpVec_[
j].second=1;
1287 jumpVec_.back().first=1;
1288 jumpVec_.back().second=0;
1299 const value_type& size
1302 numberOfElements_ = size;
1303 numberOfSets_ = size;
1304 ranks_.resize(
static_cast<SizeTType
>(size));
1305 parents_.resize(
static_cast<SizeTType
>(size));
1306 jumpVec_.resize(
static_cast<SizeTType
>(size));
1308 lastRep_=
static_cast<SizeTType
>(size)-1;
1309 for(T
j=0;
j<size; ++
j) {
1310 ranks_[
static_cast<SizeTType
>(
j)] = 0;
1311 parents_[
static_cast<SizeTType
>(
j)] =
j;
1314 jumpVec_.front().first=0;
1315 jumpVec_.front().second=1;
1316 for(T
j=1;
j<size-1;++
j){
1317 jumpVec_[
j].first =1;
1318 jumpVec_[
j].second=1;
1320 jumpVec_.back().first=1;
1321 jumpVec_.back().second=0;
1331inline typename IterablePartition<T>::value_type
1339 while(parents_[
static_cast<SizeTType
>(root)] != root) {
1340 root = parents_[
static_cast<SizeTType
>(root)];
1352inline typename IterablePartition<T>::value_type
1360 while(parents_[
static_cast<SizeTType
>(root)] != root) {
1361 root = parents_[
static_cast<SizeTType
>(root)];
1365 value_type
tmp = parents_[
static_cast<SizeTType
>(
element)];
1366 parents_[
static_cast<SizeTType
>(
element)] = root;
1390 if(ranks_[
static_cast<SizeTType
>(
element1)] < ranks_[
static_cast<SizeTType
>(
element2)]) {
1396 else if(ranks_[
static_cast<SizeTType
>(
element1)] > ranks_[
static_cast<SizeTType
>(
element2)]) {
1404 ++ranks_[
static_cast<SizeTType
>(
element1)];
1409 this->eraseElement(
notRep,
false);