38#ifndef VIGRA_NEW_MERGE_GRAPH_HXX
39#define VIGRA_NEW_MERGE_GRAPH_HXX
43#include "delegate/delegate.hxx"
53#include "multi_array.hxx"
54#include "tinyvector.hxx"
55#include "multi_array.hxx"
57#include "graph_maps.hxx"
58#include "graph_item_impl.hxx"
59#include "random_access_set.hxx"
60#include "iteratorfacade.hxx"
65namespace merge_graph_detail {
77:
public ForwardIteratorFacade<
78 ConstRepIter<T>,T,true
82 typedef IterablePartition<T> IterablePartitionType;
83 ConstRepIter(
const IterablePartitionType & p,
const T cr)
96 friend class vigra::IteratorFacadeCoreAccess;
100 return partition_!=NULL && currentRep_==partition_->firstRep();
103 return partition_==NULL || currentRep_>partition_->lastRep();
106 bool equal(
const ConstRepIter & other)
const{
107 return (this->isEnd() && other.isEnd() ) || ((this->isEnd()==other.isEnd() ) && this->currentRep_==other.currentRep_);
111 if(partition_->jumpVec_[currentRep_].second==0){
115 currentRep_+=partition_->jumpVec_[currentRep_].second;
120 if(partition_->jumpVec_[currentRep_].first==0){
125 currentRep_-=partition_->jumpVec_[currentRep_].first;
129 const T & dereference()
const{
135 const IterablePartitionType * partition_;
149 friend struct ConstRepIter<T>;
150 typedef T value_type;
151 typedef std::size_t SizeTType;
156 value_type
find(
const value_type&)
const;
158 value_type numberOfElements()
const;
159 value_type numberOfSets()
const;
160 template<
class Iterator>
void elementLabeling(Iterator)
const;
161 template<
class Iterator>
void representatives(Iterator)
const;
162 void representativeLabeling(std::map<value_type, value_type>&)
const;
168 value_type firstRep()
const{
171 value_type lastRep()
const{
178 return ConstRepIter<T>(*
this,firstRep_);
180 return ConstRepIter<T>(*
this,lastRep_+1);
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_;
532class MergeGraphAdaptor
533:
public MergeGraphCallbacks<
534 detail::GenericNode<vigra::Int64> ,
535 detail::GenericEdge<vigra::Int64>
542 typedef IdType index_type;
543 typedef MergeGraphAdaptor<GRAPH> MergeGraphType;
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;
569 typedef typename UfdType::const_iterator ConstUdfIter;
570 typedef ConstUdfIter EdgeIdIt;
571 typedef ConstUdfIter NodeIdIt;
572 typedef detail::NeighborNodeFilter<MergeGraphType> NnFilter;
573 typedef detail::IncEdgeFilter<MergeGraphType> IncFilter;
574 typedef detail::IsInFilter<MergeGraphType> InFlter;
575 typedef detail::IsOutFilter<MergeGraphType> OutFilter;
577 typedef MergeGraphNodeIt<MergeGraphType> NodeIt;
578 typedef MergeGraphEdgeIt<MergeGraphType> EdgeIt;
579 typedef MergeGraphArcIt<MergeGraphType> ArcIt;
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> {
589 EdgeMap(): DenseEdgeReferenceMap<MergeGraphType,T>(){
591 EdgeMap(
const MergeGraphType & g)
592 : DenseEdgeReferenceMap<MergeGraphType,T>(g){
594 EdgeMap(
const MergeGraphType & g,
const T & val)
595 : DenseEdgeReferenceMap<MergeGraphType,T>(g,val){
600 struct NodeMap : DenseNodeReferenceMap<MergeGraphType,T> {
601 NodeMap(): DenseNodeReferenceMap<MergeGraphType,T>(){
603 NodeMap(
const MergeGraphType & g)
604 : DenseNodeReferenceMap<MergeGraphType,T>(g){
606 NodeMap(
const MergeGraphType & g,
const T & val)
607 : DenseNodeReferenceMap<MergeGraphType,T>(g,val){
612 struct ArcMap : DenseArcReferenceMap<MergeGraphType,T> {
613 ArcMap(): DenseArcReferenceMap<MergeGraphType,T>(){
615 ArcMap(
const MergeGraphType & g)
616 : DenseArcReferenceMap<MergeGraphType,T>(g){
618 ArcMap(
const MergeGraphType & g,
const T & val)
619 : DenseArcReferenceMap<MergeGraphType,T>(g,val){
627 MergeGraphAdaptor(
const MergeGraphAdaptor& other );
628 MergeGraphAdaptor& operator=(
const MergeGraphAdaptor& );
630 MergeGraphAdaptor(
const Graph & graph);
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;
644 EdgeIdIt edgeIdsBegin()
const;
645 EdgeIdIt edgeIdsEnd()
const;
646 NodeIdIt nodeIdsBegin()
const;
647 NodeIdIt nodeIdsEnd()
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 md = 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;
799 friend class MergeGraphNodeIt<MergeGraphType>;
800 friend class MergeGraphArcIt<MergeGraphType>;
801 friend class MergeGraphEdgeIt<MergeGraphType>;
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_;
831MergeGraphAdaptor<GRAPH>::MergeGraphAdaptor(
const GRAPH & graph )
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)
840 for(index_type possibleNodeId = 0 ; possibleNodeId <= graph_.maxNodeId(); ++possibleNodeId){
841 if(graph_.nodeFromId(possibleNodeId)==lemon::INVALID){
842 nodeUfd_.eraseElement(possibleNodeId);
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();
873 for(index_type possibleNodeId = 0 ; possibleNodeId <= graph_.maxNodeId(); ++possibleNodeId){
875 nodeVector_[possibleNodeId].clear();
876 if(graph_.nodeFromId(possibleNodeId)==lemon::INVALID){
877 nodeUfd_.eraseElement(possibleNodeId);
880 nodeVector_[possibleNodeId].id_ = possibleNodeId;
884 for(index_type possibleEdgeId = 0 ; possibleEdgeId <= graph_.maxEdgeId(); ++possibleEdgeId){
885 const GraphEdge possibleEdge(graph_.edgeFromId(possibleEdgeId));
886 if(possibleEdge==lemon::INVALID){
887 edgeUfd_.eraseElement(possibleEdgeId);
890 const index_type guid = graphUId(possibleEdgeId);
891 const index_type gvid = graphVId(possibleEdgeId);
892 nodeVector_[ guid ].insert(gvid,possibleEdgeId);
893 nodeVector_[ gvid ].insert(guid,possibleEdgeId);
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
921 const Edge edge = findEdge(uNode,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)){
1098 const IdType reprEdgeIndex = reprEdgeId(edgeIndex);
1099 if(reprEdgeIndex!=edgeIndex){
1103 const index_type rnid0= uId(reprEdgeIndex);
1104 const index_type rnid1= vId(reprEdgeIndex);
1105 return rnid0!=rnid1;
1113template<
class GRAPH>
1115MergeGraphAdaptor<GRAPH>::hasNodeId(
1116 const typename MergeGraphAdaptor<GRAPH>::IdType nodeIndex
1119 return nodeIndex<=maxNodeId() && !nodeUfd_.isErased(nodeIndex) && nodeUfd_.find(nodeIndex)==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
1135 return nodeUfd_.find(nodeIndex);
1138template<
class GRAPH>
1139inline bool MergeGraphAdaptor<GRAPH>::stateOfInitalEdge(
1140 const typename MergeGraphAdaptor<GRAPH>::IdType initalEdge
1143 const index_type rnid0= reprNodeId( graphUId(initalEdge) );
1144 const index_type rnid1= reprNodeId( graphVId(initalEdge) );
1145 return rnid0!=rnid1;
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
1168 const index_type toDeleteEdgeIndex = id(toDeleteEdge);
1169 const index_type nodesIds[2]={id(u(toDeleteEdge)),id(v(toDeleteEdge))};
1172 nodeUfd_.merge(nodesIds[0],nodesIds[1]);
1173 const IdType newNodeRep = reprNodeId(nodesIds[0]);
1174 const IdType notNewNodeRep = (newNodeRep == nodesIds[0] ? nodesIds[1] : nodesIds[0] );
1176 typename NodeStorage::AdjIt iter=nodeVector_[notNewNodeRep].adjacencyBegin();
1177 typename NodeStorage::AdjIt end =nodeVector_[notNewNodeRep].adjacencyEnd();
1180 for(;iter!=end;++iter){
1181 const size_t adjToDeadNodeId = iter->nodeId();
1182 if(newNodeRep < 0 || adjToDeadNodeId!=
static_cast<unsigned long long>(newNodeRep)){
1186 std::pair<index_type,bool> found=nodeVector_[adjToDeadNodeId].findEdge(newNodeRep);
1190 edgeUfd_.merge(iter->edgeId(),found.first);
1192 const index_type edgeA = iter->edgeId();
1193 const index_type edgeB = found.first;
1194 const index_type edgeR = edgeUfd_.find(edgeA);
1195 const index_type edgeNR = edgeR==edgeA ? edgeB : edgeA;
1197 nodeVector_[adjToDeadNodeId].eraseFromAdjacency(notNewNodeRep);
1200 nodeVector_[adjToDeadNodeId].eraseFromAdjacency(newNodeRep);
1201 nodeVector_[adjToDeadNodeId].insert(newNodeRep,edgeR);
1204 nodeVector_[newNodeRep].eraseFromAdjacency(adjToDeadNodeId);
1205 nodeVector_[newNodeRep].insert(adjToDeadNodeId,edgeR);
1207 doubleEdges_[nDoubleEdges_]=std::pair<index_type,index_type>(edgeR,edgeNR );
1211 nodeVector_[adjToDeadNodeId].eraseFromAdjacency(notNewNodeRep);
1213 nodeVector_[adjToDeadNodeId].insert(newNodeRep,iter->edgeId());
1217 nodeVector_[newNodeRep].insert(adjToDeadNodeId,iter->edgeId());
1224 nodeVector_[newNodeRep].eraseFromAdjacency(notNewNodeRep);
1226 nodeVector_[notNewNodeRep].clear();
1228 edgeUfd_.eraseElement(toDeleteEdgeIndex);
1232 this->callMergeNodeCallbacks(Node(newNodeRep),Node(notNewNodeRep));
1235 for(
size_t de=0;de<nDoubleEdges_;++de){
1236 this->callMergeEdgeCallbacks(Edge(doubleEdges_[de].first),Edge(doubleEdges_[de].second));
1239 this->callEraseEdgeCallbacks(Edge(toDeleteEdgeIndex));
1246namespace merge_graph_detail {
1255 numberOfElements_(0),
1267 const value_type& size
1269: parents_(static_cast<SizeTType>(size)),
1270 ranks_(static_cast<SizeTType>(size)),
1271 jumpVec_(static_cast<SizeTType>(size)),
1273 lastRep_(static_cast<SizeTType>(size)-1),
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
1334 const value_type& element
1338 value_type root = element;
1339 while(parents_[
static_cast<SizeTType
>(root)] != root) {
1340 root = parents_[
static_cast<SizeTType
>(root)];
1352inline typename IterablePartition<T>::value_type
1359 value_type root = element;
1360 while(parents_[
static_cast<SizeTType
>(root)] != root) {
1361 root = parents_[
static_cast<SizeTType
>(root)];
1364 while(element != root) {
1365 value_type tmp = parents_[
static_cast<SizeTType
>(element)];
1366 parents_[
static_cast<SizeTType
>(element)] = root;
1381 value_type element1,
1386 element1 =
find(element1);
1387 element2 =
find(element2);
1388 if(element1!=element2){
1390 if(ranks_[
static_cast<SizeTType
>(element1)] < ranks_[
static_cast<SizeTType
>(element2)]) {
1391 parents_[
static_cast<SizeTType
>(element1)] = element2;
1396 else if(ranks_[
static_cast<SizeTType
>(element1)] > ranks_[
static_cast<SizeTType
>(element2)]) {
1397 parents_[
static_cast<SizeTType
>(element2)] = element1;
1402 else if(element1 != element2) {
1403 parents_[
static_cast<SizeTType
>(element2)] = element1;
1404 ++ranks_[
static_cast<SizeTType
>(element1)];
1409 this->eraseElement(notRep,
false);
1414inline typename IterablePartition<T>::value_type
1415IterablePartition<T>::numberOfElements()
const
1417 return numberOfElements_;
1421inline typename IterablePartition<T>::value_type
1422IterablePartition<T>::numberOfSets()
const
1424 return numberOfSets_;
1428inline bool operator == (
const ConstRepIter<T> & iter,
const lemon::Invalid & ){
1429 return iter.isEnd();
1432inline bool operator == (
const lemon::Invalid & ,
const ConstRepIter<T> & iter){
1433 return iter.isEnd();
1437inline bool operator != (
const ConstRepIter<T> & iter,
const lemon::Invalid & ){
1438 return !iter.isEnd();
1441inline bool operator != (
const lemon::Invalid & ,
const ConstRepIter<T> & iter){
1442 return !iter.isEnd();
Definition merge_graph_adaptor.hxx:147
IterablePartition(const value_type &)
Definition merge_graph_adaptor.hxx:1266
value_type find(const value_type &) const
Definition merge_graph_adaptor.hxx:1333
IterablePartition()
Construct a partition.
Definition merge_graph_adaptor.hxx:1249
void reset(const value_type &)
Definition merge_graph_adaptor.hxx:1298
void merge(value_type, value_type)
Definition merge_graph_adaptor.hxx:1380
value_type find(value_type)
Definition merge_graph_adaptor.hxx:1354
detail::SelectIntegerType< 64, detail::SignedIntTypes >::type Int64
64-bit signed int
Definition sized_int.hxx:177