From e812ca464ad2b4e7c4f3ce70cd597142b7b841ec Mon Sep 17 00:00:00 2001 From: turcksin Date: Tue, 1 Oct 2013 17:12:43 +0000 Subject: [PATCH] Fix a bug in graph coloring and add a test for it. git-svn-id: https://svn.dealii.org/trunk@31058 0785d39b-7218-0410-832d-ea1e28bc413d --- deal.II/include/deal.II/base/graph_coloring.h | 12 +- tests/base/graph_coloring_04.cc | 108 ++++++++++++++++++ tests/base/graph_coloring_04/cmp/generic | 2 + 3 files changed, 117 insertions(+), 5 deletions(-) create mode 100644 tests/base/graph_coloring_04.cc create mode 100644 tests/base/graph_coloring_04/cmp/generic diff --git a/deal.II/include/deal.II/base/graph_coloring.h b/deal.II/include/deal.II/base/graph_coloring.h index 2349fbe994..fcd4d0b0c9 100644 --- a/deal.II/include/deal.II/base/graph_coloring.h +++ b/deal.II/include/deal.II/base/graph_coloring.h @@ -25,8 +25,10 @@ #include #include +#include #include + DEAL_II_NAMESPACE_OPEN /// This namespace contains the functions necessary to color a graph. @@ -120,7 +122,7 @@ namespace graph_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 degrees(partition_size); std::vector > conflict_indices(partition_size); std::vector > graph(partition_size); @@ -132,7 +134,7 @@ namespace graph_coloring { std::sort(conflict_indices[i].begin(),conflict_indices[i].end()); } - // Compute the degree of each vertex of the graph using the + // Compute the degree of each vertex of the graph using the // intersection of the conflict indices. std::vector conflict_indices_intersection; std::vector::iterator intersection_it; @@ -156,14 +158,14 @@ namespace graph_coloring { } // Sort the vertices by decreasing degree. - std::vector::iterator degrees_it; + std::vector::iterator degrees_it; for (unsigned int i=0; i +#include + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + + + +template +std::vector get_conflict_indices( + const typename DoFHandler::active_cell_iterator &it) +{ + std::vector local_dof_indices(it->get_fe().dofs_per_cell); + it->get_dof_indices(local_dof_indices); + + return local_dof_indices; +} + + +template +void check () +{ + Triangulation triangulation; + GridGenerator::hyper_shell (triangulation, + Point(), + 1, 2, + (dim==3) ? 96 : 12, + true); + + triangulation.refine_global (3); + + for (unsigned int i=0; i<3; ++i) + { + Vector estimated_error_per_cell (triangulation.n_active_cells()); + for (unsigned int i=0; i< estimated_error_per_cell.size(); ++i) + estimated_error_per_cell(i) = i; + GridRefinement:: + refine_and_coarsen_fixed_fraction (triangulation, + estimated_error_per_cell, + 0.3, 0.1); + triangulation.execute_coarsening_and_refinement(); + } + + FE_Q fe(1); + DoFHandler stokes_dof_handler (triangulation); + stokes_dof_handler.distribute_dofs (fe); + + for (typename DoFHandler::active_cell_iterator cell=stokes_dof_handler.begin_active(); + cell != stokes_dof_handler.end(); ++cell) + cell->clear_user_flag (); + std::vector::active_cell_iterator> > coloring + = graph_coloring::make_graph_coloring(stokes_dof_handler.begin_active(), + stokes_dof_handler.end(), + std_cxx1x::function ( + const typename DoFHandler::active_cell_iterator &)>(&get_conflict_indices)); + + for (unsigned int c=0; cset_user_flag(); + + for (typename DoFHandler::active_cell_iterator cell=stokes_dof_handler.begin_active(); + cell != stokes_dof_handler.end(); ++cell) + Assert (cell->user_flag_set () == true, ExcInternalError()); + + deallog<<"OK"< (); + + return 0; +} diff --git a/tests/base/graph_coloring_04/cmp/generic b/tests/base/graph_coloring_04/cmp/generic new file mode 100644 index 0000000000..0fd8fc12f0 --- /dev/null +++ b/tests/base/graph_coloring_04/cmp/generic @@ -0,0 +1,2 @@ + +DEAL::OK -- 2.39.5