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" 1037b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/ADT/GraphLite/Digraph.h" 1137b74a387bb3993387029859c2d9d051c41c724eStephen 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. 1837b74a387bb3993387029859c2d9d051c41c724eStephen HinesGraphTest::GraphTest() { 1987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 2087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 2187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines// Destructor can do clean-up work that doesn't throw exceptions here. 2237b74a387bb3993387029859c2d9d051c41c724eStephen HinesGraphTest::~GraphTest() { 2387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 2487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 2587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines// SetUp() will be called immediately before each test. 2637b74a387bb3993387029859c2d9d051c41c724eStephen Hinesvoid GraphTest::SetUp() { 2787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 2887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 2987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines// TearDown() will be called immediately after each test. 3037b74a387bb3993387029859c2d9d051c41c724eStephen Hinesvoid GraphTest::TearDown() { 3187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 3287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 3387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines//===----------------------------------------------------------------------===// 3487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines// Testcases 3587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines//===----------------------------------------------------------------------===// 3637b74a387bb3993387029859c2d9d051c41c724eStephen HinesTEST_F(GraphTest, list_digraph_add_n_erase_nodes_1) { 3787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph graph; 3887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 3987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u1 = graph.addNode(); 4087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u2 = graph.addNode(); 4187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u3 = graph.addNode(); 4287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 4387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u1->first_in); 4487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u1->first_out); 4537b74a387bb3993387029859c2d9d051c41c724eStephen Hines ASSERT_TRUE(u2 == u1->prev); 4687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u1->next); 4787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 4887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u2->first_in); 4987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u2->first_out); 5037b74a387bb3993387029859c2d9d051c41c724eStephen Hines ASSERT_TRUE(u3 == u2->prev); 5137b74a387bb3993387029859c2d9d051c41c724eStephen Hines ASSERT_TRUE(u1 == u2->next); 5287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 5387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u3->first_in); 5487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u3->first_out); 5537b74a387bb3993387029859c2d9d051c41c724eStephen Hines ASSERT_TRUE(u2 == u3->next); 5687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u3->prev); 5787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 5887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* head = NULL; 5987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines graph.getHead(head); 6087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(head == u3); 6187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 6287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines graph.erase(*u2); 6387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 6487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u1->first_in); 6587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u1->first_out); 6637b74a387bb3993387029859c2d9d051c41c724eStephen Hines ASSERT_TRUE(u3 == u1->prev); 6787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u1->next); 6887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 6987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u3->first_in); 7087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u3->first_out); 7137b74a387bb3993387029859c2d9d051c41c724eStephen Hines ASSERT_TRUE(u1 == u3->next); 7287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u3->prev); 7387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 7487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u2->first_in); 7587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u2->first_out); 7687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u2->prev); 7787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u2->next); 7887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 7987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines graph.getHead(head); 8087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(head == u3); 8187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 8287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 8337b74a387bb3993387029859c2d9d051c41c724eStephen HinesTEST_F(GraphTest, list_digraph_add_n_erase_nodes_2) { 8487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph graph; 8587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 8687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u1 = graph.addNode(); 8787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u2 = graph.addNode(); 8887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u3 = graph.addNode(); 8987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 9087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u1->first_in); 9187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u1->first_out); 9237b74a387bb3993387029859c2d9d051c41c724eStephen Hines ASSERT_TRUE(u2 == u1->prev); 9387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u1->next); 9487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 9587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u2->first_in); 9687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u2->first_out); 9737b74a387bb3993387029859c2d9d051c41c724eStephen Hines ASSERT_TRUE(u3 == u2->prev); 9837b74a387bb3993387029859c2d9d051c41c724eStephen Hines ASSERT_TRUE(u1 == u2->next); 9987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 10087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u3->first_in); 10187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u3->first_out); 10237b74a387bb3993387029859c2d9d051c41c724eStephen Hines ASSERT_TRUE(u2 == u3->next); 10387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u3->prev); 10487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 10587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* head = NULL; 10687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines graph.getHead(head); 10787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(head == u3); 10887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 10987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines graph.erase(*u1); 11087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 11187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u1->first_in); 11287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u1->first_out); 11387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u1->prev); 11487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u1->next); 11587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 11687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u2->first_in); 11787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u2->first_out); 11837b74a387bb3993387029859c2d9d051c41c724eStephen Hines ASSERT_TRUE(u3 == u2->prev); 11987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u2->next); 12087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 12187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u3->first_in); 12287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u3->first_out); 12337b74a387bb3993387029859c2d9d051c41c724eStephen Hines ASSERT_TRUE(u2 == u3->next); 12487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u3->prev); 12587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 12687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines graph.getHead(head); 12787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(head == u3); 12887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 12987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 13037b74a387bb3993387029859c2d9d051c41c724eStephen HinesTEST_F(GraphTest, list_digraph_add_n_erase_nodes_3) { 13187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph graph; 13287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 13387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u1 = graph.addNode(); 13487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u2 = graph.addNode(); 13587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u3 = graph.addNode(); 13687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 13787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u1->first_in); 13887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u1->first_out); 13937b74a387bb3993387029859c2d9d051c41c724eStephen Hines ASSERT_TRUE(u2 == u1->prev); 14087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u1->next); 14187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 14287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u2->first_in); 14387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u2->first_out); 14437b74a387bb3993387029859c2d9d051c41c724eStephen Hines ASSERT_TRUE(u3 == u2->prev); 14537b74a387bb3993387029859c2d9d051c41c724eStephen Hines ASSERT_TRUE(u1 == u2->next); 14687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 14787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u3->first_in); 14887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u3->first_out); 14937b74a387bb3993387029859c2d9d051c41c724eStephen Hines ASSERT_TRUE(u2 == u3->next); 15087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u3->prev); 15187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 15287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* head = NULL; 15387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines graph.getHead(head); 15487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(head == u3); 15587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 15687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines graph.erase(*u3); 15787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 15887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u3->first_in); 15987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u3->first_out); 16087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u3->prev); 16187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u3->next); 16287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 16387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u1->first_in); 16487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u1->first_out); 16537b74a387bb3993387029859c2d9d051c41c724eStephen Hines ASSERT_TRUE(u2 == u1->prev); 16687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u1->next); 16787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 16887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u2->first_in); 16987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u2->first_out); 17037b74a387bb3993387029859c2d9d051c41c724eStephen Hines ASSERT_TRUE(u1 == u2->next); 17187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == u2->prev); 17287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 17387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines graph.getHead(head); 17487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(head == u2); 17587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 17687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 17737b74a387bb3993387029859c2d9d051c41c724eStephen HinesTEST_F(GraphTest, list_digraph_add_arcs_1) { 17887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph graph; 17987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 18087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u1 = graph.addNode(); 18187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u2 = graph.addNode(); 18287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u3 = graph.addNode(); 18387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 18487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Arc* a1 = graph.addArc(*u1, *u2); 18587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Arc* a2 = graph.addArc(*u2, *u3); 18687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Arc* a3 = graph.addArc(*u3, *u1); 18787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 18887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u1 == a1->source && u2 == a1->target); 18987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u2 == a2->source && u3 == a2->target); 19087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u3 == a3->source && u1 == a3->target); 19187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 19287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u1->first_in == a3 && u1->first_out == a1); 19387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u2->first_in == a1 && u2->first_out == a2); 19487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u3->first_in == a2 && u3->first_out == a3); 19587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 19687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 19737b74a387bb3993387029859c2d9d051c41c724eStephen HinesTEST_F(GraphTest, list_digraph_add_arcs_2) { 19887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph graph; 19987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 20087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u1 = graph.addNode(); 20187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u2 = graph.addNode(); 20287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u3 = graph.addNode(); 20387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 20487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Arc* a1 = graph.addArc(*u1, *u1); 20587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Arc* a2 = graph.addArc(*u1, *u2); 20687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Arc* a3 = graph.addArc(*u1, *u3); 20787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 20887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u1 == a1->source && u1 == a1->target); 20987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u1 == a2->source && u2 == a2->target); 21087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u1 == a3->source && u3 == a3->target); 21187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 21287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u1->first_in == a1 && u1->first_out == a3); 21387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u2->first_in == a2 && u2->first_out == NULL); 21487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u3->first_in == a3 && u3->first_out == NULL); 21587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 21687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 21737b74a387bb3993387029859c2d9d051c41c724eStephen HinesTEST_F(GraphTest, list_digraph_add_n_erase_arcs_1) { 21887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph graph; 21987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 22087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u1 = graph.addNode(); 22187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u2 = graph.addNode(); 22287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u3 = graph.addNode(); 22387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 22487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Arc* a1 = graph.addArc(*u1, *u2); 22587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Arc* a2 = graph.addArc(*u2, *u3); 22687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Arc* a3 = graph.addArc(*u3, *u1); 22787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 22887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines graph.erase(*a2); 229551ae4ebd3e9d137ea668fb83ae4a55b8cfba451Stephen Hines 23087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u1 == a1->source && u2 == a1->target); 23187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u3 == a3->source && u1 == a3->target); 23287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 23387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // remove from the fan-out list 23487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u2->first_in == a1 && u2->first_out == NULL); 23587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 23687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // remove from the fan-in list 23787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u3->first_in == NULL && u3->first_out == a3); 23887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 23987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // put into free list 24087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == a2->next_in); 24187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 24287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 24337b74a387bb3993387029859c2d9d051c41c724eStephen HinesTEST_F(GraphTest, list_digraph_add_n_erase_arcs_2) { 24487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph graph; 24587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 24687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u1 = graph.addNode(); 24787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u2 = graph.addNode(); 24887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u3 = graph.addNode(); 24987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 25087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Arc* a1 = graph.addArc(*u1, *u2); 25187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Arc* a2 = graph.addArc(*u2, *u3); 25287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Arc* a3 = graph.addArc(*u3, *u1); 25387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 25487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines graph.erase(*a1); 255551ae4ebd3e9d137ea668fb83ae4a55b8cfba451Stephen Hines 25687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u2 == a2->source && u3 == a2->target); 25787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u3 == a3->source && u1 == a3->target); 25887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 25987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // remove from the fan-out list 26087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u1->first_in == a3 && u1->first_out == NULL); 26187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 26287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // remove from the fan-in list 26387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u2->first_in == NULL && u2->first_out == a2); 26487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 26587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // put into free list 26687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == a1->next_in); 26787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 26887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 26937b74a387bb3993387029859c2d9d051c41c724eStephen HinesTEST_F(GraphTest, list_digraph_add_n_erase_arcs_3) { 27087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph graph; 27187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 27287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u1 = graph.addNode(); 27387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u2 = graph.addNode(); 27487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u3 = graph.addNode(); 27587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 27687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Arc* a1 = graph.addArc(*u1, *u2); 27787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Arc* a2 = graph.addArc(*u2, *u3); 27887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Arc* a3 = graph.addArc(*u3, *u1); 27987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 28087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines graph.erase(*a3); 281551ae4ebd3e9d137ea668fb83ae4a55b8cfba451Stephen Hines 28287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u1 == a1->source && u2 == a1->target); 28387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u2 == a2->source && u3 == a2->target); 28487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 28587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // remove from the fan-out list 28687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u1->first_in == NULL && u1->first_out == a1); 28787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 28887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // remove from the fan-in list 28987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u3->first_in == a2 && u3->first_out == NULL); 29087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 29187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines // put into free list 29287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(NULL == a3->next_in); 29387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 29487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 29537b74a387bb3993387029859c2d9d051c41c724eStephen HinesTEST_F(GraphTest, list_digraph_add_n_erase_arcs_4) { 29687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph graph; 29787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 29887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u1 = graph.addNode(); 29987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u2 = graph.addNode(); 30087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Node* u3 = graph.addNode(); 30187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 30287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ListDigraph::Arc* a1 = graph.addArc(*u1, *u1); 30387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines graph.addArc(*u1, *u2); 30487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines graph.addArc(*u1, *u3); 30587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 30687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines graph.erase(*u1); 30787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 30887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u2->first_in == NULL); 30987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(u3->first_in == NULL); 31087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_TRUE(a1->next_in == NULL); 31187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 31287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 31337b74a387bb3993387029859c2d9d051c41c724eStephen HinesTEST_F(GraphTest, api_test) { 31487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines Digraph graph; 31587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 31687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines Digraph::Node node = graph.addNode(); 31787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines graph.addNode(); 31887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines graph.addNode(); 31987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines graph.addNode(); 32087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 32187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_EQ(4, graph.numOfNodes()); 32287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines ASSERT_EQ(0, graph.numOfArcs()); 32387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 324