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 +#include +#include +#include +#include // for integer_traits +#include +#include + +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 Stacks { + typedef SignedInteger value_type; + typedef typename std::vector::size_type size_type; + public: + Stacks(size_type n) : data(n) {} + + //: stack + class stack { + typedef typename std::vector::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::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::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 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 Marker { + typedef SignedInteger value_type; + typedef typename std::vector::size_type size_type; + + static value_type done() + { return (std::numeric_limits::max)()/2; } + public: + Marker(size_type _num, VertexIndexMap index_map) + : tag(1 - (std::numeric_limits::max)()), + data(_num, - (std::numeric_limits::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::max)(); + for (size_type i = 0; i < num; ++i) + if ( data[i] < done() ) + data[i] = - (std::numeric_limits::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::max)(); + + for (size_type i=0; i::max)(); + + multiple_tag = tag + mdeg0; + } + } + + void set_tag_as_multiple_tag() { tag = multiple_tag; } + + protected: + value_type tag; + value_type multiple_tag; + std::vector 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 degreelists_marker { + public: + typedef SignedInteger value_type; + typedef typename std::vector::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 marks; + VertexIndexMap id; + }; + + // Helper function object for edge removal + template + class predicateRemoveEdge1 { + typedef typename graph_traits::vertex_descriptor vertex_t; + typedef typename graph_traits::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 predicate_remove_tagged_edges + { + typedef typename graph_traits::vertex_descriptor vertex_t; + typedef typename graph_traits::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 mmd_impl + { + // Typedefs + typedef graph_traits Traits; + typedef typename Traits::vertices_size_type size_type; + typedef typename detail::integer_traits::difference_type + diff_t; + typedef typename Traits::vertex_descriptor vertex_t; + typedef typename Traits::adjacency_iterator adj_iter; + typedef iterator_property_map IndexVertexMap; + typedef detail::Stacks Workspace; + typedef bucket_sorter + DegreeLists; + typedef Numbering + NumberingD; + typedef degreelists_marker + DegreeListsMarker; + typedef Marker 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 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::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 + p(G, marker, numbering, element_neighbor, vertex_index_map); + + predicate_remove_tagged_edges 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 + 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 + 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 + 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