187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines//===- GraphTest.cpp ------------------------------------------------------===// 287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines// 387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines// The MCLinker Project 487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines// 587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines// This file is distributed under the University of Illinois Open Source 687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines// License. See LICENSE.TXT for details. 787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines// 887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines//===----------------------------------------------------------------------===// 987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#include "GraphTest.h" 1087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#include <mcld/ADT/GraphLite/Digraph.h> 1187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#include <mcld/ADT/GraphLite/ListDigraph.h> 1287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 1387f34658dec9097d987d254a990ea7f311bfc95fStephen Hinesusing namespace mcld; 1487f34658dec9097d987d254a990ea7f311bfc95fStephen Hinesusing namespace mcld::test; 1587f34658dec9097d987d254a990ea7f311bfc95fStephen Hinesusing namespace mcld::graph; 1687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 1787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines// Constructor can do set-up work for all test here. 1887f34658dec9097d987d254a990ea7f311bfc95fStephen HinesGraphTest::GraphTest() 1987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines{ 2087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 2187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 2287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines// Destructor can do clean-up work that doesn't throw exceptions here. 2387f34658dec9097d987d254a990ea7f311bfc95fStephen HinesGraphTest::~GraphTest() 2487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines{ 2587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 2687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 2787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines// SetUp() will be called immediately before each test. 2887f34658dec9097d987d254a990ea7f311bfc95fStephen Hinesvoid GraphTest::SetUp() 2987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines{ 3087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 3187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 3287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines// TearDown() will be called immediately after each test. 3387f34658dec9097d987d254a990ea7f311bfc95fStephen Hinesvoid GraphTest::TearDown() 3487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines{ 3587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 3687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 3787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines//===----------------------------------------------------------------------===// 3887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines// Testcases 3987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines//===----------------------------------------------------------------------===// 4087f34658dec9097d987d254a990ea7f311bfc95fStephen HinesTEST_F(GraphTest, list_digraph_add_n_erase_nodes_1) 4187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines{ 4287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph graph; 4387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 4487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u1 = graph.addNode(); 4587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u2 = graph.addNode(); 4687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u3 = graph.addNode(); 4787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 4887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u1->first_in); 4987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u1->first_out); 5087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u2 == u1->prev); 5187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u1->next); 5287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 5387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u2->first_in); 5487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u2->first_out); 5587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u3 == u2->prev); 5687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u1 == u2->next); 5787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 5887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u3->first_in); 5987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u3->first_out); 6087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u2 == u3->next); 6187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u3->prev); 6287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 6387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* head = NULL; 6487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines graph.getHead(head); 6587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(head == u3); 6687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 6787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines graph.erase(*u2); 6887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 6987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u1->first_in); 7087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u1->first_out); 7187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u3 == u1->prev); 7287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u1->next); 7387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 7487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u3->first_in); 7587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u3->first_out); 7687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u1 == u3->next); 7787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u3->prev); 7887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 7987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u2->first_in); 8087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u2->first_out); 8187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u2->prev); 8287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u2->next); 8387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 8487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines graph.getHead(head); 8587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(head == u3); 8687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 8787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 8887f34658dec9097d987d254a990ea7f311bfc95fStephen HinesTEST_F(GraphTest, list_digraph_add_n_erase_nodes_2) 8987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines{ 9087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph graph; 9187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 9287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u1 = graph.addNode(); 9387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u2 = graph.addNode(); 9487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u3 = graph.addNode(); 9587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 9687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u1->first_in); 9787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u1->first_out); 9887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u2 == u1->prev); 9987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u1->next); 10087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 10187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u2->first_in); 10287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u2->first_out); 10387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u3 == u2->prev); 10487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u1 == u2->next); 10587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 10687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u3->first_in); 10787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u3->first_out); 10887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u2 == u3->next); 10987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u3->prev); 11087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 11187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* head = NULL; 11287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines graph.getHead(head); 11387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(head == u3); 11487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 11587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines graph.erase(*u1); 11687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 11787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u1->first_in); 11887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u1->first_out); 11987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u1->prev); 12087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u1->next); 12187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 12287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u2->first_in); 12387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u2->first_out); 12487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u3 == u2->prev); 12587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u2->next); 12687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 12787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u3->first_in); 12887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u3->first_out); 12987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u2 == u3->next); 13087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u3->prev); 13187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 13287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines graph.getHead(head); 13387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(head == u3); 13487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 13587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 13687f34658dec9097d987d254a990ea7f311bfc95fStephen HinesTEST_F(GraphTest, list_digraph_add_n_erase_nodes_3) 13787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines{ 13887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph graph; 13987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 14087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u1 = graph.addNode(); 14187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u2 = graph.addNode(); 14287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u3 = graph.addNode(); 14387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 14487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u1->first_in); 14587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u1->first_out); 14687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u2 == u1->prev); 14787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u1->next); 14887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 14987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u2->first_in); 15087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u2->first_out); 15187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u3 == u2->prev); 15287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u1 == u2->next); 15387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 15487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u3->first_in); 15587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u3->first_out); 15687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u2 == u3->next); 15787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u3->prev); 15887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 15987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* head = NULL; 16087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines graph.getHead(head); 16187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(head == u3); 16287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 16387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines graph.erase(*u3); 16487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 16587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u3->first_in); 16687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u3->first_out); 16787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u3->prev); 16887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u3->next); 16987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 17087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u1->first_in); 17187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u1->first_out); 17287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u2 == u1->prev); 17387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u1->next); 17487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 17587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u2->first_in); 17687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u2->first_out); 17787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u1 == u2->next); 17887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u2->prev); 17987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 18087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines graph.getHead(head); 18187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(head == u2); 18287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 18387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 18487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 18587f34658dec9097d987d254a990ea7f311bfc95fStephen HinesTEST_F(GraphTest, list_digraph_add_arcs_1) 18687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines{ 18787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph graph; 18887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 18987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u1 = graph.addNode(); 19087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u2 = graph.addNode(); 19187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u3 = graph.addNode(); 19287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 19387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Arc* a1 = graph.addArc(*u1, *u2); 19487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Arc* a2 = graph.addArc(*u2, *u3); 19587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Arc* a3 = graph.addArc(*u3, *u1); 19687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 19787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u1 == a1->source && u2 == a1->target); 19887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u2 == a2->source && u3 == a2->target); 19987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u3 == a3->source && u1 == a3->target); 20087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 20187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u1->first_in == a3 && u1->first_out == a1); 20287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u2->first_in == a1 && u2->first_out == a2); 20387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u3->first_in == a2 && u3->first_out == a3); 20487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 20587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 20687f34658dec9097d987d254a990ea7f311bfc95fStephen HinesTEST_F(GraphTest, list_digraph_add_arcs_2) 20787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines{ 20887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph graph; 20987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 21087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u1 = graph.addNode(); 21187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u2 = graph.addNode(); 21287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u3 = graph.addNode(); 21387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 21487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Arc* a1 = graph.addArc(*u1, *u1); 21587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Arc* a2 = graph.addArc(*u1, *u2); 21687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Arc* a3 = graph.addArc(*u1, *u3); 21787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 21887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u1 == a1->source && u1 == a1->target); 21987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u1 == a2->source && u2 == a2->target); 22087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u1 == a3->source && u3 == a3->target); 22187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 22287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u1->first_in == a1 && u1->first_out == a3); 22387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u2->first_in == a2 && u2->first_out == NULL); 22487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u3->first_in == a3 && u3->first_out == NULL); 22587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 22687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 22787f34658dec9097d987d254a990ea7f311bfc95fStephen HinesTEST_F(GraphTest, list_digraph_add_n_erase_arcs_1) 22887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines{ 22987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph graph; 23087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 23187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u1 = graph.addNode(); 23287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u2 = graph.addNode(); 23387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u3 = graph.addNode(); 23487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 23587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Arc* a1 = graph.addArc(*u1, *u2); 23687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Arc* a2 = graph.addArc(*u2, *u3); 23787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Arc* a3 = graph.addArc(*u3, *u1); 23887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 23987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines graph.erase(*a2); 240551ae4ebd3e9d137ea668fb83ae4a55b8cfba451Stephen Hines 24187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u1 == a1->source && u2 == a1->target); 24287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u3 == a3->source && u1 == a3->target); 24387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 24487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // remove from the fan-out list 24587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u2->first_in == a1 && u2->first_out == NULL); 24687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 24787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // remove from the fan-in list 24887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u3->first_in == NULL && u3->first_out == a3); 24987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 25087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // put into free list 25187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == a2->next_in); 25287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 25387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 25487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 25587f34658dec9097d987d254a990ea7f311bfc95fStephen HinesTEST_F(GraphTest, list_digraph_add_n_erase_arcs_2) 25687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines{ 25787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph graph; 25887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 25987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u1 = graph.addNode(); 26087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u2 = graph.addNode(); 26187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u3 = graph.addNode(); 26287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 26387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Arc* a1 = graph.addArc(*u1, *u2); 26487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Arc* a2 = graph.addArc(*u2, *u3); 26587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Arc* a3 = graph.addArc(*u3, *u1); 26687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 26787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines graph.erase(*a1); 268551ae4ebd3e9d137ea668fb83ae4a55b8cfba451Stephen Hines 26987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u2 == a2->source && u3 == a2->target); 27087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u3 == a3->source && u1 == a3->target); 27187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 27287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // remove from the fan-out list 27387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u1->first_in == a3 && u1->first_out == NULL); 27487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 27587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // remove from the fan-in list 27687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u2->first_in == NULL && u2->first_out == a2); 27787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 27887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // put into free list 27987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == a1->next_in); 28087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 28187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 28287f34658dec9097d987d254a990ea7f311bfc95fStephen HinesTEST_F(GraphTest, list_digraph_add_n_erase_arcs_3) 28387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines{ 28487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph graph; 28587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 28687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u1 = graph.addNode(); 28787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u2 = graph.addNode(); 28887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u3 = graph.addNode(); 28987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 29087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Arc* a1 = graph.addArc(*u1, *u2); 29187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Arc* a2 = graph.addArc(*u2, *u3); 29287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Arc* a3 = graph.addArc(*u3, *u1); 29387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 29487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines graph.erase(*a3); 295551ae4ebd3e9d137ea668fb83ae4a55b8cfba451Stephen Hines 29687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u1 == a1->source && u2 == a1->target); 29787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u2 == a2->source && u3 == a2->target); 29887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 29987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // remove from the fan-out list 30087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u1->first_in == NULL && u1->first_out == a1); 30187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 30287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // remove from the fan-in list 30387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u3->first_in == a2 && u3->first_out == NULL); 30487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 30587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // put into free list 30687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == a3->next_in); 30787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 30887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 30987f34658dec9097d987d254a990ea7f311bfc95fStephen HinesTEST_F(GraphTest, list_digraph_add_n_erase_arcs_4) 31087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines{ 31187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph graph; 31287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 31387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u1 = graph.addNode(); 31487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u2 = graph.addNode(); 31587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u3 = graph.addNode(); 31687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 31787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Arc* a1 = graph.addArc(*u1, *u1); 31887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines graph.addArc(*u1, *u2); 31987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines graph.addArc(*u1, *u3); 32087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 32187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines graph.erase(*u1); 32287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 32387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u2->first_in == NULL); 32487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u3->first_in == NULL); 32587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(a1->next_in == NULL); 32687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 32787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 32887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 32987f34658dec9097d987d254a990ea7f311bfc95fStephen HinesTEST_F(GraphTest, api_test) 33087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines{ 33187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines Digraph graph; 33287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 33387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines Digraph::Node node = graph.addNode(); 33487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines graph.addNode(); 33587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines graph.addNode(); 33687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines graph.addNode(); 33787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 33887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_EQ(4, graph.numOfNodes()); 33987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_EQ(0, graph.numOfArcs()); 34087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 341