TrustGraph.h

#pragma once
 
#include <boost/container/flat_set.hpp>
 
#include <csf/Digraph.h>
 
#include <algorithm>
#include <set>
#include <vector>
 
namespace xrpl::test::csf {

template <class Peer>
class TrustGraph
{
    using Graph = Digraph<Peer>;
 
    Graph graph_;
 
public:
    TrustGraph() = default;
 
    Graph const&
    graph()
    {
        return graph_;
    }

    void
    trust(Peer const& from, Peer const& to)
    {
        graph_.connect(from, to);
    }

    void
    untrust(Peer const& from, Peer const& to)
    {
        graph_.disconnect(from, to);
    }
 
    //< Whether from trusts to
    [[nodiscard]] bool
    trusts(Peer const& from, Peer const& to) const
    {
        return graph_.connected(from, to);
    }

    [[nodiscard]] auto
    trustedPeers(Peer const& a) const
    {
        return graph_.outVertices(a);
    }

    struct ForkInfo
    {
        std::set<Peer> unlA;
        std::set<Peer> unlB;
        int overlap;
        double required;
    };
 
    //< Return nodes that fail the white-paper no-forking condition
    [[nodiscard]] std::vector<ForkInfo>
    forkablePairs(double quorum) const
    {
        // Check the forking condition by looking at intersection
        // of UNL between all pairs of nodes.
 
        // TODO: Use the improved bound instead of the whitepaper bound.
 
        using UNL = std::set<Peer>;
        std::set<UNL> unique;
        for (Peer const peer : graph_.outVertices())
        {
            unique.emplace(std::begin(trustedPeers(peer)), std::end(trustedPeers(peer)));
        }
 
        std::vector<UNL> uniqueUNLs(unique.begin(), unique.end());
        std::vector<ForkInfo> res;
 
        // Loop over all pairs of uniqueUNLs
        for (auto i = 0uz; i < uniqueUNLs.size(); ++i)
        {
            for (auto j = i + 1; j < uniqueUNLs.size(); ++j)
            {
                auto const& unlA = uniqueUNLs[i];
                auto const& unlB = uniqueUNLs[j];
                double const rhs = 2.0 * (1. - quorum) * std::max(unlA.size(), unlB.size());
 
                int const intersectionSize = std::count_if(
                    unlA.begin(), unlA.end(), [&](Peer p) { return unlB.find(p) != unlB.end(); });
 
                if (intersectionSize < rhs)
                {
                    res.emplace_back(ForkInfo{unlA, unlB, intersectionSize, rhs});
                }
            }
        }
        return res;
    }

    [[nodiscard]] bool
    canFork(double quorum) const
    {
        return !forkablePairs(quorum).empty();
    }
};
 
}  // namespace xrpl::test::csf