diff -r ee5959aa4410 -r c280de819a73 src/work/johanna/ma_order.h --- a/src/work/johanna/ma_order.h Sun Apr 17 18:57:22 2005 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,87 +0,0 @@ -// -*- C++ -*- // - -#ifndef LEMON_MA_ORDER_H -#define LEMON_MA_ORDER_H - -#include -#include -#include - -namespace lemon { - - template , - std::greater >, - typename OrderVect = std::vector > - class MAOrder { - - typedef typename Graph::Node Node; - typedef typename Graph::NodeIt NodeIt; - typedef typename Graph::Edge Edge; - typedef typename Graph::OutEdgeIt OutEdgeIt; - typedef typename Graph::NodeMap NodeMapInt; - - const Graph& G; - - OrderVect& order; - - - public: - - MAOrder(const Graph& _G, OrderVect& _order) : G(_G), order(_order) {} - - void run() - { - Node first; - G.first(first); - run(first); - } - - void run(Node first) - { - NodeMapInt heapMap(G, -1); - Heap heap(heapMap); - - heap.push(first, 0); - - NodeIt n; - G.first(n); - while ( G.valid(n) ) { - - while(!heap.empty()) { - Node a = heap.top(); - heap.pop(); - order.push_back(a); - - OutEdgeIt e; - G.first(e,a); - for (;G.valid(e);G.next(e)) { - Node v = G.target(e); // hmm - if (heap.state(v) == Heap::IN_HEAP ) { - heap.decrease(v, heap[v]+1); - } - else if (heap.state(v) == Heap::PRE_HEAP) { - heap.push(v, 1); - } - } - - } - - while( G.valid(n) ) { - if (heap.state(n) == Heap::PRE_HEAP) { - heap.push(n,0); - break; - } - G.next(n); - } - } - - } - - - }; - -} // namespace lemon - -#endif // LEMON_MA_ORDER_H