Fix the struct weak ordering used by independent set ordering, tests for it
diff --git a/internal/ceres/graph_algorithms.h b/internal/ceres/graph_algorithms.h
index cb9913a..e83531d 100644
--- a/internal/ceres/graph_algorithms.h
+++ b/internal/ceres/graph_algorithms.h
@@ -50,7 +50,7 @@
bool operator()(const Vertex& lhs, const Vertex& rhs) const {
if (graph_.Neighbors(lhs).size() == graph_.Neighbors(rhs).size()) {
- return lhs->user_state() < rhs->user_state();
+ return (lhs < rhs);
}
return (graph_.Neighbors(lhs).size() < graph_.Neighbors(rhs).size());
}
diff --git a/internal/ceres/graph_algorithms_test.cc b/internal/ceres/graph_algorithms_test.cc
index bce0183..a67d7b7 100644
--- a/internal/ceres/graph_algorithms_test.cc
+++ b/internal/ceres/graph_algorithms_test.cc
@@ -165,5 +165,29 @@
}
}
+TEST(VertexDegreeLessThan, TotalOrdering) {
+ Graph<int> graph;
+ graph.AddVertex(0);
+ graph.AddVertex(1);
+ graph.AddVertex(2);
+ graph.AddVertex(3);
+
+ // 0-1 2-3
+ // All vertices have degree 1.
+ graph.AddEdge(0, 1, 1.0);
+ graph.AddEdge(2, 3, 1.0);
+ VertexDegreeLessThan<int> less_than(graph);
+
+ for (int i = 0; i < 4; ++i) {
+ EXPECT_FALSE(less_than(i,i))
+ << "Failing vertex: " << i;
+ for (int j = 0; j < 4; ++j) {
+ if (i != j) {
+ EXPECT_TRUE(less_than(i,j) ^ less_than(j,i))
+ << "Failing vertex pair: " << i << " " << j;
+ }
+ }
+ }
+}
} // namespace internal
} // namespace ceres
