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. --- sdk/lowlevel/source/NvBlastFamilyGraph.cpp | 1294 ++++++++++++++-------------- 1 file changed, 647 insertions(+), 647 deletions(-) mode change 100644 => 100755 sdk/lowlevel/source/NvBlastFamilyGraph.cpp (limited to 'sdk/lowlevel/source/NvBlastFamilyGraph.cpp') diff --git a/sdk/lowlevel/source/NvBlastFamilyGraph.cpp b/sdk/lowlevel/source/NvBlastFamilyGraph.cpp old mode 100644 new mode 100755 index 2d879c1..f0918de --- a/sdk/lowlevel/source/NvBlastFamilyGraph.cpp +++ b/sdk/lowlevel/source/NvBlastFamilyGraph.cpp @@ -1,647 +1,647 @@ -// 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 "NvBlastFamilyGraph.h" - -#include "NvBlastAssert.h" - -#include -#include - -#define SANITY_CHECKS 0 - -namespace Nv -{ -namespace Blast -{ - - -size_t FamilyGraph::fillMemory(FamilyGraph* familyGraph, uint32_t nodeCount, uint32_t bondCount) -{ - // calculate all offsets, and dataSize as a result - NvBlastCreateOffsetStart(sizeof(FamilyGraph)); - const size_t NvBlastCreateOffsetAlign16(dirtyNodeLinksOffset, sizeof(NodeIndex) * nodeCount); - const size_t NvBlastCreateOffsetAlign16(firstDirtyNodeIndicesOffset, sizeof(uint32_t) * nodeCount); - const size_t NvBlastCreateOffsetAlign16(islandIdsOffset, sizeof(IslandId) * nodeCount); - const size_t NvBlastCreateOffsetAlign16(fastRouteOffset, sizeof(NodeIndex) * nodeCount); - const size_t NvBlastCreateOffsetAlign16(hopCountsOffset, sizeof(uint32_t) * nodeCount); - const size_t NvBlastCreateOffsetAlign16(isEdgeRemovedOffset, FixedBoolArray::requiredMemorySize(bondCount)); - const size_t NvBlastCreateOffsetAlign16(isNodeInDirtyListOffset, FixedBoolArray::requiredMemorySize(nodeCount)); - const size_t dataSize = NvBlastCreateOffsetEndAlign16(); - - // fill only if familyGraph was passed (otherwise we just used this function to get dataSize) - if (familyGraph) - { - familyGraph->m_dirtyNodeLinksOffset = static_cast(dirtyNodeLinksOffset); - familyGraph->m_firstDirtyNodeIndicesOffset = static_cast(firstDirtyNodeIndicesOffset); - familyGraph->m_islandIdsOffset = static_cast(islandIdsOffset); - familyGraph->m_fastRouteOffset = static_cast(fastRouteOffset); - familyGraph->m_hopCountsOffset = static_cast(hopCountsOffset); - familyGraph->m_isEdgeRemovedOffset = static_cast(isEdgeRemovedOffset); - familyGraph->m_isNodeInDirtyListOffset = static_cast(isNodeInDirtyListOffset); - - new (familyGraph->getIsEdgeRemoved())FixedBoolArray(bondCount); - new (familyGraph->getIsNodeInDirtyList())FixedBoolArray(nodeCount); - } - - return dataSize; -} - - -FamilyGraph::FamilyGraph(const SupportGraph* graph) -{ - // fill memory with all internal data - // we need chunks count for size calculation - const uint32_t nodeCount = graph->m_nodeCount; - const uint32_t bondCount = graph->getAdjacencyPartition()[nodeCount] / 2; - - fillMemory(this, nodeCount, bondCount); - - // fill arrays with invalid indices / max value (0xFFFFFFFF) - memset(getIslandIds(), 0xFF, nodeCount*sizeof(uint32_t)); - memset(getFastRoute(), 0xFF, nodeCount*sizeof(uint32_t)); - memset(getHopCounts(), 0xFF, nodeCount*sizeof(uint32_t)); // Initializing to large value - memset(getDirtyNodeLinks(), 0xFF, nodeCount*sizeof(uint32_t)); // No dirty list initially - memset(getFirstDirtyNodeIndices(), 0xFF, nodeCount*sizeof(uint32_t)); - - getIsNodeInDirtyList()->clear(); - getIsEdgeRemoved()->fill(); -} - - -/** -Graph initialization, reset all internal data to initial state. Marks all nodes dirty for this actor. -First island search probably would be the longest one, as it has to traverse whole graph and set all the optimization stuff like fastRoute and hopCounts for all nodes. -*/ -void FamilyGraph::initialize(ActorIndex actorIndex, const SupportGraph* graph) -{ - // used internal data pointers - NodeIndex* dirtyNodeLinks = getDirtyNodeLinks(); - uint32_t* firstDirtyNodeIndices = getFirstDirtyNodeIndices(); - - // link dirty nodes - for (NodeIndex node = 1; node < graph->m_nodeCount; node++) - { - dirtyNodeLinks[node-1] = node; - } - firstDirtyNodeIndices[actorIndex] = 0; - - getIsNodeInDirtyList()->fill(); - getIsEdgeRemoved()->clear(); -} - - -void FamilyGraph::addToDirtyNodeList(ActorIndex actorIndex, NodeIndex node) -{ - // used internal data pointers - FixedBoolArray* isNodeInDirtyList = getIsNodeInDirtyList(); - NodeIndex* dirtyNodeLinks = getDirtyNodeLinks(); - uint32_t* firstDirtyNodeIndices = getFirstDirtyNodeIndices(); - - // check for bitmap first for avoid O(n) list search - if (isNodeInDirtyList->test(node)) - return; - - // add node to dirty node list head - dirtyNodeLinks[node] = firstDirtyNodeIndices[actorIndex]; - firstDirtyNodeIndices[actorIndex] = node; - isNodeInDirtyList->set(node); -} - - -/** -Removes fast routes and marks involved nodes as dirty -*/ -bool FamilyGraph::notifyEdgeRemoved(ActorIndex actorIndex, NodeIndex node0, NodeIndex node1, const SupportGraph* graph) -{ - NVBLAST_ASSERT(node0 < graph->m_nodeCount); - NVBLAST_ASSERT(node1 < graph->m_nodeCount); - - // used internal data pointers - NodeIndex* fastRoute = getFastRoute(); - const uint32_t* adjacencyPartition = graph->getAdjacencyPartition(); - const uint32_t* adjacentBondIndices = graph->getAdjacentBondIndices(); - - // search for bond - for (uint32_t adjacencyIndex = adjacencyPartition[node0]; adjacencyIndex < adjacencyPartition[node0 + 1]; adjacencyIndex++) - { - if (getAdjacentNode(adjacencyIndex, graph) == node1) - { - // found bond - const uint32_t bondIndex = adjacentBondIndices[adjacencyIndex]; - - // remove bond - getIsEdgeRemoved()->set(bondIndex); - - // broke fast route if it goes through this edge: - if (fastRoute[node0] == node1) - fastRoute[node0] = invalidIndex(); - if (fastRoute[node1] == node0) - fastRoute[node1] = invalidIndex(); - - // mark nodes dirty (add to list if doesn't exist) - addToDirtyNodeList(actorIndex, node0); - addToDirtyNodeList(actorIndex, node1); - - // we don't expect to be more than one bond between 2 nodes - return true; - } - } - - return false; -} - -bool FamilyGraph::notifyEdgeRemoved(ActorIndex actorIndex, NodeIndex node0, NodeIndex node1, uint32_t bondIndex, const SupportGraph* graph) -{ - NV_UNUSED(graph); - NVBLAST_ASSERT(node0 < graph->m_nodeCount); - NVBLAST_ASSERT(node1 < graph->m_nodeCount); - - getIsEdgeRemoved()->set(bondIndex); - - - NodeIndex* fastRoute = getFastRoute(); - - // broke fast route if it goes through this edge: - if (fastRoute[node0] == node1) - fastRoute[node0] = invalidIndex(); - if (fastRoute[node1] == node0) - fastRoute[node1] = invalidIndex(); - - // mark nodes dirty (add to list if doesn't exist) - addToDirtyNodeList(actorIndex, node0); - addToDirtyNodeList(actorIndex, node1); - - return true; -} - -bool FamilyGraph::notifyNodeRemoved(ActorIndex actorIndex, NodeIndex nodeIndex, const SupportGraph* graph) -{ - NVBLAST_ASSERT(nodeIndex < graph->m_nodeCount); - - // used internal data pointers - NodeIndex* fastRoute = getFastRoute(); - const uint32_t* adjacencyPartition = graph->getAdjacencyPartition(); - const uint32_t* adjacentBondIndices = graph->getAdjacentBondIndices(); - - // remove all edges leaving this node - for (uint32_t adjacencyIndex = adjacencyPartition[nodeIndex]; adjacencyIndex < adjacencyPartition[nodeIndex + 1]; adjacencyIndex++) - { - const uint32_t adjacentNodeIndex = getAdjacentNode(adjacencyIndex, graph); - if (!isInvalidIndex(adjacentNodeIndex)) - { - const uint32_t bondIndex = adjacentBondIndices[adjacencyIndex]; - getIsEdgeRemoved()->set(bondIndex); - - if (fastRoute[adjacentNodeIndex] == nodeIndex) - fastRoute[adjacentNodeIndex] = invalidIndex(); - if (fastRoute[nodeIndex] == adjacentNodeIndex) - fastRoute[nodeIndex] = invalidIndex(); - - addToDirtyNodeList(actorIndex, adjacentNodeIndex); - } - } - addToDirtyNodeList(actorIndex, nodeIndex); - - // ignore this node in partition (only needed for "chunk deleted from graph") - // getIslandIds()[nodeIndex] = invalidIndex(); - - return true; -} - -void FamilyGraph::unwindRoute(uint32_t traversalIndex, NodeIndex lastNode, uint32_t hopCount, IslandId id, FixedArray* visitedNodes) -{ - // used internal data pointers - IslandId* islandIds = getIslandIds(); - NodeIndex* fastRoute = getFastRoute(); - uint32_t* hopCounts = getHopCounts(); - - uint32_t currIndex = traversalIndex; - uint32_t hc = hopCount + 1; //Add on 1 for the hop to the witness/root node. - do - { - TraversalState& state = visitedNodes->at(currIndex); - hopCounts[state.mNodeIndex] = hc++; - islandIds[state.mNodeIndex] = id; - fastRoute[state.mNodeIndex] = lastNode; - currIndex = state.mPrevIndex; - lastNode = state.mNodeIndex; - } - while(currIndex != invalidIndex()); -} - - -bool FamilyGraph::tryFastPath(NodeIndex startNode, NodeIndex targetNode, IslandId islandId, FixedArray* visitedNodes, FixedBitmap* isNodeWitness, const SupportGraph* graph) -{ - NV_UNUSED(graph); - - // used internal data pointers - IslandId* islandIds = getIslandIds(); - NodeIndex* fastRoute = getFastRoute(); - - // prepare for iterating path - NodeIndex currentNode = startNode; - uint32_t visitedNotesInitialSize = visitedNodes->size(); - uint32_t depth = 0; - - bool found = false; - do - { - // witness ? - if (isNodeWitness->test(currentNode)) - { - // Already visited and not tagged with invalid island == a witness! - found = islandIds[currentNode] != invalidIndex(); - break; - } - - // reached targetNode ? - if (currentNode == targetNode) - { - found = true; - break; - } - - TraversalState state(currentNode, visitedNodes->size(), visitedNodes->size() - 1, depth++); - visitedNodes->pushBack(state); - - NVBLAST_ASSERT(isInvalidIndex(fastRoute[currentNode]) || hasEdge(currentNode, fastRoute[currentNode], graph)); - - islandIds[currentNode] = invalidIndex(); - isNodeWitness->set(currentNode); - - currentNode = fastRoute[currentNode]; - } while (currentNode != invalidIndex()); - - for (uint32_t a = visitedNotesInitialSize; a < visitedNodes->size(); ++a) - { - TraversalState& state = visitedNodes->at(a); - islandIds[state.mNodeIndex] = islandId; - } - - // if fast path failed we have to remove all isWitness marks on visited nodes and nodes from visited list - if (!found) - { - for (uint32_t a = visitedNotesInitialSize; a < visitedNodes->size(); ++a) - { - TraversalState& state = visitedNodes->at(a); - isNodeWitness->reset(state.mNodeIndex); - } - - visitedNodes->forceSize_Unsafe(visitedNotesInitialSize); - } - - return found; -} - - -bool FamilyGraph::findRoute(NodeIndex startNode, NodeIndex targetNode, IslandId islandId, FixedArray* visitedNodes, FixedBitmap* isNodeWitness, NodePriorityQueue* priorityQueue, const SupportGraph* graph) -{ - // used internal data pointers - IslandId* islandIds = getIslandIds(); - NodeIndex* fastRoute = getFastRoute(); - uint32_t* hopCounts = getHopCounts(); - const uint32_t* adjacencyPartition = graph->getAdjacencyPartition(); - - // Firstly, traverse the fast path and tag up witnesses. TryFastPath can fail. In that case, no witnesses are left but this node is permitted to report - // that it is still part of the island. Whichever node lost its fast path will be tagged as dirty and will be responsible for recovering the fast path - // and tagging up the visited nodes - if (fastRoute[startNode] != invalidIndex()) - { - if (tryFastPath(startNode, targetNode, islandId, visitedNodes, isNodeWitness, graph)) - return true; - } - - // If we got here, there was no fast path. Therefore, we need to fall back on searching for the root node. This is optimized by using "hop counts". - // These are per-node counts that indicate the expected number of hops from this node to the root node. These are lazily evaluated and updated - // as new edges are formed or when traversals occur to re-establish islands. As a result, they may be inaccurate but they still serve the purpose - // of guiding our search to minimize the chances of us doing an exhaustive search to find the root node. - islandIds[startNode] = invalidIndex(); - TraversalState startTraversal(startNode, visitedNodes->size(), invalidIndex(), 0); - isNodeWitness->set(startNode); - QueueElement element(&visitedNodes->pushBack(startTraversal), hopCounts[startNode]); - priorityQueue->push(element); - - do - { - QueueElement currentQE = priorityQueue->pop(); - - TraversalState& currentState = *currentQE.mState; - NodeIndex& currentNode = currentState.mNodeIndex; - - // iterate all edges of currentNode - for (uint32_t adjacencyIndex = adjacencyPartition[currentNode]; adjacencyIndex < adjacencyPartition[currentNode + 1]; adjacencyIndex++) - { - NodeIndex nextIndex = getAdjacentNode(adjacencyIndex, graph); - - if (nextIndex != invalidIndex()) - { - if (nextIndex == targetNode) - { - // targetNode found! - unwindRoute(currentState.mCurrentIndex, nextIndex, 0, islandId, visitedNodes); - return true; - } - - if (isNodeWitness->test(nextIndex)) - { - // We already visited this node. This means that it's either in the priority queue already or we - // visited in on a previous pass. If it was visited on a previous pass, then it already knows what island it's in. - // We now need to test the island id to find out if this node knows the root. - // If it has a valid root id, that id *is* our new root. We can guesstimate our hop count based on the node's properties - - IslandId visitedIslandId = islandIds[nextIndex]; - if (visitedIslandId != invalidIndex()) - { - // If we get here, we must have found a node that knows a route to our root node. It must not be a different island - // because that would caused me to have been visited already because totally separate islands trigger a full traversal on - // the orphaned side. - NVBLAST_ASSERT(visitedIslandId == islandId); - unwindRoute(currentState.mCurrentIndex, nextIndex, hopCounts[nextIndex], islandId, visitedNodes); - return true; - } - } - else - { - // This node has not been visited yet, so we need to push it into the stack and continue traversing - TraversalState state(nextIndex, visitedNodes->size(), currentState.mCurrentIndex, currentState.mDepth + 1); - QueueElement qe(&visitedNodes->pushBack(state), hopCounts[nextIndex]); - priorityQueue->push(qe); - isNodeWitness->set(nextIndex); - NVBLAST_ASSERT(islandIds[nextIndex] == islandId); - islandIds[nextIndex] = invalidIndex(); //Flag as invalid island until we know whether we can find root or an island id. - } - } - } - } while (priorityQueue->size()); - - return false; -} - - -size_t FamilyGraph::findIslandsRequiredScratch(uint32_t graphNodeCount) -{ - const size_t visitedNodesSize = align16(FixedArray::requiredMemorySize(graphNodeCount)); - const size_t isNodeWitnessSize = align16(FixedBitmap::requiredMemorySize(graphNodeCount)); - const size_t priorityQueueSize = align16(NodePriorityQueue::requiredMemorySize(graphNodeCount)); - - // Aligned and padded - return 16 + visitedNodesSize - + isNodeWitnessSize - + priorityQueueSize; -} - - -uint32_t FamilyGraph::findIslands(ActorIndex actorIndex, void* scratch, const SupportGraph* graph) -{ - // check if we have at least 1 dirty node for this actor before proceeding - uint32_t* firstDirtyNodeIndices = getFirstDirtyNodeIndices(); - if (isInvalidIndex(firstDirtyNodeIndices[actorIndex])) - return 0; - - // used internal data pointers - IslandId* islandIds = getIslandIds(); - NodeIndex* fastRoute = getFastRoute(); - uint32_t* hopCounts = getHopCounts(); - NodeIndex* dirtyNodeLinks = getDirtyNodeLinks(); - FixedBoolArray* isNodeInDirtyList = getIsNodeInDirtyList(); - - // prepare intermediate data on scratch - scratch = (void*)align16((size_t)scratch); // Bump to 16-byte alignment (see padding in findIslandsRequiredScratch) - const uint32_t nodeCount = graph->m_nodeCount; - - FixedArray* visitedNodes = new (scratch)FixedArray(); - scratch = pointerOffset(scratch, align16(FixedArray::requiredMemorySize(nodeCount))); - - FixedBitmap* isNodeWitness = new (scratch)FixedBitmap(nodeCount); - scratch = pointerOffset(scratch, align16(FixedBitmap::requiredMemorySize(nodeCount))); - - NodePriorityQueue* priorityQueue = new (scratch)NodePriorityQueue(); - scratch = pointerOffset(scratch, align16(NodePriorityQueue::requiredMemorySize(nodeCount))); - - // reset nodes visited bitmap - isNodeWitness->clear(); - - uint32_t newIslandsCount = 0; - - while (!isInvalidIndex(firstDirtyNodeIndices[actorIndex])) - { - // Pop head off of dirty node's list - const NodeIndex dirtyNode = firstDirtyNodeIndices[actorIndex]; - firstDirtyNodeIndices[actorIndex] = dirtyNodeLinks[dirtyNode]; - dirtyNodeLinks[dirtyNode] = invalidIndex(); - NVBLAST_ASSERT(isNodeInDirtyList->test(dirtyNode)); - isNodeInDirtyList->reset(dirtyNode); - - // clear PriorityQueue - priorityQueue->clear(); - - // if we already visited this node before in this loop it's not dirty anymore - if (isNodeWitness->test(dirtyNode)) - continue; - - NodeIndex& islandRootNode = islandIds[dirtyNode]; - IslandId islandId = islandRootNode; // the same in this implementation - - // if this node is island root node we don't need to do anything - if (islandRootNode == dirtyNode) - continue; - - // clear visited notes list (to fill during traverse) - visitedNodes->clear(); - - // try finding island root node from this dirtyNode - if (findRoute(dirtyNode, islandRootNode, islandId, visitedNodes, isNodeWitness, priorityQueue, graph)) - { - // We found the root node so let's let every visited node know that we found its root - // and we can also update our hop counts because we recorded how many hops it took to reach this - // node - - // We already filled in the path to the root/witness with accurate hop counts. Now we just need to fill in the estimates - // for the remaining nodes and re-define their islandIds. We approximate their path to the root by just routing them through - // the route we already found. - - // This loop works because visitedNodes are recorded in the order they were visited and we already filled in the critical path - // so the remainder of the paths will just fork from that path. - for (uint32_t b = 0; b < visitedNodes->size(); ++b) - { - TraversalState& state = visitedNodes->at(b); - if (isInvalidIndex(islandIds[state.mNodeIndex])) - { - hopCounts[state.mNodeIndex] = hopCounts[visitedNodes->at(state.mPrevIndex).mNodeIndex] + 1; - fastRoute[state.mNodeIndex] = visitedNodes->at(state.mPrevIndex).mNodeIndex; - islandIds[state.mNodeIndex] = islandId; - } - } - } - else - { - // NEW ISLAND BORN! - - // If I traversed and could not find the root node, then I have established a new island. In this island, I am the root node - // and I will point all my nodes towards me. Furthermore, I have established how many steps it took to reach all nodes in my island - - // OK. We need to separate the islands. We have a list of nodes that are part of the new island (visitedNodes) and we know that the - // first node in that list is the root node. - -#if SANITY_CHECKS - NVBLAST_ASSERT(!canFindRoot(dirtyNode, islandRootNode, NULL)); -#endif - - IslandId newIsland = dirtyNode; - newIslandsCount++; - - hopCounts[dirtyNode] = 0; - fastRoute[dirtyNode] = invalidIndex(); - islandIds[dirtyNode] = newIsland; - - for (uint32_t a = 1; a < visitedNodes->size(); ++a) - { - NodeIndex visitedNode = visitedNodes->at(a).mNodeIndex; - hopCounts[visitedNode] = visitedNodes->at(a).mDepth; //How many hops to root - fastRoute[visitedNode] = visitedNodes->at(visitedNodes->at(a).mPrevIndex).mNodeIndex; - islandIds[visitedNode] = newIsland; - } - } - } - - // all dirty nodes processed - return newIslandsCount; -} - - -/** -!!! Debug/Test function. -Function to check that root between nodes exists. -*/ -bool FamilyGraph::canFindRoot(NodeIndex startNode, NodeIndex targetNode, FixedArray* visitedNodes, const SupportGraph* graph) -{ - if (visitedNodes) - visitedNodes->pushBack(startNode); - - if (startNode == targetNode) - return true; - - std::vector visitedState; - visitedState.resize(graph->m_nodeCount); - for (uint32_t i = 0; i < graph->m_nodeCount; i++) - visitedState[i] = false; - - std::stack stack; - - stack.push(startNode); - visitedState[startNode] = true; - - const uint32_t* adjacencyPartition = graph->getAdjacencyPartition(); - do - { - NodeIndex currentNode = stack.top(); - stack.pop(); - - for (uint32_t adjacencyIndex = adjacencyPartition[currentNode]; adjacencyIndex < adjacencyPartition[currentNode + 1]; adjacencyIndex++) - { - NodeIndex nextNode = getAdjacentNode(adjacencyIndex, graph); - - if (isInvalidIndex(nextNode)) - continue; - - if (!visitedState[nextNode]) - { - if (nextNode == targetNode) - { - return true; - } - - visitedState[nextNode] = true; - stack.push(nextNode); - - if (visitedNodes) - visitedNodes->pushBack(nextNode); - } - } - - } while (!stack.empty()); - - return false; -} - - -/** -!!! Debug/Test function. -Function to check if edge exists. -*/ -bool FamilyGraph::hasEdge(NodeIndex node0, NodeIndex node1, const SupportGraph* graph) const -{ - const uint32_t* adjacencyPartition = graph->getAdjacencyPartition(); - uint32_t edges = 0; - for (uint32_t adjacencyIndex = adjacencyPartition[node0]; adjacencyIndex < adjacencyPartition[node0 + 1]; adjacencyIndex++) - { - if (getAdjacentNode(adjacencyIndex, graph) == node1) - { - edges++; - break; - } - } - for (uint32_t adjacencyIndex = adjacencyPartition[node1]; adjacencyIndex < adjacencyPartition[node1 + 1]; adjacencyIndex++) - { - if (getAdjacentNode(adjacencyIndex, graph) == node0) - { - edges++; - break; - } - } - return edges > 0; -} - - -/** -!!! Debug/Test function. -Function to calculate and return edges count -*/ -uint32_t FamilyGraph::getEdgesCount(const SupportGraph* graph) const -{ - const uint32_t* adjacencyPartition = graph->getAdjacencyPartition(); - uint32_t edges = 0; - for (NodeIndex n = 0; n < graph->m_nodeCount; n++) - { - for (uint32_t adjacencyIndex = adjacencyPartition[n]; adjacencyIndex < adjacencyPartition[n + 1]; adjacencyIndex++) - { - if (getAdjacentNode(adjacencyIndex, graph) != invalidIndex()) - edges++; - } - } - NVBLAST_ASSERT(edges % 2 == 0); - return edges / 2; -} - - - - -} // namespace Nv -} // namespace Blast - +// 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 "NvBlastFamilyGraph.h" + +#include "NvBlastAssert.h" + +#include +#include + +#define SANITY_CHECKS 0 + +namespace Nv +{ +namespace Blast +{ + + +size_t FamilyGraph::fillMemory(FamilyGraph* familyGraph, uint32_t nodeCount, uint32_t bondCount) +{ + // calculate all offsets, and dataSize as a result + NvBlastCreateOffsetStart(sizeof(FamilyGraph)); + const size_t NvBlastCreateOffsetAlign16(dirtyNodeLinksOffset, sizeof(NodeIndex) * nodeCount); + const size_t NvBlastCreateOffsetAlign16(firstDirtyNodeIndicesOffset, sizeof(uint32_t) * nodeCount); + const size_t NvBlastCreateOffsetAlign16(islandIdsOffset, sizeof(IslandId) * nodeCount); + const size_t NvBlastCreateOffsetAlign16(fastRouteOffset, sizeof(NodeIndex) * nodeCount); + const size_t NvBlastCreateOffsetAlign16(hopCountsOffset, sizeof(uint32_t) * nodeCount); + const size_t NvBlastCreateOffsetAlign16(isEdgeRemovedOffset, FixedBoolArray::requiredMemorySize(bondCount)); + const size_t NvBlastCreateOffsetAlign16(isNodeInDirtyListOffset, FixedBoolArray::requiredMemorySize(nodeCount)); + const size_t dataSize = NvBlastCreateOffsetEndAlign16(); + + // fill only if familyGraph was passed (otherwise we just used this function to get dataSize) + if (familyGraph) + { + familyGraph->m_dirtyNodeLinksOffset = static_cast(dirtyNodeLinksOffset); + familyGraph->m_firstDirtyNodeIndicesOffset = static_cast(firstDirtyNodeIndicesOffset); + familyGraph->m_islandIdsOffset = static_cast(islandIdsOffset); + familyGraph->m_fastRouteOffset = static_cast(fastRouteOffset); + familyGraph->m_hopCountsOffset = static_cast(hopCountsOffset); + familyGraph->m_isEdgeRemovedOffset = static_cast(isEdgeRemovedOffset); + familyGraph->m_isNodeInDirtyListOffset = static_cast(isNodeInDirtyListOffset); + + new (familyGraph->getIsEdgeRemoved())FixedBoolArray(bondCount); + new (familyGraph->getIsNodeInDirtyList())FixedBoolArray(nodeCount); + } + + return dataSize; +} + + +FamilyGraph::FamilyGraph(const SupportGraph* graph) +{ + // fill memory with all internal data + // we need chunks count for size calculation + const uint32_t nodeCount = graph->m_nodeCount; + const uint32_t bondCount = graph->getAdjacencyPartition()[nodeCount] / 2; + + fillMemory(this, nodeCount, bondCount); + + // fill arrays with invalid indices / max value (0xFFFFFFFF) + memset(getIslandIds(), 0xFF, nodeCount*sizeof(uint32_t)); + memset(getFastRoute(), 0xFF, nodeCount*sizeof(uint32_t)); + memset(getHopCounts(), 0xFF, nodeCount*sizeof(uint32_t)); // Initializing to large value + memset(getDirtyNodeLinks(), 0xFF, nodeCount*sizeof(uint32_t)); // No dirty list initially + memset(getFirstDirtyNodeIndices(), 0xFF, nodeCount*sizeof(uint32_t)); + + getIsNodeInDirtyList()->clear(); + getIsEdgeRemoved()->fill(); +} + + +/** +Graph initialization, reset all internal data to initial state. Marks all nodes dirty for this actor. +First island search probably would be the longest one, as it has to traverse whole graph and set all the optimization stuff like fastRoute and hopCounts for all nodes. +*/ +void FamilyGraph::initialize(ActorIndex actorIndex, const SupportGraph* graph) +{ + // used internal data pointers + NodeIndex* dirtyNodeLinks = getDirtyNodeLinks(); + uint32_t* firstDirtyNodeIndices = getFirstDirtyNodeIndices(); + + // link dirty nodes + for (NodeIndex node = 1; node < graph->m_nodeCount; node++) + { + dirtyNodeLinks[node-1] = node; + } + firstDirtyNodeIndices[actorIndex] = 0; + + getIsNodeInDirtyList()->fill(); + getIsEdgeRemoved()->clear(); +} + + +void FamilyGraph::addToDirtyNodeList(ActorIndex actorIndex, NodeIndex node) +{ + // used internal data pointers + FixedBoolArray* isNodeInDirtyList = getIsNodeInDirtyList(); + NodeIndex* dirtyNodeLinks = getDirtyNodeLinks(); + uint32_t* firstDirtyNodeIndices = getFirstDirtyNodeIndices(); + + // check for bitmap first for avoid O(n) list search + if (isNodeInDirtyList->test(node)) + return; + + // add node to dirty node list head + dirtyNodeLinks[node] = firstDirtyNodeIndices[actorIndex]; + firstDirtyNodeIndices[actorIndex] = node; + isNodeInDirtyList->set(node); +} + + +/** +Removes fast routes and marks involved nodes as dirty +*/ +bool FamilyGraph::notifyEdgeRemoved(ActorIndex actorIndex, NodeIndex node0, NodeIndex node1, const SupportGraph* graph) +{ + NVBLAST_ASSERT(node0 < graph->m_nodeCount); + NVBLAST_ASSERT(node1 < graph->m_nodeCount); + + // used internal data pointers + NodeIndex* fastRoute = getFastRoute(); + const uint32_t* adjacencyPartition = graph->getAdjacencyPartition(); + const uint32_t* adjacentBondIndices = graph->getAdjacentBondIndices(); + + // search for bond + for (uint32_t adjacencyIndex = adjacencyPartition[node0]; adjacencyIndex < adjacencyPartition[node0 + 1]; adjacencyIndex++) + { + if (getAdjacentNode(adjacencyIndex, graph) == node1) + { + // found bond + const uint32_t bondIndex = adjacentBondIndices[adjacencyIndex]; + + // remove bond + getIsEdgeRemoved()->set(bondIndex); + + // broke fast route if it goes through this edge: + if (fastRoute[node0] == node1) + fastRoute[node0] = invalidIndex(); + if (fastRoute[node1] == node0) + fastRoute[node1] = invalidIndex(); + + // mark nodes dirty (add to list if doesn't exist) + addToDirtyNodeList(actorIndex, node0); + addToDirtyNodeList(actorIndex, node1); + + // we don't expect to be more than one bond between 2 nodes + return true; + } + } + + return false; +} + +bool FamilyGraph::notifyEdgeRemoved(ActorIndex actorIndex, NodeIndex node0, NodeIndex node1, uint32_t bondIndex, const SupportGraph* graph) +{ + NV_UNUSED(graph); + NVBLAST_ASSERT(node0 < graph->m_nodeCount); + NVBLAST_ASSERT(node1 < graph->m_nodeCount); + + getIsEdgeRemoved()->set(bondIndex); + + + NodeIndex* fastRoute = getFastRoute(); + + // broke fast route if it goes through this edge: + if (fastRoute[node0] == node1) + fastRoute[node0] = invalidIndex(); + if (fastRoute[node1] == node0) + fastRoute[node1] = invalidIndex(); + + // mark nodes dirty (add to list if doesn't exist) + addToDirtyNodeList(actorIndex, node0); + addToDirtyNodeList(actorIndex, node1); + + return true; +} + +bool FamilyGraph::notifyNodeRemoved(ActorIndex actorIndex, NodeIndex nodeIndex, const SupportGraph* graph) +{ + NVBLAST_ASSERT(nodeIndex < graph->m_nodeCount); + + // used internal data pointers + NodeIndex* fastRoute = getFastRoute(); + const uint32_t* adjacencyPartition = graph->getAdjacencyPartition(); + const uint32_t* adjacentBondIndices = graph->getAdjacentBondIndices(); + + // remove all edges leaving this node + for (uint32_t adjacencyIndex = adjacencyPartition[nodeIndex]; adjacencyIndex < adjacencyPartition[nodeIndex + 1]; adjacencyIndex++) + { + const uint32_t adjacentNodeIndex = getAdjacentNode(adjacencyIndex, graph); + if (!isInvalidIndex(adjacentNodeIndex)) + { + const uint32_t bondIndex = adjacentBondIndices[adjacencyIndex]; + getIsEdgeRemoved()->set(bondIndex); + + if (fastRoute[adjacentNodeIndex] == nodeIndex) + fastRoute[adjacentNodeIndex] = invalidIndex(); + if (fastRoute[nodeIndex] == adjacentNodeIndex) + fastRoute[nodeIndex] = invalidIndex(); + + addToDirtyNodeList(actorIndex, adjacentNodeIndex); + } + } + addToDirtyNodeList(actorIndex, nodeIndex); + + // ignore this node in partition (only needed for "chunk deleted from graph") + // getIslandIds()[nodeIndex] = invalidIndex(); + + return true; +} + +void FamilyGraph::unwindRoute(uint32_t traversalIndex, NodeIndex lastNode, uint32_t hopCount, IslandId id, FixedArray* visitedNodes) +{ + // used internal data pointers + IslandId* islandIds = getIslandIds(); + NodeIndex* fastRoute = getFastRoute(); + uint32_t* hopCounts = getHopCounts(); + + uint32_t currIndex = traversalIndex; + uint32_t hc = hopCount + 1; //Add on 1 for the hop to the witness/root node. + do + { + TraversalState& state = visitedNodes->at(currIndex); + hopCounts[state.mNodeIndex] = hc++; + islandIds[state.mNodeIndex] = id; + fastRoute[state.mNodeIndex] = lastNode; + currIndex = state.mPrevIndex; + lastNode = state.mNodeIndex; + } + while(currIndex != invalidIndex()); +} + + +bool FamilyGraph::tryFastPath(NodeIndex startNode, NodeIndex targetNode, IslandId islandId, FixedArray* visitedNodes, FixedBitmap* isNodeWitness, const SupportGraph* graph) +{ + NV_UNUSED(graph); + + // used internal data pointers + IslandId* islandIds = getIslandIds(); + NodeIndex* fastRoute = getFastRoute(); + + // prepare for iterating path + NodeIndex currentNode = startNode; + uint32_t visitedNotesInitialSize = visitedNodes->size(); + uint32_t depth = 0; + + bool found = false; + do + { + // witness ? + if (isNodeWitness->test(currentNode)) + { + // Already visited and not tagged with invalid island == a witness! + found = islandIds[currentNode] != invalidIndex(); + break; + } + + // reached targetNode ? + if (currentNode == targetNode) + { + found = true; + break; + } + + TraversalState state(currentNode, visitedNodes->size(), visitedNodes->size() - 1, depth++); + visitedNodes->pushBack(state); + + NVBLAST_ASSERT(isInvalidIndex(fastRoute[currentNode]) || hasEdge(currentNode, fastRoute[currentNode], graph)); + + islandIds[currentNode] = invalidIndex(); + isNodeWitness->set(currentNode); + + currentNode = fastRoute[currentNode]; + } while (currentNode != invalidIndex()); + + for (uint32_t a = visitedNotesInitialSize; a < visitedNodes->size(); ++a) + { + TraversalState& state = visitedNodes->at(a); + islandIds[state.mNodeIndex] = islandId; + } + + // if fast path failed we have to remove all isWitness marks on visited nodes and nodes from visited list + if (!found) + { + for (uint32_t a = visitedNotesInitialSize; a < visitedNodes->size(); ++a) + { + TraversalState& state = visitedNodes->at(a); + isNodeWitness->reset(state.mNodeIndex); + } + + visitedNodes->forceSize_Unsafe(visitedNotesInitialSize); + } + + return found; +} + + +bool FamilyGraph::findRoute(NodeIndex startNode, NodeIndex targetNode, IslandId islandId, FixedArray* visitedNodes, FixedBitmap* isNodeWitness, NodePriorityQueue* priorityQueue, const SupportGraph* graph) +{ + // used internal data pointers + IslandId* islandIds = getIslandIds(); + NodeIndex* fastRoute = getFastRoute(); + uint32_t* hopCounts = getHopCounts(); + const uint32_t* adjacencyPartition = graph->getAdjacencyPartition(); + + // Firstly, traverse the fast path and tag up witnesses. TryFastPath can fail. In that case, no witnesses are left but this node is permitted to report + // that it is still part of the island. Whichever node lost its fast path will be tagged as dirty and will be responsible for recovering the fast path + // and tagging up the visited nodes + if (fastRoute[startNode] != invalidIndex()) + { + if (tryFastPath(startNode, targetNode, islandId, visitedNodes, isNodeWitness, graph)) + return true; + } + + // If we got here, there was no fast path. Therefore, we need to fall back on searching for the root node. This is optimized by using "hop counts". + // These are per-node counts that indicate the expected number of hops from this node to the root node. These are lazily evaluated and updated + // as new edges are formed or when traversals occur to re-establish islands. As a result, they may be inaccurate but they still serve the purpose + // of guiding our search to minimize the chances of us doing an exhaustive search to find the root node. + islandIds[startNode] = invalidIndex(); + TraversalState startTraversal(startNode, visitedNodes->size(), invalidIndex(), 0); + isNodeWitness->set(startNode); + QueueElement element(&visitedNodes->pushBack(startTraversal), hopCounts[startNode]); + priorityQueue->push(element); + + do + { + QueueElement currentQE = priorityQueue->pop(); + + TraversalState& currentState = *currentQE.mState; + NodeIndex& currentNode = currentState.mNodeIndex; + + // iterate all edges of currentNode + for (uint32_t adjacencyIndex = adjacencyPartition[currentNode]; adjacencyIndex < adjacencyPartition[currentNode + 1]; adjacencyIndex++) + { + NodeIndex nextIndex = getAdjacentNode(adjacencyIndex, graph); + + if (nextIndex != invalidIndex()) + { + if (nextIndex == targetNode) + { + // targetNode found! + unwindRoute(currentState.mCurrentIndex, nextIndex, 0, islandId, visitedNodes); + return true; + } + + if (isNodeWitness->test(nextIndex)) + { + // We already visited this node. This means that it's either in the priority queue already or we + // visited in on a previous pass. If it was visited on a previous pass, then it already knows what island it's in. + // We now need to test the island id to find out if this node knows the root. + // If it has a valid root id, that id *is* our new root. We can guesstimate our hop count based on the node's properties + + IslandId visitedIslandId = islandIds[nextIndex]; + if (visitedIslandId != invalidIndex()) + { + // If we get here, we must have found a node that knows a route to our root node. It must not be a different island + // because that would caused me to have been visited already because totally separate islands trigger a full traversal on + // the orphaned side. + NVBLAST_ASSERT(visitedIslandId == islandId); + unwindRoute(currentState.mCurrentIndex, nextIndex, hopCounts[nextIndex], islandId, visitedNodes); + return true; + } + } + else + { + // This node has not been visited yet, so we need to push it into the stack and continue traversing + TraversalState state(nextIndex, visitedNodes->size(), currentState.mCurrentIndex, currentState.mDepth + 1); + QueueElement qe(&visitedNodes->pushBack(state), hopCounts[nextIndex]); + priorityQueue->push(qe); + isNodeWitness->set(nextIndex); + NVBLAST_ASSERT(islandIds[nextIndex] == islandId); + islandIds[nextIndex] = invalidIndex(); //Flag as invalid island until we know whether we can find root or an island id. + } + } + } + } while (priorityQueue->size()); + + return false; +} + + +size_t FamilyGraph::findIslandsRequiredScratch(uint32_t graphNodeCount) +{ + const size_t visitedNodesSize = align16(FixedArray::requiredMemorySize(graphNodeCount)); + const size_t isNodeWitnessSize = align16(FixedBitmap::requiredMemorySize(graphNodeCount)); + const size_t priorityQueueSize = align16(NodePriorityQueue::requiredMemorySize(graphNodeCount)); + + // Aligned and padded + return 16 + visitedNodesSize + + isNodeWitnessSize + + priorityQueueSize; +} + + +uint32_t FamilyGraph::findIslands(ActorIndex actorIndex, void* scratch, const SupportGraph* graph) +{ + // check if we have at least 1 dirty node for this actor before proceeding + uint32_t* firstDirtyNodeIndices = getFirstDirtyNodeIndices(); + if (isInvalidIndex(firstDirtyNodeIndices[actorIndex])) + return 0; + + // used internal data pointers + IslandId* islandIds = getIslandIds(); + NodeIndex* fastRoute = getFastRoute(); + uint32_t* hopCounts = getHopCounts(); + NodeIndex* dirtyNodeLinks = getDirtyNodeLinks(); + FixedBoolArray* isNodeInDirtyList = getIsNodeInDirtyList(); + + // prepare intermediate data on scratch + scratch = (void*)align16((size_t)scratch); // Bump to 16-byte alignment (see padding in findIslandsRequiredScratch) + const uint32_t nodeCount = graph->m_nodeCount; + + FixedArray* visitedNodes = new (scratch)FixedArray(); + scratch = pointerOffset(scratch, align16(FixedArray::requiredMemorySize(nodeCount))); + + FixedBitmap* isNodeWitness = new (scratch)FixedBitmap(nodeCount); + scratch = pointerOffset(scratch, align16(FixedBitmap::requiredMemorySize(nodeCount))); + + NodePriorityQueue* priorityQueue = new (scratch)NodePriorityQueue(); + scratch = pointerOffset(scratch, align16(NodePriorityQueue::requiredMemorySize(nodeCount))); + + // reset nodes visited bitmap + isNodeWitness->clear(); + + uint32_t newIslandsCount = 0; + + while (!isInvalidIndex(firstDirtyNodeIndices[actorIndex])) + { + // Pop head off of dirty node's list + const NodeIndex dirtyNode = firstDirtyNodeIndices[actorIndex]; + firstDirtyNodeIndices[actorIndex] = dirtyNodeLinks[dirtyNode]; + dirtyNodeLinks[dirtyNode] = invalidIndex(); + NVBLAST_ASSERT(isNodeInDirtyList->test(dirtyNode)); + isNodeInDirtyList->reset(dirtyNode); + + // clear PriorityQueue + priorityQueue->clear(); + + // if we already visited this node before in this loop it's not dirty anymore + if (isNodeWitness->test(dirtyNode)) + continue; + + NodeIndex& islandRootNode = islandIds[dirtyNode]; + IslandId islandId = islandRootNode; // the same in this implementation + + // if this node is island root node we don't need to do anything + if (islandRootNode == dirtyNode) + continue; + + // clear visited notes list (to fill during traverse) + visitedNodes->clear(); + + // try finding island root node from this dirtyNode + if (findRoute(dirtyNode, islandRootNode, islandId, visitedNodes, isNodeWitness, priorityQueue, graph)) + { + // We found the root node so let's let every visited node know that we found its root + // and we can also update our hop counts because we recorded how many hops it took to reach this + // node + + // We already filled in the path to the root/witness with accurate hop counts. Now we just need to fill in the estimates + // for the remaining nodes and re-define their islandIds. We approximate their path to the root by just routing them through + // the route we already found. + + // This loop works because visitedNodes are recorded in the order they were visited and we already filled in the critical path + // so the remainder of the paths will just fork from that path. + for (uint32_t b = 0; b < visitedNodes->size(); ++b) + { + TraversalState& state = visitedNodes->at(b); + if (isInvalidIndex(islandIds[state.mNodeIndex])) + { + hopCounts[state.mNodeIndex] = hopCounts[visitedNodes->at(state.mPrevIndex).mNodeIndex] + 1; + fastRoute[state.mNodeIndex] = visitedNodes->at(state.mPrevIndex).mNodeIndex; + islandIds[state.mNodeIndex] = islandId; + } + } + } + else + { + // NEW ISLAND BORN! + + // If I traversed and could not find the root node, then I have established a new island. In this island, I am the root node + // and I will point all my nodes towards me. Furthermore, I have established how many steps it took to reach all nodes in my island + + // OK. We need to separate the islands. We have a list of nodes that are part of the new island (visitedNodes) and we know that the + // first node in that list is the root node. + +#if SANITY_CHECKS + NVBLAST_ASSERT(!canFindRoot(dirtyNode, islandRootNode, NULL)); +#endif + + IslandId newIsland = dirtyNode; + newIslandsCount++; + + hopCounts[dirtyNode] = 0; + fastRoute[dirtyNode] = invalidIndex(); + islandIds[dirtyNode] = newIsland; + + for (uint32_t a = 1; a < visitedNodes->size(); ++a) + { + NodeIndex visitedNode = visitedNodes->at(a).mNodeIndex; + hopCounts[visitedNode] = visitedNodes->at(a).mDepth; //How many hops to root + fastRoute[visitedNode] = visitedNodes->at(visitedNodes->at(a).mPrevIndex).mNodeIndex; + islandIds[visitedNode] = newIsland; + } + } + } + + // all dirty nodes processed + return newIslandsCount; +} + + +/** +!!! Debug/Test function. +Function to check that root between nodes exists. +*/ +bool FamilyGraph::canFindRoot(NodeIndex startNode, NodeIndex targetNode, FixedArray* visitedNodes, const SupportGraph* graph) +{ + if (visitedNodes) + visitedNodes->pushBack(startNode); + + if (startNode == targetNode) + return true; + + std::vector visitedState; + visitedState.resize(graph->m_nodeCount); + for (uint32_t i = 0; i < graph->m_nodeCount; i++) + visitedState[i] = false; + + std::stack stack; + + stack.push(startNode); + visitedState[startNode] = true; + + const uint32_t* adjacencyPartition = graph->getAdjacencyPartition(); + do + { + NodeIndex currentNode = stack.top(); + stack.pop(); + + for (uint32_t adjacencyIndex = adjacencyPartition[currentNode]; adjacencyIndex < adjacencyPartition[currentNode + 1]; adjacencyIndex++) + { + NodeIndex nextNode = getAdjacentNode(adjacencyIndex, graph); + + if (isInvalidIndex(nextNode)) + continue; + + if (!visitedState[nextNode]) + { + if (nextNode == targetNode) + { + return true; + } + + visitedState[nextNode] = true; + stack.push(nextNode); + + if (visitedNodes) + visitedNodes->pushBack(nextNode); + } + } + + } while (!stack.empty()); + + return false; +} + + +/** +!!! Debug/Test function. +Function to check if edge exists. +*/ +bool FamilyGraph::hasEdge(NodeIndex node0, NodeIndex node1, const SupportGraph* graph) const +{ + const uint32_t* adjacencyPartition = graph->getAdjacencyPartition(); + uint32_t edges = 0; + for (uint32_t adjacencyIndex = adjacencyPartition[node0]; adjacencyIndex < adjacencyPartition[node0 + 1]; adjacencyIndex++) + { + if (getAdjacentNode(adjacencyIndex, graph) == node1) + { + edges++; + break; + } + } + for (uint32_t adjacencyIndex = adjacencyPartition[node1]; adjacencyIndex < adjacencyPartition[node1 + 1]; adjacencyIndex++) + { + if (getAdjacentNode(adjacencyIndex, graph) == node0) + { + edges++; + break; + } + } + return edges > 0; +} + + +/** +!!! Debug/Test function. +Function to calculate and return edges count +*/ +uint32_t FamilyGraph::getEdgesCount(const SupportGraph* graph) const +{ + const uint32_t* adjacencyPartition = graph->getAdjacencyPartition(); + uint32_t edges = 0; + for (NodeIndex n = 0; n < graph->m_nodeCount; n++) + { + for (uint32_t adjacencyIndex = adjacencyPartition[n]; adjacencyIndex < adjacencyPartition[n + 1]; adjacencyIndex++) + { + if (getAdjacentNode(adjacencyIndex, graph) != invalidIndex()) + edges++; + } + } + NVBLAST_ASSERT(edges % 2 == 0); + return edges / 2; +} + + + + +} // namespace Nv +} // namespace Blast + -- cgit v1.2.3