src/work/johanna/ma_order.h
author deba
Wed, 08 Sep 2004 12:06:45 +0000 (2004-09-08)
changeset 822 88226d9fe821
child 921 818510fa3d99
permissions -rw-r--r--
The MapFactories have been removed from the code because
if we use macros then they increases only the complexity.

The pair iterators of the maps are separeted from the maps.

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