beckerjc@350: // -*- C++ -*- //
beckerjc@350: 
beckerjc@350: #ifndef HUGO_MA_ORDER_H
beckerjc@350: #define HUGO_MA_ORDER_H
beckerjc@350: 
beckerjc@350: #include <vector>
beckerjc@350: #include <functional>
beckerjc@350: #include <bin_heap.h>
beckerjc@350: 
beckerjc@350: namespace hugo {
beckerjc@350: 
beckerjc@350:   template <typename Graph, 
beckerjc@350: 	    typename Heap = BinHeap<typename Graph::Node, int, 
beckerjc@350: 				    typename Graph::NodeMap<int>, 
beckerjc@350: 				    std::greater<int> >,
beckerjc@350: 	    typename OrderVect = std::vector<typename Graph::Node> >
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<int> 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)) {
beckerjc@350: 	    Node v = G.head(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: 
beckerjc@350: } // namespace hugo
beckerjc@350: 
beckerjc@350: #endif // HUGO_MA_ORDER_H