transaction/tests/DirectedGraph_unittest.cpp

/**
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 **/

#include "transaction/DirectedGraph.hpp"

#include <vector>

#include "transaction/Transaction.hpp"

#include "gtest/gtest.h"

namespace quickstep {
namespace transaction {

class DirectedGraphTest : public ::testing::Test {
 protected:
  DirectedGraphTest()
      : tid3_(3),
        tid4_(4),
        tid5_(5),
        tid6_(6) {
  }

  DirectedGraph wait_for_graph_;
  transaction_id tid3_;
  transaction_id tid4_;
  transaction_id tid5_;
  transaction_id tid6_;
};

TEST_F(DirectedGraphTest, AddNode) {
  // The nodes are not added yet, total no of nodesshould be zero.
  EXPECT_EQ(0u, wait_for_graph_.getNumNodes());

  wait_for_graph_.addNodeUnchecked(tid3_);

  // One node is added.
  EXPECT_EQ(1u, wait_for_graph_.getNumNodes());

  wait_for_graph_.addNodeUnchecked(tid4_);

  // Another node is added.
  EXPECT_EQ(2u, wait_for_graph_.getNumNodes());

  wait_for_graph_.addNodeUnchecked(tid5_);
  wait_for_graph_.addNodeUnchecked(tid6_);

  // Total no of nodes should be 4 right now.
  EXPECT_EQ(4u, wait_for_graph_.getNumNodes());
}

TEST_F(DirectedGraphTest, AddEdge) {
  DirectedGraph::node_id nid3 = wait_for_graph_.addNodeUnchecked(tid3_);
  DirectedGraph::node_id nid6 = wait_for_graph_.addNodeUnchecked(tid6_);
  DirectedGraph::node_id nid4 = wait_for_graph_.addNodeUnchecked(tid4_);
  DirectedGraph::node_id nid5 = wait_for_graph_.addNodeUnchecked(tid5_);

  // Add edges.
  wait_for_graph_.addEdgeUnchecked(nid3, nid5);
  wait_for_graph_.addEdgeUnchecked(nid6, nid4);
  wait_for_graph_.addEdgeUnchecked(nid3, nid6);
  wait_for_graph_.addEdgeUnchecked(nid4, nid6);

  // Check whether the edges are already there.
  EXPECT_TRUE(wait_for_graph_.hasEdge(nid3, nid5));
  EXPECT_TRUE(wait_for_graph_.hasEdge(nid6, nid4));
  EXPECT_TRUE(wait_for_graph_.hasEdge(nid4, nid6));
  EXPECT_TRUE(wait_for_graph_.hasEdge(nid3, nid6));

  // Check non-existent edges.
  EXPECT_FALSE(wait_for_graph_.hasEdge(nid5, nid3));
  EXPECT_FALSE(wait_for_graph_.hasEdge(nid6, nid3));
  EXPECT_FALSE(wait_for_graph_.hasEdge(nid4, nid5));
}

TEST_F(DirectedGraphTest, GetAdjacentNodes) {
  // Add 4 disconnected nodes to the graph.
  DirectedGraph::node_id nid3 = wait_for_graph_.addNodeUnchecked(tid3_);
  DirectedGraph::node_id nid6 = wait_for_graph_.addNodeUnchecked(tid6_);
  DirectedGraph::node_id nid4 = wait_for_graph_.addNodeUnchecked(tid4_);
  DirectedGraph::node_id nid5 = wait_for_graph_.addNodeUnchecked(tid5_);

  std::vector<DirectedGraph::node_id> result1 = wait_for_graph_.getAdjacentNodes(nid3);
  // nid3 has no edge to other nodes.
  EXPECT_EQ(0u, result1.size());

  // Now nid3 has outgoing edge to nid4 and nid5.
  wait_for_graph_.addEdgeUnchecked(nid3, nid4);
  wait_for_graph_.addEdgeUnchecked(nid3, nid5);

  std::vector<DirectedGraph::node_id> result2 = wait_for_graph_.getAdjacentNodes(nid3);
  // Therefore, number of outgoing edges from nid3 is 2.
  EXPECT_EQ(2u, result2.size());

  // Add an edge from nid3 to nid6.
  wait_for_graph_.addEdgeUnchecked(nid3, nid6);
  std::vector<DirectedGraph::node_id> result3 = wait_for_graph_.getAdjacentNodes(nid3);

  // Now there are 3 outgoing edges.
  EXPECT_EQ(3u, result3.size());

  // Again add edge from nid3 to nid6.
  wait_for_graph_.addEdgeUnchecked(nid3, nid6);
  std::vector<DirectedGraph::node_id> result4 = wait_for_graph_.getAdjacentNodes(nid3);
  // Since we have already add same edge before, number of edges are still 3.
  EXPECT_EQ(3u, result4.size());
}

}  // namespace transaction
}  // namespace quickstep