From 93f48664833097fb458901c830dd4643fbbcff0a Mon Sep 17 00:00:00 2001
From: nivesh <nidhinivesh.d@gmail.com>
Date: Tue, 5 Dec 2017 19:25:24 +0100
Subject: [PATCH] color_sparsity_pattern function added in GraphColoring
 namespace. Test added for the same.

Added assertion
---
 include/deal.II/base/graph_coloring.h | 10 ++++
 include/deal.II/lac/sparsity_tools.h  | 23 ++++----
 source/base/CMakeLists.txt            |  1 +
 source/base/graph_coloring.cc         | 30 ++++++++++
 source/lac/sparsity_tools.cc          |  9 ++-
 tests/zoltan/zoltan_02.cc             | 10 ----
 tests/zoltan/zoltan_03.cc             | 81 +++++++++++++++++++++++++++
 tests/zoltan/zoltan_03.output         |  8 +++
 8 files changed, 150 insertions(+), 22 deletions(-)
 create mode 100644 source/base/graph_coloring.cc
 create mode 100644 tests/zoltan/zoltan_03.cc
 create mode 100644 tests/zoltan/zoltan_03.output

diff --git a/include/deal.II/base/graph_coloring.h b/include/deal.II/base/graph_coloring.h
index 7513dbc9bb..c8d1f6cdf0 100644
--- a/include/deal.II/base/graph_coloring.h
+++ b/include/deal.II/base/graph_coloring.h
@@ -22,6 +22,7 @@
 #include <deal.II/base/thread_management.h>
 #include <boost/unordered_map.hpp>
 #include <boost/unordered_set.hpp>
+#include <deal.II/lac/sparsity_tools.h>
 
 #include <functional>
 #include <set>
@@ -542,6 +543,15 @@ namespace GraphColoring
     return internal::gather_colors(partition_coloring);
   }
 
+  /**
+   * GraphColoring::color_sparsity_pattern, a wrapper function for
+   * SparsityTools::color_sparsity_pattern, is an alternate method for
+   * coloring using graph connections represented by SparsityPattern.
+   * For further details, refer to SparsityTools::color_sparsity_pattern.
+   */
+  unsigned int color_sparsity_pattern (const SparsityPattern     &sparsity_pattern,
+                                       std::vector<unsigned int> &color_indices);
+
 } // End graph_coloring namespace
 
 DEAL_II_NAMESPACE_CLOSE
diff --git a/include/deal.II/lac/sparsity_tools.h b/include/deal.II/lac/sparsity_tools.h
index 0a2ee7cc23..811bd2620c 100644
--- a/include/deal.II/lac/sparsity_tools.h
+++ b/include/deal.II/lac/sparsity_tools.h
@@ -112,19 +112,22 @@ namespace SparsityTools
    * an edge between two nodes. The goal is to assign each node a color index
    * such that no two directly connected nodes have the same color.
    * The assigned colors are listed in @p color_indices indexed from one and
-   * the function returns total number of colors used. Note that this function
-   * requires that SparsityPattern be symmetric (and hence square) i.e an
-   * undirected graph representation. We do not check for symmetry of the
-   * sparsity pattern, since this is an expensive operation, but rather leave
-   * this as the responsibility of caller of this function.
+   * the function returns total number of colors used. ZOLTAN coloring
+   * algorithm is run in serial by each processor. Hence all processors have
+   * coloring information of all the nodes. A wrapper function to this
+   * function is available in GraphColoring namespace as well.
    *
-   * ZOLTAN coloring algorithm is run in serial by each processor. Hence all
-   * processors have coloring information of all the nodes.
+   * Note that this function requires that SparsityPattern be symmetric
+   * (and hence square) i.e an undirected graph representation. We do not
+   * check for symmetry of the sparsity pattern, since this is an expensive
+   * operation, but rather leave this as the responsibility of caller of
+   * this function.
    *
    * @image html color_undirected_graph.png
-   * For example, the above image shows 5 nodes numbered from 0 to 4.
-   * The connections shown are bidirectional. After coloring, no two connected
-   * nodes have the same color.
+   * The usage of the function is illustrated by the image above, showing five
+   * nodes numbered from 0 to 4. The connections shown are bidirectional.
+   * After coloring, it is clear that no two directly connected nodes are
+   * assigned the same color.
    *
    * If deal.II was not installed with package ZOLTAN, this function will
    * generate an error.
diff --git a/source/base/CMakeLists.txt b/source/base/CMakeLists.txt
index c140d4c722..5361e2a66d 100644
--- a/source/base/CMakeLists.txt
+++ b/source/base/CMakeLists.txt
@@ -39,6 +39,7 @@ SET(_unity_include_src
   function_time.cc
   geometry_info.cc
   geometric_utilities.cc
+  graph_coloring.cc
   index_set.cc
   job_identifier.cc
   logstream.cc
diff --git a/source/base/graph_coloring.cc b/source/base/graph_coloring.cc
new file mode 100644
index 0000000000..41cea44093
--- /dev/null
+++ b/source/base/graph_coloring.cc
@@ -0,0 +1,30 @@
+// ---------------------------------------------------------------------
+//
+// Copyright (C) 1998 - 2015 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.
+//
+// ---------------------------------------------------------------------
+
+#include <deal.II/base/graph_coloring.h>
+
+
+DEAL_II_NAMESPACE_OPEN
+
+namespace GraphColoring
+{
+  unsigned int color_sparsity_pattern (const SparsityPattern     &sparsity_pattern,
+                                       std::vector<unsigned int> &color_indices)
+  {
+    return SparsityTools::color_sparsity_pattern (sparsity_pattern, color_indices);
+  }
+}
+
+DEAL_II_NAMESPACE_CLOSE
diff --git a/source/lac/sparsity_tools.cc b/source/lac/sparsity_tools.cc
index ea3d33bd0e..5733b4b061 100644
--- a/source/lac/sparsity_tools.cc
+++ b/source/lac/sparsity_tools.cc
@@ -381,9 +381,14 @@ namespace SparsityTools
                         color_exp.data());
 
     //Check for error code
-    Assert (rc == ZOLTAN_OK , ExcInternalError());
+    Assert (rc == ZOLTAN_OK ,
+            ExcInternalError());
+
+    //Allocate and assign color indices
+    color_indices.resize(num_objects);
+    Assert (color_exp.size() == color_indices.size(),
+            ExcDimensionMismatch (color_exp.size(),color_indices.size()));
 
-    //Allocate and assign color
     std::copy (color_exp.begin(), color_exp.end(), color_indices.begin());
 
     unsigned int n_colors = *(std::max_element (color_indices.begin(),
diff --git a/tests/zoltan/zoltan_02.cc b/tests/zoltan/zoltan_02.cc
index 585b5840da..d3630b3ec2 100644
--- a/tests/zoltan/zoltan_02.cc
+++ b/tests/zoltan/zoltan_02.cc
@@ -18,17 +18,7 @@
 
 
 #include "../tests.h"
-#include <deal.II/grid/tria.h>
-#include <deal.II/grid/tria_accessor.h>
-#include <deal.II/grid/tria_iterator.h>
-#include <deal.II/grid/grid_tools.h>
-#include <deal.II/grid/grid_generator.h>
 #include <deal.II/lac/sparsity_tools.h>
-#include <deal.II/numerics/data_out.h>
-
-#include <fstream>
-#include <vector>
-
 
 void fill_graph (DynamicSparsityPattern &graph)
 {
diff --git a/tests/zoltan/zoltan_03.cc b/tests/zoltan/zoltan_03.cc
new file mode 100644
index 0000000000..fd44a9b082
--- /dev/null
+++ b/tests/zoltan/zoltan_03.cc
@@ -0,0 +1,81 @@
+// ---------------------------------------------------------------------
+//
+// Copyright (C) 2004 - 2015 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 wrapper function GraphColoring::color_sparsity_pattern
+
+
+#include "../tests.h"
+#include <deal.II/base/graph_coloring.h>
+
+
+void fill_graph (DynamicSparsityPattern &graph)
+{
+  //Edges in only one direction
+  graph.add(0,1);
+  graph.add(0,2);
+  graph.add(1,2);
+  graph.add(1,4);
+  graph.add(4,3);
+  graph.add(2,4);
+  graph.add(3,2);
+
+  //Edges in opposite direction
+  graph.add(1,0);
+  graph.add(2,0);
+  graph.add(2,1);
+  graph.add(4,1);
+  graph.add(3,4);
+  graph.add(4,2);
+  graph.add(2,3);
+}
+
+
+int main (int argc, char **argv)
+{
+  //Initialize MPI and Zoltan
+  Utilities::MPI::MPI_InitFinalize mpi_initialization (argc, argv);
+  MPILogInitAll all;
+
+  //Number of nodes
+  unsigned int num_indices = 5;
+
+  //Create temporary object to hold graph connection info.
+  DynamicSparsityPattern dynamic_sparse_graph;
+  dynamic_sparse_graph.reinit(num_indices,num_indices);
+
+  //fill dynamic sparsity pattern
+  fill_graph(dynamic_sparse_graph);
+
+  //Create sparity pattern to hold graph connection info.
+  SparsityPattern sp_graph;
+  sp_graph.copy_from(dynamic_sparse_graph);
+
+  Assert( num_indices == sp_graph.n_rows() , ExcInternalError() );
+
+  std::vector<unsigned int> color_indices;
+  unsigned int num_colors;
+
+  color_indices.resize(num_indices);
+  num_colors = GraphColoring::color_sparsity_pattern (sp_graph, color_indices);
+
+  //color
+  deallog << "Coloring" << std::endl;
+  deallog << "Number of colors used: " << num_colors << std::endl;
+  for (unsigned int i=0; i<num_indices; i++)
+    {
+      deallog << i << " " << color_indices[i] << std::endl;
+    }
+}
diff --git a/tests/zoltan/zoltan_03.output b/tests/zoltan/zoltan_03.output
new file mode 100644
index 0000000000..4bcd6770b8
--- /dev/null
+++ b/tests/zoltan/zoltan_03.output
@@ -0,0 +1,8 @@
+
+DEAL:0::Coloring
+DEAL:0::Number of colors used: 4
+DEAL:0::0 1
+DEAL:0::1 2
+DEAL:0::2 3
+DEAL:0::3 1
+DEAL:0::4 4
-- 
2.39.5