source: lemon-0.x/src/work/johanna/ma_order.h @ 1059:bd97feae7d90

// -*- C++ -*- //

#ifndef LEMON_MA_ORDER_H
#define LEMON_MA_ORDER_H

#include <vector>
#include <functional>
#include <bin_heap.h>

namespace lemon {

  template <typename Graph, 
            typename Heap = BinHeap<typename Graph::Node, int, 
                                    typename Graph::NodeMap<int>, 
                                    std::greater<int> >,
            typename OrderVect = std::vector<typename Graph::Node> >
  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<int> 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