lemon-0.x: src/work/johanna/ma_order.h@70e2886211d5

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

     3 #ifndef LEMON_MA_ORDER_H

     4 #define LEMON_MA_ORDER_H

     6 #include <vector>

     7 #include <functional>

     8 #include <bin_heap.h>

    10 namespace lemon {

    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 {

    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;

    25     const Graph& G;

    27     OrderVect& order;

    30   public:

    32     MAOrder(const Graph& _G, OrderVect& _order) : G(_G), order(_order) {}

    34     void run()

    35     {

    36       Node first;

    37       G.first(first);

    38       run(first);

    39     }

    41     void run(Node first)

    42     {

    43       NodeMapInt heapMap(G, -1);

    44       Heap heap(heapMap);

    46       heap.push(first, 0);

    48       NodeIt n;

    49       G.first(n);

    50       while ( G.valid(n) ) {

    52 	while(!heap.empty()) {

    53 	  Node a = heap.top();

    54 	  heap.pop();

    55 	  order.push_back(a);

    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 	  }

    69 	}

    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       }

    80     }

    83   };

    85 } // namespace lemon

    87 #endif // LEMON_MA_ORDER_H

author	alpar
	Tue, 05 Oct 2004 09:41:05 +0000
changeset 938	70e2886211d5
parent 350	3a9a767b841e
child 986	e997802b855c
permissions	-rw-r--r--