From 7115f60b91b5717d90f643fd692010905c7004db Mon Sep 17 00:00:00 2001 From: Bryan Galdrikian Date: Thu, 31 May 2018 11:36:08 -0700 Subject: Blast 1.1.3. See docs/release_notes.txt. --- test/src/unit/FamilyGraphTests.cpp | 810 ++++++++++++++++++------------------- 1 file changed, 405 insertions(+), 405 deletions(-) mode change 100644 => 100755 test/src/unit/FamilyGraphTests.cpp (limited to 'test/src/unit/FamilyGraphTests.cpp') diff --git a/test/src/unit/FamilyGraphTests.cpp b/test/src/unit/FamilyGraphTests.cpp old mode 100644 new mode 100755 index d0a872d..bfbea01 --- a/test/src/unit/FamilyGraphTests.cpp +++ b/test/src/unit/FamilyGraphTests.cpp @@ -1,405 +1,405 @@ -// This code contains NVIDIA Confidential Information and is disclosed to you -// under a form of NVIDIA software license agreement provided separately to you. -// -// Notice -// NVIDIA Corporation and its licensors retain all intellectual property and -// proprietary rights in and to this software and related documentation and -// any modifications thereto. Any use, reproduction, disclosure, or -// distribution of this software and related documentation without an express -// license agreement from NVIDIA Corporation is strictly prohibited. -// -// ALL NVIDIA DESIGN SPECIFICATIONS, CODE ARE PROVIDED "AS IS.". NVIDIA MAKES -// NO WARRANTIES, EXPRESSED, IMPLIED, STATUTORY, OR OTHERWISE WITH RESPECT TO -// THE MATERIALS, AND EXPRESSLY DISCLAIMS ALL IMPLIED WARRANTIES OF NONINFRINGEMENT, -// MERCHANTABILITY, AND FITNESS FOR A PARTICULAR PURPOSE. -// -// Information and code furnished is believed to be accurate and reliable. -// However, NVIDIA Corporation assumes no responsibility for the consequences of use of such -// information or for any infringement of patents or other rights of third parties that may -// result from its use. No license is granted by implication or otherwise under any patent -// or patent rights of NVIDIA Corporation. Details are subject to change without notice. -// This code supersedes and replaces all information previously supplied. -// NVIDIA Corporation products are not authorized for use as critical -// components in life support devices or systems without express written approval of -// NVIDIA Corporation. -// -// Copyright (c) 2016-2018 NVIDIA Corporation. All rights reserved. - - -#include "BlastBaseTest.h" - -#include "NvBlastSupportGraph.h" -#include "NvBlastFamilyGraph.h" -#include "NvBlastAssert.h" -#include "NvBlastIndexFns.h" - -#include -#include -#include -#include -#include - - -// ==================================================================================================================== -// HELPERS -// ==================================================================================================================== - -::testing::AssertionResult VectorMatch(const std::vector& actual, const uint32_t* expected, uint32_t size) -{ - for (size_t i(0); i < size; ++i) - { - if (expected[i] != actual[i]) - { - testing::Message msg; - msg << "array[" << i - << "] (" << actual[i] << ") != expected[" << i - << "] (" << expected[i] << ")"; - return (::testing::AssertionFailure(msg));; - } - } - - return ::testing::AssertionSuccess(); -} - -#define VECTOR_MATCH(actual, ...) \ -{ \ - const uint32_t arr[] = { __VA_ARGS__ }; \ - const uint32_t size = (sizeof(arr) / sizeof(arr[0])); \ - EXPECT_EQ(size, actual.size()); \ - EXPECT_TRUE(VectorMatch(actual, arr, size)); \ -} - - -// ==================================================================================================================== -// TEST CLASS -// ==================================================================================================================== - -using namespace Nv::Blast; - -template -class FamilyGraphTest : public BlastBaseTest < FailLevel, Verbosity > -{ -public: - FamilyGraphTest() - { - } - -protected: - FamilyGraph* buildFamilyGraph(uint32_t chunkCount, const uint32_t* adjacentChunkPartition, const uint32_t* adjacentChunkIndices) - { - NVBLAST_ASSERT(m_memoryBlock.size() == 0); // can't build twice per test - - // Fill SupportGraph with data: - NvBlastCreateOffsetStart(sizeof(SupportGraph)); - const size_t NvBlastCreateOffsetAlign16(chunkIndicesOffset, chunkCount*sizeof(uint32_t)); - const size_t NvBlastCreateOffsetAlign16(adjacencyPartitionOffset, (chunkCount + 1)*sizeof(uint32_t)); - const size_t NvBlastCreateOffsetAlign16(adjacentNodeIndicesOffset, adjacentChunkPartition[chunkCount] * sizeof(uint32_t)); - const size_t NvBlastCreateOffsetAlign16(adjacentBondIndicesOffset, adjacentChunkPartition[chunkCount] * sizeof(uint32_t)); - const size_t graphDataSize = NvBlastCreateOffsetEndAlign16(); - m_graphMemory.resize(graphDataSize); - m_graph = reinterpret_cast(m_graphMemory.data()); - - m_graph->m_nodeCount = chunkCount; - m_graph->m_chunkIndicesOffset = static_cast(chunkIndicesOffset); - m_graph->m_adjacencyPartitionOffset = static_cast(adjacencyPartitionOffset); - m_graph->m_adjacentNodeIndicesOffset = static_cast(adjacentNodeIndicesOffset); - m_graph->m_adjacentBondIndicesOffset = static_cast(adjacentBondIndicesOffset); - - memcpy(m_graph->getAdjacencyPartition(), adjacentChunkPartition, (chunkCount + 1) * sizeof(uint32_t)); - memcpy(m_graph->getAdjacentNodeIndices(), adjacentChunkIndices, adjacentChunkPartition[chunkCount] * sizeof(uint32_t)); - - // fill bondIndices by incrementing bondIndex and putting same bondIndex in mirror bond index for (n0, n1) == (n1, n0) - memset(m_graph->getAdjacentBondIndices(), (uint32_t)-1, adjacentChunkPartition[chunkCount] * sizeof(uint32_t)); - uint32_t bondIndex = 0; - for (uint32_t chunk0 = 0; chunk0 < m_graph->m_nodeCount; chunk0++) - { - for (uint32_t i = m_graph->getAdjacencyPartition()[chunk0]; i < m_graph->getAdjacencyPartition()[chunk0 + 1]; i++) - { - if (m_graph->getAdjacentBondIndices()[i] == (uint32_t)-1) - { - m_graph->getAdjacentBondIndices()[i] = bondIndex; - - uint32_t chunk1 = m_graph->getAdjacentNodeIndices()[i]; - for (uint32_t j = m_graph->getAdjacencyPartition()[chunk1]; j < m_graph->getAdjacencyPartition()[chunk1 + 1]; j++) - { - if (m_graph->getAdjacentNodeIndices()[j] == chunk0) - { - m_graph->getAdjacentBondIndices()[j] = bondIndex; - } - } - bondIndex++; - } - } - } - - // reserve memory for family graph and asset pointer - uint32_t familyGraphMemorySize = (uint32_t)FamilyGraph::requiredMemorySize(m_graph->m_nodeCount, bondIndex); - m_memoryBlock.resize(familyGraphMemorySize); - // placement new family graph - FamilyGraph* familyGraph = new(m_memoryBlock.data()) FamilyGraph(m_graph); - - return familyGraph; - } - - struct IslandInfo - { - std::vector nodes; - }; - - /** - Function to gather islands info for tests and debug purposes - Returned islands sorted by nodes counts. Island nodes also sorted by NodeIndex. - */ - void getIslandsInfo(const FamilyGraph& graph, std::vector& info) - { - IslandId* islandIds = graph.getIslandIds(); - - std::map islandMap; - - for (NodeIndex n = 0; n < m_graph->m_nodeCount; n++) - { - EXPECT_TRUE(islandIds[n] != invalidIndex()); - IslandId islandId = islandIds[n]; - if (islandMap.find(islandId) == islandMap.end()) - { - IslandInfo info; - info.nodes.push_back(n); - islandMap[islandId] = info; - } - else - { - islandMap[islandId].nodes.push_back(n); - } - } - - for (auto it = islandMap.begin(); it != islandMap.end(); ++it) - { - std::sort(it->second.nodes.begin(), it->second.nodes.end()); - info.push_back(it->second); - } - - // sort islands by size ascending - std::sort(info.begin(), info.end(), [](const IslandInfo& i0, const IslandInfo& i1) -> bool - { - size_t s0 = i0.nodes.size(); - size_t s1 = i1.nodes.size(); - if (s0 == s1 && s0 > 0) - { - s0 = i0.nodes[0]; - s1 = i1.nodes[0]; - } - return s0 < s1; - }); - } - - static const uint32_t DEFAULT_ACTOR_INDEX = 0; - - SupportGraph* m_graph; - std::vector m_graphMemory; - std::vector m_memoryBlock; -}; - -typedef FamilyGraphTest FamilyGraphTestAllowWarnings; -typedef FamilyGraphTest FamilyGraphTestStrict; - - -// ==================================================================================================================== -// GRAPH DATA -// ==================================================================================================================== - -// Graph 0: -// -// 0 -- 1 -- 2 -- 3 -// | | | | -// | | | | -// 4 -- 5 6 -- 7 -// -const uint32_t chunkCount0 = 8; -const uint32_t adjacentChunkPartition0[] = { 0, 2, 5, 8, 10, 12, 14, 16, 18 }; -const uint32_t adjacentChunkIndices0[] = { /*0*/ 1, 4, /*1*/ 0, 2, 5, /*2*/ 1, 3, 6, /*3*/ 2, 7, /*4*/ 0, 5, /*5*/ 1, 4, /*6*/ 2, 7, /*7*/ 3, 6 }; - - -// Graph 1: -// -// 0 -- 1 -- 2 -- 3 -// | | | | -// 4 -- 5 -- 6 -- 7 -// | | | | -// 8 -- 9 -- 10-- 11 -// -const uint32_t chunkCount1 = 12; -const uint32_t adjacentChunkPartition1[] = { 0, 2, 5, 8, 10, 13, 17, 21, 24, 26, 29, 32, 34 }; -const uint32_t adjacentChunkIndices1[] = { /*0*/ 1, 4, /*1*/ 0, 2, 5, /*2*/ 1, 3, 6, /*3*/ 2, 7, /*4*/ 0, 5, 8, /*5*/ 1, 4, 6, 9, /*6*/ 2, 5, 7, 10, - /*7*/ 3, 6, 11, /*8*/ 4, 9, /*9*/ 5, 8, 10, /*10*/ 6, 9, 11, /*11*/ 7, 10 }; - - -// ==================================================================================================================== -// TESTS -// ==================================================================================================================== - -TEST_F(FamilyGraphTestStrict, Graph0FindIslands0) -{ - FamilyGraph* graph = buildFamilyGraph(chunkCount0, adjacentChunkPartition0, adjacentChunkIndices0); - graph->initialize(DEFAULT_ACTOR_INDEX, m_graph); - - std::vector scratch; - scratch.resize((size_t)FamilyGraph::findIslandsRequiredScratch(chunkCount0)); - - EXPECT_EQ(9, graph->getEdgesCount(m_graph)); - graph->notifyEdgeRemoved(DEFAULT_ACTOR_INDEX, 0, 4, m_graph); - EXPECT_EQ(8, graph->getEdgesCount(m_graph)); - EXPECT_EQ(1, graph->findIslands(DEFAULT_ACTOR_INDEX, scratch.data(), m_graph)); - - graph->notifyEdgeRemoved(DEFAULT_ACTOR_INDEX, 1, 2, m_graph); - EXPECT_EQ(1, graph->findIslands(DEFAULT_ACTOR_INDEX, scratch.data(), m_graph)); - - std::vector info; - getIslandsInfo(*graph, info); - EXPECT_EQ(2, info.size()); - VECTOR_MATCH(info[0].nodes, 0, 1, 4, 5); - VECTOR_MATCH(info[1].nodes, 2, 3, 6, 7); -} - -TEST_F(FamilyGraphTestStrict, Graph0FindIslands1) -{ - FamilyGraph* graph = buildFamilyGraph(chunkCount0, adjacentChunkPartition0, adjacentChunkIndices0); - graph->initialize(DEFAULT_ACTOR_INDEX, m_graph); - - std::vector scratch; - scratch.resize((size_t)FamilyGraph::findIslandsRequiredScratch(chunkCount0)); - - graph->notifyEdgeRemoved(DEFAULT_ACTOR_INDEX, 0, 4, m_graph); - graph->notifyEdgeRemoved(DEFAULT_ACTOR_INDEX, 4, 5, m_graph); - graph->notifyEdgeRemoved(DEFAULT_ACTOR_INDEX, 1, 2, m_graph); - EXPECT_EQ(6, graph->getEdgesCount(m_graph)); - EXPECT_EQ(3, graph->findIslands(DEFAULT_ACTOR_INDEX, scratch.data(), m_graph)); - - std::vector info; - getIslandsInfo(*graph, info); - EXPECT_EQ(3, info.size()); - VECTOR_MATCH(info[0].nodes, 4); - VECTOR_MATCH(info[1].nodes, 0, 1, 5); - VECTOR_MATCH(info[2].nodes, 2, 3, 6, 7); -} - -TEST_F(FamilyGraphTestStrict, Graph0FindIslandsDifferentActors) -{ - const uint32_t ACTOR_0_INDEX = 5; - const uint32_t ACTOR_1_INDEX = 2; - - FamilyGraph* graph = buildFamilyGraph(chunkCount0, adjacentChunkPartition0, adjacentChunkIndices0); - graph->initialize(ACTOR_0_INDEX, m_graph); - - std::vector scratch; - scratch.resize((size_t)FamilyGraph::findIslandsRequiredScratch(chunkCount0)); - - EXPECT_EQ(0, graph->findIslands(ACTOR_1_INDEX, scratch.data(), m_graph)); - EXPECT_EQ(1, graph->findIslands(ACTOR_0_INDEX, scratch.data(), m_graph)); - - graph->notifyEdgeRemoved(ACTOR_0_INDEX, 2, 1, m_graph); - EXPECT_EQ(8, graph->getEdgesCount(m_graph)); - - EXPECT_EQ(1, graph->findIslands(ACTOR_0_INDEX, scratch.data(), m_graph)); - - graph->notifyEdgeRemoved(ACTOR_1_INDEX, 2, 6, m_graph); - graph->notifyEdgeRemoved(ACTOR_1_INDEX, 7, 3, m_graph); - EXPECT_EQ(1, graph->findIslands(ACTOR_1_INDEX, scratch.data(), m_graph)); - - graph->notifyEdgeRemoved(ACTOR_0_INDEX, 0, 1, m_graph); - graph->notifyEdgeRemoved(ACTOR_0_INDEX, 4, 5, m_graph); - EXPECT_EQ(1, graph->findIslands(ACTOR_0_INDEX, scratch.data(), m_graph)); - - - std::vector info; - getIslandsInfo(*graph, info); - EXPECT_EQ(4, info.size()); - VECTOR_MATCH(info[0].nodes, 0, 4); - VECTOR_MATCH(info[1].nodes, 1, 5); - VECTOR_MATCH(info[2].nodes, 2, 3); - VECTOR_MATCH(info[3].nodes, 6, 7); -} - -TEST_F(FamilyGraphTestStrict, Graph1FindIslands0) -{ - FamilyGraph* graph = buildFamilyGraph(chunkCount1, adjacentChunkPartition1, adjacentChunkIndices1); - graph->initialize(DEFAULT_ACTOR_INDEX, m_graph); - - std::vector scratch; - scratch.resize((size_t)FamilyGraph::findIslandsRequiredScratch(chunkCount1)); - - graph->notifyEdgeRemoved(DEFAULT_ACTOR_INDEX, 0, 4, m_graph); - graph->notifyEdgeRemoved(DEFAULT_ACTOR_INDEX, 1, 5, m_graph); - graph->notifyEdgeRemoved(DEFAULT_ACTOR_INDEX, 2, 6, m_graph); - graph->notifyEdgeRemoved(DEFAULT_ACTOR_INDEX, 3, 7, m_graph); - graph->notifyEdgeRemoved(DEFAULT_ACTOR_INDEX, 5, 6, m_graph); - graph->notifyEdgeRemoved(DEFAULT_ACTOR_INDEX, 9, 10, m_graph); - EXPECT_EQ(11, graph->getEdgesCount(m_graph)); - EXPECT_EQ(3, graph->findIslands(DEFAULT_ACTOR_INDEX, scratch.data(), m_graph)); - - std::vector info; - getIslandsInfo(*graph, info); - EXPECT_EQ(3, info.size()); - - VECTOR_MATCH(info[0].nodes, 0, 1, 2, 3); - VECTOR_MATCH(info[1].nodes, 4, 5, 8, 9); - VECTOR_MATCH(info[2].nodes, 6, 7, 10, 11); -} - -TEST_F(FamilyGraphTestStrict, Graph1FindIslands1) -{ - FamilyGraph* graph = buildFamilyGraph(chunkCount1, adjacentChunkPartition1, adjacentChunkIndices1); - graph->initialize(DEFAULT_ACTOR_INDEX, m_graph); - - std::vector scratch; - scratch.resize((size_t)FamilyGraph::findIslandsRequiredScratch(chunkCount1)); - - graph->notifyEdgeRemoved(DEFAULT_ACTOR_INDEX, 0, 4, m_graph); - EXPECT_EQ(1, graph->findIslands(DEFAULT_ACTOR_INDEX, scratch.data(), m_graph)); - graph->notifyEdgeRemoved(DEFAULT_ACTOR_INDEX, 1, 5, m_graph); - EXPECT_EQ(0, graph->findIslands(DEFAULT_ACTOR_INDEX, scratch.data(), m_graph)); - graph->notifyEdgeRemoved(DEFAULT_ACTOR_INDEX, 2, 6, m_graph); - EXPECT_EQ(0, graph->findIslands(DEFAULT_ACTOR_INDEX, scratch.data(), m_graph)); - graph->notifyEdgeRemoved(DEFAULT_ACTOR_INDEX, 3, 7, m_graph); - EXPECT_EQ(1, graph->findIslands(DEFAULT_ACTOR_INDEX, scratch.data(), m_graph)); - graph->notifyEdgeRemoved(DEFAULT_ACTOR_INDEX, 5, 6, m_graph); - EXPECT_EQ(0, graph->findIslands(DEFAULT_ACTOR_INDEX, scratch.data(), m_graph)); - graph->notifyEdgeRemoved(DEFAULT_ACTOR_INDEX, 9, 10, m_graph); - EXPECT_EQ(1, graph->findIslands(DEFAULT_ACTOR_INDEX, scratch.data(), m_graph)); - - std::vector info; - getIslandsInfo(*graph, info); - EXPECT_EQ(3, info.size()); - VECTOR_MATCH(info[0].nodes, 0, 1, 2, 3); - VECTOR_MATCH(info[1].nodes, 4, 5, 8, 9); - VECTOR_MATCH(info[2].nodes, 6, 7, 10, 11); -} - -TEST_F(FamilyGraphTestStrict, Graph1FindIslandsRemoveAllEdges) -{ - FamilyGraph* graph = buildFamilyGraph(chunkCount1, adjacentChunkPartition1, adjacentChunkIndices1); - graph->initialize(DEFAULT_ACTOR_INDEX, m_graph); - - std::vector scratch; - scratch.resize((size_t)FamilyGraph::findIslandsRequiredScratch(chunkCount1)); - - uint32_t edges = graph->getEdgesCount(m_graph); - for (uint32_t node0 = 0; node0 < chunkCount1; node0++) - { - for (uint32_t i = adjacentChunkPartition1[node0]; i < adjacentChunkPartition1[node0 + 1]; i++) - { - if (graph->notifyEdgeRemoved(DEFAULT_ACTOR_INDEX, node0, adjacentChunkIndices1[i], m_graph)) - { - edges--; - EXPECT_EQ(edges, graph->getEdgesCount(m_graph)); - } - } - } - EXPECT_EQ(0, graph->getEdgesCount(m_graph)); - - EXPECT_EQ(12, graph->findIslands(DEFAULT_ACTOR_INDEX, scratch.data(), m_graph)); - - for (uint32_t node0 = 0; node0 < chunkCount1; node0++) - { - EXPECT_EQ(node0, graph->getIslandIds()[node0]); - } -} +// This code contains NVIDIA Confidential Information and is disclosed to you +// under a form of NVIDIA software license agreement provided separately to you. +// +// Notice +// NVIDIA Corporation and its licensors retain all intellectual property and +// proprietary rights in and to this software and related documentation and +// any modifications thereto. Any use, reproduction, disclosure, or +// distribution of this software and related documentation without an express +// license agreement from NVIDIA Corporation is strictly prohibited. +// +// ALL NVIDIA DESIGN SPECIFICATIONS, CODE ARE PROVIDED "AS IS.". NVIDIA MAKES +// NO WARRANTIES, EXPRESSED, IMPLIED, STATUTORY, OR OTHERWISE WITH RESPECT TO +// THE MATERIALS, AND EXPRESSLY DISCLAIMS ALL IMPLIED WARRANTIES OF NONINFRINGEMENT, +// MERCHANTABILITY, AND FITNESS FOR A PARTICULAR PURPOSE. +// +// Information and code furnished is believed to be accurate and reliable. +// However, NVIDIA Corporation assumes no responsibility for the consequences of use of such +// information or for any infringement of patents or other rights of third parties that may +// result from its use. No license is granted by implication or otherwise under any patent +// or patent rights of NVIDIA Corporation. Details are subject to change without notice. +// This code supersedes and replaces all information previously supplied. +// NVIDIA Corporation products are not authorized for use as critical +// components in life support devices or systems without express written approval of +// NVIDIA Corporation. +// +// Copyright (c) 2016-2018 NVIDIA Corporation. All rights reserved. + + +#include "BlastBaseTest.h" + +#include "NvBlastSupportGraph.h" +#include "NvBlastFamilyGraph.h" +#include "NvBlastAssert.h" +#include "NvBlastIndexFns.h" + +#include +#include +#include +#include +#include + + +// ==================================================================================================================== +// HELPERS +// ==================================================================================================================== + +::testing::AssertionResult VectorMatch(const std::vector& actual, const uint32_t* expected, uint32_t size) +{ + for (size_t i(0); i < size; ++i) + { + if (expected[i] != actual[i]) + { + testing::Message msg; + msg << "array[" << i + << "] (" << actual[i] << ") != expected[" << i + << "] (" << expected[i] << ")"; + return (::testing::AssertionFailure(msg));; + } + } + + return ::testing::AssertionSuccess(); +} + +#define VECTOR_MATCH(actual, ...) \ +{ \ + const uint32_t arr[] = { __VA_ARGS__ }; \ + const uint32_t size = (sizeof(arr) / sizeof(arr[0])); \ + EXPECT_EQ(size, actual.size()); \ + EXPECT_TRUE(VectorMatch(actual, arr, size)); \ +} + + +// ==================================================================================================================== +// TEST CLASS +// ==================================================================================================================== + +using namespace Nv::Blast; + +template +class FamilyGraphTest : public BlastBaseTest < FailLevel, Verbosity > +{ +public: + FamilyGraphTest() + { + } + +protected: + FamilyGraph* buildFamilyGraph(uint32_t chunkCount, const uint32_t* adjacentChunkPartition, const uint32_t* adjacentChunkIndices) + { + NVBLAST_ASSERT(m_memoryBlock.size() == 0); // can't build twice per test + + // Fill SupportGraph with data: + NvBlastCreateOffsetStart(sizeof(SupportGraph)); + const size_t NvBlastCreateOffsetAlign16(chunkIndicesOffset, chunkCount*sizeof(uint32_t)); + const size_t NvBlastCreateOffsetAlign16(adjacencyPartitionOffset, (chunkCount + 1)*sizeof(uint32_t)); + const size_t NvBlastCreateOffsetAlign16(adjacentNodeIndicesOffset, adjacentChunkPartition[chunkCount] * sizeof(uint32_t)); + const size_t NvBlastCreateOffsetAlign16(adjacentBondIndicesOffset, adjacentChunkPartition[chunkCount] * sizeof(uint32_t)); + const size_t graphDataSize = NvBlastCreateOffsetEndAlign16(); + m_graphMemory.resize(graphDataSize); + m_graph = reinterpret_cast(m_graphMemory.data()); + + m_graph->m_nodeCount = chunkCount; + m_graph->m_chunkIndicesOffset = static_cast(chunkIndicesOffset); + m_graph->m_adjacencyPartitionOffset = static_cast(adjacencyPartitionOffset); + m_graph->m_adjacentNodeIndicesOffset = static_cast(adjacentNodeIndicesOffset); + m_graph->m_adjacentBondIndicesOffset = static_cast(adjacentBondIndicesOffset); + + memcpy(m_graph->getAdjacencyPartition(), adjacentChunkPartition, (chunkCount + 1) * sizeof(uint32_t)); + memcpy(m_graph->getAdjacentNodeIndices(), adjacentChunkIndices, adjacentChunkPartition[chunkCount] * sizeof(uint32_t)); + + // fill bondIndices by incrementing bondIndex and putting same bondIndex in mirror bond index for (n0, n1) == (n1, n0) + memset(m_graph->getAdjacentBondIndices(), (uint32_t)-1, adjacentChunkPartition[chunkCount] * sizeof(uint32_t)); + uint32_t bondIndex = 0; + for (uint32_t chunk0 = 0; chunk0 < m_graph->m_nodeCount; chunk0++) + { + for (uint32_t i = m_graph->getAdjacencyPartition()[chunk0]; i < m_graph->getAdjacencyPartition()[chunk0 + 1]; i++) + { + if (m_graph->getAdjacentBondIndices()[i] == (uint32_t)-1) + { + m_graph->getAdjacentBondIndices()[i] = bondIndex; + + uint32_t chunk1 = m_graph->getAdjacentNodeIndices()[i]; + for (uint32_t j = m_graph->getAdjacencyPartition()[chunk1]; j < m_graph->getAdjacencyPartition()[chunk1 + 1]; j++) + { + if (m_graph->getAdjacentNodeIndices()[j] == chunk0) + { + m_graph->getAdjacentBondIndices()[j] = bondIndex; + } + } + bondIndex++; + } + } + } + + // reserve memory for family graph and asset pointer + uint32_t familyGraphMemorySize = (uint32_t)FamilyGraph::requiredMemorySize(m_graph->m_nodeCount, bondIndex); + m_memoryBlock.resize(familyGraphMemorySize); + // placement new family graph + FamilyGraph* familyGraph = new(m_memoryBlock.data()) FamilyGraph(m_graph); + + return familyGraph; + } + + struct IslandInfo + { + std::vector nodes; + }; + + /** + Function to gather islands info for tests and debug purposes + Returned islands sorted by nodes counts. Island nodes also sorted by NodeIndex. + */ + void getIslandsInfo(const FamilyGraph& graph, std::vector& info) + { + IslandId* islandIds = graph.getIslandIds(); + + std::map islandMap; + + for (NodeIndex n = 0; n < m_graph->m_nodeCount; n++) + { + EXPECT_TRUE(islandIds[n] != invalidIndex()); + IslandId islandId = islandIds[n]; + if (islandMap.find(islandId) == islandMap.end()) + { + IslandInfo info; + info.nodes.push_back(n); + islandMap[islandId] = info; + } + else + { + islandMap[islandId].nodes.push_back(n); + } + } + + for (auto it = islandMap.begin(); it != islandMap.end(); ++it) + { + std::sort(it->second.nodes.begin(), it->second.nodes.end()); + info.push_back(it->second); + } + + // sort islands by size ascending + std::sort(info.begin(), info.end(), [](const IslandInfo& i0, const IslandInfo& i1) -> bool + { + size_t s0 = i0.nodes.size(); + size_t s1 = i1.nodes.size(); + if (s0 == s1 && s0 > 0) + { + s0 = i0.nodes[0]; + s1 = i1.nodes[0]; + } + return s0 < s1; + }); + } + + static const uint32_t DEFAULT_ACTOR_INDEX = 0; + + SupportGraph* m_graph; + std::vector m_graphMemory; + std::vector m_memoryBlock; +}; + +typedef FamilyGraphTest FamilyGraphTestAllowWarnings; +typedef FamilyGraphTest FamilyGraphTestStrict; + + +// ==================================================================================================================== +// GRAPH DATA +// ==================================================================================================================== + +// Graph 0: +// +// 0 -- 1 -- 2 -- 3 +// | | | | +// | | | | +// 4 -- 5 6 -- 7 +// +const uint32_t chunkCount0 = 8; +const uint32_t adjacentChunkPartition0[] = { 0, 2, 5, 8, 10, 12, 14, 16, 18 }; +const uint32_t adjacentChunkIndices0[] = { /*0*/ 1, 4, /*1*/ 0, 2, 5, /*2*/ 1, 3, 6, /*3*/ 2, 7, /*4*/ 0, 5, /*5*/ 1, 4, /*6*/ 2, 7, /*7*/ 3, 6 }; + + +// Graph 1: +// +// 0 -- 1 -- 2 -- 3 +// | | | | +// 4 -- 5 -- 6 -- 7 +// | | | | +// 8 -- 9 -- 10-- 11 +// +const uint32_t chunkCount1 = 12; +const uint32_t adjacentChunkPartition1[] = { 0, 2, 5, 8, 10, 13, 17, 21, 24, 26, 29, 32, 34 }; +const uint32_t adjacentChunkIndices1[] = { /*0*/ 1, 4, /*1*/ 0, 2, 5, /*2*/ 1, 3, 6, /*3*/ 2, 7, /*4*/ 0, 5, 8, /*5*/ 1, 4, 6, 9, /*6*/ 2, 5, 7, 10, + /*7*/ 3, 6, 11, /*8*/ 4, 9, /*9*/ 5, 8, 10, /*10*/ 6, 9, 11, /*11*/ 7, 10 }; + + +// ==================================================================================================================== +// TESTS +// ==================================================================================================================== + +TEST_F(FamilyGraphTestStrict, Graph0FindIslands0) +{ + FamilyGraph* graph = buildFamilyGraph(chunkCount0, adjacentChunkPartition0, adjacentChunkIndices0); + graph->initialize(DEFAULT_ACTOR_INDEX, m_graph); + + std::vector scratch; + scratch.resize((size_t)FamilyGraph::findIslandsRequiredScratch(chunkCount0)); + + EXPECT_EQ(9, graph->getEdgesCount(m_graph)); + graph->notifyEdgeRemoved(DEFAULT_ACTOR_INDEX, 0, 4, m_graph); + EXPECT_EQ(8, graph->getEdgesCount(m_graph)); + EXPECT_EQ(1, graph->findIslands(DEFAULT_ACTOR_INDEX, scratch.data(), m_graph)); + + graph->notifyEdgeRemoved(DEFAULT_ACTOR_INDEX, 1, 2, m_graph); + EXPECT_EQ(1, graph->findIslands(DEFAULT_ACTOR_INDEX, scratch.data(), m_graph)); + + std::vector info; + getIslandsInfo(*graph, info); + EXPECT_EQ(2, info.size()); + VECTOR_MATCH(info[0].nodes, 0, 1, 4, 5); + VECTOR_MATCH(info[1].nodes, 2, 3, 6, 7); +} + +TEST_F(FamilyGraphTestStrict, Graph0FindIslands1) +{ + FamilyGraph* graph = buildFamilyGraph(chunkCount0, adjacentChunkPartition0, adjacentChunkIndices0); + graph->initialize(DEFAULT_ACTOR_INDEX, m_graph); + + std::vector scratch; + scratch.resize((size_t)FamilyGraph::findIslandsRequiredScratch(chunkCount0)); + + graph->notifyEdgeRemoved(DEFAULT_ACTOR_INDEX, 0, 4, m_graph); + graph->notifyEdgeRemoved(DEFAULT_ACTOR_INDEX, 4, 5, m_graph); + graph->notifyEdgeRemoved(DEFAULT_ACTOR_INDEX, 1, 2, m_graph); + EXPECT_EQ(6, graph->getEdgesCount(m_graph)); + EXPECT_EQ(3, graph->findIslands(DEFAULT_ACTOR_INDEX, scratch.data(), m_graph)); + + std::vector info; + getIslandsInfo(*graph, info); + EXPECT_EQ(3, info.size()); + VECTOR_MATCH(info[0].nodes, 4); + VECTOR_MATCH(info[1].nodes, 0, 1, 5); + VECTOR_MATCH(info[2].nodes, 2, 3, 6, 7); +} + +TEST_F(FamilyGraphTestStrict, Graph0FindIslandsDifferentActors) +{ + const uint32_t ACTOR_0_INDEX = 5; + const uint32_t ACTOR_1_INDEX = 2; + + FamilyGraph* graph = buildFamilyGraph(chunkCount0, adjacentChunkPartition0, adjacentChunkIndices0); + graph->initialize(ACTOR_0_INDEX, m_graph); + + std::vector scratch; + scratch.resize((size_t)FamilyGraph::findIslandsRequiredScratch(chunkCount0)); + + EXPECT_EQ(0, graph->findIslands(ACTOR_1_INDEX, scratch.data(), m_graph)); + EXPECT_EQ(1, graph->findIslands(ACTOR_0_INDEX, scratch.data(), m_graph)); + + graph->notifyEdgeRemoved(ACTOR_0_INDEX, 2, 1, m_graph); + EXPECT_EQ(8, graph->getEdgesCount(m_graph)); + + EXPECT_EQ(1, graph->findIslands(ACTOR_0_INDEX, scratch.data(), m_graph)); + + graph->notifyEdgeRemoved(ACTOR_1_INDEX, 2, 6, m_graph); + graph->notifyEdgeRemoved(ACTOR_1_INDEX, 7, 3, m_graph); + EXPECT_EQ(1, graph->findIslands(ACTOR_1_INDEX, scratch.data(), m_graph)); + + graph->notifyEdgeRemoved(ACTOR_0_INDEX, 0, 1, m_graph); + graph->notifyEdgeRemoved(ACTOR_0_INDEX, 4, 5, m_graph); + EXPECT_EQ(1, graph->findIslands(ACTOR_0_INDEX, scratch.data(), m_graph)); + + + std::vector info; + getIslandsInfo(*graph, info); + EXPECT_EQ(4, info.size()); + VECTOR_MATCH(info[0].nodes, 0, 4); + VECTOR_MATCH(info[1].nodes, 1, 5); + VECTOR_MATCH(info[2].nodes, 2, 3); + VECTOR_MATCH(info[3].nodes, 6, 7); +} + +TEST_F(FamilyGraphTestStrict, Graph1FindIslands0) +{ + FamilyGraph* graph = buildFamilyGraph(chunkCount1, adjacentChunkPartition1, adjacentChunkIndices1); + graph->initialize(DEFAULT_ACTOR_INDEX, m_graph); + + std::vector scratch; + scratch.resize((size_t)FamilyGraph::findIslandsRequiredScratch(chunkCount1)); + + graph->notifyEdgeRemoved(DEFAULT_ACTOR_INDEX, 0, 4, m_graph); + graph->notifyEdgeRemoved(DEFAULT_ACTOR_INDEX, 1, 5, m_graph); + graph->notifyEdgeRemoved(DEFAULT_ACTOR_INDEX, 2, 6, m_graph); + graph->notifyEdgeRemoved(DEFAULT_ACTOR_INDEX, 3, 7, m_graph); + graph->notifyEdgeRemoved(DEFAULT_ACTOR_INDEX, 5, 6, m_graph); + graph->notifyEdgeRemoved(DEFAULT_ACTOR_INDEX, 9, 10, m_graph); + EXPECT_EQ(11, graph->getEdgesCount(m_graph)); + EXPECT_EQ(3, graph->findIslands(DEFAULT_ACTOR_INDEX, scratch.data(), m_graph)); + + std::vector info; + getIslandsInfo(*graph, info); + EXPECT_EQ(3, info.size()); + + VECTOR_MATCH(info[0].nodes, 0, 1, 2, 3); + VECTOR_MATCH(info[1].nodes, 4, 5, 8, 9); + VECTOR_MATCH(info[2].nodes, 6, 7, 10, 11); +} + +TEST_F(FamilyGraphTestStrict, Graph1FindIslands1) +{ + FamilyGraph* graph = buildFamilyGraph(chunkCount1, adjacentChunkPartition1, adjacentChunkIndices1); + graph->initialize(DEFAULT_ACTOR_INDEX, m_graph); + + std::vector scratch; + scratch.resize((size_t)FamilyGraph::findIslandsRequiredScratch(chunkCount1)); + + graph->notifyEdgeRemoved(DEFAULT_ACTOR_INDEX, 0, 4, m_graph); + EXPECT_EQ(1, graph->findIslands(DEFAULT_ACTOR_INDEX, scratch.data(), m_graph)); + graph->notifyEdgeRemoved(DEFAULT_ACTOR_INDEX, 1, 5, m_graph); + EXPECT_EQ(0, graph->findIslands(DEFAULT_ACTOR_INDEX, scratch.data(), m_graph)); + graph->notifyEdgeRemoved(DEFAULT_ACTOR_INDEX, 2, 6, m_graph); + EXPECT_EQ(0, graph->findIslands(DEFAULT_ACTOR_INDEX, scratch.data(), m_graph)); + graph->notifyEdgeRemoved(DEFAULT_ACTOR_INDEX, 3, 7, m_graph); + EXPECT_EQ(1, graph->findIslands(DEFAULT_ACTOR_INDEX, scratch.data(), m_graph)); + graph->notifyEdgeRemoved(DEFAULT_ACTOR_INDEX, 5, 6, m_graph); + EXPECT_EQ(0, graph->findIslands(DEFAULT_ACTOR_INDEX, scratch.data(), m_graph)); + graph->notifyEdgeRemoved(DEFAULT_ACTOR_INDEX, 9, 10, m_graph); + EXPECT_EQ(1, graph->findIslands(DEFAULT_ACTOR_INDEX, scratch.data(), m_graph)); + + std::vector info; + getIslandsInfo(*graph, info); + EXPECT_EQ(3, info.size()); + VECTOR_MATCH(info[0].nodes, 0, 1, 2, 3); + VECTOR_MATCH(info[1].nodes, 4, 5, 8, 9); + VECTOR_MATCH(info[2].nodes, 6, 7, 10, 11); +} + +TEST_F(FamilyGraphTestStrict, Graph1FindIslandsRemoveAllEdges) +{ + FamilyGraph* graph = buildFamilyGraph(chunkCount1, adjacentChunkPartition1, adjacentChunkIndices1); + graph->initialize(DEFAULT_ACTOR_INDEX, m_graph); + + std::vector scratch; + scratch.resize((size_t)FamilyGraph::findIslandsRequiredScratch(chunkCount1)); + + uint32_t edges = graph->getEdgesCount(m_graph); + for (uint32_t node0 = 0; node0 < chunkCount1; node0++) + { + for (uint32_t i = adjacentChunkPartition1[node0]; i < adjacentChunkPartition1[node0 + 1]; i++) + { + if (graph->notifyEdgeRemoved(DEFAULT_ACTOR_INDEX, node0, adjacentChunkIndices1[i], m_graph)) + { + edges--; + EXPECT_EQ(edges, graph->getEdgesCount(m_graph)); + } + } + } + EXPECT_EQ(0, graph->getEdgesCount(m_graph)); + + EXPECT_EQ(12, graph->findIslands(DEFAULT_ACTOR_INDEX, scratch.data(), m_graph)); + + for (uint32_t node0 = 0; node0 < chunkCount1; node0++) + { + EXPECT_EQ(node0, graph->getIslandIds()[node0]); + } +} -- cgit v1.2.3