TrustGraph.h

#ifndef XRPL_TEST_CSF_UNL_H_INCLUDED
#define XRPL_TEST_CSF_UNL_H_INCLUDED
 
#include <test/csf/random.h>
 
#include <boost/container/flat_set.hpp>
 
#include <chrono>
#include <numeric>
#include <random>
#include <vector>
 
namespace ripple {
namespace test {
namespace 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
    bool
    trusts(Peer const& from, Peer const& to) const
    {
        return graph_.connected(from, to);
    }
 
    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
    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 (int i = 0; i < uniqueUNLs.size(); ++i)
        {
            for (int j = (i + 1); j < uniqueUNLs.size(); ++j)
            {
                auto const& unlA = uniqueUNLs[i];
                auto const& unlB = uniqueUNLs[j];
                double rhs =
                    2.0 * (1. - quorum) * std::max(unlA.size(), unlB.size());
 
                int 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;
    }
 
    bool
    canFork(double quorum) const
    {
        return !forkablePairs(quorum).empty();
    }
};
 
}  // namespace csf
}  // namespace test
}  // namespace ripple
 
#endif