equal
deleted
inserted
replaced
|
1 // -*- C++ -*- // |
|
2 |
|
3 #ifndef HUGO_MA_ORDER_H |
|
4 #define HUGO_MA_ORDER_H |
|
5 |
|
6 #include <vector> |
|
7 #include <functional> |
|
8 #include <bin_heap.h> |
|
9 |
|
10 namespace hugo { |
|
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.head(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 hugo |
|
86 |
|
87 #endif // HUGO_MA_ORDER_H |