1.1 --- a/src/work/johanna/Makefile	Sat Apr 17 19:19:57 2004 +0000
     1.2 +++ b/src/work/johanna/Makefile	Sat Apr 17 19:34:43 2004 +0000
     1.3 @@ -1,4 +1,4 @@
     1.4 -BINARIES = kruskal_test
     1.5 +BINARIES = kruskal_test ma_order_test
     1.6  INCLUDEDIRS= -I. -I.. -I../../include -I../{marci,jacint,alpar,klao,akos}
     1.7  include ../makefile
     1.8  

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/src/work/johanna/ma_order.h	Sat Apr 17 19:34:43 2004 +0000
     2.3 @@ -0,0 +1,87 @@
     2.4 +// -*- C++ -*- //
     2.5 +
     2.6 +#ifndef HUGO_MA_ORDER_H
     2.7 +#define HUGO_MA_ORDER_H
     2.8 +
     2.9 +#include <vector>
    2.10 +#include <functional>
    2.11 +#include <bin_heap.h>
    2.12 +
    2.13 +namespace hugo {
    2.14 +
    2.15 +  template <typename Graph, 
    2.16 +	    typename Heap = BinHeap<typename Graph::Node, int, 
    2.17 +				    typename Graph::NodeMap<int>, 
    2.18 +				    std::greater<int> >,
    2.19 +	    typename OrderVect = std::vector<typename Graph::Node> >
    2.20 +  class MAOrder {
    2.21 +
    2.22 +    typedef typename Graph::Node Node;
    2.23 +    typedef typename Graph::NodeIt NodeIt;
    2.24 +    typedef typename Graph::Edge Edge;
    2.25 +    typedef typename Graph::OutEdgeIt OutEdgeIt;
    2.26 +    typedef typename Graph::NodeMap<int> NodeMapInt;
    2.27 +
    2.28 +    const Graph& G;
    2.29 +
    2.30 +    OrderVect& order;
    2.31 +
    2.32 +
    2.33 +  public:
    2.34 +    
    2.35 +    MAOrder(const Graph& _G, OrderVect& _order) : G(_G), order(_order) {}
    2.36 +
    2.37 +    void run()
    2.38 +    {
    2.39 +      Node first;
    2.40 +      G.first(first);
    2.41 +      run(first);
    2.42 +    }
    2.43 +
    2.44 +    void run(Node first)
    2.45 +    {
    2.46 +      NodeMapInt heapMap(G, -1);
    2.47 +      Heap heap(heapMap);
    2.48 +      
    2.49 +      heap.push(first, 0);
    2.50 +
    2.51 +      NodeIt n;
    2.52 +      G.first(n);
    2.53 +      while ( G.valid(n) ) {
    2.54 +
    2.55 +	while(!heap.empty()) {
    2.56 +	  Node a = heap.top();
    2.57 +	  heap.pop();
    2.58 +	  order.push_back(a);
    2.59 +
    2.60 +	  OutEdgeIt e;
    2.61 +	  G.first(e,a);
    2.62 +	  for (;G.valid(e);G.next(e)) {
    2.63 +	    Node v = G.head(e); // hmm
    2.64 +	    if (heap.state(v) == Heap::IN_HEAP ) {
    2.65 +	      heap.decrease(v, heap[v]+1);
    2.66 +	    }
    2.67 +	    else if (heap.state(v) == Heap::PRE_HEAP) {
    2.68 +	      heap.push(v, 1);
    2.69 +	    }
    2.70 +	  }
    2.71 +
    2.72 +	}
    2.73 +
    2.74 +	while( G.valid(n) ) {
    2.75 +	  if (heap.state(n) == Heap::PRE_HEAP) {
    2.76 +	    heap.push(n,0);
    2.77 +	    break;
    2.78 +	  }
    2.79 +	  G.next(n);
    2.80 +	}
    2.81 +      }
    2.82 +
    2.83 +    }
    2.84 +
    2.85 +
    2.86 +  };
    2.87 +
    2.88 +} // namespace hugo
    2.89 +
    2.90 +#endif // HUGO_MA_ORDER_H

     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/src/work/johanna/ma_order_test.cc	Sat Apr 17 19:34:43 2004 +0000
     3.3 @@ -0,0 +1,57 @@
     3.4 +#include <string>
     3.5 +#include <iostream>
     3.6 +#include <map>
     3.7 +#include <vector>
     3.8 +
     3.9 +#include <ma_order.h>
    3.10 +#include <list_graph.h>
    3.11 +
    3.12 +
    3.13 +using namespace std;
    3.14 +using namespace hugo;
    3.15 +
    3.16 +int main() {
    3.17 +
    3.18 +  typedef ListGraph::Node Node;
    3.19 +  typedef ListGraph::Edge Edge;
    3.20 +  typedef ListGraph::NodeIt NodeIt;
    3.21 +  typedef ListGraph::EdgeIt EdgeIt;
    3.22 +
    3.23 +  ListGraph G;
    3.24 +
    3.25 +  Node v3=G.addNode();
    3.26 +  Node v5=G.addNode();
    3.27 +  Node v2=G.addNode();
    3.28 +  Node v0=G.addNode();
    3.29 +  Node v4=G.addNode();
    3.30 +  Node v1=G.addNode();
    3.31 +  
    3.32 +  G.addEdge(v0, v1);G.addEdge(v0, v1);G.addEdge(v0, v1);
    3.33 +  G.addEdge(v0, v2);
    3.34 +  G.addEdge(v0, v3);G.addEdge(v0, v3);
    3.35 +  G.addEdge(v1, v2);G.addEdge(v1, v2);
    3.36 +  G.addEdge(v2, v4);
    3.37 +  G.addEdge(v3, v4);
    3.38 +  G.addEdge(v4, v5);
    3.39 +
    3.40 +  G.addEdge(v1, v0);G.addEdge(v1, v0);G.addEdge(v1, v0);
    3.41 +  G.addEdge(v2, v0);
    3.42 +  G.addEdge(v3, v0);G.addEdge(v3, v0);
    3.43 +  G.addEdge(v2, v1);G.addEdge(v2, v1);
    3.44 +  G.addEdge(v4, v2);
    3.45 +  G.addEdge(v4, v3);
    3.46 +  G.addEdge(v5, v4);
    3.47 +
    3.48 +
    3.49 +  vector<Node> ma_order;
    3.50 +  MAOrder<ListGraph>  mao(G,ma_order);
    3.51 +  mao.run(v0);
    3.52 +  vector<Node>::iterator i;
    3.53 +  for (i = ma_order.begin(); i!=ma_order.end(); ++i) {
    3.54 +    cout << *i << " ";
    3.55 +  }
    3.56 +  cout << endl;
    3.57 +  cout << v0 << " " << v1 << " " << v2 << " " << v3 << " " << v4 << " "
    3.58 +       << v5 << endl;
    3.59 +
    3.60 +}