equal
deleted
inserted
replaced
22 /// \file |
22 /// \file |
23 /// \brief Maximum cardinality search and min cut in undirected graphs. |
23 /// \brief Maximum cardinality search and min cut in undirected graphs. |
24 |
24 |
25 #include <lemon/list_graph.h> |
25 #include <lemon/list_graph.h> |
26 #include <lemon/bin_heap.h> |
26 #include <lemon/bin_heap.h> |
27 #include <lemon/linear_heap.h> |
27 #include <lemon/bucket_heap.h> |
28 |
28 |
29 #include <lemon/bits/invalid.h> |
29 #include <lemon/bits/invalid.h> |
30 #include <lemon/error.h> |
30 #include <lemon/error.h> |
31 #include <lemon/maps.h> |
31 #include <lemon/maps.h> |
32 |
32 |
46 |
46 |
47 template <typename CapacityKey> |
47 template <typename CapacityKey> |
48 struct HeapSelector<ConstMap<CapacityKey, Const<int, 1> > > { |
48 struct HeapSelector<ConstMap<CapacityKey, Const<int, 1> > > { |
49 template <typename Key, typename Value, typename Ref> |
49 template <typename Key, typename Value, typename Ref> |
50 struct Selector { |
50 struct Selector { |
51 typedef LinearHeap<Key, Ref, false > Heap; |
51 typedef BucketHeap<Key, Ref, false > Heap; |
52 }; |
52 }; |
53 }; |
53 }; |
54 |
54 |
55 } |
55 } |
56 |
56 |
92 /// |
92 /// |
93 /// The heap type used by MaxCardinalitySearch algorithm. It should |
93 /// The heap type used by MaxCardinalitySearch algorithm. It should |
94 /// maximalize the priorities. The default heap type is |
94 /// maximalize the priorities. The default heap type is |
95 /// the \ref BinHeap, but it is specialized when the |
95 /// the \ref BinHeap, but it is specialized when the |
96 /// CapacityMap is ConstMap<Graph::Node, Const<int, 1> > |
96 /// CapacityMap is ConstMap<Graph::Node, Const<int, 1> > |
97 /// to LinearHeap. |
97 /// to BucketHeap. |
98 /// |
98 /// |
99 /// \sa MaxCardinalitySearch |
99 /// \sa MaxCardinalitySearch |
100 typedef typename _min_cut_bits |
100 typedef typename _min_cut_bits |
101 ::HeapSelector<CapacityMap> |
101 ::HeapSelector<CapacityMap> |
102 ::template Selector<typename Graph::Node, Value, HeapCrossRef> |
102 ::template Selector<typename Graph::Node, Value, HeapCrossRef> |
839 /// to test how many links have to be destroyed in the netaux to split it |
839 /// to test how many links have to be destroyed in the netaux to split it |
840 /// at least two distinict subnetaux. |
840 /// at least two distinict subnetaux. |
841 /// |
841 /// |
842 /// The complexity of the algorithm is O(n*e*log(n)) but with Fibonacci |
842 /// The complexity of the algorithm is O(n*e*log(n)) but with Fibonacci |
843 /// heap it can be decreased to O(n*e+n^2*log(n)). When the neutral capacity |
843 /// heap it can be decreased to O(n*e+n^2*log(n)). When the neutral capacity |
844 /// map is used then it uses LinearHeap which results O(n*e) time complexity. |
844 /// map is used then it uses BucketHeap which results O(n*e) time complexity. |
845 #ifdef DOXYGEN |
845 #ifdef DOXYGEN |
846 template <typename _Graph, typename _CapacityMap, typename _Traits> |
846 template <typename _Graph, typename _CapacityMap, typename _Traits> |
847 #else |
847 #else |
848 template <typename _Graph = ListUGraph, |
848 template <typename _Graph = ListUGraph, |
849 typename _CapacityMap = typename _Graph::template UEdgeMap<int>, |
849 typename _CapacityMap = typename _Graph::template UEdgeMap<int>, |