Digraph.h

#pragma once
 
#include <boost/container/flat_map.hpp>
#include <boost/range/adaptor/transformed.hpp>
#include <boost/range/iterator_range.hpp>
 
#include <fstream>
#include <optional>
#include <type_traits>
#include <unordered_map>
 
namespace xrpl {
namespace detail {
// Dummy class when no edge data needed for graph
struct NoEdgeData
{
};
 
}  // namespace detail
 
namespace test::csf {

template <class Vertex, class EdgeData = detail::NoEdgeData>
class Digraph
{
    using Links = boost::container::flat_map<Vertex, EdgeData>;
    using Graph = boost::container::flat_map<Vertex, Links>;
    Graph graph_;
 
    // Allows returning empty iterables for unknown vertices
    Links empty_;
 
public:
    bool
    connect(Vertex source, Vertex target, EdgeData e)
    {
        return graph_[source].emplace(target, e).second;
    }

    bool
    connect(Vertex source, Vertex target)
    {
        return connect(source, target, EdgeData{});
    }

    bool
    disconnect(Vertex source, Vertex target)
    {
        auto it = graph_.find(source);
        if (it != graph_.end())
        {
            return it->second.erase(target) > 0;
        }
        return false;
    }

    [[nodiscard]] std::optional<EdgeData>
    edge(Vertex source, Vertex target) const
    {
        auto it = graph_.find(source);
        if (it != graph_.end())
        {
            auto edgeIt = it->second.find(target);
            if (edgeIt != it->second.end())
                return edgeIt->second;
        }
        return std::nullopt;
    }

    [[nodiscard]] bool
    connected(Vertex source, Vertex target) const
    {
        return edge(source, target) != std::nullopt;
    }

    [[nodiscard]] auto
    outVertices() const
    {
        return boost::adaptors::transform(
            graph_, [](Graph::value_type const& v) { return v.first; });
    }

    [[nodiscard]] auto
    outVertices(Vertex source) const
    {
        auto transform = [](Links::value_type const& link) { return link.first; };
        auto it = graph_.find(source);
        if (it != graph_.end())
            return boost::adaptors::transform(it->second, transform);
 
        return boost::adaptors::transform(empty_, transform);
    }

    struct Edge
    {
        Vertex source;
        Vertex target;
        EdgeData data;
    };

    [[nodiscard]] auto
    outEdges(Vertex source) const
    {
        auto transform = [source](Links::value_type const& link) {
            return Edge{source, link.first, link.second};
        };
 
        auto it = graph_.find(source);
        if (it != graph_.end())
            return boost::adaptors::transform(it->second, transform);
 
        return boost::adaptors::transform(empty_, transform);
    }

    [[nodiscard]] std::size_t
    outDegree(Vertex source) const
    {
        auto it = graph_.find(source);
        if (it != graph_.end())
            return it->second.size();
        return 0;
    }

    template <class VertexName>
    void
    saveDot(std::ostream& out, VertexName&& vertexName) const
    {
        out << "digraph {\n";
        for (auto const& [vertex, links] : graph_)
        {
            auto const fromName = vertexName(vertex);
            for (auto const& eData : links)
            {
                auto const toName = vertexName(eData.first);
                out << fromName << " -> " << toName << ";\n";
            }
        }
        out << "}\n";
    }
 
    template <class VertexName>
    void
    saveDot(std::string const& fileName, VertexName&& vertexName) const
    {
        std::ofstream out(fileName);
        saveDot(out, std::forward<VertexName>(vertexName));
    }
};
 
}  // namespace test::csf
 
}  // namespace xrpl