Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #include "cartographer/mapping/internal/connected_components.h"
00018
00019 #include <algorithm>
00020 #include <memory>
00021 #include <vector>
00022
00023 #include "gtest/gtest.h"
00024
00025 namespace cartographer {
00026 namespace mapping {
00027 namespace {
00028
00029 constexpr int kNumTrajectories = 10;
00030
00031 TEST(ConnectedComponentsTest, TransitivelyConnected) {
00032 ConnectedComponents connected_components;
00033
00034
00035 for (int trajectory_a = 0; trajectory_a < kNumTrajectories; ++trajectory_a) {
00036 for (int trajectory_b = 0; trajectory_b < kNumTrajectories;
00037 ++trajectory_b) {
00038 EXPECT_EQ(trajectory_a == trajectory_b,
00039 connected_components.TransitivelyConnected(trajectory_a,
00040 trajectory_b));
00041 }
00042 }
00043
00044
00045 connected_components.Connect(0, 1);
00046 EXPECT_TRUE(connected_components.TransitivelyConnected(0, 1));
00047 connected_components.Connect(8, 9);
00048 EXPECT_TRUE(connected_components.TransitivelyConnected(8, 9));
00049 EXPECT_FALSE(connected_components.TransitivelyConnected(0, 9));
00050
00051 connected_components.Connect(1, 8);
00052 for (int i : {0, 1}) {
00053 for (int j : {8, 9}) {
00054 EXPECT_TRUE(connected_components.TransitivelyConnected(i, j));
00055 }
00056 }
00057 }
00058
00059 TEST(ConnectedComponentsTest, EmptyConnectedComponents) {
00060 ConnectedComponents connected_components;
00061 auto connections = connected_components.Components();
00062 EXPECT_EQ(0, connections.size());
00063 }
00064
00065 TEST(ConnectedComponentsTest, ConnectedComponents) {
00066 ConnectedComponents connected_components;
00067 for (int i = 0; i <= 4; ++i) {
00068 connected_components.Connect(0, i);
00069 }
00070 for (int i = 5; i <= 9; ++i) {
00071 connected_components.Connect(5, i);
00072 }
00073 auto connections = connected_components.Components();
00074 ASSERT_EQ(2, connections.size());
00075
00076 const std::vector<int>* zero_cluster = nullptr;
00077 const std::vector<int>* five_cluster = nullptr;
00078 if (std::find(connections[0].begin(), connections[0].end(), 0) !=
00079 connections[0].end()) {
00080 zero_cluster = &connections[0];
00081 five_cluster = &connections[1];
00082 } else {
00083 zero_cluster = &connections[1];
00084 five_cluster = &connections[0];
00085 }
00086 for (int i = 0; i <= 9; ++i) {
00087 EXPECT_EQ(i <= 4, std::find(zero_cluster->begin(), zero_cluster->end(),
00088 i) != zero_cluster->end());
00089 EXPECT_EQ(i > 4, std::find(five_cluster->begin(), five_cluster->end(), i) !=
00090 five_cluster->end());
00091 }
00092 }
00093
00094 TEST(ConnectedComponentsTest, ConnectionCount) {
00095 ConnectedComponents connected_components;
00096 for (int i = 0; i < kNumTrajectories; ++i) {
00097 connected_components.Connect(0, 1);
00098
00099 EXPECT_EQ(i + 1, connected_components.ConnectionCount(1, 0));
00100 }
00101 for (int i = 1; i < 9; ++i) {
00102 EXPECT_EQ(0, connected_components.ConnectionCount(i, i + 1));
00103 }
00104 }
00105
00106 TEST(ConnectedComponentsTest, ReflexiveConnectivity) {
00107 ConnectedComponents connected_components;
00108 EXPECT_TRUE(connected_components.TransitivelyConnected(0, 0));
00109 EXPECT_EQ(0, connected_components.ConnectionCount(0, 0));
00110 connected_components.Add(0);
00111 EXPECT_TRUE(connected_components.TransitivelyConnected(0, 0));
00112 EXPECT_EQ(0, connected_components.ConnectionCount(0, 0));
00113 }
00114
00115 }
00116 }
00117 }