From 5c32e533b678075684ab5ba1f1d021cd902d0c7e Mon Sep 17 00:00:00 2001 From: Wolfgang Bangerth Date: Thu, 7 Nov 2013 21:52:09 +0000 Subject: [PATCH] Add some more comments. git-svn-id: https://svn.dealii.org/trunk@31577 0785d39b-7218-0410-832d-ea1e28bc413d --- deal.II/include/deal.II/base/graph_coloring.h | 35 +++++++++++-------- 1 file changed, 20 insertions(+), 15 deletions(-) diff --git a/deal.II/include/deal.II/base/graph_coloring.h b/deal.II/include/deal.II/base/graph_coloring.h index 5209f238bf..db8d238f14 100644 --- a/deal.II/include/deal.II/base/graph_coloring.h +++ b/deal.II/include/deal.II/base/graph_coloring.h @@ -20,6 +20,7 @@ #include +#include #include #include #include @@ -163,18 +164,20 @@ namespace GraphColoring * @param[in] get_conflict_indices A user defined function object returning * a set of indicators that are descriptive of what represents a * conflict. See above for a more thorough discussion. - * @return A set of sets of iterators (where sets are represented by + * @param[out] partition_coloring A set of sets of iterators (where sets are represented by * std::vector for efficiency). Each element of the outermost set * corresponds to the iterators pointing to objects that are in the * same partition (have the same color) and consequently do not * conflict. The elements of different sets may conflict. */ template - std::vector > + void make_dsatur_coloring(std::vector &partition, - const std_cxx1x::function (const Iterator &)> &get_conflict_indices) + const std_cxx1x::function (const Iterator &)> &get_conflict_indices, + std::vector > &partition_coloring) { - std::vector > partition_coloring; + partition_coloring.clear (); + // Number of zones composing the partitioning. const unsigned int partition_size(partition.size()); std::vector sorted_vertices(partition_size); @@ -265,16 +268,17 @@ namespace GraphColoring 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. + * Given a partition-coloring graph, i.e., a set of zones (partitions) each + * of which is colored, produce a combined coloring for the entire set of + * iterators. This is possible because any color on an + * even (resp. odd) zone does not conflict with any color of any other even + * (resp. odd) zone. Consequently, we can combine colors from all even and all + * odd zones. This function tries to create colors of similar number of elements. */ template std::vector > @@ -473,17 +477,18 @@ namespace GraphColoring get_conflict_indices); // Color the iterators within each partition. + // Run the coloring algorithm on each zone in parallel const unsigned int partitioning_size(partitioning.size()); std::vector > > partition_coloring(partitioning_size); - // TODO: run these in parallel + Threads::TaskGroup<> tasks; for (unsigned int i=0; i, + partitioning[i], + get_conflict_indices, + partition_coloring[i]); + tasks.join_all(); // Gather the colors together. return internal::gather_colors(partition_coloring); -- 2.39.5