diff -r 666f914201fb -r 2fe1408b6811 epoc32/include/stdapis/boost/graph/minimum_degree_ordering.hpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/epoc32/include/stdapis/boost/graph/minimum_degree_ordering.hpp	Tue Mar 16 16:12:26 2010 +0000
@@ -0,0 +1,655 @@
+//-*-c++-*-
+//=======================================================================
+// Copyright 1997-2001 University of Notre Dame.
+// Authors: Lie-Quan Lee, Jeremy Siek
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+//=======================================================================
+//
+#ifndef MINIMUM_DEGREE_ORDERING_HPP
+#define MINIMUM_DEGREE_ORDERING_HPP
+
+#include <vector>
+#include <cassert>
+#include <boost/config.hpp>
+#include <boost/pending/bucket_sorter.hpp>
+#include <boost/detail/numeric_traits.hpp> // for integer_traits
+#include <boost/graph/graph_traits.hpp>
+#include <boost/property_map.hpp>
+
+namespace boost {
+
+  namespace detail {
+
+    // 
+    // Given a set of n integers (where the integer values range from
+    // zero to n-1), we want to keep track of a collection of stacks
+    // of integers. It so happens that an integer will appear in at
+    // most one stack at a time, so the stacks form disjoint sets.
+    // Because of these restrictions, we can use one big array to
+    // store all the stacks, intertwined with one another.
+    // No allocation/deallocation happens in the push()/pop() methods
+    // so this is faster than using std::stack's.
+    //
+    template <class SignedInteger>
+    class Stacks {
+      typedef SignedInteger value_type;
+      typedef typename std::vector<value_type>::size_type size_type;
+    public:
+      Stacks(size_type n) : data(n) {}
+      
+      //: stack 
+      class stack {
+        typedef typename std::vector<value_type>::iterator Iterator;
+      public:
+        stack(Iterator _data, const value_type& head)
+          :  data(_data), current(head) {}
+
+        // did not use default argument here to avoid internal compiler error
+        // in g++.
+        stack(Iterator _data)
+          : data(_data), current(-(std::numeric_limits<value_type>::max)()) {}
+        
+        void pop() {
+          assert(! empty());
+          current = data[current];
+        }
+        void push(value_type v) {
+          data[v] = current; 
+          current = v;
+        }
+        bool empty() {
+          return current == -(std::numeric_limits<value_type>::max)(); 
+        }
+        value_type& top() { return current; }
+      private:
+        Iterator data;
+        value_type current;
+      };
+
+      // To return a stack object 
+      stack make_stack()
+        { return stack(data.begin()); }
+    protected:
+      std::vector<value_type> data;
+    };
+
+
+    // marker class, a generalization of coloring. 
+    //
+    // This class is to provide a generalization of coloring which has
+    // complexity of amortized constant time to set all vertices' color
+    // back to be untagged. It implemented by increasing a tag.
+    //
+    // The colors are:
+    //   not tagged 
+    //   tagged
+    //   multiple_tagged
+    //   done
+    //
+    template <class SignedInteger, class Vertex, class VertexIndexMap>
+    class Marker {
+      typedef SignedInteger value_type;
+      typedef typename std::vector<value_type>::size_type size_type;
+      
+      static value_type done() 
+      { return (std::numeric_limits<value_type>::max)()/2; }
+    public:
+      Marker(size_type _num, VertexIndexMap index_map) 
+        : tag(1 - (std::numeric_limits<value_type>::max)()),
+          data(_num, - (std::numeric_limits<value_type>::max)()),
+          id(index_map) {}
+      
+      void mark_done(Vertex node) { data[get(id, node)] = done(); }
+      
+      bool is_done(Vertex node) { return data[get(id, node)] == done(); }
+      
+      void mark_tagged(Vertex node) { data[get(id, node)] = tag; }
+      
+      void mark_multiple_tagged(Vertex node) { data[get(id, node)] = multiple_tag; }
+  
+      bool is_tagged(Vertex node) const { return data[get(id, node)] >= tag; }
+
+      bool is_not_tagged(Vertex node) const { return data[get(id, node)] < tag; }
+
+      bool is_multiple_tagged(Vertex node) const 
+        { return data[get(id, node)] >= multiple_tag; }
+
+      void increment_tag() {
+        const size_type num = data.size();
+        ++tag;
+        if ( tag >= done() ) {
+          tag = 1 - (std::numeric_limits<value_type>::max)();
+          for (size_type i = 0; i < num; ++i)
+            if ( data[i] < done() ) 
+              data[i] = - (std::numeric_limits<value_type>::max)();
+        }
+      }
+      
+      void set_multiple_tag(value_type mdeg0) 
+      { 
+        const size_type num = data.size();
+        multiple_tag = tag + mdeg0; 
+        
+        if ( multiple_tag >= done() ) {
+          tag = 1-(std::numeric_limits<value_type>::max)();
+          
+          for (size_type i=0; i<num; i++)
+            if ( data[i] < done() ) 
+              data[i] = -(std::numeric_limits<value_type>::max)();
+          
+          multiple_tag = tag + mdeg0; 
+        }
+      }
+      
+      void set_tag_as_multiple_tag() { tag = multiple_tag; }
+      
+    protected:
+      value_type tag;
+      value_type multiple_tag;
+      std::vector<value_type> data;
+      VertexIndexMap id;
+    };
+    
+    template< class Iterator, class SignedInteger, 
+       class Vertex, class VertexIndexMap, int offset = 1 >
+    class Numbering {
+      typedef SignedInteger number_type;
+      number_type num; //start from 1 instead of zero
+      Iterator   data;
+      number_type max_num;
+      VertexIndexMap id;
+    public:
+      Numbering(Iterator _data, number_type _max_num, VertexIndexMap id) 
+        : num(1), data(_data), max_num(_max_num), id(id) {}
+      void operator()(Vertex node) { data[get(id, node)] = -num; }
+      bool all_done(number_type i = 0) const { return num + i > max_num; }
+      void increment(number_type i = 1) { num += i; }
+      bool is_numbered(Vertex node) const {
+        return data[get(id, node)] < 0;
+      }
+      void indistinguishable(Vertex i, Vertex j) {
+        data[get(id, i)] = - (get(id, j) + offset);
+      }
+    };
+
+    template <class SignedInteger, class Vertex, class VertexIndexMap>
+    class degreelists_marker {
+    public:
+      typedef SignedInteger value_type;
+      typedef typename std::vector<value_type>::size_type size_type;
+      degreelists_marker(size_type n, VertexIndexMap id)
+        : marks(n, 0), id(id) {}
+      void mark_need_update(Vertex i) { marks[get(id, i)] = 1;  }
+      bool need_update(Vertex i) { return marks[get(id, i)] == 1; }
+      bool outmatched_or_done (Vertex i) { return marks[get(id, i)] == -1; }
+      void mark(Vertex i) { marks[get(id, i)] = -1; }
+      void unmark(Vertex i) { marks[get(id, i)] = 0; }
+    private:
+      std::vector<value_type> marks;
+      VertexIndexMap id;
+    };
+
+    // Helper function object for edge removal
+    template <class Graph, class MarkerP, class NumberD, class Stack,
+      class VertexIndexMap>
+    class predicateRemoveEdge1 {
+      typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
+      typedef typename graph_traits<Graph>::edge_descriptor edge_t;
+    public:
+      predicateRemoveEdge1(Graph& _g, MarkerP& _marker, 
+                           NumberD _numbering, Stack& n_e, VertexIndexMap id)
+        : g(&_g), marker(&_marker), numbering(_numbering),
+          neighbor_elements(&n_e), id(id) {}
+
+      bool operator()(edge_t e) {
+        vertex_t dist = target(e, *g);
+        if ( marker->is_tagged(dist) )
+          return true;
+        marker->mark_tagged(dist);
+        if (numbering.is_numbered(dist)) {
+          neighbor_elements->push(get(id, dist));
+          return true;
+        }
+        return false;
+      }
+    private:
+      Graph*   g;
+      MarkerP* marker;
+      NumberD  numbering;
+      Stack*   neighbor_elements;
+      VertexIndexMap id;
+    };
+
+    // Helper function object for edge removal
+    template <class Graph, class MarkerP>
+    class predicate_remove_tagged_edges
+    {
+      typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
+      typedef typename graph_traits<Graph>::edge_descriptor edge_t;
+    public:
+      predicate_remove_tagged_edges(Graph& _g, MarkerP& _marker)
+        : g(&_g), marker(&_marker) {}
+
+      bool operator()(edge_t e) {
+        vertex_t dist = target(e, *g);
+        if ( marker->is_tagged(dist) )
+          return true;
+        return false;
+      }
+    private:
+      Graph*   g;
+      MarkerP* marker;
+    };
+
+    template<class Graph, class DegreeMap, 
+             class InversePermutationMap, 
+             class PermutationMap,
+             class SuperNodeMap, 
+             class VertexIndexMap>
+    class mmd_impl
+    {
+      // Typedefs
+      typedef graph_traits<Graph> Traits;
+      typedef typename Traits::vertices_size_type size_type;
+      typedef typename detail::integer_traits<size_type>::difference_type 
+        diff_t;
+      typedef typename Traits::vertex_descriptor vertex_t;
+      typedef typename Traits::adjacency_iterator adj_iter;
+      typedef iterator_property_map<vertex_t*, 
+        identity_property_map, vertex_t, vertex_t&> IndexVertexMap;
+      typedef detail::Stacks<diff_t> Workspace;
+      typedef bucket_sorter<size_type, vertex_t, DegreeMap, VertexIndexMap> 
+        DegreeLists;
+      typedef Numbering<InversePermutationMap, diff_t, vertex_t,VertexIndexMap>
+        NumberingD;
+      typedef degreelists_marker<diff_t, vertex_t, VertexIndexMap> 
+        DegreeListsMarker;
+      typedef Marker<diff_t, vertex_t, VertexIndexMap> MarkerP;
+
+      // Data Members
+
+      // input parameters
+      Graph& G;
+      int delta;
+      DegreeMap degree;
+      InversePermutationMap inverse_perm;
+      PermutationMap perm;
+      SuperNodeMap supernode_size;
+      VertexIndexMap vertex_index_map;
+
+      // internal data-structures
+      std::vector<vertex_t> index_vertex_vec;
+      size_type n;
+      IndexVertexMap index_vertex_map;
+      DegreeLists degreelists;
+      NumberingD numbering;
+      DegreeListsMarker degree_lists_marker;
+      MarkerP marker;
+      Workspace work_space;
+    public:
+      mmd_impl(Graph& g, size_type n_, int delta, DegreeMap degree, 
+               InversePermutationMap inverse_perm, 
+               PermutationMap perm,
+               SuperNodeMap supernode_size, 
+               VertexIndexMap id) 
+        : G(g), delta(delta), degree(degree), 
+        inverse_perm(inverse_perm), 
+        perm(perm), 
+        supernode_size(supernode_size), 
+        vertex_index_map(id),
+        index_vertex_vec(n_), 
+        n(n_),
+        degreelists(n_ + 1, n_, degree, id),
+        numbering(inverse_perm, n_, vertex_index_map),
+        degree_lists_marker(n_, vertex_index_map), 
+        marker(n_, vertex_index_map),
+        work_space(n_)
+      {
+        typename graph_traits<Graph>::vertex_iterator v, vend;
+        size_type vid = 0;
+        for (tie(v, vend) = vertices(G); v != vend; ++v, ++vid)
+          index_vertex_vec[vid] = *v;
+        index_vertex_map = IndexVertexMap(&index_vertex_vec[0]);
+
+        // Initialize degreelists.  Degreelists organizes the nodes
+        // according to their degree.
+        for (tie(v, vend) = vertices(G); v != vend; ++v) {
+          put(degree, *v, out_degree(*v, G));
+          degreelists.push(*v);
+        }
+      }
+
+      void do_mmd()
+      {
+        // Eliminate the isolated nodes -- these are simply the nodes
+        // with no neighbors, which are accessible as a list (really, a
+        // stack) at location 0.  Since these don't affect any other
+        // nodes, we can eliminate them without doing degree updates.
+        typename DegreeLists::stack list_isolated = degreelists[0];
+        while (!list_isolated.empty()) {
+          vertex_t node = list_isolated.top();
+          marker.mark_done(node);
+          numbering(node);
+          numbering.increment();
+          list_isolated.pop();
+        }
+        size_type min_degree = 1;
+        typename DegreeLists::stack list_min_degree = degreelists[min_degree];
+
+        while (list_min_degree.empty()) {
+          ++min_degree;
+          list_min_degree = degreelists[min_degree];
+        }
+
+        // check if the whole eliminating process is done
+        while (!numbering.all_done()) {
+
+          size_type min_degree_limit = min_degree + delta; // WARNING
+          typename Workspace::stack llist = work_space.make_stack();
+
+          // multiple elimination
+          while (delta >= 0) {
+
+            // Find the next non-empty degree
+            for (list_min_degree = degreelists[min_degree]; 
+                 list_min_degree.empty() && min_degree <= min_degree_limit; 
+                 ++min_degree, list_min_degree = degreelists[min_degree])
+              ;
+            if (min_degree > min_degree_limit)
+              break;
+
+            const vertex_t node = list_min_degree.top();
+            const size_type node_id = get(vertex_index_map, node);
+            list_min_degree.pop();
+            numbering(node);
+
+            // check if node is the last one
+            if (numbering.all_done(supernode_size[node])) {
+              numbering.increment(supernode_size[node]);
+              break;
+            }
+            marker.increment_tag();
+            marker.mark_tagged(node);
+
+            this->eliminate(node);
+
+            numbering.increment(supernode_size[node]);
+            llist.push(node_id);
+          } // multiple elimination
+
+          if (numbering.all_done()) 
+            break;
+
+          this->update( llist, min_degree);
+        }
+
+      } // do_mmd()
+
+      void eliminate(vertex_t node)
+      {
+        typename Workspace::stack element_neighbor = work_space.make_stack();
+
+        // Create two function objects for edge removal
+        typedef typename Workspace::stack WorkStack;
+        predicateRemoveEdge1<Graph, MarkerP, NumberingD, 
+                             WorkStack, VertexIndexMap>
+          p(G, marker, numbering, element_neighbor, vertex_index_map);
+
+        predicate_remove_tagged_edges<Graph, MarkerP> p2(G, marker);
+
+        // Reconstruct the adjacent node list, push element neighbor in a List.
+        remove_out_edge_if(node, p, G);
+        //during removal element neighbors are collected.
+
+        while (!element_neighbor.empty()) {
+          // element absorb
+          size_type e_id = element_neighbor.top();
+          vertex_t element = get(index_vertex_map, e_id);
+          adj_iter i, i_end;
+          for (tie(i, i_end) = adjacent_vertices(element, G); i != i_end; ++i){
+            vertex_t i_node = *i;
+            if (!marker.is_tagged(i_node) && !numbering.is_numbered(i_node)) {
+              marker.mark_tagged(i_node);
+              add_edge(node, i_node, G);
+            }
+          }
+          element_neighbor.pop();
+        }
+        adj_iter v, ve;
+        for (tie(v, ve) = adjacent_vertices(node, G); v != ve; ++v) {
+          vertex_t v_node = *v;
+          if (!degree_lists_marker.need_update(v_node) 
+              && !degree_lists_marker.outmatched_or_done(v_node)) {
+            degreelists.remove(v_node);
+          }
+          //update out edges of v_node
+          remove_out_edge_if(v_node, p2, G);
+
+          if ( out_degree(v_node, G) == 0 ) { // indistinguishable nodes
+            supernode_size[node] += supernode_size[v_node];
+            supernode_size[v_node] = 0;
+            numbering.indistinguishable(v_node, node);
+            marker.mark_done(v_node);
+            degree_lists_marker.mark(v_node);
+          } else {                           // not indistinguishable nodes
+            add_edge(v_node, node, G);
+            degree_lists_marker.mark_need_update(v_node);
+          }
+        }
+      } // eliminate()
+
+
+      template <class Stack>
+      void update(Stack llist, size_type& min_degree)
+      {
+        size_type min_degree0 = min_degree + delta + 1;
+
+        while (! llist.empty()) {
+          size_type deg, deg0 = 0;
+
+          marker.set_multiple_tag(min_degree0);
+          typename Workspace::stack q2list = work_space.make_stack();
+          typename Workspace::stack qxlist = work_space.make_stack();
+
+          vertex_t current = get(index_vertex_map, llist.top());
+          adj_iter i, ie;
+          for (tie(i,ie) = adjacent_vertices(current, G); i != ie; ++i) {
+            vertex_t i_node = *i;
+            const size_type i_id = get(vertex_index_map, i_node);
+            if (supernode_size[i_node] != 0) {
+              deg0 += supernode_size[i_node];
+              marker.mark_multiple_tagged(i_node);
+              if (degree_lists_marker.need_update(i_node)) {
+                if (out_degree(i_node, G) == 2)
+                  q2list.push(i_id);
+                else
+                  qxlist.push(i_id);
+              }
+            }
+          }
+
+          while (!q2list.empty()) {
+            const size_type u_id = q2list.top();
+            vertex_t u_node = get(index_vertex_map, u_id);
+            // if u_id is outmatched by others, no need to update degree
+            if (degree_lists_marker.outmatched_or_done(u_node)) {
+              q2list.pop();
+              continue;
+            }
+            marker.increment_tag();
+            deg = deg0;
+
+            adj_iter nu = adjacent_vertices(u_node, G).first;
+            vertex_t neighbor = *nu;
+            if (neighbor == u_node) {
+              ++nu;
+              neighbor = *nu;
+            }
+            if (numbering.is_numbered(neighbor)) {
+              adj_iter i, ie;
+              for (tie(i,ie) = adjacent_vertices(neighbor, G);
+                   i != ie; ++i) {
+                const vertex_t i_node = *i;
+                if (i_node == u_node || supernode_size[i_node] == 0)
+                  continue;
+                if (marker.is_tagged(i_node)) {
+                  if (degree_lists_marker.need_update(i_node)) {
+                    if ( out_degree(i_node, G) == 2 ) { // is indistinguishable
+                      supernode_size[u_node] += supernode_size[i_node];
+                      supernode_size[i_node] = 0;
+                      numbering.indistinguishable(i_node, u_node);
+                      marker.mark_done(i_node);
+                      degree_lists_marker.mark(i_node);
+                    } else                        // is outmatched
+                      degree_lists_marker.mark(i_node);
+                  }
+                } else {
+                  marker.mark_tagged(i_node);
+                  deg += supernode_size[i_node];
+                }
+              }
+            } else
+              deg += supernode_size[neighbor];
+
+            deg -= supernode_size[u_node];
+            degree[u_node] = deg; //update degree
+            degreelists[deg].push(u_node);
+            //u_id has been pushed back into degreelists
+            degree_lists_marker.unmark(u_node);
+            if (min_degree > deg) 
+              min_degree = deg;
+            q2list.pop();
+          } // while (!q2list.empty())
+
+          while (!qxlist.empty()) {
+            const size_type u_id = qxlist.top();
+            const vertex_t u_node = get(index_vertex_map, u_id);
+
+            // if u_id is outmatched by others, no need to update degree
+            if (degree_lists_marker.outmatched_or_done(u_node)) {
+              qxlist.pop();
+              continue;
+            }
+            marker.increment_tag();
+            deg = deg0;
+            adj_iter i, ie;
+            for (tie(i, ie) = adjacent_vertices(u_node, G); i != ie; ++i) {
+              vertex_t i_node = *i;
+              if (marker.is_tagged(i_node)) 
+                continue;
+              marker.mark_tagged(i_node);
+
+              if (numbering.is_numbered(i_node)) {
+                adj_iter j, je;
+                for (tie(j, je) = adjacent_vertices(i_node, G); j != je; ++j) {
+                  const vertex_t j_node = *j;
+                  if (marker.is_not_tagged(j_node)) {
+                    marker.mark_tagged(j_node);
+                    deg += supernode_size[j_node];
+                  }
+                }
+              } else
+                deg += supernode_size[i_node];
+            } // for adjacent vertices of u_node
+            deg -= supernode_size[u_node];
+            degree[u_node] = deg;
+            degreelists[deg].push(u_node);
+            // u_id has been pushed back into degreelists
+            degree_lists_marker.unmark(u_node); 
+            if (min_degree > deg)
+              min_degree = deg;
+            qxlist.pop();
+          } // while (!qxlist.empty()) {
+
+          marker.set_tag_as_multiple_tag();
+          llist.pop();
+        } // while (! llist.empty())
+
+      } // update()
+
+
+      void build_permutation(InversePermutationMap next,
+                             PermutationMap prev) 
+      {
+        // collect the permutation info
+        size_type i;
+        for (i = 0; i < n; ++i) {
+          diff_t size = supernode_size[get(index_vertex_map, i)];
+          if ( size <= 0 ) {
+            prev[i] = next[i];
+            supernode_size[get(index_vertex_map, i)]
+              = next[i] + 1;  // record the supernode info
+          } else
+            prev[i] = - next[i];
+        }
+        for (i = 1; i < n + 1; ++i) {
+          if ( prev[i-1] > 0 )
+            continue;
+          diff_t parent = i;
+          while ( prev[parent - 1] < 0 ) {
+            parent = - prev[parent - 1];
+          }
+
+          diff_t root = parent;
+          diff_t num = prev[root - 1] + 1;
+          next[i-1] = - num;
+          prev[root-1] = num;
+
+          parent = i;
+          diff_t next_node = - prev[parent - 1];
+          while (next_node > 0) {
+            prev[parent-1] = - root;
+            parent = next_node;
+            next_node = - prev[parent - 1];
+          }
+        }
+        for (i = 0; i < n; i++) {
+          diff_t num = - next[i] - 1;
+          next[i] = num;
+          prev[num] = i;
+        }
+      } // build_permutation()
+    };
+
+  } //namespace detail
+
+
+  // MMD algorithm
+  // 
+  //The implementation presently includes the enhancements for mass
+  //elimination, incomplete degree update, multiple elimination, and
+  //external degree.
+  //
+  //Important Note: This implementation requires the BGL graph to be
+  //directed.  Therefore, nonzero entry (i, j) in a symmetrical matrix
+  //A coresponds to two directed edges (i->j and j->i).
+  //
+  //see Alan George and Joseph W. H. Liu, The Evolution of the Minimum
+  //Degree Ordering Algorithm, SIAM Review, 31, 1989, Page 1-19
+  template<class Graph, class DegreeMap, 
+           class InversePermutationMap, 
+           class PermutationMap,
+           class SuperNodeMap, class VertexIndexMap>
+  void minimum_degree_ordering
+    (Graph& G, 
+     DegreeMap degree, 
+     InversePermutationMap inverse_perm, 
+     PermutationMap perm, 
+     SuperNodeMap supernode_size, 
+     int delta, 
+     VertexIndexMap vertex_index_map)
+  {
+    detail::mmd_impl<Graph,DegreeMap,InversePermutationMap,
+      PermutationMap, SuperNodeMap, VertexIndexMap> 
+      impl(G, num_vertices(G), delta, degree, inverse_perm, 
+           perm, supernode_size, vertex_index_map);
+    impl.do_mmd();
+    impl.build_permutation(inverse_perm, perm);
+  }
+
+} // namespace boost
+
+#endif // MINIMUM_DEGREE_ORDERING_HPP