From 439b850060e74a3043901445fc00cec8320546ec Mon Sep 17 00:00:00 2001 From: turcksin Date: Tue, 17 Sep 2013 23:23:55 +0000 Subject: [PATCH] Start graph coloring abilities for work_stream. git-svn-id: https://svn.dealii.org/trunk@30781 0785d39b-7218-0410-832d-ea1e28bc413d --- deal.II/include/deal.II/base/graph_coloring.h | 358 ++++++++++++++++++ tests/base/graph_coloring_01.cc | 73 ++++ tests/base/graph_coloring_01/cmp/generic | 13 + 3 files changed, 444 insertions(+) create mode 100644 deal.II/include/deal.II/base/graph_coloring.h create mode 100644 tests/base/graph_coloring_01.cc create mode 100644 tests/base/graph_coloring_01/cmp/generic diff --git a/deal.II/include/deal.II/base/graph_coloring.h b/deal.II/include/deal.II/base/graph_coloring.h new file mode 100644 index 0000000000..47c4a0826b --- /dev/null +++ b/deal.II/include/deal.II/base/graph_coloring.h @@ -0,0 +1,358 @@ + +// --------------------------------------------------------------------- +// $Id: work_stream.h 30494 2013-08-26 10:04:44Z kronbichler $ +// +// Copyright (C) 2008 - 2013 by the deal.II authors +// +// This file is part of the deal.II library. +// +// The deal.II library is free software; you can use it, redistribute +// it, and/or modify it under the terms of the GNU Lesser General +// Public License as published by the Free Software Foundation; either +// version 2.1 of the License, or (at your option) any later version. +// The full text of the license can be found in the file LICENSE at +// the top level of the deal.II distribution. +// +// --------------------------------------------------------------------- + +#ifndef __deal2__graph_coloring_h +#define __deal2__graph_coloring_h + + +#include +#include +#include +#include + +#include + +DEAL_II_NAMESPACE_OPEN + +// Currently graph_coloring only works for on uniform mesh, with a uniform +// order for the polynomials, and only for continuous FE. +namespace graph_coloring { + + /** + * Create the partitioning using a simplified version of the Cuthill-McKee + * algorithm (Breadth First Search algorithm). + */ + template + std::vector > create_partitioning(Iterator const &begin, + typename identity::type const &end) + { + std::vector > partitioning(1,std::vector (1,begin)); + // Create a map from dofs to cells + boost::unordered_map > dof_to_cell; + for (Iterator it=begin; it!=end; ++it) + { + // Need to check that it works with hp + const unsigned int dofs_per_cell(it->get_fe().dofs_per_cell); + std::vector local_dof_indices(dofs_per_cell); + it->get_dof_indices(local_dof_indices); + for (unsigned int i=0; i used_it; + used_it.insert(begin); + while (!done) + { + typename std::vector::iterator vector_it(partitioning.back().begin()); + typename std::vector::iterator vector_end(partitioning.back().end()); + std::vector new_zone; + for (; vector_it!=vector_end; ++vector_it) + { + const unsigned int dofs_per_cell((*vector_it)->get_fe().dofs_per_cell); + std::vector local_dof_indices(dofs_per_cell); + (*vector_it)->get_dof_indices(local_dof_indices); + for (unsigned int i=0; i iterator_vector(dof_to_cell[local_dof_indices[i]]); + for (unsigned int j=0; j + std::vector > make_dsatur_coloring(std::vector const &partition) + { + std::vector > partition_coloring; + // Number of zones composing the partitioning. + const unsigned int partition_size(partition.size()); + std::vector sorted_vertices(partition_size); + std::vector degrees(partition_size); + std::vector > local_dof_indices(partition_size); + std::vector > graph(partition_size); + + // Get the dofs associated to each cell. The dof_indices have to be sorted so + // set_intersection can be used later. + for (unsigned int i=0; iget_fe().dofs_per_cell); + partition[i]->get_dof_indices(local_dof_indices[i]); + std::sort(local_dof_indices[i].begin(),local_dof_indices[i].end()); + } + + // Compute the degree of each vertex of the graph (cell) using the + // intersection of dofs + std::vector dofs_intersection; + std::vector::iterator intersection_it; + for (unsigned int i=0; i::iterator degrees_it; + for (unsigned int i=0; i > colors_used; + for (unsigned int i=0; i (1, + partition[current_vertex])); + boost::unordered_set tmp; + tmp.insert(current_vertex); + colors_used.push_back(tmp); + } + } + + return partition_coloring; + } + + /** + * Given a partition-coloring graph, gather the colors together. All the + * colors on even (resp. odd) partition can be executed simultaneously. This + * function tries to create colors of similar number of elements. + */ + template + std::vector > + gather_colors(std::vector > > const &partition_coloring) + { + std::vector > coloring; + + // Count the number of iterators in each color. + const unsigned int partition_size(partition_coloring.size()); + std::vector > colors_counter(partition_size); + for (unsigned int i=0; i used_k; + for (unsigned int j=0; j::iterator it; + it = std::max_element(colors_counter[i].begin(),colors_counter[i].end()); + unsigned int min_cells(-1); + unsigned int pos(0); + // Find the color of coloring with the least number of colors among + // the colors that have not been used yet. + for (unsigned int k=0; k used_k; + for (unsigned int j=0; j::iterator it; + it = std::max_element(colors_counter[i].begin(),colors_counter[i].end()); + unsigned int min_cells(-1); + unsigned int pos(0); + // Find the color of coloring with the least number of colors among + // the colors that have not been used yet. + for (unsigned int k=0; k + std::vector > + make_graph_coloring(Iterator const &begin,typename identity::type const &end) + { + // Create the partitioning. + std::vector > partitioning = create_partitioning(begin,end); + + // Color the cells within each partition. + const unsigned int partitioning_size(partitioning.size()); + std::vector > > partition_coloring( + partitioning_size); + for (unsigned int i=0; i > coloring = gather_colors(partition_coloring); + + return coloring; + } + +} // End graph_coloring namespace + +DEAL_II_NAMESPACE_CLOSE + + +//---------------------------- graph_coloring.h --------------------------- +// end of #ifndef __deal2__graph_coloring_h +#endif +//---------------------------- graph_coloring.h --------------------------- diff --git a/tests/base/graph_coloring_01.cc b/tests/base/graph_coloring_01.cc new file mode 100644 index 0000000000..d53a51d32c --- /dev/null +++ b/tests/base/graph_coloring_01.cc @@ -0,0 +1,73 @@ +// --------------------------------------------------------------------- +// $Id: graph_coloring.cc 30045 2013-07-18 19:18:00Z maier $ +// +// Copyright (C) 2003 - 2013 by the deal.II authors +// +// This file is part of the deal.II library. +// +// The deal.II library is free software; you can use it, redistribute +// it, and/or modify it under the terms of the GNU Lesser General +// Public License as published by the Free Software Foundation; either +// version 2.1 of the License, or (at your option) any later version. +// The full text of the license can be found in the file LICENSE at +// the top level of the deal.II distribution. +// +// --------------------------------------------------------------------- + + + +// Check that graph coloring works on uniform mesh with a uniform polynomial +// order. + + +#include "../tests.h" +#include +#include + +#include +#include +#include +#include +#include +#include +#include +#include + +template +void check() +{ + // Create the Triangulation and the DoFHandler + Triangulation triangulation; + GridGenerator::hyper_cube(triangulation); + triangulation.refine_global(2); + FE_Q fe(2); + DoFHandler dof_handler(triangulation); + dof_handler.distribute_dofs(fe); + + // Create the coloring + std::vector::active_cell_iterator> > coloring( + graph_coloring::make_graph_coloring(dof_handler.begin_active(),dof_handler.end())); + + // Output the coloring + for (unsigned int color=0; colorcenter()[j]<<" "; + deallog< (); + + return 0; +} diff --git a/tests/base/graph_coloring_01/cmp/generic b/tests/base/graph_coloring_01/cmp/generic new file mode 100644 index 0000000000..4c55a8feea --- /dev/null +++ b/tests/base/graph_coloring_01/cmp/generic @@ -0,0 +1,13 @@ + +DEAL::Color: 0 +DEAL::0.6250 0.3750 0.1250 0.6250 +DEAL::Color: 1 +DEAL::0.3750 0.6250 0.6250 0.1250 +DEAL::Color: 2 +DEAL::0.6250 0.6250 0.1250 0.1250 +DEAL::Color: 3 +DEAL::0.3750 0.1250 0.8750 0.6250 0.3750 0.8750 0.8750 0.1250 +DEAL::Color: 4 +DEAL::0.1250 0.3750 0.6250 0.8750 0.8750 0.3750 0.1250 0.8750 +DEAL::Color: 5 +DEAL::0.3750 0.3750 0.8750 0.8750 -- 2.39.5