sparseInputPathFinder.h

Go to the documentation of this file.

//
// Copyright 2025 Pixar
//
// Licensed under the terms set forth in the LICENSE.txt file available at
// https://openusd.org/license.
//
#ifndef PXR_EXEC_VDF_SPARSE_INPUT_PATH_FINDER_H
#define PXR_EXEC_VDF_SPARSE_INPUT_PATH_FINDER_H
 
 
#include "pxr/pxr.h"
 
#include "pxr/exec/vdf/api.h"
#include "pxr/exec/vdf/connection.h"
#include "pxr/exec/vdf/request.h"
 
#include "pxr/base/tf/hash.h"
#include "pxr/base/tf/hashmap.h"
#include "pxr/base/tf/hashset.h"
#include "pxr/base/tf/stringUtils.h"
 
#include <vector>
 
PXR_NAMESPACE_OPEN_SCOPE
 
class VdfNode;
 
class VdfSparseInputPathFinder
{
public:
 
    typedef bool (*InputCallback)(const VdfInput &input);
 
    VDF_API
    static void Traverse(
        const VdfMaskedOutput &start,
        const VdfMaskedOutput &target,
        InputCallback inputCallback,
        std::vector<VdfConnectionConstVector> *paths);
 
    VDF_API
    static void FindAllCyclePaths(
        const VdfMaskedOutput &start,
        InputCallback inputCallback,
        std::vector<VdfConnectionConstVector> *paths);
 
// -----------------------------------------------------------------------------
 
private:
 
    VdfSparseInputPathFinder(
        const VdfMaskedOutput &start,
        const VdfMaskedOutput &target,
        InputCallback inputCallback,
        std::vector<VdfConnectionConstVector> *paths);
 
    // A class that represents a segment of a path.
    struct _PathSegment
    {
        _PathSegment()
        :   id(0), len(0) {}
 
        _PathSegment(unsigned int id, unsigned int len)
        :   id(id), len(len) {}
 
        // Equality operator.
        bool operator==(const _PathSegment &rhs) const {
            return id == rhs.id && len == rhs.len;
        }
        
        std::string GetAsString() const {
            return TfStringPrintf("{#%u / %u}", id, len);
        }
 
        unsigned int id, len;    // id and length of the segment
    };
 
    // A stack frame, aka. a masked output and its path segment pending to
    // be visited.
    struct _StackFrame : public _PathSegment
    {
        _StackFrame(
            const VdfMaskedOutput &maskedOutput,
            const _PathSegment &segment)
        :   _PathSegment(segment),
            maskedOutput(maskedOutput) {}
 
        VdfMaskedOutput maskedOutput;
    };
 
    // Objects of type _PotentialResult represent potential result paths.  They 
    // are created when the traversal encounters a previously visited connection
    // at \p encountered.  However, the moment we discover that path we don't
    // know if that path may or may not have results because we don't know if it 
    // has been traversed fully. 
    //
    // Therefore _PotentialResult objects are created and evaluated after the
    // traversal is finished.  Note that the \p ending segment ends at \p 
    // encountered by definition. 
    //
    struct _PotentialResult
    {
        _PotentialResult(
            const _PathSegment &ending, const _PathSegment &encountered)
        :   ending(ending),
            encountered(encountered) {}
 
        // Equality operator.
        bool operator==(const _PotentialResult &rhs) const {
            return ending == rhs.ending && encountered == rhs.encountered;
        }
 
        struct HashFunctor
        {
            size_t operator()(const _PotentialResult &p) const {
                return TfHash::Combine(
                    p.ending.id,
                    p.ending.len,
                    p.encountered.id,
                    p.encountered.len);
            }
        };
 
        // The ending path segment.
        _PathSegment ending;
 
        // The path and index being merged into.  Note that the len of 
        // encountered segment is the last element that is included in the 
        // path. 
        _PathSegment encountered;
    };
 
    using _VisitedDependencyToSegmentMap =
        TfHashMap<VdfMask, _PathSegment, VdfMask::HashFunctor>;
 
    // A map from VdfConnection pointer to _VisitedDependencyToSegmentMap. 
    // Tracks visited connections. 
    using _VisitedConnectionsInfoMap =
        TfHashMap<const VdfConnection *, _VisitedDependencyToSegmentMap, TfHash>;
 
    // A map from path to parent _PathSegment.  This is used to quickly find
    // parent path segments or a path.  Note that the parent is a path segment
    // because the parent path may continue after a child forked off it.
    using _PathToParentSegmentMap =
        TfHashMap<unsigned int, _PathSegment, TfHash>;
 
    // A map from path to result connection vector.  This map tracks the 
    // directly found results during traversal.  A directly found result is
    // when the traversal manages to find the result node without finding a
    // previously visited connection.
    using _PathToResultMap =
        TfHashMap<unsigned int, VdfConnectionConstVector, TfHash>;
 
    // A map from path to all its children paths.
    using _PathToPathChildrenMap =
        TfHashMap<unsigned int, std::vector<unsigned int>>;
 
    // A set of pending results.
    using _PotentialResults = 
        TfHashSet<_PotentialResult, _PotentialResult::HashFunctor>;
 
    // A map from path-id to first relevant input discovered.
    using _PathToRelevanceMap = 
        TfHashMap<unsigned int, const VdfInput *, TfHash>;
 
private:
 
    // Helper to traverse a frame.
    void _TraverseFrame(const _StackFrame &frame, bool isStartFrame);
 
    // Helper for _TraverseOutput.
    void _TraverseSeenConnection(
        const _PathSegment &ending, const _PathSegment &encountered);
 
    // Helper to build the full path from pathId (including all parent paths).
    VdfConnectionConstVector _BuildFullPath(
        const _PathSegment &end, const _PathSegment *start) const;
 
    // Helper to finalize pending results.
    void _FinalizePendingResults(
        std::vector<VdfConnectionConstVector> *paths) const;
 
    // Helper to _FinalizePendingResults().
    void _AppendChildPathsToWorkingSet(
        std::set<unsigned int> *pathToLookup,
        unsigned int pathId,
        const _PathSegment &encounteredSegment,
        unsigned int joiningPathId) const;
 
private:
 
    // The output that we are searching for.
    const VdfOutput *_targetOutput;
 
    // The input callback used to determine if a path is relevant.
    InputCallback _inputCallback;
 
    // The discovered paths index via path index.
    std::vector<VdfConnectionConstVector> _paths;
 
    // A map from path-id to relevance group.
    _PathToRelevanceMap _pathToRelevanceMap;
 
    // Map from VdfConnection pointer to _PathSegment.  Tracks visited
    // connections.
    _VisitedConnectionsInfoMap _visitedConnectionsInfoMap;
 
    // Map from path to parent _PathSegment.  This is used to quickly find
    // parent path segments or a path.  Note that the parent is a path segment
    // because the parent path may continue after a child forked off it.
    _PathToParentSegmentMap _pathToParentSegmentMap;
 
    // A map from path to all its children paths.
    _PathToPathChildrenMap _pathToPathChildrenMap;
 
    // A map from path to result connection vector.  This map tracks the 
    // directly found results during traversal.  A directly found result is
    // when the traversal manages to find the result node without finding a
    // previously visited connection.  Note that not all paths have results.
    _PathToResultMap _pathToResultMap;
 
    // A vector of pending stack frames for traversal.
    std::vector<_StackFrame> _stack;
 
    // A set of pending results.
    _PotentialResults _potentialResults;
};
 
#endif
 
PXR_NAMESPACE_CLOSE_SCOPE