equal
deleted
inserted
replaced
63 typedef typename Graph::UEdge UEdge; |
63 typedef typename Graph::UEdge UEdge; |
64 typedef typename Graph::UEdgeIt UEdgeIt; |
64 typedef typename Graph::UEdgeIt UEdgeIt; |
65 typedef typename Graph::NodeIt NodeIt; |
65 typedef typename Graph::NodeIt NodeIt; |
66 typedef typename Graph::IncEdgeIt IncEdgeIt; |
66 typedef typename Graph::IncEdgeIt IncEdgeIt; |
67 |
67 |
68 typedef UnionFindEnum<Node, Graph::template NodeMap> UFE; |
68 typedef typename Graph::template NodeMap<int> UFECrossRef; |
|
69 typedef UnionFindEnum<Node, UFECrossRef> UFE; |
69 |
70 |
70 public: |
71 public: |
71 |
72 |
72 ///Indicates the Gallai-Edmonds decomposition of the graph. |
73 ///Indicates the Gallai-Edmonds decomposition of the graph. |
73 |
74 |
119 |
120 |
120 typename Graph::template NodeMap<Node> ear(g,INVALID); |
121 typename Graph::template NodeMap<Node> ear(g,INVALID); |
121 //undefined for the base nodes of the blossoms (i.e. for the |
122 //undefined for the base nodes of the blossoms (i.e. for the |
122 //representative elements of UFE blossom) and for the nodes in C |
123 //representative elements of UFE blossom) and for the nodes in C |
123 |
124 |
124 typename UFE::MapType blossom_base(g); |
125 UFECrossRef blossom_base(g); |
125 UFE blossom(blossom_base); |
126 UFE blossom(blossom_base); |
126 typename UFE::MapType tree_base(g); |
127 |
|
128 UFECrossRef tree_base(g); |
127 UFE tree(tree_base); |
129 UFE tree(tree_base); |
|
130 |
128 //If these UFE's would be members of the class then also |
131 //If these UFE's would be members of the class then also |
129 //blossom_base and tree_base should be a member. |
132 //blossom_base and tree_base should be a member. |
130 |
133 |
131 //We build only one tree and the other vertices uncovered by the |
134 //We build only one tree and the other vertices uncovered by the |
132 //matching belong to C. (They can be considered as singleton |
135 //matching belong to C. (They can be considered as singleton |
547 Node tmp=v; |
550 Node tmp=v; |
548 v=_mate[u]; |
551 v=_mate[u]; |
549 _mate.set(u,tmp); |
552 _mate.set(u,tmp); |
550 } |
553 } |
551 Node y=blossom.find(x); |
554 Node y=blossom.find(x); |
552 typename UFE::ItemIt it; |
555 for (typename UFE::ItemIt tit(tree, y); tit != INVALID; ++tit) { |
553 for (tree.first(it,blossom.find(x)); tree.valid(it); tree.next(it)) { |
556 if ( position[tit] == D ) { |
554 if ( position[it] == D ) { |
557 for (typename UFE::ItemIt bit(blossom, tit); bit != INVALID; ++bit) { |
555 typename UFE::ItemIt b_it; |
558 position.set( bit ,C); |
556 for (blossom.first(b_it,it); blossom.valid(b_it); blossom.next(b_it)) { |
|
557 position.set( b_it ,C); |
|
558 } |
559 } |
559 blossom.eraseClass(it); |
560 blossom.eraseClass(tit); |
560 } else position.set( it ,C); |
561 } else position.set( tit ,C); |
561 } |
562 } |
562 tree.eraseClass(y); |
563 tree.eraseClass(y); |
563 |
564 |
564 } |
565 } |
565 |
566 |