x
Yes
No
Do you want to visit DriveHQ English website?
首页
产品服务
价格
免费试用
下载客户端
关于我们
云文件服务
|
云备份服务
|
FTP服务
|
企业邮箱服务
|
网站托管
|
客户端软件
云文件服务
云备份服务
FTP服务
企业级邮箱服务
网站托管
客户端软件
king_ordering.hpp - Hosted on DriveHQ Cloud IT Platform
返回上层目录
上传
下载
共享
发布
新建文件夹
新建文件
复制
剪切
删除
粘贴
评论
升级服务
路径: \\game3dprogramming\materials\GameFactory\GameFactoryDemo\references\boost_1_35_0\boost\graph\king_ordering.hpp
旋转
特效
属性
历史版本
//======================================================================= // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. // Copyright 2004, 2005 Trustees of Indiana University // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, // Doug Gregor, D. Kevin McGrath // // 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 BOOST_GRAPH_KING_HPP #define BOOST_GRAPH_KING_HPP #include
#include
/* King Algorithm for matrix reordering */ namespace boost { namespace detail { template
class bfs_king_visitor:public default_bfs_visitor { public: bfs_king_visitor(OutputIterator *iter, Buffer *b, Compare compare, PseudoDegreeMap deg, std::vector
loc, VecMap color, VertexIndexMap vertices): permutation(iter), Qptr(b), degree(deg), comp(compare), Qlocation(loc), colors(color), vertex_map(vertices) { } template
void finish_vertex(Vertex, Graph& g) { typename graph_traits
::out_edge_iterator ei, ei_end; Vertex v, w; typedef typename std::deque
::iterator iterator; typedef typename std::deque
::reverse_iterator reverse_iterator; reverse_iterator rend = Qptr->rend()-index_begin; reverse_iterator rbegin = Qptr->rbegin(); //heap the vertices already there std::make_heap(rbegin, rend, boost::bind
(comp, _2, _1)); unsigned i = 0; for(i = index_begin; i != Qptr->size(); ++i){ colors[get(vertex_map, (*Qptr)[i])] = 1; Qlocation[get(vertex_map, (*Qptr)[i])] = i; } i = 0; for( ; rbegin != rend; rend--){ percolate_down
(i); w = (*Qptr)[index_begin+i]; for (tie(ei, ei_end) = out_edges(w, g); ei != ei_end; ++ei) { v = target(*ei, g); put(degree, v, get(degree, v) - 1); if (colors[get(vertex_map, v)] == 1) { percolate_up
(get(vertex_map, v), i); } } colors[get(vertex_map, w)] = 0; i++; } } template
void examine_vertex(Vertex u, const Graph&) { *(*permutation)++ = u; index_begin = Qptr->size(); } protected: //this function replaces pop_heap, and tracks state information template
void percolate_down(int offset){ typedef typename std::deque
::reverse_iterator reverse_iterator; int heap_last = index_begin + offset; int heap_first = Qptr->size() - 1; //pop_heap functionality: //swap first, last std::swap((*Qptr)[heap_last], (*Qptr)[heap_first]); //swap in the location queue std::swap(Qlocation[heap_first], Qlocation[heap_last]); //set drifter, children int drifter = heap_first; int drifter_heap = Qptr->size() - drifter; int right_child_heap = drifter_heap * 2 + 1; int right_child = Qptr->size() - right_child_heap; int left_child_heap = drifter_heap * 2; int left_child = Qptr->size() - left_child_heap; //check that we are staying in the heap bool valid = (right_child < heap_last) ? false : true; //pick smallest child of drifter, and keep in mind there might only be left child int smallest_child = (valid && get(degree, (*Qptr)[left_child]) > get(degree,(*Qptr)[right_child])) ? right_child : left_child; while(valid && smallest_child < heap_last && comp((*Qptr)[drifter], (*Qptr)[smallest_child])){ //if smallest child smaller than drifter, swap them std::swap((*Qptr)[smallest_child], (*Qptr)[drifter]); std::swap(Qlocation[drifter], Qlocation[smallest_child]); //update the values, run again, as necessary drifter = smallest_child; drifter_heap = Qptr->size() - drifter; right_child_heap = drifter_heap * 2 + 1; right_child = Qptr->size() - right_child_heap; left_child_heap = drifter_heap * 2; left_child = Qptr->size() - left_child_heap; valid = (right_child < heap_last) ? false : true; smallest_child = (valid && get(degree, (*Qptr)[left_child]) > get(degree,(*Qptr)[right_child])) ? right_child : left_child; } } // this is like percolate down, but we always compare against the // parent, as there is only a single choice template
void percolate_up(int vertex, int offset){ int child_location = Qlocation[vertex]; int heap_child_location = Qptr->size() - child_location; int heap_parent_location = (int)(heap_child_location/2); unsigned parent_location = Qptr->size() - heap_parent_location; bool valid = (heap_parent_location != 0 && child_location > index_begin + offset && parent_location < Qptr->size()); while(valid && comp((*Qptr)[child_location], (*Qptr)[parent_location])){ //swap in the heap std::swap((*Qptr)[child_location], (*Qptr)[parent_location]); //swap in the location queue std::swap(Qlocation[child_location], Qlocation[parent_location]); child_location = parent_location; heap_child_location = heap_parent_location; heap_parent_location = (int)(heap_child_location/2); parent_location = Qptr->size() - heap_parent_location; valid = (heap_parent_location != 0 && child_location > index_begin + offset); } } OutputIterator *permutation; int index_begin; Buffer *Qptr; PseudoDegreeMap degree; Compare comp; std::vector
Qlocation; VecMap colors; VertexIndexMap vertex_map; }; } // namespace detail template
OutputIterator king_ordering(const Graph& g, std::deque< typename graph_traits
::vertex_descriptor > vertex_queue, OutputIterator permutation, ColorMap color, DegreeMap degree, VertexIndexMap index_map) { typedef typename property_traits
::value_type ds_type; typedef typename property_traits
::value_type ColorValue; typedef color_traits
Color; typedef typename graph_traits
::vertex_descriptor Vertex; typedef iterator_property_map
::iterator, VertexIndexMap, ds_type, ds_type&> PseudoDegreeMap; typedef indirect_cmp
> Compare; typedef typename boost::sparse::sparse_ordering_queue
queue; typedef typename detail::bfs_king_visitor
, VertexIndexMap > Visitor; typedef typename graph_traits
::vertices_size_type vertices_size_type; std::vector
pseudo_degree_vec(num_vertices(g)); PseudoDegreeMap pseudo_degree(pseudo_degree_vec.begin(), index_map); typename graph_traits
::vertex_iterator ui, ui_end; queue Q; // Copy degree to pseudo_degree // initialize the color map for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui){ put(pseudo_degree, *ui, get(degree, *ui)); put(color, *ui, Color::white()); } Compare comp(pseudo_degree); std::vector
colors(num_vertices(g)); for(vertices_size_type i = 0; i < num_vertices(g); i++) colors[i] = 0; std::vector
loc(num_vertices(g)); //create the visitor Visitor vis(&permutation, &Q, comp, pseudo_degree, loc, colors, index_map); while( !vertex_queue.empty() ) { Vertex s = vertex_queue.front(); vertex_queue.pop_front(); //call BFS with visitor breadth_first_visit(g, s, Q, vis, color); } return permutation; } // This is the case where only a single starting vertex is supplied. template
OutputIterator king_ordering(const Graph& g, typename graph_traits
::vertex_descriptor s, OutputIterator permutation, ColorMap color, DegreeMap degree, VertexIndexMap index_map) { std::deque< typename graph_traits
::vertex_descriptor > vertex_queue; vertex_queue.push_front( s ); return king_ordering(g, vertex_queue, permutation, color, degree, index_map); } template < class Graph, class OutputIterator, class ColorMap, class DegreeMap, class VertexIndexMap> OutputIterator king_ordering(const Graph& G, OutputIterator permutation, ColorMap color, DegreeMap degree, VertexIndexMap index_map) { if (vertices(G).first == vertices(G).second) return permutation; typedef typename boost::graph_traits
::vertex_descriptor Vertex; typedef typename boost::graph_traits
::vertex_iterator VerIter; typedef typename property_traits
::value_type ColorValue; typedef color_traits
Color; std::deque
vertex_queue; // Mark everything white BGL_FORALL_VERTICES_T(v, G, Graph) put(color, v, Color::white()); // Find one vertex from each connected component BGL_FORALL_VERTICES_T(v, G, Graph) { if (get(color, v) == Color::white()) { depth_first_visit(G, v, dfs_visitor<>(), color); vertex_queue.push_back(v); } } // Find starting nodes for all vertices // TBD: How to do this with a directed graph? for (typename std::deque
::iterator i = vertex_queue.begin(); i != vertex_queue.end(); ++i) *i = find_starting_node(G, *i, color, degree); return king_ordering(G, vertex_queue, permutation, color, degree, index_map); } template
OutputIterator king_ordering(const Graph& G, OutputIterator permutation, VertexIndexMap index_map) { if (vertices(G).first == vertices(G).second) return permutation; typedef out_degree_property_map
DegreeMap; std::vector
colors(num_vertices(G)); return king_ordering(G, permutation, make_iterator_property_map(&colors[0], index_map, colors[0]), make_out_degree_map(G), index_map); } template
inline OutputIterator king_ordering(const Graph& G, OutputIterator permutation) { return king_ordering(G, permutation, get(vertex_index, G)); } } // namespace boost #endif // BOOST_GRAPH_KING_HPP
king_ordering.hpp
网页地址
文件地址
上一页
52/95
下一页
下载
( 11 KB )
Comments
Total ratings:
0
Average rating:
无评论
of 10
Would you like to comment?
Join now
, or
Logon
if you are already a member.