KraView  Changes On Branch complete

cmake_minimum_required(VERSION 3.6)

project(
  fifrgraph
  VERSION 0.1.0
  LANGUAGES CXX)

add_subdirectory(src/fifr/graph)

# Enable testing if this is toplevel.
if ( BUILD_TESTING AND (CMAKE_PROJECT_NAME STREQUAL PROJECT_NAME) )
  enable_testing()
  add_subdirectory(tests)
endif ()


# package stuff

include(CMakePackageConfigHelpers)
write_basic_package_version_file(
  "${CMAKE_CURRENT_BINARY_DIR}/FifrGraph/FifrGraphConfigVersion.cmake"
  VERSION ${fifrgraph_VERSION}
  COMPATIBILITY SameMajorVersion
  )

export(
  EXPORT FifrGraphTargets
  FILE "${CMAKE_CURRENT_BINARY_DIR}/FifrGraph/FifrGraphTargets.cmake"
  NAMESPACE Fifr::
  )
configure_file(cmake/FifrGraphConfig.cmake
  "${CMAKE_CURRENT_BINARY_DIR}/FifrGraph/FifrGraphConfig.cmake"
  COPYONLY)

set(ConfigPackageLocation lib/cmake/FifrGraph)
install(EXPORT FifrGraphTargets
  FILE FifrGraphTargets.cmake
  NAMESPACE Fifr::
  DESTINATION ${ConfigPackageLocation}
  )
install(
  FILES
  cmake/FifrGraphConfig.cmake
  "${CMAKE_CURRENT_BINARY_DIR}/FifrGraph/FifrGraphConfigVersion.cmake"
  DESTINATION ${ConfigPackageLocation}
  COMPONENT
  devel
  )

include("${CMAKE_CURRENT_LIST_DIR}/FifrGraphTargets.cmake")

/*
 * Copyright (c) 2018 Frank Fischer <frank-fischer@shadow-soft.de>
 *
 * This program is free software: you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see  <http://www.gnu.org/licenses/>
 */

#ifndef __FIFR_GRAPH_ATTRIBUTEDGRAPH_HXX__
#define __FIFR_GRAPH_ATTRIBUTEDGRAPH_HXX__

#include <iosfwd>
#include <vector>

namespace fifr {
namespace graph {
template <typename Graph, typename G, typename V, typename E>
class AttributedGraph : public Graph
{
public:
    using size_type = typename Graph::size_type;
    using node_type = typename Graph::node_type;
    using edge_type = typename Graph::edge_type;
    using id_type = typename Graph::id_type;

    class builder : protected Graph::builder
    {
        friend class AttributedGraph;

    public:
        explicit builder(size_type node_capacity = 0, size_type edge_capacity = 0)
            : Graph::builder(node_capacity, edge_capacity)
        {
            node_attrs_.reserve(node_capacity);
            edge_attrs_.reserve(edge_capacity);
        }

        explicit builder(G attrs) : attrs_(std::move(attrs)) {}

        node_type add_node(V v = {})
        {
            node_attrs_.push_back(v);
            return Graph::builder::add_node();
        }

        std::vector<node_type> add_nodes(size_type n)
        {
            node_attrs_.resize(node_attrs_.size() + n, {});
            return Graph::builder::add_nodes(n);
        }

        std::vector<node_type> add_nodes(const std::vector<V>& attrs)
        {
            auto n = attrs.size();
            for (auto&& v : attrs) {
                node_attrs_.push_back(std::move(v));
            }
            return Graph::builder::add_nodes(n);
        }

        using Graph::builder::id2node;
        using Graph::builder::node_id;

        V& node(node_type u) { return node_attrs_.at(Graph::builder::node_id(u)); }

        const V& node(node_type u) const { return node_attrs_.at(Graph::builder::node_id(u)); }

        edge_type add_edge(node_type u, node_type v, E e = {})
        {
            edge_attrs_.push_back(std::move(e));
            return Graph::builder::add_edge(u, v);
        }

        using Graph::builder::edge_id;
        using Graph::builder::id2edge;

        E& edge(edge_type e) { return edge_attrs_.at(Graph::builder::edge_id(e)); }

        const E& edge(edge_type e) const { return edge_attrs_.at(Graph::builder::edge_id(e)); }

    private:
        G attrs_;
        std::vector<V> node_attrs_;
        std::vector<E> edge_attrs_;
    };

public:
    AttributedGraph() = default;

    AttributedGraph(AttributedGraph&& g) noexcept = default;
    explicit AttributedGraph(const AttributedGraph& g) = default;
    AttributedGraph& operator=(AttributedGraph&& g) noexcept = default;
    AttributedGraph& operator=(const AttributedGraph& g) = delete;
    ~AttributedGraph() = default;

    explicit AttributedGraph(builder&& b)
        : Graph(std::move(b)),
          attrs_(std::move(b.attrs_)),
          node_attrs_(std::move(b.node_attrs_)),
          edge_attrs_(std::move(b.edge_attrs_))
    {
    }

    explicit AttributedGraph(typename Graph::builder&& b)
        : Graph(std::move(b)), attrs_{}, node_attrs_(Graph::num_nodes()), edge_attrs_(Graph::num_edges())
    {
    }

    G& attr() { return attrs_; }
    const G& attr() const { return attrs_; }

    G& operator*() { return attrs_; }
    const G& operator*() const { return attrs_; }

    G* operator->() { return &attrs_; }
    const G* operator->() const { return &attrs_; }

    V& node(node_type u) { return node_attrs_[Graph::node_id(u)]; }
    const V& node(node_type u) const { return node_attrs_[Graph::node_id(u)]; }

    V& operator[](node_type u) { return node(u); }
    const V& operator[](node_type u) const { return node(u); }

    E& edge(edge_type e) { return edge_attrs_[Graph::edge_id(e)]; }
    const E& edge(edge_type e) const { return edge_attrs_[Graph::edge_id(e)]; }

    E& operator[](edge_type e) { return edge(e); }
    const E& operator[](edge_type e) const { return edge(e); }

    template <typename Gr_, typename G_, typename V_, typename E_>
    friend std::ostream& operator<<(std::ostream& out, const AttributedGraph<Gr_, G_, V_, E_>& g);
    template <typename Gr_, typename G_, typename V_, typename E_>
    friend std::istream& operator>>(std::istream& in, AttributedGraph<Gr_, G_, V_, E_>& g);

private:
    G attrs_;
    std::vector<V> node_attrs_;
    std::vector<E> edge_attrs_;
};

}  // namespace graph
}  // namespace fifr

#endif

/*
 * Copyright (c) 2018 Frank Fischer <frank-fischer@shadow-soft.de>
 *
 * This program is free software: you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see  <http://www.gnu.org/licenses/>
 */

#include "AttributedGraph.hxx"

#include <fifr/util/PrettyStruct.hxx>

namespace fifr {
namespace graph {
template <typename Graph, typename G, typename V, typename E>
std::ostream& operator<<(std::ostream& out, const AttributedGraph<Graph, G, V, E>& g)
{
    fifr::util::pretty_print_struct_multiline(out,
                                              "AttributedGraph",
                                              "graph",
                                              static_cast<const Graph&>(g),
                                              "attrs",
                                              g.attrs_,
                                              "nodes",
                                              fifr::util::multiline(g.node_attrs_),
                                              "edges",
                                              fifr::util::multiline(g.edge_attrs_));
    return out;
}

template <typename Graph, typename G, typename V, typename E>
std::istream& operator>>(std::istream& in, AttributedGraph<Graph, G, V, E>& g)
{
    fifr::util::pretty_read_struct(in,
                                   "AttributedGraph",
                                   "graph",
                                   static_cast<Graph&>(g),
                                   "attrs",
                                   g.attrs_,
                                   "nodes",
                                   g.node_attrs_,
                                   "edges",
                                   g.edge_attrs_);
    if (g.node_attrs_.size() != g.num_nodes()) {
        throw fifr::util::ReadError("Invalid number of node attributes");
    }
    if (g.edge_attrs_.size() != g.num_edges()) {
        throw fifr::util::ReadError("Invalid number of edge attributes");
    }
    return in;
}
}  // namespace graph
}  // namespace fifr

cmake_minimum_required(VERSION 3.6)

cmake_policy(SET CMP0063 NEW)

add_library(Graph STATIC
  Grav.cxx
  LinkedListGraph.cxx
  LinkedListGraphIO.cxx)
add_library(Fifr::Graph ALIAS Graph)

set_property(TARGET Graph PROPERTY OUTPUT_NAME fifrgraph)
target_compile_features(Graph PUBLIC cxx_std_20)

if (CMAKE_CXX_COMPILER_ID MATCHES "Clang|GNU")
  target_compile_options(Graph PRIVATE -W -Wall -pedantic)
endif ()

# Packages

if (NOT TARGET Fifr::Util)
  find_package(FifrUtil REQUIRED)
endif()
target_link_libraries(Graph Fifr::Util)

# Install stuff

target_include_directories(Graph INTERFACE
  $<INSTALL_INTERFACE:include>
  $<BUILD_INTERFACE:${CMAKE_CURRENT_SOURCE_DIR}/../..>)

install(
  TARGETS Graph
  EXPORT FifrGraphTargets
  ARCHIVE DESTINATION lib
  LIBRARY DESTINATION lib
  INCLUDES DESTINATION include
  )

install(
  DIRECTORY .
  DESTINATION include/fifr/graph
  COMPONENT headers
  FILES_MATCHING PATTERN "*.hxx"
  )

/*
 * Copyright (c) 2024 Frank Fischer <frank-fischer@shadow-soft.de>
 *
 * This program is free software: you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see  <http://www.gnu.org/licenses/>
 */

#ifndef __FIFR_GRAPH_CLASSES_HXX__
#define __FIFR_GRAPH_CLASSES_HXX__

#include <cstddef>
#include <memory>

namespace fifr {
namespace graph {
/// Return a cycle.
///
/// If the graph is directed the cycle will be a directed cycle.
template <typename G>
G cycle(std::size_t n)
{
    typename G::builder builder(n, n);
    auto nodes = builder.add_nodes(n);
    for (std::size_t i = 0; i < nodes.size(); ++i) {
        builder.add_edge(nodes[i], nodes[(i + 1) % nodes.size()]);
    }
    return G(std::move(builder));
}

/// Return a complete bipartite graph.
///
/// The edges are directed from the `n` to the `m` nodes.
template <typename G>
G complete_bipartite(std::size_t n, std::size_t m)
{
    typename G::builder builder(n + m, n * m);
    auto a_nodes = builder.add_nodes(n);
    auto b_nodes = builder.add_nodes(m);
    for (auto u : a_nodes) {
        for (auto v : b_nodes) {
            builder.add_edge(u, v);
        }
    }
    return G(std::move(builder));
}

/// Return a Peterson graph.
template <typename G>
G peterson()
{
    typename G::builder builder(10, 15);
    auto nodes = builder.add_nodes(10);
    for (std::size_t i = 0; i < 5; i++) {
        builder.add_edge(nodes[i], nodes[(i + 1) % 5]);
        builder.add_edge(nodes[i + 5], nodes[((i + 1) % 5) + 5]);
        builder.add_edge(nodes[i], nodes[i + 5]);
    }
    return G(std::move(builder));
}

/// Return a hypercube of dimension `d`.
template <typename G>
G hypercube(std::size_t d)
{
    // TODO: check size of d
    std::size_t n = 1 << d;
    typename G::builder builder(n, n * d);
    auto nodes = builder.add_nodes(n);
    for (std::size_t i = 0; i < n; i++) {
        for (std::size_t bit = 0; bit < d; bit++) {
            if ((i & (1 << bit)) == 0) {
                builder.add_edge(nodes[i], nodes[i | (1 << bit)]);
            }
        }
    }
    return G(std::move(builder));
}

}  // namespace graph
}  // namespace fifr

#endif

/*
 * Copyright (c) 2017 Frank Fischer
 *
 * This file is part of KraView.
 *
 * KraView is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * KraView is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with KraView.  If not, see <http://www.gnu.org/licenses/>.
 */

#include "Grav.hxx"

#include <fifr/util/Convert.hxx>

#include <algorithm>
#include <charconv>
#include <istream>
#include <optional>
#include <sstream>
#include <unordered_map>
#include <utility>
#include <vector>

using namespace fifr::util;

namespace {
template <typename T>
auto str2num(const std::string& str, std::string::size_type beg, std::string::size_type& endpos) -> std::optional<T>
{
    T n;
    // Skip whitespace at the beginning
    while (beg < str.size() && isspace(str[beg]) != 0) {
        beg++;
    }
    auto result = std::from_chars(&str[beg], &str[str.size()], n);
    if (result.ec == std::errc()) {
        endpos = static_cast<std::string::size_type>(result.ptr - str.c_str());
        return {n};
    }
    endpos = beg;
    return std::nullopt;
}

std::optional<unsigned long> str2ul(const std::string& str, std::string::size_type beg, std::string::size_type& endpos)
{
    return str2num<unsigned long>(str, beg, endpos);
}

std::optional<unsigned> str2u(const std::string& str, std::string::size_type beg, std::string::size_type& endpos)
{
    return str2num<unsigned>(str, beg, endpos);
}

std::optional<double> str2d(const std::string& str, std::string::size_type beg, std::string::size_type& endpos)
{
    char* end = nullptr;
    auto n = std::strtod(str.c_str() + beg, &end);  // NOLINT
    if (end != nullptr && end >= str.c_str()) {
        endpos = static_cast<std::string::size_type>(end - str.c_str());
        return {n};
    }
    endpos = beg;
    return {};
}
}  // namespace

namespace fifr {
namespace graph {
namespace grav {
std::string Attributes::operator[](const std::string& attr) const
{
    for (auto&& it : *this) {
        if (it.first == attr) {
            return it.second;
        }
    }
    return {};
}

Attributes::const_iterator& Attributes::const_iterator::operator++()
{
    auto pos = data_.find('\0', pos_);
    if (pos != std::string::npos) {
        pos = data_.find('\0', pos + 1);
        if (pos != std::string::npos) {
            pos_ = pos + 1;
        } else {
            pos_ = data_.size();
        }
    } else {
        pos_ = data_.size();
    }
    return *this;
}

Attributes::const_iterator::value_type Attributes::const_iterator::operator*() const
{
    auto keyend = data_.find('\0', pos_);
    if (keyend == std::string::npos) {
        return {data_.substr(pos_), {}};
    }
    auto valend = data_.find('\0', keyend + 1);
    return {data_.substr(pos_, keyend - pos_), data_.substr(keyend + 1, valend - keyend - 1)};
}

static Net::Node add_node(Net::builder& net,
                          std::unordered_map<unsigned, Net::Node>& nodes_by_number,
                          size_type nodenumber,
                          NodeInfo nodedata)
{
    auto ret = nodes_by_number.insert({nodenumber, Net::nonode});

    if (ret.second) {
        ret.first->second = net.add_node(std::move(nodedata));
    } else {
        net.node(ret.first->second) = std::move(nodedata);
    }

    return ret.first->second;
}

static std::string::size_type parse_uint(const std::string& line, std::string::size_type pos, unsigned& n)
{
    std::string::size_type end;
    auto nn = str2u(line, pos, end);
    if (nn && (end == line.size() || isspace(line[end]) != 0)) {
        n = *nn;
        return end;
    }
    throw ReadError(std::string("Expected number, got '") + line.substr(pos) + "'");
}

static std::string::size_type parse_double(const std::string& line, std::string::size_type pos, double& n)
{
    std::string::size_type end;
    auto nn = str2d(line, pos, end);
    if (nn && (end == line.size() || isspace(line[end]) != 0)) {
        n = *nn;
        return end;
    }
    throw ReadError("Expected number, got '" + line.substr(pos) + "'");
}

static std::string::size_type parse_color(const std::string& line, std::string::size_type pos, Color& c)
{
    std::string::size_type end;

    auto r = str2ul(line, pos, end);
    if (!r || end >= line.size() || line[end] != ',') {
        throw ReadError("Invalid RGB color: " + line.substr(pos));
    }
    if (*r >= 256) {
        throw ReadError("Invalid red value in RGB color: " + line.substr(pos, end - pos));
    }

    pos = end + 1;
    auto g = str2ul(line, pos, end);
    if (!g || end >= line.size() || line[end] != ',') {
        throw ReadError("Invalid RGB color: " + line.substr(pos));
    }
    if (*g >= 256) {
        throw ReadError("Invalid green RGB color: " + line.substr(pos, end - pos));
    }

    pos = end + 1;
    auto b = str2ul(line, pos, end);
    if (!b || (end < line.size() && line[end] != ',' && isspace(line[end]) == 0)) {
        throw ReadError("Invalid RGB color: " + line.substr(pos));
    }
    if (end < line.size() && line[end] == ',') {
        // alpha value following
        pos = end + 1;
        auto a = str2d(line, pos, end);
        if (!a || (end < line.size() && isspace(line[end]) == 0)) {
            throw ReadError("Invalid RGB color: " + line.substr(pos));
        }
        if (a < -1e-6 || a > 1 + 1e-6) {
            throw ReadError("Invalid alpha value for color: " + line.substr(pos, end - pos));
        }
        c.alpha = *a;
    } else if (*b >= 256) {
        throw ReadError("Invalid blue RGB color: " + line.substr(pos, end - pos));
    }

    c.r = static_cast<uint8_t>(*r);
    c.g = static_cast<uint8_t>(*g);
    c.b = static_cast<uint8_t>(*b);

    return end;
}

static void parse_node_options(NodeInfo& node, const std::string& line, std::string::size_type pos, unsigned& desclen)
{
    desclen = 0;
    for (;;) {
        pos = line.find_first_not_of(" \t\r\n", pos);
        if (pos == std::string::npos) {
            break;
        }
        auto end = line.find_first_of(": \t\r\n", pos);
        if (end != std::string::npos && line[end] == ':') {
            if (line.compare(pos, end - pos, "x") == 0) {
                end = parse_double(line, end + 1, node.x);
            } else if (line.compare(pos, end - pos, "y") == 0) {
                end = parse_double(line, end + 1, node.y);
            } else if (line.compare(pos, end - pos, "weight") == 0) {
                end = parse_double(line, end + 1, node.weight);
            } else if (line.compare(pos, end - pos, "color") == 0) {
                end = parse_color(line, end + 1, node.color);
            } else if (line.compare(pos, end - pos, "desc") == 0) {
                end = parse_uint(line, end + 1, desclen);
            } else {
                throw ReadError("Unknown node option: " + line.substr(pos, end));
            }
        } else {
            if (end == std::string::npos) {
                end = line.size();
            }
            if (line.compare(pos, end - pos, "circ") == 0) {
                node.type = NodeType::Circle;
            } else if (line.compare(pos, end - pos, "disc") == 0) {
                node.type = NodeType::Disc;
            } else {
                throw ReadError("Unknown node option: " + line.substr(pos, end));
            }
        }
        pos = end;
    }
}

static Net::Node parse_node(Net::builder& net,
                            std::unordered_map<unsigned, Net::Node>& nodes_by_number,
                            const std::string& line,
                            std::string::size_type pos,
                            NodeInfo& defaultnode,
                            unsigned& desc)
{
    assert(line.size() < std::numeric_limits<std::string::size_type>::max());
    assert(line.size() < std::numeric_limits<unsigned>::max());

    desc = 0;

    std::string::size_type end;
    auto nodenr = str2ul(line, pos, end);

    if (end == line.size() || (isspace(line[end]) != 0)) {
        auto nodeid = add_node(net, nodes_by_number, *nodenr, defaultnode);
        auto& ndata = net.node(nodeid);
        if (end != line.size()) {
            parse_node_options(ndata, line, end, desc);
        }
        return nodeid;
    }
    parse_node_options(defaultnode, line, end, desc);
    if (desc > 0) {
        throw ReadError("Description not allowed for default options");
    }
    return Net::nonode;
}

static void parse_arc_options(EdgeInfo& edge, const std::string& line, std::string::size_type pos, unsigned& desclen)
{
    for (;;) {
        pos = line.find_first_not_of(" \t\r\n", pos);
        if (pos == std::string::npos) {
            break;
        }
        auto end = line.find(':', pos);
        if (end == std::string::npos) {
            throw ReadError("Unknown arc option: " + line.substr(pos, end));
        }
        if (line.compare(pos, end - pos, "flow") == 0) {
            end = parse_double(line, end + 1, edge.flow);
        } else if (line.compare(pos, end - pos, "cost") == 0) {
            end = parse_double(line, end + 1, edge.cost);
        } else if (line.compare(pos, end - pos, "color") == 0) {
            end = parse_color(line, end + 1, edge.color);
        } else if (line.compare(pos, end - pos, "desc") == 0) {
            end = parse_uint(line, end + 1, desclen);
        } else {
            throw ReadError("Unknown arc option: " + line.substr(pos, end));
        }
        pos = end;
    }
}

static Net::Edge parse_arc(Net::builder& net,
                           const std::unordered_map<unsigned, Net::Node>& nodes_by_number,
                           const std::string& line,
                           std::string::size_type pos,
                           EdgeInfo& defaultedge,
                           unsigned& desc)
{
    std::string::size_type end;
    auto srcnr = str2u(line, pos, end);
    if (srcnr && (end == line.size() || (isspace(line[end]) != 0))) {
        auto snknr = str2u(line, end, end);
        if (!snknr || (end < line.size() && (isspace(line[end]) == 0))) {
            throw ReadError("Invalid arc line: " + line);
        }

        auto srcit = nodes_by_number.find(*srcnr);
        if (srcit == nodes_by_number.end()) {
            throw ReadError("Unknown source node: " + std::to_string(*srcnr));
        }
        auto src = srcit->second;

        auto snkit = nodes_by_number.find(*snknr);
        if (snkit == nodes_by_number.end()) {
            throw ReadError("Unknown sink node: " + std::to_string(*snknr));
        }
        auto snk = snkit->second;

        auto arcid = net.add_edge(src, snk, defaultedge);
        parse_arc_options(net.edge(arcid), line, end, desc);
        return arcid;
    }
    parse_arc_options(defaultedge, line, end, desc);
    if (desc > 0) {
        throw ReadError("Description not allowed for default options");
    }

    return Net::noedge;
}

static Net read_net_from_lines(const NetSequence::getline_function& getline, size_type& lineno)
{
    NodeInfo defaultnode;
    defaultnode.x = 0;
    defaultnode.y = 0;
    defaultnode.color = Color{0, 0, 0, 1.0};
    defaultnode.type = NodeType::Circle;
    defaultnode.weight = 0;

    EdgeInfo defaultedge;
    defaultedge.color = Color{0, 0, 0, 1.0};
    defaultedge.flow = 0;
    defaultedge.cost = 0;

    Net::builder net;
    std::unordered_map<unsigned, Net::Node> nodes_by_number;

    std::string line;
    std::string desc;
    char* locale = setlocale(LC_NUMERIC, "C");
    try {
        bool found_end = false;
        while (getline(line, 0)) {
            lineno += 1;

            std::string::size_type pos = line.find('#');
            pos = line.find_last_not_of(" \t\r", pos);
            if (pos == std::string::npos) {
                continue;  // empty line
            }
            line.erase(pos + 1, std::string::npos);
            pos = line.find_first_not_of(" \t\r");

            auto end = line.find_first_of(" \t\r\n", pos);
            if (end == std::string::npos) {
                end = line.size();
            }
            if (line.compare(pos, end - pos, "node") == 0) {
                unsigned desclen = 0;
                Net::Node nodeid = parse_node(net, nodes_by_number, line, end + 1, defaultnode, desclen);
                if (desclen > 0) {
                    NodeInfo& n = net.node(nodeid);
                    if (!getline(desc, desclen)) {
                        throw ReadError("Too few bytes for description data.");
                    }
                    for (auto& it : desc) {
                        if (it == '\n') {
                            it = '\0';
                            lineno += 1;
                        }
                    }
                    n.attributes = Attributes(std::move(desc));
                }
            } else if (line.compare(pos, end - pos, "arc") == 0 || line.compare(pos, end - pos, "edge") == 0) {
                unsigned desclen = 0;
                Net::Edge arcid = parse_arc(net, nodes_by_number, line, end + 1, defaultedge, desclen);
                if (arcid != Net::noedge && line.compare(pos, end - pos, "edge") == 0) {
                    net.edge(arcid).directed = false;
                }
                if (desclen > 0) {
                    EdgeInfo& a = net.edge(arcid);
                    if (!getline(desc, desclen)) {
                        throw ReadError("Too few bytes for description data.");
                    }

                    for (auto& it : desc) {
                        if (it == '\n') {
                            it = '\0';
                            lineno += 1;
                        }
                    }
                    a.attributes = Attributes(std::move(desc));
                }
            } else if (line.compare(pos, end - pos, "end") == 0) {
                found_end = true;
                break;
            } else {
                throw ReadError(std::string("Unknown command: ") + line.substr(pos, end - pos) +
                                " (expected 'arc', 'edge' or 'node')");
            }
        }
        if (!found_end) {
            throw ReadError("Unexpected end of file (missing 'end' line?)");
        }
    } catch (ReadError& e) {
        e.set_line(lineno);
        setlocale(LC_NUMERIC, locale);
        throw;
    } catch (...) {
        setlocale(LC_NUMERIC, locale);
        throw;
    }
    setlocale(LC_NUMERIC, locale);

    return Net(std::move(net));
}

struct NetSequence::Data {
    std::string name;
    std::vector<Net> steps;
};

NetSequence::NetSequence(const std::string& name) : d(new Data{name, {}}) {}

NetSequence::NetSequence(NetSequence&& net) noexcept : d(std::move(net.d)) {}

NetSequence& NetSequence::operator=(NetSequence&& net) noexcept
{
    d = std::move(net.d);
    return *this;
}

NetSequence::~NetSequence() = default;

std::size_t NetSequence::size() const
{
    return d->steps.size();
}

const std::string& NetSequence::name() const
{
    return d->name;
}

const Net& NetSequence::operator[](std::size_t i) const
{
    return d->steps.at(i);
}

void NetSequence::add(Net net)
{
    d->steps.push_back(std::move(net));
}

NetSequence::Series NetSequence::from_stream(std::istream& in, const readgraph_function& readgraph, Series&& series)
{
    size_type lineno = 0;
    return NetSequence::from_stream(in, readgraph, lineno, std::move(series));
}

NetSequence::Series NetSequence::from_stream(std::istream& in,
                                             const readgraph_function& readgraph,
                                             size_type& lineno,
                                             Series&& series)
{
    return from_lines(
        [&](std::string& line, std::size_t len) {
            if (in.good()) {
                if (len == 0) {
                    std::getline(in, line);
                } else {
                    line.resize(len);
                    in.read(&(line[0]), static_cast<std::streamsize>(len));
                    return in.gcount() == (int)len;
                }
                return true;
            }
            return false;
        },
        readgraph,
        lineno,
        std::move(series));
}

NetSequence::Series NetSequence::from_lines(const getline_function& getline,
                                            const readgraph_function& readgraph,
                                            Series&& series)
{
    size_type lineno = 0;
    return from_lines(getline, readgraph, lineno, std::move(series));
}

NetSequence::Series NetSequence::from_lines(const getline_function& getline,
                                            const readgraph_function& readgraph,
                                            size_type& lineno,
                                            Series&& series)
{
    std::string line;
    while (getline(line, 0)) {
        lineno++;

        // remove comments, skip whitespace
        auto cmdbeg = line.find_first_not_of(" \t\r\n");
        auto nameend = line.find_last_not_of(" \t\r\n", line.find('#'));

        if (nameend != std::string::npos) {
            nameend += 1;  // position after the found character
        }

        // skip empty lines
        if (cmdbeg == std::string::npos) {
            continue;
        }

        // find command
        auto cmdend = line.find_first_of(" \t\r\n", cmdbeg);

        if (line.compare(cmdbeg, cmdend - cmdbeg, "newgraph") == 0 ||
            line.compare(cmdbeg, cmdend - cmdbeg, "addgraph") == 0)
        {
            auto namebeg = line.find_first_not_of(" \t\r\n", cmdend);
            if (namebeg == std::string::npos || namebeg >= nameend) {
                throw ReadError("Expected network name after " + line.substr(cmdbeg, cmdend - cmdbeg));
            }

            Net net;
            auto seqname = line.substr(namebeg, nameend - namebeg);
            auto it = series.find(seqname);
            if (it != series.end() && line[namebeg] == 'a') {
                auto& seq = it->second;
                net = Net((*seq)[seq->size() - 1]);
            }

            if (it == series.end()) {
                std::shared_ptr<NetSequence> newseq(new NetSequence(seqname));
                it = series.insert({seqname, std::move(newseq)}).first;
            }

            readgraph(seqname, it->second->size());

            try {
                net = read_net_from_lines(getline, lineno);
            } catch (...) {
                throw;
            }

            it->second->add(std::move(net));
        } else {
            throw ReadError("Unexpected command: " + line.substr(cmdbeg, cmdend - cmdbeg), lineno);
        }
    }
    return std::move(series);
}
}  // namespace grav
}  // namespace graph
}  // namespace fifr

/*
 * Copyright (c) 2017, 2018 Frank Fischer
 *
 * This file is part of KraView.
 *
 * KraView is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * KraView is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with KraView.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef __FIFR_GRAPH_GRAV_HXX__
#define __FIFR_GRAPH_GRAV_HXX__

#include "AttributedGraph.hxx"
#include "LinkedListGraph.hxx"

#include <functional>
#include <iosfwd>
#include <limits>
#include <map>
#include <memory>
#include <stdexcept>
#include <string>

namespace fifr {
namespace graph {
namespace grav {
using size_type = std::size_t;

/**
 * An error occurred when reading a grav file.
 */
class ReadError : public std::runtime_error
{
public:
    explicit ReadError(const std::string& msg) : ReadError(msg, 0) {}

    ReadError(const std::string& msg, size_type lineno) : std::runtime_error(msg), _lineno(lineno) {}

    ReadError(const ReadError&) = delete;

    ReadError(ReadError&&) noexcept = default;

    ReadError& operator=(const ReadError&) = delete;

    ReadError& operator=(ReadError&&) noexcept = default;

    ~ReadError() noexcept override = default;

    void set_line(size_type lineno) { _lineno = lineno; }

    [[nodiscard]] size_type lineno() const { return _lineno; }

private:
    size_type _lineno;
};

/**
 * Attributes for a node or edge.
 */
class Attributes
{
public:
    class const_iterator
    {
    public:
        using difference_type = std::ptrdiff_t;
        using value_type = std::pair<const std::string, const std::string>;
        using reference = std::pair<const std::string, const std::string>&;
        using pointer = std::pair<const std::string, const std::string>*;
        using iterator_category = std::forward_iterator_tag;

    public:
        const_iterator(const std::string& data, std::string::size_type pos) : data_(data), pos_(pos) {}

        value_type operator*() const;

        const_iterator& operator++();

        const_iterator operator++(int)
        {
            auto copy = *this;
            ++*this;
            return copy;
        }

        bool operator==(const const_iterator& it) const { return pos_ == it.pos_; }

        bool operator!=(const const_iterator& it) const { return !(*this == it); }

    private:
        const std::string& data_;
        std::string::size_type pos_;
    };

public:
    Attributes() = default;

    explicit Attributes(std::string&& data) : data_(std::move(data)) {}

    std::string operator[](const std::string& attr) const;

    [[nodiscard]] const_iterator begin() const { return {data_, 0}; }

    [[nodiscard]] const_iterator end() const { return {data_, data_.size()}; }

private:
    std::string data_;
};

struct Color {
    uint8_t r;
    uint8_t g;
    uint8_t b;
    double alpha;
};

enum class NodeType { None = -1, Circle, Disc };

struct NodeInfo {
    double x = 0;
    double y = 0;
    Color color = {};
    NodeType type = NodeType::None;
    double weight = 0;

    Attributes attributes;
};

struct EdgeInfo {
    Color color = {};
    double flow = 0;
    double cost = 0;
    bool directed = true;

    Attributes attributes;
};

using Empty = std::tuple<>;

class Net : public fifr::graph::AttributedGraph<Digraph, Empty, NodeInfo, EdgeInfo>
{
public:
    using Super = fifr::graph::AttributedGraph<Digraph, Empty, NodeInfo, EdgeInfo>;

    using Edge = Super::edge_type;
    using Node = Super::node_type;
    using builder = Super::builder;

    static constexpr Node nonode = Digraph::nonode;
    static constexpr Edge noedge = Digraph::noedge;

public:
    Net() = default;

    Net(Net&&) noexcept = default;

    explicit Net(const Net&) = default;

    explicit Net(Net::builder&& builder) : Super(Super(std::move(builder))) {}

    Net& operator=(Net&&) noexcept = default;

    Net& operator=(const Net&) = delete;

    ~Net() = default;
};

class NetSequence
{
public:
    using Series = std::map<std::string, std::shared_ptr<NetSequence>>;

    /**
     * Function read input data.
     *
     * The read data must be returned in the first argument.
     * The second argument is the number of bytes to read. If it is 0 a whole
     * line is read. The function must return true if the desired number of
     * bytes or a whole line could be read, otherwise it must return false.
     */
    using getline_function = std::function<bool(std::string&, std::size_t)>;

    using readgraph_function = std::function<void(const std::string&, std::size_t)>;

public:
    explicit NetSequence(const std::string& name);

    NetSequence(NetSequence&& net) noexcept;

    NetSequence(const NetSequence& net) = delete;

    NetSequence& operator=(NetSequence&& net) noexcept;

    NetSequence& operator=(const NetSequence& net) = delete;

    ~NetSequence();

    /// Return the number of networks in this sequence.
    [[nodiscard]] std::size_t size() const;

    /// Return the i-th network.
    const Net& operator[](std::size_t i) const;

    /// Return the name of this sequence.
    [[nodiscard]] const std::string& name() const;

    /// Append another network to the sequence.
    void add(Net net);

    /// Read a series of gravs from an input stream.
    static Series from_stream(std::istream& in,
                              const readgraph_function& readgraph,
                              size_type& lineno,
                              Series&& series = {});

    /// @overload
    static Series from_stream(std::istream& in, const readgraph_function& readgraph, Series&& series = {});

    /// Read a series of gravs from an input stream.
    static Series from_lines(const getline_function& getline,
                             const readgraph_function& readgraph,
                             size_type& lineno,
                             Series&& series = {});

    /// @overload
    static Series from_lines(const getline_function& getline, const readgraph_function& readgraph, Series&& series = {});

private:
    struct Data;
    std::unique_ptr<Data> d;
};
}  // namespace grav
}  // namespace graph
}  // namespace fifr

#endif

/*
 * Copyright (c) 2018 Frank Fischer <frank-fischer@shadow-soft.de>
 *
 * This program is free software: you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see  <http://www.gnu.org/licenses/>
 */

#ifndef __FIFR_GRAPH_KRUSKAL_HXX__
#define __FIFR_GRAPH_KRUSKAL_HXX__

#include <algorithm>
#include <numeric>
#include <vector>

namespace fifr {
namespace graph {
/// Solve the Minimum Spanning Tree problem using Kruskal's algorithm.
///
/// - `graph` is the graph
/// - `weights` is a vector of edges weights
///
/// This implementation is sub-optimal because it does not use clever Union-Find
/// data structures.
template <typename G, typename W>
std::vector<typename G::Edge> kruskal(const G& graph, const W& weights)
{
    using E = typename G::Edge;
    std::vector<E> edges;
    edges.reserve(graph.num_edges());
    for (auto e : graph.edges()) {
        edges.push_back(e);
    }

    // sort edges by weight
    std::sort(edges.begin(), edges.end(), [&](E e, E f) { return weights(e) < weights(f); });

    typename G::template node_map<std::size_t> components(graph, 0);

    // fill `components` with {0, 1, 2, ..., g.num_nodes() - 1}.
    std::iota(components.begin(), components.end(), 0);

    std::vector<E> tree;
    tree.reserve(graph.num_nodes() - 1);

    for (auto e : edges) {
        auto uv = graph.enodes(e);
        auto u = uv.first;
        auto v = uv.second;
        auto comp_u = components[u];
        auto comp_v = components[v];

        if (comp_u != comp_v) {
            tree.push_back(e);
            for (auto& c : components) {
                if (c == comp_v) {
                    c = comp_u;
                }
            }
        }

        if (components.size() + 1 == graph.num_nodes()) {
            break;
        }
    }

    return tree;
}

}  // namespace graph
}  // namespace fifr

#endif

/*
 * Copyright (c) 2018 Frank Fischer <frank-fischer@shadow-soft.de>
 *
 * This program is free software: you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see  <http://www.gnu.org/licenses/>
 */

#include "LinkedListGraph.hxx"

namespace fifr {
namespace graph {
template class LinkedListGraph<uint16_t>;
template class LinkedListDigraph<uint16_t>;
template class LinkedListNetwork<uint16_t>;

template class LinkedListGraph<uint32_t>;
template class LinkedListDigraph<uint32_t>;
template class LinkedListNetwork<uint32_t>;

template class LinkedListGraph<uint64_t>;
template class LinkedListDigraph<uint64_t>;
template class LinkedListNetwork<uint64_t>;

}  // namespace graph
}  // namespace fifr

/*
 * Copyright (c) 2018 Frank Fischer <frank-fischer@shadow-soft.de>
 *
 * This program is free software: you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see  <http://www.gnu.org/licenses/>
 */

#ifndef __FIFR_GRAPH_LINKEDLISTGRAPH_HXX__
#define __FIFR_GRAPH_LINKEDLISTGRAPH_HXX__

#include <cassert>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <iosfwd>
#include <limits>
#include <tuple>
#include <vector>

namespace fifr {
namespace graph {
/// Enumeration for the graph type.
enum class GraphType { Undirected, Directed };

/// A tag for undirected graphs.
struct undirected {
    static const GraphType id = GraphType::Undirected;
};

/// A tag for directed graphs.
struct directed {
    static const GraphType id = GraphType::Directed;
};

template <typename ID = uint32_t>
class LinkedListDigraph;

template <typename ID = uint32_t>
class LinkedListNetwork;

template <typename ID = uint32_t>
class LinkedListGraph;

namespace linkedlistgraph {
template <typename ID>
constexpr ID NO_ID = std::numeric_limits<ID>::max();

/// A node.
template <typename ID>
class Node
{
    friend class LinkedListGraph<ID>;
    friend class LinkedListDigraph<ID>;
    friend class LinkedListNetwork<ID>;
    friend struct std::hash<Node<ID>>;

public:
    Node() = default;
    explicit Node(ID id) : id(id) {}

    Node(const Node&) = default;
    Node(Node&&) noexcept = default;
    Node& operator=(const Node&) = default;
    Node& operator=(Node&&) noexcept = default;

    ~Node() = default;

    bool operator==(const Node& u) const { return id == u.id; }
    bool operator!=(const Node& u) const { return !(*this == u); }

    template <typename ID_>
    friend std::ostream& operator<<(std::ostream& out, const Node<ID_>& u);
    template <typename ID_>
    friend std::istream& operator>>(std::istream& in, Node<ID_>& u);

private:
    ID id = NO_ID<ID>;
};

/// An edge.
template <typename ID>
class Edge
{
    friend class LinkedListGraph<ID>;
    friend class LinkedListDigraph<ID>;
    friend class LinkedListNetwork<ID>;
    friend struct std::hash<Edge<ID>>;

public:
    Edge() = default;
    explicit Edge(ID id) : id(id) {}

    Edge(const Edge&) = default;
    Edge(Edge&&) noexcept = default;
    Edge& operator=(const Edge&) = default;
    Edge& operator=(Edge&&) noexcept = default;

    ~Edge() = default;

    bool operator==(const Edge& e) const { return id >> 1u == e.id >> 1u; }
    bool operator!=(const Edge& e) const { return !(*this == e); }

    template <typename ID_>
    friend std::ostream& operator<<(std::ostream& out, const Edge<ID_>& e);
    template <typename ID_>
    friend std::istream& operator>>(std::istream& in, Edge<ID_>& e);

private:
    ID id = NO_ID<ID>;
};

}  // namespace linkedlistgraph

template <typename ID>
class LinkedListGraph
{
protected:
    static constexpr ID no_id = linkedlistgraph::NO_ID<ID>;

    struct NodeData {
        /// The first adjacent edge.
        ID first = no_id;
    };

    struct EdgeData {
        /// The sink node.
        ID snk = no_id;
        /// The next arc adjacent to the source node.
        ID next = no_id;
    };

public:
    /// This graph is undirected.
    using graph_type = undirected;

    using size_type = std::size_t;
    using id_type = ID;

    /// Type of nodes.
    using Node = linkedlistgraph::Node<ID>;
    /// Type of nodes.
    using node_type = Node;

    /// Type of edges.
    using Edge = linkedlistgraph::Edge<ID>;
    /// Type of edges.
    using edge_type = Edge;

    /// Iterator over a consecutive range of valid IDs.
    template <typename T, ID offset>
    class id_iterator
    {
        friend class LinkedListGraph;

    public:
        using value_type = T;
        using pointer = const T*;
        using reference = T;
        using iterator_category = std::bidirectional_iterator_tag;

    public:
        id_iterator() = default;

        reference operator*() const { return T(id_); }

        id_iterator& operator++()
        {
            id_ += offset;
            return *this;
        }

        id_iterator operator++(int)
        {
            auto it = *this;
            ++(*this);
            return it;
        }

        id_iterator& operator--()
        {
            id_ -= offset;
            return *this;
        }

        id_iterator operator--(int)
        {
            auto it = *this;
            --(*this);
            return it;
        }

        bool operator==(const id_iterator& it) const { return id_ == it.id_; }
        bool operator!=(const id_iterator& it) const { return !(*this == it); }

    private:
        explicit id_iterator(ID id) : id_(id) {}

    private:
        ID id_ = no_id;
    };

    template <typename It>
    class range_proxy
    {
        friend class LinkedListGraph;

    public:
        using iterator = It;

    private:
        range_proxy(It&& begin, It&& end) : begin_(begin), end_(end) {}

    public:
        template <typename It_>
        explicit range_proxy(range_proxy<It_>&& rng) : begin_(It(rng.begin_)), end_(It(rng.end_))
        {
        }

        iterator begin() const { return begin_; }
        iterator end() const { return end_; }

    private:
        It begin_;
        It end_;
    };

    class neigh_iterator
    {
        friend class LinkedListDigraph<ID>::in_iterator;
        friend class LinkedListDigraph<ID>::out_iterator;

    public:
        using value_type = std::pair<Edge, Node>;
        using reference = std::pair<Edge, Node>;
        using iterator_category = std::forward_iterator_tag;

    public:
        neigh_iterator(ID edge, const std::vector<EdgeData>& edges) : edge_(edge), edges_(edges) {}

        reference operator*() const { return {edge(), node()}; }

        /// Return the current edge.
        [[nodiscard]] Edge edge() const
        {
            assert(edge_ != no_id);
            return Edge(edge_);
        }

        /// Return the other adjacent node of the current edge.
        [[nodiscard]] Node node() const
        {
            assert(edge_ != no_id);
            return Node(edges_[edge_].snk);
        }

        neigh_iterator& operator++()
        {
            assert(edge_ != no_id);
            edge_ = edges_[edge_].next;
            return *this;
        }

        neigh_iterator operator++(int)
        {
            auto it = *this;
            ++(*this);
            return it;
        }

        bool operator==(const neigh_iterator& it) const { return edge_ == it.edge_; }
        bool operator!=(const neigh_iterator& it) const { return !(*this == it); }

    private:
        ID edge_;
        const std::vector<EdgeData>& edges_;
    };

    using node_iterator = id_iterator<Node, 1>;
    using edge_iterator = id_iterator<Edge, 2>;

    using node_range = range_proxy<node_iterator>;
    using edge_range = range_proxy<edge_iterator>;
    using neigh_range = range_proxy<neigh_iterator>;

    class builder
    {
        friend class LinkedListGraph;

    public:
        explicit builder(std::size_t node_capacity = 0, std::size_t edge_capacity = 0)
        {
            nodes_.reserve(node_capacity);
            edges_.reserve(edge_capacity);
        }

        /// Return the number of nodes.
        [[nodiscard]] size_type num_nodes() const { return nodes_.size(); }

        /// Return the number of edges.
        [[nodiscard]] size_type num_edges() const { return edges_.size() / 2; }

        /// Add a new node to the graph.
        Node add_node()
        {
            assert(nodes_.size() + 1 < no_id);
            nodes_.push_back(NodeData{});
            return Node(static_cast<ID>(nodes_.size() - 1));
        }

        /// Add several nodes to the graph.
        std::vector<Node> add_nodes(size_type nnew)
        {
            std::vector<Node> newnodes;
            newnodes.reserve(nnew);
            for (size_type i = 0; i < nnew; ++i) {
                newnodes.push_back(add_node());
            }
            return newnodes;
        }

        /// Return the id of a node.
        [[nodiscard]] ID node_id(Node u) const { return u.id; }

        /// Return the node with a certain id.
        [[nodiscard]] Node id2node(ID id) const
        {
            assert(id >= 0 && id < static_cast<ID>(nodes_.size()));
            return Node(id);
        }

        /// Add an edge between u and v to the graph.
        Edge add_edge(Node u, Node v)
        {
            assert(edges_.size() + 2 < no_id);
            auto eid = static_cast<ID>(edges_.size());
            auto uid = u.id;
            auto vid = v.id;
            edges_.push_back(EdgeData{vid, nodes_[uid].first});
            edges_.push_back(EdgeData{uid, nodes_[vid].first});
            nodes_[uid].first = eid;
            nodes_[vid].first = eid + 1;
            return Edge(eid);
        }

        /// Return the id of an edge.
        [[nodiscard]] ID edge_id(Edge e) const { return e.id >> 1; }

        /// Return the edge with a certain id.
        [[nodiscard]] Edge id2edge(ID id) const
        {
            assert(id >= 0 && id < static_cast<ID>(edges_.size()));
            return Edge(id);
        }

    private:
        std::vector<NodeData> nodes_;
        std::vector<EdgeData> edges_;
    };

    /// A vector assigning some value to each node.
    template <typename T>
    class node_map : public std::vector<T>
    {
    public:
        explicit node_map(const LinkedListGraph& g) : std::vector<T>(g.num_nodes()) {}

        node_map(const LinkedListGraph& g, const T& value) : std::vector<T>(g.num_nodes(), value) {}

        node_map(const LinkedListGraph& g, std::vector<T> values) : std::vector<T>(std::move(values))
        {
            assert(std::vector<T>::size() == g.num_nodes());
        }

        T& operator[](Node u) { return std::vector<T>::operator[](u.id); }
        const T& operator[](Node u) const { return std::vector<T>::operator[](u.id); }
    };

    /// A vector assigning some value to each edge.
    template <typename T>
    class edge_map : public std::vector<T>
    {
    public:
        explicit edge_map(const LinkedListGraph& g) : std::vector<T>(g.num_edges()) {}

        edge_map(const LinkedListGraph& g, const T& value) : std::vector<T>(g.num_edges(), value) {}

        edge_map(const LinkedListGraph& g, std::vector<T> values) : std::vector<T>(std::move(values))
        {
            assert(std::vector<T>::size() == g.num_edges());
        }

        T& operator[](Edge e) { return std::vector<T>::operator[](e.id >> 1); }
        const T& operator[](Edge e) const { return std::vector<T>::operator[](e.id >> 1); }
    };

public:
    /// A non-existing node.
    static constexpr Node nonode = Node();
    /// A non-existing edge.
    static constexpr Edge noedge = Edge();

public:
    LinkedListGraph() = default;

    LinkedListGraph(LinkedListGraph&&) noexcept = default;

    explicit LinkedListGraph(const LinkedListGraph&) = default;

    explicit LinkedListGraph(builder&& b) : nodes_(std::move(b.nodes_)), edges_(std::move(b.edges_)) {}

    LinkedListGraph& operator=(LinkedListGraph&&) noexcept = default;

    LinkedListGraph& operator=(const LinkedListGraph&) = default;

    ~LinkedListGraph() = default;

public:
    /// Return the number of nodes.
    [[nodiscard]] size_type num_nodes() const { return nodes_.size(); }

    /// Return the number of edges.
    [[nodiscard]] size_type num_edges() const { return edges_.size() / 2; }

    /// Return the end nodes of an edge.
    ///
    /// Note that the order of the nodes is undefined. In fact, each time the
    /// method is called the order of the returned nodes may be different.
    [[nodiscard]] std::pair<Node, Node> enodes(Edge e) const
    {
        assert(e.id != no_id);
        return {Node{edges_[e.id | 1u].snk}, Node{edges_[e.id & ~static_cast<ID>(1)].snk}};
    }

    /// Return a node range.
    [[nodiscard]] node_range nodes() const
    {
        return {node_iterator(0), node_iterator(static_cast<ID>(nodes_.size()))};
    };

    /// Return the id associated with a node.
    [[nodiscard]] ID node_id(Node u) const
    {
        assert(u.id != no_id);
        return u.id;
    }

    /// Return the node with the given id.
    [[nodiscard]] Node id2node(ID id) const
    {
        assert(id >= 0 && id < static_cast<ID>(nodes_.size()));
        return Node(id);
    }

    /// Return an edge range.
    [[nodiscard]] edge_range edges() const
    {
        return {edge_iterator(0), edge_iterator(static_cast<ID>(edges_.size()))};
    };

    /// Return the id associated with a edge.
    [[nodiscard]] ID edge_id(Edge e) const
    {
        assert(e.id != no_id);
        return e.id >> 1u;
    }

    /// Return the edge with the given id.
    [[nodiscard]] Edge id2edge(ID id) const
    {
        assert(id >= 0 && (id * 2) < static_cast<ID>(edges_.size()));
        return Edge(id * 2);
    }

    /// Return a range over all edges adjacent to the given node `u`.
    [[nodiscard]] neigh_range neighs(Node u) const
    {
        assert(u.id != no_id);
        return {neigh_iterator(nodes_[u.id].first, edges_), neigh_iterator(no_id, edges_)};
    }

    template <typename ID_>
    friend std::ostream& operator<<(std::ostream& out, const LinkedListGraph<ID_>& g);
    template <typename ID_>
    friend std::istream& operator>>(std::istream& in, LinkedListGraph<ID_>& g);

protected:
    std::vector<NodeData> nodes_;
    std::vector<EdgeData> edges_;
};

template <typename ID>
class LinkedListDigraph : public LinkedListGraph<ID>
{
public:
    /// This graph is undirected.
    using graph_type = directed;

    using super_type = LinkedListGraph<ID>;
    using typename super_type::Edge;
    using typename super_type::Node;

    using typename super_type::neigh_iterator;

public:
    class in_iterator
    {
    public:
        using value_type = std::pair<Edge, Node>;
        using reference = std::pair<Edge, Node>;
        using iterator_category = std::forward_iterator_tag;

    public:
        explicit in_iterator(neigh_iterator it) : it_(it)
        {
            while ((it_.edge_ & 1u) == 0 && it_.edge_ != super_type::no_id) {
                ++it_;
            }
        }

        reference operator*() const { return *it_; }

        /// Return the current edge.
        [[nodiscard]] Edge edge() const { return it_.edge(); }

        /// Return the other adjacent node of the current edge.
        [[nodiscard]] Node node() const { return it_.node(); }

        in_iterator& operator++()
        {
            do {
                ++it_;
            } while ((it_.edge_ & 1u) == 0 && it_.edge_ != super_type::no_id);
            return *this;
        }

        in_iterator operator++(int)
        {
            auto it = *this;
            ++(*this);
            return it;
        }

        bool operator==(const in_iterator& it) const { return it_ == it.it_; }
        bool operator!=(const in_iterator& it) const { return !(*this == it); }

    private:
        neigh_iterator it_;
    };

    class out_iterator
    {
    public:
        using value_type = std::pair<Edge, Node>;
        using reference = std::pair<Edge, Node>;
        using iterator_category = std::forward_iterator_tag;

    public:
        explicit out_iterator(neigh_iterator it) : it_(it)
        {
            while ((it_.edge_ & 1u) != 0 && it_.edge_ != super_type::no_id) {
                ++it_;
            }
        }

        reference operator*() const { return *it_; }

        /// Return the current edge.
        [[nodiscard]] Edge edge() const { return it_.edge(); }

        /// Return the other adjacent node of the current edge.
        [[nodiscard]] Node node() const { return it_.node(); }

        out_iterator& operator++()
        {
            do {
                ++it_;
            } while ((it_.edge_ & 1u) != 0 && it_.edge_ != super_type::no_id);
            return *this;
        }

        out_iterator operator++(int)
        {
            auto it = *this;
            ++(*this);
            return it;
        }

        bool operator==(const out_iterator& it) const { return it_ == it.it_; }
        bool operator!=(const out_iterator& it) const { return !(*this == it); }

    private:
        neigh_iterator it_;
    };

    using in_range = typename super_type::template range_proxy<in_iterator>;
    using out_range = typename super_type::template range_proxy<out_iterator>;

    using typename super_type::builder;

public:
    LinkedListDigraph() = default;

    LinkedListDigraph(LinkedListDigraph&&) noexcept = default;

    explicit LinkedListDigraph(const LinkedListDigraph&) = default;

    LinkedListDigraph& operator=(LinkedListDigraph&&) noexcept = default;

    LinkedListDigraph& operator=(const LinkedListDigraph&) noexcept = delete;

    explicit LinkedListDigraph(builder&& b) : super_type(std::move(b)) {}

    ~LinkedListDigraph() = default;

    /// Return the source node of edge e.
    [[nodiscard]] Node src(Edge e) const
    {
        assert(e.id != super_type::no_id);
        return Node(super_type::edges_[e.id | 1u].snk);
    }

    /// Return the sink node of edge e.
    [[nodiscard]] Node snk(Edge e) const
    {
        assert(e.id != super_type::no_id);
        return Node(super_type::edges_[e.id & ~static_cast<ID>(1)].snk);
    }

    /// Return a range over all edges with destination node `u`.
    [[nodiscard]] in_range inedges(Node u) const
    {
        assert(u.id != super_type::no_id);
        return in_range(super_type::neighs(u));
    }

    /// Return a range over all edges with source node `u`.
    [[nodiscard]] out_range outedges(Node u) const
    {
        assert(u.id != super_type::no_id);
        return out_range(super_type::neighs(u));
    }
};

template <typename ID>
class LinkedListNetwork : public LinkedListDigraph<ID>
{
public:
    using super_type = LinkedListDigraph<ID>;
    using typename super_type::builder;
    using typename super_type::Edge;
    using typename super_type::Node;

    /// A vector assigning some value to each edge.
    template <typename T>
    class biedge_map : public std::vector<T>
    {
    public:
        explicit biedge_map(const LinkedListNetwork& g) : std::vector<T>(g.num_edges() * 2) {}

        biedge_map(const LinkedListNetwork& g, const T& value) : std::vector<T>(g.num_edges() * 2, value) {}

        T& operator[](Edge e) { return std::vector<T>::operator[](e.id); }
        const T& operator[](Edge e) const { return std::vector<T>::operator[](e.id); }
    };

public:
    LinkedListNetwork() = default;

    LinkedListNetwork(LinkedListNetwork&&) noexcept = default;

    explicit LinkedListNetwork(const LinkedListNetwork&) = default;

    LinkedListNetwork& operator=(LinkedListNetwork&&) noexcept = default;

    LinkedListNetwork& operator=(const LinkedListNetwork&) = delete;

    explicit LinkedListNetwork(builder&& b) : super_type(std::move(b)) {}

    ~LinkedListNetwork() = default;

    /// Return true if `e` is the reverse edge of `f`.
    [[nodiscard]] bool is_reverse(Edge e, Edge f) const
    {
        assert(e.id != super_type::no_id);
        assert(f.id != super_type::no_id);
        return (e.id ^ f.id) == 1;
    }

    /// Return the reverse edge of `e`.
    [[nodiscard]] Edge reverse(Edge e) const
    {
        assert(e.id != super_type::no_id);
        return Edge(e.id ^ 1u);
    }

    /// Return true if `e` is a forward edge.
    [[nodiscard]] bool is_forward(Edge e) const
    {
        assert(e.id != super_type::no_id);
        return (e.id & 1u) == 0;
    }

    /// Return the forward edge of `e`.
    ///
    /// If `e` is itself a forward edge, the edge `e` is returned, otherwise its
    /// reverse edge is returned.
    [[nodiscard]] Edge forward(Edge e) const { return is_forward(e) ? e : reverse(e); }

    /// Return true if `e` is a backward edge.
    [[nodiscard]] bool is_backward(Edge e) const { return !is_forward(e); }

    /// Return the backward edge of `e`.
    ///
    /// If `e` is itself a backward edge, the edge `e` is returned, otherwise its
    /// reverse edge is returned.
    [[nodiscard]] Edge backward(Edge e) const { return is_backward(e) ? e : reverse(e); }

    /// Return the source of the directed edge `e`.
    ///
    /// If `e` is a forward edge, this is the same as `src` otherwise it is
    /// `snk`.
    [[nodiscard]] Node bisrc(Edge e) const { return is_forward(e) ? super_type::src(e) : super_type::snk(e); }

    /// Return the sink of the directed edge `e`.
    ///
    /// If `e` is a forward edge, this is the same as `snk` otherwise it is
    /// `src`.
    [[nodiscard]] Node bisnk(Edge e) const { return is_forward(e) ? super_type::snk(e) : super_type::src(e); }
};

/// Default undirected graph with 32bit indices.
using Graph = LinkedListGraph<>;
/// Default directed graph with 32bit indices.
using Digraph = LinkedListDigraph<>;
/// Default network with 32bit indices.
using Net = LinkedListNetwork<>;

extern template class LinkedListGraph<uint16_t>;
extern template class LinkedListDigraph<uint16_t>;
extern template class LinkedListNetwork<uint16_t>;

extern template class LinkedListGraph<uint32_t>;
extern template class LinkedListDigraph<uint32_t>;
extern template class LinkedListNetwork<uint32_t>;

extern template class LinkedListGraph<uint64_t>;
extern template class LinkedListDigraph<uint64_t>;
extern template class LinkedListNetwork<uint64_t>;

}  // namespace graph
}  // namespace fifr

namespace std {
template <typename ID>
struct hash<fifr::graph::linkedlistgraph::Node<ID>> {
    std::size_t operator()(fifr::graph::linkedlistgraph::Node<ID> node) const noexcept
    {
        return std::hash<ID>{}(node.id);
    }
};

template <typename ID>
struct hash<fifr::graph::linkedlistgraph::Edge<ID>> {
    std::size_t operator()(fifr::graph::linkedlistgraph::Edge<ID> edge) const noexcept
    {
        return std::hash<ID>{}(edge.id >> 1);
    }
};
}  // namespace std

#endif