00001 #include "transform_graph/graph_internal.h"
00002
00003 #include <string>
00004 #include <vector>
00005 #include <gtest/gtest.h>
00006
00007 using std::string;
00008 using std::vector;
00009
00010 namespace transform_graph {
00011 namespace internal {
00012 TEST(TestGraphInternal, EmptyGraphFails) {
00013 Graph graph;
00014 vector<string> path;
00015 bool success = graph.Path("base_link", "tool", &path);
00016 EXPECT_FALSE(graph.HasVertex("base_link"));
00017 EXPECT_FALSE(graph.HasVertex("tool"));
00018 EXPECT_FALSE(success);
00019 }
00020
00021 TEST(TestGraphInternal, SimpleCase) {
00022 Graph graph;
00023 vector<string> path;
00024 graph.AddEdge("base_link", "tool");
00025 bool success = graph.Path("base_link", "tool", &path);
00026 EXPECT_TRUE(success);
00027 ASSERT_EQ(2, path.size());
00028 EXPECT_EQ("base_link", path[0]);
00029 EXPECT_EQ("tool", path[1]);
00030 }
00031
00032 TEST(TestGraphInternal, BackwardsSimpleCase) {
00033 Graph graph;
00034 vector<string> path;
00035 graph.AddEdge("base_link", "tool");
00036 bool success = graph.Path("tool", "base_link", &path);
00037 EXPECT_TRUE(success);
00038 ASSERT_EQ(2, path.size());
00039 EXPECT_EQ("tool", path[0]);
00040 EXPECT_EQ("base_link", path[1]);
00041 }
00042
00043 TEST(TestGraphInternal, SingleNodeSelfEdge) {
00044 Graph graph;
00045 vector<string> path;
00046 graph.AddEdge("base_link", "base_link");
00047 bool success = graph.Path("base_link", "base_link", &path);
00048 EXPECT_TRUE(success);
00049 ASSERT_EQ(1, path.size());
00050 EXPECT_EQ("base_link", path[0]);
00051 }
00052
00053 TEST(TestGraphInternal, SourceTargetSame) {
00054 Graph graph;
00055 vector<string> path;
00056 graph.AddEdge("base_link", "tool");
00057 bool success = graph.Path("base_link", "base_link", &path);
00058 EXPECT_TRUE(success);
00059 ASSERT_EQ(1, path.size());
00060 EXPECT_EQ("base_link", path[0]);
00061 }
00062
00063 TEST(TestGraphInternal, LinkedList) {
00064 Graph graph;
00065 vector<string> path;
00066 graph.AddEdge("A", "B");
00067 graph.AddEdge("B", "C");
00068 graph.AddEdge("C", "D");
00069 bool success = graph.Path("B", "D", &path);
00070 EXPECT_TRUE(success);
00071 ASSERT_EQ(3, path.size());
00072 EXPECT_EQ("B", path[0]);
00073 EXPECT_EQ("C", path[1]);
00074 EXPECT_EQ("D", path[2]);
00075 }
00076
00077 TEST(TestGraphInternal, BackwardsLinkedList) {
00078 Graph graph;
00079 vector<string> path;
00080 graph.AddEdge("A", "B");
00081 graph.AddEdge("B", "C");
00082 graph.AddEdge("C", "D");
00083 bool success = graph.Path("D", "A", &path);
00084 EXPECT_TRUE(success);
00085 ASSERT_EQ(4, path.size());
00086 EXPECT_EQ("D", path[0]);
00087 EXPECT_EQ("C", path[1]);
00088 EXPECT_EQ("B", path[2]);
00089 EXPECT_EQ("A", path[3]);
00090 }
00091
00092 TEST(TestGraphInternal, DiamondBisected) {
00093 Graph graph;
00094 vector<string> path;
00095 graph.AddEdge("A", "B");
00096 graph.AddEdge("A", "C");
00097 graph.AddEdge("B", "C");
00098 graph.AddEdge("B", "D");
00099 graph.AddEdge("C", "D");
00100 bool success = graph.Path("A", "D", &path);
00101 EXPECT_TRUE(success);
00102 ASSERT_EQ(3, path.size());
00103 EXPECT_EQ("A", path[0]);
00104 EXPECT_TRUE(path[1] == "B" || path[1] == "C");
00105 EXPECT_EQ("D", path[2]);
00106 }
00107
00108 TEST(TestGraphInternal, ShortestPath) {
00109 Graph graph;
00110 vector<string> path;
00111 graph.AddEdge("A", "B");
00112 graph.AddEdge("B", "C");
00113 graph.AddEdge("C", "D");
00114 graph.AddEdge("D", "E");
00115 graph.AddEdge("E", "A");
00116 bool success = graph.Path("A", "C", &path);
00117 EXPECT_TRUE(success);
00118 ASSERT_EQ(3, path.size());
00119 EXPECT_EQ("A", path[0]);
00120 EXPECT_EQ("B", path[1]);
00121 EXPECT_EQ("C", path[2]);
00122 }
00123
00124 TEST(TestGraphInternal, ShortestPathBackwards) {
00125 Graph graph;
00126 vector<string> path;
00127 graph.AddEdge("A", "B");
00128 graph.AddEdge("B", "C");
00129 graph.AddEdge("C", "D");
00130 graph.AddEdge("D", "E");
00131 graph.AddEdge("E", "A");
00132 bool success = graph.Path("A", "D", &path);
00133 EXPECT_TRUE(success);
00134 ASSERT_EQ(3, path.size());
00135 EXPECT_EQ("A", path[0]);
00136 EXPECT_EQ("E", path[1]);
00137 EXPECT_EQ("D", path[2]);
00138 }
00139
00140 TEST(TestGraphInternal, DisconnectedFail) {
00141 Graph graph;
00142 vector<string> path;
00143 graph.AddEdge("A", "B");
00144 graph.AddEdge("C", "D");
00145 bool success = graph.Path("A", "C", &path);
00146 EXPECT_FALSE(success);
00147 }
00148
00149 TEST(TestGraphInternal, DisconnectedSuccess) {
00150 Graph graph;
00151 vector<string> path;
00152 graph.AddEdge("A", "B");
00153 graph.AddEdge("C", "D");
00154 bool success = graph.Path("A", "B", &path);
00155 EXPECT_TRUE(success);
00156 ASSERT_EQ(2, path.size());
00157 EXPECT_EQ("A", path[0]);
00158 EXPECT_EQ("B", path[1]);
00159 }
00160
00161 TEST(TestGraphInternal, MiddleSelfLoop) {
00162 Graph graph;
00163 vector<string> path;
00164 graph.AddEdge("A", "B");
00165 graph.AddEdge("B", "B");
00166 graph.AddEdge("B", "C");
00167 bool success = graph.Path("C", "A", &path);
00168 EXPECT_TRUE(success);
00169 ASSERT_EQ(3, path.size());
00170 EXPECT_EQ("C", path[0]);
00171 EXPECT_EQ("B", path[1]);
00172 EXPECT_EQ("A", path[2]);
00173 }
00174 }
00175 }
00176
00177 int main(int argc, char **argv) {
00178 testing::InitGoogleTest(&argc, argv);
00179 return RUN_ALL_TESTS();
00180 }