src/work/johanna/ma_order.h
author marci
Thu, 06 May 2004 15:24:42 +0000
changeset 552 83c22ca968d8
child 921 818510fa3d99
permissions -rw-r--r--
top-sort, for fezso's sake
beckerjc@350
     1
// -*- C++ -*- //
beckerjc@350
     2
beckerjc@350
     3
#ifndef HUGO_MA_ORDER_H
beckerjc@350
     4
#define HUGO_MA_ORDER_H
beckerjc@350
     5
beckerjc@350
     6
#include <vector>
beckerjc@350
     7
#include <functional>
beckerjc@350
     8
#include <bin_heap.h>
beckerjc@350
     9
beckerjc@350
    10
namespace hugo {
beckerjc@350
    11
beckerjc@350
    12
  template <typename Graph, 
beckerjc@350
    13
	    typename Heap = BinHeap<typename Graph::Node, int, 
beckerjc@350
    14
				    typename Graph::NodeMap<int>, 
beckerjc@350
    15
				    std::greater<int> >,
beckerjc@350
    16
	    typename OrderVect = std::vector<typename Graph::Node> >
beckerjc@350
    17
  class MAOrder {
beckerjc@350
    18
beckerjc@350
    19
    typedef typename Graph::Node Node;
beckerjc@350
    20
    typedef typename Graph::NodeIt NodeIt;
beckerjc@350
    21
    typedef typename Graph::Edge Edge;
beckerjc@350
    22
    typedef typename Graph::OutEdgeIt OutEdgeIt;
beckerjc@350
    23
    typedef typename Graph::NodeMap<int> NodeMapInt;
beckerjc@350
    24
beckerjc@350
    25
    const Graph& G;
beckerjc@350
    26
beckerjc@350
    27
    OrderVect& order;
beckerjc@350
    28
beckerjc@350
    29
beckerjc@350
    30
  public:
beckerjc@350
    31
    
beckerjc@350
    32
    MAOrder(const Graph& _G, OrderVect& _order) : G(_G), order(_order) {}
beckerjc@350
    33
beckerjc@350
    34
    void run()
beckerjc@350
    35
    {
beckerjc@350
    36
      Node first;
beckerjc@350
    37
      G.first(first);
beckerjc@350
    38
      run(first);
beckerjc@350
    39
    }
beckerjc@350
    40
beckerjc@350
    41
    void run(Node first)
beckerjc@350
    42
    {
beckerjc@350
    43
      NodeMapInt heapMap(G, -1);
beckerjc@350
    44
      Heap heap(heapMap);
beckerjc@350
    45
      
beckerjc@350
    46
      heap.push(first, 0);
beckerjc@350
    47
beckerjc@350
    48
      NodeIt n;
beckerjc@350
    49
      G.first(n);
beckerjc@350
    50
      while ( G.valid(n) ) {
beckerjc@350
    51
beckerjc@350
    52
	while(!heap.empty()) {
beckerjc@350
    53
	  Node a = heap.top();
beckerjc@350
    54
	  heap.pop();
beckerjc@350
    55
	  order.push_back(a);
beckerjc@350
    56
beckerjc@350
    57
	  OutEdgeIt e;
beckerjc@350
    58
	  G.first(e,a);
beckerjc@350
    59
	  for (;G.valid(e);G.next(e)) {
beckerjc@350
    60
	    Node v = G.head(e); // hmm
beckerjc@350
    61
	    if (heap.state(v) == Heap::IN_HEAP ) {
beckerjc@350
    62
	      heap.decrease(v, heap[v]+1);
beckerjc@350
    63
	    }
beckerjc@350
    64
	    else if (heap.state(v) == Heap::PRE_HEAP) {
beckerjc@350
    65
	      heap.push(v, 1);
beckerjc@350
    66
	    }
beckerjc@350
    67
	  }
beckerjc@350
    68
beckerjc@350
    69
	}
beckerjc@350
    70
beckerjc@350
    71
	while( G.valid(n) ) {
beckerjc@350
    72
	  if (heap.state(n) == Heap::PRE_HEAP) {
beckerjc@350
    73
	    heap.push(n,0);
beckerjc@350
    74
	    break;
beckerjc@350
    75
	  }
beckerjc@350
    76
	  G.next(n);
beckerjc@350
    77
	}
beckerjc@350
    78
      }
beckerjc@350
    79
beckerjc@350
    80
    }
beckerjc@350
    81
beckerjc@350
    82
beckerjc@350
    83
  };
beckerjc@350
    84
beckerjc@350
    85
} // namespace hugo
beckerjc@350
    86
beckerjc@350
    87
#endif // HUGO_MA_ORDER_H