COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/johanna/ma_order.h @ 497:500456d50d21

Last change on this file since 497:500456d50d21 was 350:3a9a767b841e, checked in by beckerjc, 20 years ago

Maximum Adjacency Ordering (beta)

File size: 1.5 KB
Line 
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
10namespace 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
Note: See TracBrowser for help on using the repository browser.