1.1 --- a/src/work/johanna/ma_order.h Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,87 +0,0 @@
1.4 -// -*- C++ -*- //
1.5 -
1.6 -#ifndef LEMON_MA_ORDER_H
1.7 -#define LEMON_MA_ORDER_H
1.8 -
1.9 -#include <vector>
1.10 -#include <functional>
1.11 -#include <bin_heap.h>
1.12 -
1.13 -namespace lemon {
1.14 -
1.15 - template <typename Graph,
1.16 - typename Heap = BinHeap<typename Graph::Node, int,
1.17 - typename Graph::NodeMap<int>,
1.18 - std::greater<int> >,
1.19 - typename OrderVect = std::vector<typename Graph::Node> >
1.20 - class MAOrder {
1.21 -
1.22 - typedef typename Graph::Node Node;
1.23 - typedef typename Graph::NodeIt NodeIt;
1.24 - typedef typename Graph::Edge Edge;
1.25 - typedef typename Graph::OutEdgeIt OutEdgeIt;
1.26 - typedef typename Graph::NodeMap<int> NodeMapInt;
1.27 -
1.28 - const Graph& G;
1.29 -
1.30 - OrderVect& order;
1.31 -
1.32 -
1.33 - public:
1.34 -
1.35 - MAOrder(const Graph& _G, OrderVect& _order) : G(_G), order(_order) {}
1.36 -
1.37 - void run()
1.38 - {
1.39 - Node first;
1.40 - G.first(first);
1.41 - run(first);
1.42 - }
1.43 -
1.44 - void run(Node first)
1.45 - {
1.46 - NodeMapInt heapMap(G, -1);
1.47 - Heap heap(heapMap);
1.48 -
1.49 - heap.push(first, 0);
1.50 -
1.51 - NodeIt n;
1.52 - G.first(n);
1.53 - while ( G.valid(n) ) {
1.54 -
1.55 - while(!heap.empty()) {
1.56 - Node a = heap.top();
1.57 - heap.pop();
1.58 - order.push_back(a);
1.59 -
1.60 - OutEdgeIt e;
1.61 - G.first(e,a);
1.62 - for (;G.valid(e);G.next(e)) {
1.63 - Node v = G.target(e); // hmm
1.64 - if (heap.state(v) == Heap::IN_HEAP ) {
1.65 - heap.decrease(v, heap[v]+1);
1.66 - }
1.67 - else if (heap.state(v) == Heap::PRE_HEAP) {
1.68 - heap.push(v, 1);
1.69 - }
1.70 - }
1.71 -
1.72 - }
1.73 -
1.74 - while( G.valid(n) ) {
1.75 - if (heap.state(n) == Heap::PRE_HEAP) {
1.76 - heap.push(n,0);
1.77 - break;
1.78 - }
1.79 - G.next(n);
1.80 - }
1.81 - }
1.82 -
1.83 - }
1.84 -
1.85 -
1.86 - };
1.87 -
1.88 -} // namespace lemon
1.89 -
1.90 -#endif // LEMON_MA_ORDER_H