Line | |
---|
1 | // -*- C++ -*- // |
---|
2 | |
---|
3 | #ifndef LEMON_MA_ORDER_H |
---|
4 | #define LEMON_MA_ORDER_H |
---|
5 | |
---|
6 | #include <vector> |
---|
7 | #include <functional> |
---|
8 | #include <bin_heap.h> |
---|
9 | |
---|
10 | namespace lemon { |
---|
11 | |
---|
12 | template <typename Graph, |
---|
13 | typename Heap = BinHeap<typename Graph::Node, int, |
---|
14 | typename Graph::NodeMap<int>, |
---|
15 | std::greater<int> >, |
---|
16 | typename OrderVect = std::vector<typename Graph::Node> > |
---|
17 | class MAOrder { |
---|
18 | |
---|
19 | typedef typename Graph::Node Node; |
---|
20 | typedef typename Graph::NodeIt NodeIt; |
---|
21 | typedef typename Graph::Edge Edge; |
---|
22 | typedef typename Graph::OutEdgeIt OutEdgeIt; |
---|
23 | typedef typename Graph::NodeMap<int> NodeMapInt; |
---|
24 | |
---|
25 | const Graph& G; |
---|
26 | |
---|
27 | OrderVect& order; |
---|
28 | |
---|
29 | |
---|
30 | public: |
---|
31 | |
---|
32 | MAOrder(const Graph& _G, OrderVect& _order) : G(_G), order(_order) {} |
---|
33 | |
---|
34 | void run() |
---|
35 | { |
---|
36 | Node first; |
---|
37 | G.first(first); |
---|
38 | run(first); |
---|
39 | } |
---|
40 | |
---|
41 | void run(Node first) |
---|
42 | { |
---|
43 | NodeMapInt heapMap(G, -1); |
---|
44 | Heap heap(heapMap); |
---|
45 | |
---|
46 | heap.push(first, 0); |
---|
47 | |
---|
48 | NodeIt n; |
---|
49 | G.first(n); |
---|
50 | while ( G.valid(n) ) { |
---|
51 | |
---|
52 | while(!heap.empty()) { |
---|
53 | Node a = heap.top(); |
---|
54 | heap.pop(); |
---|
55 | order.push_back(a); |
---|
56 | |
---|
57 | OutEdgeIt e; |
---|
58 | G.first(e,a); |
---|
59 | for (;G.valid(e);G.next(e)) { |
---|
60 | Node v = G.target(e); // hmm |
---|
61 | if (heap.state(v) == Heap::IN_HEAP ) { |
---|
62 | heap.decrease(v, heap[v]+1); |
---|
63 | } |
---|
64 | else if (heap.state(v) == Heap::PRE_HEAP) { |
---|
65 | heap.push(v, 1); |
---|
66 | } |
---|
67 | } |
---|
68 | |
---|
69 | } |
---|
70 | |
---|
71 | while( G.valid(n) ) { |
---|
72 | if (heap.state(n) == Heap::PRE_HEAP) { |
---|
73 | heap.push(n,0); |
---|
74 | break; |
---|
75 | } |
---|
76 | G.next(n); |
---|
77 | } |
---|
78 | } |
---|
79 | |
---|
80 | } |
---|
81 | |
---|
82 | |
---|
83 | }; |
---|
84 | |
---|
85 | } // namespace lemon |
---|
86 | |
---|
87 | #endif // LEMON_MA_ORDER_H |
---|
Note: See
TracBrowser
for help on using the repository browser.