//-*-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 | |
// 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 (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) { | |
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 (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 |