beckerjc@350: // -*- C++ -*- // beckerjc@350: alpar@921: #ifndef LEMON_MA_ORDER_H alpar@921: #define LEMON_MA_ORDER_H beckerjc@350: beckerjc@350: #include beckerjc@350: #include beckerjc@350: #include beckerjc@350: alpar@921: namespace lemon { beckerjc@350: beckerjc@350: template , beckerjc@350: std::greater >, beckerjc@350: typename OrderVect = std::vector > beckerjc@350: class MAOrder { beckerjc@350: beckerjc@350: typedef typename Graph::Node Node; beckerjc@350: typedef typename Graph::NodeIt NodeIt; beckerjc@350: typedef typename Graph::Edge Edge; beckerjc@350: typedef typename Graph::OutEdgeIt OutEdgeIt; beckerjc@350: typedef typename Graph::NodeMap NodeMapInt; beckerjc@350: beckerjc@350: const Graph& G; beckerjc@350: beckerjc@350: OrderVect& order; beckerjc@350: beckerjc@350: beckerjc@350: public: beckerjc@350: beckerjc@350: MAOrder(const Graph& _G, OrderVect& _order) : G(_G), order(_order) {} beckerjc@350: beckerjc@350: void run() beckerjc@350: { beckerjc@350: Node first; beckerjc@350: G.first(first); beckerjc@350: run(first); beckerjc@350: } beckerjc@350: beckerjc@350: void run(Node first) beckerjc@350: { beckerjc@350: NodeMapInt heapMap(G, -1); beckerjc@350: Heap heap(heapMap); beckerjc@350: beckerjc@350: heap.push(first, 0); beckerjc@350: beckerjc@350: NodeIt n; beckerjc@350: G.first(n); beckerjc@350: while ( G.valid(n) ) { beckerjc@350: beckerjc@350: while(!heap.empty()) { beckerjc@350: Node a = heap.top(); beckerjc@350: heap.pop(); beckerjc@350: order.push_back(a); beckerjc@350: beckerjc@350: OutEdgeIt e; beckerjc@350: G.first(e,a); beckerjc@350: for (;G.valid(e);G.next(e)) { alpar@986: Node v = G.target(e); // hmm beckerjc@350: if (heap.state(v) == Heap::IN_HEAP ) { beckerjc@350: heap.decrease(v, heap[v]+1); beckerjc@350: } beckerjc@350: else if (heap.state(v) == Heap::PRE_HEAP) { beckerjc@350: heap.push(v, 1); beckerjc@350: } beckerjc@350: } beckerjc@350: beckerjc@350: } beckerjc@350: beckerjc@350: while( G.valid(n) ) { beckerjc@350: if (heap.state(n) == Heap::PRE_HEAP) { beckerjc@350: heap.push(n,0); beckerjc@350: break; beckerjc@350: } beckerjc@350: G.next(n); beckerjc@350: } beckerjc@350: } beckerjc@350: beckerjc@350: } beckerjc@350: beckerjc@350: beckerjc@350: }; beckerjc@350: alpar@921: } // namespace lemon beckerjc@350: alpar@921: #endif // LEMON_MA_ORDER_H