# HG changeset patch
# User beckerjc
# Date 1082230483 0
# Node ID 3a9a767b841e489d35515578a84e126479de7596
# Parent  42c660f587025a7ae23b2deb024e23e5ad97504b
Maximum Adjacency Ordering (beta)

diff -r 42c660f58702 -r 3a9a767b841e src/work/johanna/Makefile
--- a/src/work/johanna/Makefile	Sat Apr 17 19:19:57 2004 +0000
+++ b/src/work/johanna/Makefile	Sat Apr 17 19:34:43 2004 +0000
@@ -1,4 +1,4 @@
-BINARIES = kruskal_test
+BINARIES = kruskal_test ma_order_test
 INCLUDEDIRS= -I. -I.. -I../../include -I../{marci,jacint,alpar,klao,akos}
 include ../makefile
 
diff -r 42c660f58702 -r 3a9a767b841e src/work/johanna/ma_order.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/johanna/ma_order.h	Sat Apr 17 19:34:43 2004 +0000
@@ -0,0 +1,87 @@
+// -*- C++ -*- //
+
+#ifndef HUGO_MA_ORDER_H
+#define HUGO_MA_ORDER_H
+
+#include <vector>
+#include <functional>
+#include <bin_heap.h>
+
+namespace hugo {
+
+  template <typename Graph, 
+	    typename Heap = BinHeap<typename Graph::Node, int, 
+				    typename Graph::NodeMap<int>, 
+				    std::greater<int> >,
+	    typename OrderVect = std::vector<typename Graph::Node> >
+  class MAOrder {
+
+    typedef typename Graph::Node Node;
+    typedef typename Graph::NodeIt NodeIt;
+    typedef typename Graph::Edge Edge;
+    typedef typename Graph::OutEdgeIt OutEdgeIt;
+    typedef typename Graph::NodeMap<int> NodeMapInt;
+
+    const Graph& G;
+
+    OrderVect& order;
+
+
+  public:
+    
+    MAOrder(const Graph& _G, OrderVect& _order) : G(_G), order(_order) {}
+
+    void run()
+    {
+      Node first;
+      G.first(first);
+      run(first);
+    }
+
+    void run(Node first)
+    {
+      NodeMapInt heapMap(G, -1);
+      Heap heap(heapMap);
+      
+      heap.push(first, 0);
+
+      NodeIt n;
+      G.first(n);
+      while ( G.valid(n) ) {
+
+	while(!heap.empty()) {
+	  Node a = heap.top();
+	  heap.pop();
+	  order.push_back(a);
+
+	  OutEdgeIt e;
+	  G.first(e,a);
+	  for (;G.valid(e);G.next(e)) {
+	    Node v = G.head(e); // hmm
+	    if (heap.state(v) == Heap::IN_HEAP ) {
+	      heap.decrease(v, heap[v]+1);
+	    }
+	    else if (heap.state(v) == Heap::PRE_HEAP) {
+	      heap.push(v, 1);
+	    }
+	  }
+
+	}
+
+	while( G.valid(n) ) {
+	  if (heap.state(n) == Heap::PRE_HEAP) {
+	    heap.push(n,0);
+	    break;
+	  }
+	  G.next(n);
+	}
+      }
+
+    }
+
+
+  };
+
+} // namespace hugo
+
+#endif // HUGO_MA_ORDER_H
diff -r 42c660f58702 -r 3a9a767b841e src/work/johanna/ma_order_test.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/johanna/ma_order_test.cc	Sat Apr 17 19:34:43 2004 +0000
@@ -0,0 +1,57 @@
+#include <string>
+#include <iostream>
+#include <map>
+#include <vector>
+
+#include <ma_order.h>
+#include <list_graph.h>
+
+
+using namespace std;
+using namespace hugo;
+
+int main() {
+
+  typedef ListGraph::Node Node;
+  typedef ListGraph::Edge Edge;
+  typedef ListGraph::NodeIt NodeIt;
+  typedef ListGraph::EdgeIt EdgeIt;
+
+  ListGraph G;
+
+  Node v3=G.addNode();
+  Node v5=G.addNode();
+  Node v2=G.addNode();
+  Node v0=G.addNode();
+  Node v4=G.addNode();
+  Node v1=G.addNode();
+  
+  G.addEdge(v0, v1);G.addEdge(v0, v1);G.addEdge(v0, v1);
+  G.addEdge(v0, v2);
+  G.addEdge(v0, v3);G.addEdge(v0, v3);
+  G.addEdge(v1, v2);G.addEdge(v1, v2);
+  G.addEdge(v2, v4);
+  G.addEdge(v3, v4);
+  G.addEdge(v4, v5);
+
+  G.addEdge(v1, v0);G.addEdge(v1, v0);G.addEdge(v1, v0);
+  G.addEdge(v2, v0);
+  G.addEdge(v3, v0);G.addEdge(v3, v0);
+  G.addEdge(v2, v1);G.addEdge(v2, v1);
+  G.addEdge(v4, v2);
+  G.addEdge(v4, v3);
+  G.addEdge(v5, v4);
+
+
+  vector<Node> ma_order;
+  MAOrder<ListGraph>  mao(G,ma_order);
+  mao.run(v0);
+  vector<Node>::iterator i;
+  for (i = ma_order.begin(); i!=ma_order.end(); ++i) {
+    cout << *i << " ";
+  }
+  cout << endl;
+  cout << v0 << " " << v1 << " " << v2 << " " << v3 << " " << v4 << " "
+       << v5 << endl;
+
+}