[GitHub] incubator-quickstep pull request #233: QUICKSTEP-88 Topological sort functio...

```Github user hakanmemisoglu commented on a diff in the pull request:

https://github.com/apache/incubator-quickstep/pull/233#discussion_r112285916

--- Diff: utility/tests/DAG_unittest.cpp ---
}

+TEST(DAGTest, TopoSortTest) {
+  const int kNodeSize = 5;
+
+  for (int node_index = 0; node_index < kNodeSize; ++node_index) {
+    ASSERT_EQ(static_cast<std::size_t>(node_index),
+  }
+
+  /*
+   *    0
+   *   / \
+   *  v   v
+   *  1   2
+   *   \ /
+   *    v
+   *    3
+   *    |
+   *    v
+   *    4
+   *
+   */
+
+
+      dag_.getTopologicalSorting();
node_exists;
+  // First check if the ordering is a legal sequence of nodes, i.e. every
node
+  // appears exactly once.
+  for (auto node_id = 0u; node_id < dag_.size(); ++node_id) {
+    node_exists[node_id] = false;
+  }
+  for (auto i : sorted_list) {
+    node_exists[i] = true;
+  }
+  for (auto node_id = 0u; node_id < dag_.size(); ++node_id) {
+    ASSERT_TRUE(node_exists[node_id]);
+  }
+  // We apply the following condition for verifying if we have obtained a
valid
+  // topological sorting.
+  // If there is an edge i->j between two nodes i and j, then i comes
before j
+  // in the topologically sorted order.
+  // We use a map to store the position of a given node in the sorted
order.
+  // Key = node ID, value = position of the node in the sorted order.
+  std::unordered_map<std::size_t, std::size_t> position_in_sorted_order;
+  for (std::size_t i = 0; i < sorted_list.size(); ++i) {
+    position_in_sorted_order[sorted_list[i]] = i;
+  }
+  std::vector<std::tuple<std::size_t, std::size_t>> edges;
+  // Populate the list of edges.
+  edges.emplace_back(0, 1);
+  edges.emplace_back(0, 2);
+  edges.emplace_back(1, 3);
+  edges.emplace_back(2, 3);
+  edges.emplace_back(3, 4);
+  for (auto curr_edge : edges) {
--- End diff --

```