internal/ceres/reorder_program_test.cc - ceres-solver - Git at Google

 // Ceres Solver - A fast non-linear least squares minimizer
 // Copyright 2023 Google Inc. All rights reserved.
 // http://ceres-solver.org/
 //
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are met:
 //
 // * Redistributions of source code must retain the above copyright notice,
 //   this list of conditions and the following disclaimer.
 // * Redistributions in binary form must reproduce the above copyright notice,
 //   this list of conditions and the following disclaimer in the documentation
 //   and/or other materials provided with the distribution.
 // * Neither the name of Google Inc. nor the names of its contributors may be
 //   used to endorse or promote products derived from this software without
 //   specific prior written permission.
 //
 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 // POSSIBILITY OF SUCH DAMAGE.
 //
 // Author: sameeragarwal@google.com (Sameer Agarwal)

 #include "ceres/reorder_program.h"

 #include <random>
 #include <vector>

 #include "ceres/internal/config.h"
 #include "ceres/parameter_block.h"
 #include "ceres/problem_impl.h"
 #include "ceres/program.h"
 #include "ceres/sized_cost_function.h"
 #include "ceres/solver.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"

 namespace ceres {
 namespace internal {

 // Templated base class for the CostFunction signatures.
 template <int kNumResiduals, int... Ns>
 class MockCostFunctionBase : public SizedCostFunction<kNumResiduals, Ns...> {
  public:
   bool Evaluate(double const* const* parameters,
                 double* residuals,
                 double** jacobians) const final {
     // Do nothing. This is never called.
     return true;
   }
 };

 class UnaryCostFunction : public MockCostFunctionBase<2, 1> {};
 class BinaryCostFunction : public MockCostFunctionBase<2, 1, 1> {};
 class TernaryCostFunction : public MockCostFunctionBase<2, 1, 1, 1> {};

 TEST(_, ReorderResidualBlockNormalFunction) {
   ProblemImpl problem;
   double x;
   double y;
   double z;

   problem.AddParameterBlock(&x, 1);
   problem.AddParameterBlock(&y, 1);
   problem.AddParameterBlock(&z, 1);

   problem.AddResidualBlock(new UnaryCostFunction(), nullptr, &x);
   problem.AddResidualBlock(new BinaryCostFunction(), nullptr, &z, &x);
   problem.AddResidualBlock(new BinaryCostFunction(), nullptr, &z, &y);
   problem.AddResidualBlock(new UnaryCostFunction(), nullptr, &z);
   problem.AddResidualBlock(new BinaryCostFunction(), nullptr, &x, &y);
   problem.AddResidualBlock(new UnaryCostFunction(), nullptr, &y);

   auto linear_solver_ordering = std::make_shared<ParameterBlockOrdering>();
   linear_solver_ordering->AddElementToGroup(&x, 0);
   linear_solver_ordering->AddElementToGroup(&y, 0);
   linear_solver_ordering->AddElementToGroup(&z, 1);

   Solver::Options options;
   options.linear_solver_type = DENSE_SCHUR;
   options.linear_solver_ordering = linear_solver_ordering;

   const std::vector<ResidualBlock*>& residual_blocks =
       problem.program().residual_blocks();

   std::vector<ResidualBlock*> expected_residual_blocks;

   // This is a bit fragile, but it serves the purpose. We know the
   // bucketing algorithm that the reordering function uses, so we
   // expect the order for residual blocks for each e_block to be
   // filled in reverse.
   expected_residual_blocks.push_back(residual_blocks[4]);
   expected_residual_blocks.push_back(residual_blocks[1]);
   expected_residual_blocks.push_back(residual_blocks[0]);
   expected_residual_blocks.push_back(residual_blocks[5]);
   expected_residual_blocks.push_back(residual_blocks[2]);
   expected_residual_blocks.push_back(residual_blocks[3]);

   Program* program = problem.mutable_program();
   program->SetParameterOffsetsAndIndex();

   std::string message;
   EXPECT_TRUE(LexicographicallyOrderResidualBlocks(
       2, problem.mutable_program(), &message));
   EXPECT_EQ(residual_blocks.size(), expected_residual_blocks.size());
   for (int i = 0; i < expected_residual_blocks.size(); ++i) {
     EXPECT_EQ(residual_blocks[i], expected_residual_blocks[i]);
   }
 }

 TEST(_, ApplyOrderingOrderingTooSmall) {
   ProblemImpl problem;
   double x;
   double y;
   double z;

   problem.AddParameterBlock(&x, 1);
   problem.AddParameterBlock(&y, 1);
   problem.AddParameterBlock(&z, 1);

   ParameterBlockOrdering linear_solver_ordering;
   linear_solver_ordering.AddElementToGroup(&x, 0);
   linear_solver_ordering.AddElementToGroup(&y, 1);

   Program program(problem.program());
   std::string message;
   EXPECT_FALSE(ApplyOrdering(
       problem.parameter_map(), linear_solver_ordering, &program, &message));
 }

 TEST(_, ApplyOrderingNormal) {
   ProblemImpl problem;
   double x;
   double y;
   double z;

   problem.AddParameterBlock(&x, 1);
   problem.AddParameterBlock(&y, 1);
   problem.AddParameterBlock(&z, 1);

   ParameterBlockOrdering linear_solver_ordering;
   linear_solver_ordering.AddElementToGroup(&x, 0);
   linear_solver_ordering.AddElementToGroup(&y, 2);
   linear_solver_ordering.AddElementToGroup(&z, 1);

   Program* program = problem.mutable_program();
   std::string message;

   EXPECT_TRUE(ApplyOrdering(
       problem.parameter_map(), linear_solver_ordering, program, &message));
   const std::vector<ParameterBlock*>& parameter_blocks =
       program->parameter_blocks();

   EXPECT_EQ(parameter_blocks.size(), 3);
   EXPECT_EQ(parameter_blocks[0]->user_state(), &x);
   EXPECT_EQ(parameter_blocks[1]->user_state(), &z);
   EXPECT_EQ(parameter_blocks[2]->user_state(), &y);
 }

 #ifndef CERES_NO_SUITESPARSE
 class ReorderProgramForSparseCholeskyUsingSuiteSparseTest
     : public ::testing::Test {
  protected:
   void SetUp() override {
     problem_.AddResidualBlock(new UnaryCostFunction(), nullptr, &x_);
     problem_.AddResidualBlock(new BinaryCostFunction(), nullptr, &z_, &x_);
     problem_.AddResidualBlock(new BinaryCostFunction(), nullptr, &z_, &y_);
     problem_.AddResidualBlock(new UnaryCostFunction(), nullptr, &z_);
     problem_.AddResidualBlock(new BinaryCostFunction(), nullptr, &x_, &y_);
     problem_.AddResidualBlock(new UnaryCostFunction(), nullptr, &y_);
   }

   void ComputeAndValidateOrdering(
       const ParameterBlockOrdering& linear_solver_ordering) {
     Program* program = problem_.mutable_program();
     std::vector<ParameterBlock*> unordered_parameter_blocks =
         program->parameter_blocks();

     std::string error;
     EXPECT_TRUE(ReorderProgramForSparseCholesky(ceres::SUITE_SPARSE,
                                                 ceres::AMD,
                                                 linear_solver_ordering,
                                                 0, /* use all rows */
                                                 program,
                                                 &error));
     const std::vector<ParameterBlock*>& ordered_parameter_blocks =
         program->parameter_blocks();
     EXPECT_EQ(ordered_parameter_blocks.size(),
               unordered_parameter_blocks.size());

     EXPECT_THAT(unordered_parameter_blocks,
                 ::testing::UnorderedElementsAreArray(ordered_parameter_blocks));
   }

   ProblemImpl problem_;
   double x_;
   double y_;
   double z_;
 };

 TEST_F(ReorderProgramForSparseCholeskyUsingSuiteSparseTest,
        EverythingInGroupZero) {
   ParameterBlockOrdering linear_solver_ordering;
   linear_solver_ordering.AddElementToGroup(&x_, 0);
   linear_solver_ordering.AddElementToGroup(&y_, 0);
   linear_solver_ordering.AddElementToGroup(&z_, 0);

   ComputeAndValidateOrdering(linear_solver_ordering);
 }

 TEST_F(ReorderProgramForSparseCholeskyUsingSuiteSparseTest, ContiguousGroups) {
   ParameterBlockOrdering linear_solver_ordering;
   linear_solver_ordering.AddElementToGroup(&x_, 0);
   linear_solver_ordering.AddElementToGroup(&y_, 1);
   linear_solver_ordering.AddElementToGroup(&z_, 2);

   ComputeAndValidateOrdering(linear_solver_ordering);
 }

 TEST_F(ReorderProgramForSparseCholeskyUsingSuiteSparseTest, GroupsWithGaps) {
   ParameterBlockOrdering linear_solver_ordering;
   linear_solver_ordering.AddElementToGroup(&x_, 0);
   linear_solver_ordering.AddElementToGroup(&y_, 2);
   linear_solver_ordering.AddElementToGroup(&z_, 2);

   ComputeAndValidateOrdering(linear_solver_ordering);
 }

 TEST_F(ReorderProgramForSparseCholeskyUsingSuiteSparseTest,
        NonContiguousStartingAtTwo) {
   ParameterBlockOrdering linear_solver_ordering;
   linear_solver_ordering.AddElementToGroup(&x_, 2);
   linear_solver_ordering.AddElementToGroup(&y_, 4);
   linear_solver_ordering.AddElementToGroup(&z_, 4);

   ComputeAndValidateOrdering(linear_solver_ordering);
 }
 #endif  // CERES_NO_SUITESPARSE

 TEST(_, ReorderResidualBlocksbyPartition) {
   ProblemImpl problem;
   double x;
   double y;
   double z;

   problem.AddParameterBlock(&x, 1);
   problem.AddParameterBlock(&y, 1);
   problem.AddParameterBlock(&z, 1);

   problem.AddResidualBlock(new UnaryCostFunction(), nullptr, &x);
   problem.AddResidualBlock(new BinaryCostFunction(), nullptr, &z, &x);
   problem.AddResidualBlock(new BinaryCostFunction(), nullptr, &z, &y);
   problem.AddResidualBlock(new UnaryCostFunction(), nullptr, &z);
   problem.AddResidualBlock(new BinaryCostFunction(), nullptr, &x, &y);
   problem.AddResidualBlock(new UnaryCostFunction(), nullptr, &y);

   std::vector<ResidualBlockId> residual_block_ids;
   problem.GetResidualBlocks(&residual_block_ids);
   std::vector<ResidualBlock*> residual_blocks =
       problem.program().residual_blocks();
   auto rng = std::mt19937{};
   for (int i = 1; i < 6; ++i) {
     std::shuffle(
         std::begin(residual_block_ids), std::end(residual_block_ids), rng);
     std::unordered_set<ResidualBlockId> bottom(residual_block_ids.begin(),
                                                residual_block_ids.begin() + i);
     const int start_bottom =
         ReorderResidualBlocksByPartition(bottom, problem.mutable_program());
     std::vector<ResidualBlock*> actual_residual_blocks =
         problem.program().residual_blocks();
     EXPECT_THAT(actual_residual_blocks,
                 testing::UnorderedElementsAreArray(residual_blocks));
     EXPECT_EQ(start_bottom, residual_blocks.size() - i);
     for (int j = start_bottom; j < residual_blocks.size(); ++j) {
       EXPECT_THAT(bottom, ::testing::Contains(actual_residual_blocks[j]));
     }
   }
 }

 }  // namespace internal
 }  // namespace ceres
	// Ceres Solver - A fast non-linear least squares minimizer
	// Copyright 2023 Google Inc. All rights reserved.
	// http://ceres-solver.org/
	//
	// Redistribution and use in source and binary forms, with or without
	// modification, are permitted provided that the following conditions are met:
	//
	// * Redistributions of source code must retain the above copyright notice,
	// this list of conditions and the following disclaimer.
	// * Redistributions in binary form must reproduce the above copyright notice,
	// this list of conditions and the following disclaimer in the documentation
	// and/or other materials provided with the distribution.
	// * Neither the name of Google Inc. nor the names of its contributors may be
	// used to endorse or promote products derived from this software without
	// specific prior written permission.
	//
	// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
	// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
	// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
	// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
	// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
	// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
	// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
	// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
	// POSSIBILITY OF SUCH DAMAGE.
	//
	// Author: sameeragarwal@google.com (Sameer Agarwal)

	#include "ceres/reorder_program.h"

	#include <random>
	#include <vector>

	#include "ceres/internal/config.h"
	#include "ceres/parameter_block.h"
	#include "ceres/problem_impl.h"
	#include "ceres/program.h"
	#include "ceres/sized_cost_function.h"
	#include "ceres/solver.h"
	#include "gmock/gmock.h"
	#include "gtest/gtest.h"

	namespace ceres {
	namespace internal {

	// Templated base class for the CostFunction signatures.
	template <int kNumResiduals, int... Ns>
	class MockCostFunctionBase : public SizedCostFunction<kNumResiduals, Ns...> {
	public:
	bool Evaluate(double const* const* parameters,
	double* residuals,
	double** jacobians) const final {
	// Do nothing. This is never called.
	return true;
	}
	};

	class UnaryCostFunction : public MockCostFunctionBase<2, 1> {};
	class BinaryCostFunction : public MockCostFunctionBase<2, 1, 1> {};
	class TernaryCostFunction : public MockCostFunctionBase<2, 1, 1, 1> {};

	TEST(_, ReorderResidualBlockNormalFunction) {
	ProblemImpl problem;
	double x;
	double y;
	double z;

	problem.AddParameterBlock(&x, 1);
	problem.AddParameterBlock(&y, 1);
	problem.AddParameterBlock(&z, 1);

	problem.AddResidualBlock(new UnaryCostFunction(), nullptr, &x);
	problem.AddResidualBlock(new BinaryCostFunction(), nullptr, &z, &x);
	problem.AddResidualBlock(new BinaryCostFunction(), nullptr, &z, &y);
	problem.AddResidualBlock(new UnaryCostFunction(), nullptr, &z);
	problem.AddResidualBlock(new BinaryCostFunction(), nullptr, &x, &y);
	problem.AddResidualBlock(new UnaryCostFunction(), nullptr, &y);

	auto linear_solver_ordering = std::make_shared<ParameterBlockOrdering>();
	linear_solver_ordering->AddElementToGroup(&x, 0);
	linear_solver_ordering->AddElementToGroup(&y, 0);
	linear_solver_ordering->AddElementToGroup(&z, 1);

	Solver::Options options;
	options.linear_solver_type = DENSE_SCHUR;
	options.linear_solver_ordering = linear_solver_ordering;

	const std::vector<ResidualBlock*>& residual_blocks =
	problem.program().residual_blocks();

	std::vector<ResidualBlock*> expected_residual_blocks;

	// This is a bit fragile, but it serves the purpose. We know the
	// bucketing algorithm that the reordering function uses, so we
	// expect the order for residual blocks for each e_block to be
	// filled in reverse.
	expected_residual_blocks.push_back(residual_blocks[4]);
	expected_residual_blocks.push_back(residual_blocks[1]);
	expected_residual_blocks.push_back(residual_blocks[0]);
	expected_residual_blocks.push_back(residual_blocks[5]);
	expected_residual_blocks.push_back(residual_blocks[2]);
	expected_residual_blocks.push_back(residual_blocks[3]);

	Program* program = problem.mutable_program();
	program->SetParameterOffsetsAndIndex();

	std::string message;
	EXPECT_TRUE(LexicographicallyOrderResidualBlocks(
	2, problem.mutable_program(), &message));
	EXPECT_EQ(residual_blocks.size(), expected_residual_blocks.size());
	for (int i = 0; i < expected_residual_blocks.size(); ++i) {
	EXPECT_EQ(residual_blocks[i], expected_residual_blocks[i]);
	}
	}

	TEST(_, ApplyOrderingOrderingTooSmall) {
	ProblemImpl problem;
	double x;
	double y;
	double z;

	problem.AddParameterBlock(&x, 1);
	problem.AddParameterBlock(&y, 1);
	problem.AddParameterBlock(&z, 1);

	ParameterBlockOrdering linear_solver_ordering;
	linear_solver_ordering.AddElementToGroup(&x, 0);
	linear_solver_ordering.AddElementToGroup(&y, 1);

	Program program(problem.program());
	std::string message;
	EXPECT_FALSE(ApplyOrdering(
	problem.parameter_map(), linear_solver_ordering, &program, &message));
	}

	TEST(_, ApplyOrderingNormal) {
	ProblemImpl problem;
	double x;
	double y;
	double z;

	problem.AddParameterBlock(&x, 1);
	problem.AddParameterBlock(&y, 1);
	problem.AddParameterBlock(&z, 1);

	ParameterBlockOrdering linear_solver_ordering;
	linear_solver_ordering.AddElementToGroup(&x, 0);
	linear_solver_ordering.AddElementToGroup(&y, 2);
	linear_solver_ordering.AddElementToGroup(&z, 1);

	Program* program = problem.mutable_program();
	std::string message;

	EXPECT_TRUE(ApplyOrdering(
	problem.parameter_map(), linear_solver_ordering, program, &message));
	const std::vector<ParameterBlock*>& parameter_blocks =
	program->parameter_blocks();

	EXPECT_EQ(parameter_blocks.size(), 3);
	EXPECT_EQ(parameter_blocks[0]->user_state(), &x);
	EXPECT_EQ(parameter_blocks[1]->user_state(), &z);
	EXPECT_EQ(parameter_blocks[2]->user_state(), &y);
	}

	#ifndef CERES_NO_SUITESPARSE
	class ReorderProgramForSparseCholeskyUsingSuiteSparseTest
	: public ::testing::Test {
	protected:
	void SetUp() override {
	problem_.AddResidualBlock(new UnaryCostFunction(), nullptr, &x_);
	problem_.AddResidualBlock(new BinaryCostFunction(), nullptr, &z_, &x_);
	problem_.AddResidualBlock(new BinaryCostFunction(), nullptr, &z_, &y_);
	problem_.AddResidualBlock(new UnaryCostFunction(), nullptr, &z_);
	problem_.AddResidualBlock(new BinaryCostFunction(), nullptr, &x_, &y_);
	problem_.AddResidualBlock(new UnaryCostFunction(), nullptr, &y_);
	}

	void ComputeAndValidateOrdering(
	const ParameterBlockOrdering& linear_solver_ordering) {
	Program* program = problem_.mutable_program();
	std::vector<ParameterBlock*> unordered_parameter_blocks =
	program->parameter_blocks();

	std::string error;
	EXPECT_TRUE(ReorderProgramForSparseCholesky(ceres::SUITE_SPARSE,
	ceres::AMD,
	linear_solver_ordering,
	0, /* use all rows */
	program,
	&error));
	const std::vector<ParameterBlock*>& ordered_parameter_blocks =
	program->parameter_blocks();
	EXPECT_EQ(ordered_parameter_blocks.size(),
	unordered_parameter_blocks.size());

	EXPECT_THAT(unordered_parameter_blocks,
	::testing::UnorderedElementsAreArray(ordered_parameter_blocks));
	}

	ProblemImpl problem_;
	double x_;
	double y_;
	double z_;
	};

	TEST_F(ReorderProgramForSparseCholeskyUsingSuiteSparseTest,
	EverythingInGroupZero) {
	ParameterBlockOrdering linear_solver_ordering;
	linear_solver_ordering.AddElementToGroup(&x_, 0);
	linear_solver_ordering.AddElementToGroup(&y_, 0);
	linear_solver_ordering.AddElementToGroup(&z_, 0);

	ComputeAndValidateOrdering(linear_solver_ordering);
	}

	TEST_F(ReorderProgramForSparseCholeskyUsingSuiteSparseTest, ContiguousGroups) {
	ParameterBlockOrdering linear_solver_ordering;
	linear_solver_ordering.AddElementToGroup(&x_, 0);
	linear_solver_ordering.AddElementToGroup(&y_, 1);
	linear_solver_ordering.AddElementToGroup(&z_, 2);

	ComputeAndValidateOrdering(linear_solver_ordering);
	}

	TEST_F(ReorderProgramForSparseCholeskyUsingSuiteSparseTest, GroupsWithGaps) {
	ParameterBlockOrdering linear_solver_ordering;
	linear_solver_ordering.AddElementToGroup(&x_, 0);
	linear_solver_ordering.AddElementToGroup(&y_, 2);
	linear_solver_ordering.AddElementToGroup(&z_, 2);

	ComputeAndValidateOrdering(linear_solver_ordering);
	}

	TEST_F(ReorderProgramForSparseCholeskyUsingSuiteSparseTest,
	NonContiguousStartingAtTwo) {
	ParameterBlockOrdering linear_solver_ordering;
	linear_solver_ordering.AddElementToGroup(&x_, 2);
	linear_solver_ordering.AddElementToGroup(&y_, 4);
	linear_solver_ordering.AddElementToGroup(&z_, 4);

	ComputeAndValidateOrdering(linear_solver_ordering);
	}
	#endif // CERES_NO_SUITESPARSE

	TEST(_, ReorderResidualBlocksbyPartition) {
	ProblemImpl problem;
	double x;
	double y;
	double z;

	problem.AddParameterBlock(&x, 1);
	problem.AddParameterBlock(&y, 1);
	problem.AddParameterBlock(&z, 1);

	problem.AddResidualBlock(new UnaryCostFunction(), nullptr, &x);
	problem.AddResidualBlock(new BinaryCostFunction(), nullptr, &z, &x);
	problem.AddResidualBlock(new BinaryCostFunction(), nullptr, &z, &y);
	problem.AddResidualBlock(new UnaryCostFunction(), nullptr, &z);
	problem.AddResidualBlock(new BinaryCostFunction(), nullptr, &x, &y);
	problem.AddResidualBlock(new UnaryCostFunction(), nullptr, &y);

	std::vector<ResidualBlockId> residual_block_ids;
	problem.GetResidualBlocks(&residual_block_ids);
	std::vector<ResidualBlock*> residual_blocks =
	problem.program().residual_blocks();
	auto rng = std::mt19937{};
	for (int i = 1; i < 6; ++i) {
	std::shuffle(
	std::begin(residual_block_ids), std::end(residual_block_ids), rng);
	std::unordered_set<ResidualBlockId> bottom(residual_block_ids.begin(),
	residual_block_ids.begin() + i);
	const int start_bottom =
	ReorderResidualBlocksByPartition(bottom, problem.mutable_program());
	std::vector<ResidualBlock*> actual_residual_blocks =
	problem.program().residual_blocks();
	EXPECT_THAT(actual_residual_blocks,
	testing::UnorderedElementsAreArray(residual_blocks));
	EXPECT_EQ(start_bottom, residual_blocks.size() - i);
	for (int j = start_bottom; j < residual_blocks.size(); ++j) {
	EXPECT_THAT(bottom, ::testing::Contains(actual_residual_blocks[j]));
	}
	}
	}

	} // namespace internal
	} // namespace ceres