Function DFS

catboost/libs/fstr/feature_str.cpp:225–271

}

static void DFS(const TFullModel& model, const THashMap<TFeature, int, TFeatureHash>& featureToIdx, ui32 nodeIdx, TVector<std::pair<int, int>>* pathPtr, THashMap<std::pair<int, int>, double>* sumInteractionsPtr) {
    const int split = model.ModelTrees->GetModelTreeData()->GetTreeSplits()[nodeIdx];
    const auto& binFeatures = model.ModelTrees->GetBinFeatures();
    const auto& node = model.ModelTrees->GetModelTreeData()->GetNonSymmetricStepNodes()[nodeIdx];

    const auto& feature = GetFeature(model, binFeatures[split]);
    const int featureIdx = featureToIdx.at(feature);

    const ui32 leftNodeIdx = nodeIdx + node.LeftSubtreeDiff;
    const ui32 rightNodeIdx = nodeIdx + node.RightSubtreeDiff;

    int sign = -1;

    if (leftNodeIdx == nodeIdx || rightNodeIdx == nodeIdx) { // terminal

        const auto leafValues = model.ModelTrees->GetModelTreeData()->GetLeafValues();
        const int approxDimension = model.ModelTrees->GetDimensionsCount();
        const int leafValueIndex = model.ModelTrees->GetModelTreeData()->GetNonSymmetricNodeIdToLeafId()[nodeIdx];
        double delta = std::accumulate(leafValues.begin() + leafValueIndex,
                                      leafValues.begin() + leafValueIndex + approxDimension, 0.);

        for (ui32 firstIdx = 0; firstIdx < pathPtr->size(); ++firstIdx) {
            for (ui32 secondIdx = firstIdx + 1; secondIdx < pathPtr->size(); ++secondIdx) {
                int srcFeature1 = pathPtr->at(firstIdx).first;
                int srcFeature2 = pathPtr->at(secondIdx).first;
                if (srcFeature2 < srcFeature1) {
                    DoSwap(srcFeature1, srcFeature2);
                }
                if (srcFeature1 == srcFeature2) {
                    continue;
                }
                int sign = pathPtr->at(firstIdx).second * pathPtr->at(secondIdx).second;
                (*sumInteractionsPtr)[std::make_pair(srcFeature1, srcFeature2)] += sign * delta;
            }
        }
    }

    for (const ui32& childIdx: {leftNodeIdx, rightNodeIdx}) {
        if (childIdx != nodeIdx) {
            pathPtr->push_back({featureIdx, sign});
            DFS(model, featureToIdx, childIdx, pathPtr, sumInteractionsPtr);
            sign *= -1;
            pathPtr->pop_back();
        }
    }

}

TVector<TFeaturePairInteractionInfo> CalcMostInteractingFeatures(const TFullModel& model,
                                                                 const THashMap<TFeature, int, TFeatureHash>& featureToIdx,