123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664 |
- //-*-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 <boost/assert.hpp>
- #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/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() {
- BOOST_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
- bool has_no_edges;
- // 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)
- : has_no_edges(true), 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 (boost::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 (boost::tie(v, vend) = vertices(G); v != vend; ++v) {
- typename Traits::degree_size_type d = out_degree(*v, G);
- put(degree, *v, d);
- if (0 < d) has_no_edges = false;
- 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();
- }
- if (has_no_edges)
- {
- return;
- }
- 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 (boost::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 (boost::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 (boost::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 (boost::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 (boost::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 (boost::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
|