netlist_graph.cpp

Go to the documentation of this file.

#include "graph_algorithm/netlist_graph.h"
 
#include "hal_core/netlist/endpoint.h"
#include "hal_core/netlist/gate.h"
#include "hal_core/netlist/net.h"
#include "hal_core/netlist/netlist.h"
 
namespace hal
{
    namespace graph_algorithm
    {
 
        NetlistGraph::NetlistGraph(Netlist* nl) : m_nl(nl)
        {
        }
 
        NetlistGraph::NetlistGraph(Netlist* nl, igraph_t&& graph, std::unordered_map<u32, Gate*>&& nodes_to_gates) : m_nl(nl), m_graph(std::move(graph)), m_nodes_to_gates(std::move(nodes_to_gates))
        {
            // This constructor receives an already-initialized graph and takes over its ownership. Note that
            // `igraph_t` is a trivially copyable C struct, so the `std::move()` above is a bitwise copy and the
            // caller's object is left holding the same pointers -- the caller must therefore not destroy it.
            m_graph_initialized = true;
            m_graph_ptr         = &m_graph;
 
            for (const auto& [node, gate] : m_nodes_to_gates)
            {
                if (gate)
                {
                    m_gates_to_nodes[gate] = node;
                }
            }
        }
 
        NetlistGraph::~NetlistGraph()
        {
            // Guarded because the `NetlistGraph(Netlist*)` constructor leaves `m_graph` uninitialized and a
            // factory may bail out before initializing it -- see `m_graph_initialized`.
            if (m_graph_initialized)
            {
                igraph_destroy(&m_graph);
            }
        }
 
        Result<std::unique_ptr<NetlistGraph>> NetlistGraph::from_gates(const std::vector<Gate*>& gates, const std::set<Gate*>& split_gates, const std::function<bool(const Net*)>& filter)
        {
            if (gates.empty())
            {
                return ERR("no gates given");
            }
 
            Netlist* nl = gates.front()->get_netlist();
            std::unordered_set<Gate*> in_scope;
            for (auto* g : gates)
            {
                if (g == nullptr)
                {
                    return ERR("gate is a nullptr");
                }
                if (g->get_netlist() != nl)
                {
                    return ERR("gates belong to different netlists");
                }
                if (!in_scope.insert(g).second)
                {
                    return ERR("gate '" + g->get_name() + "' with ID " + std::to_string(g->get_id()) + " was given more than once");
                }
            }
 
            auto graph = std::unique_ptr<NetlistGraph>(new NetlistGraph(nl));
 
            // the primary node of a gate carries its outgoing edges, so it is the only node reachable by gate
            u32 node_counter = 0;
            for (auto* g : gates)
            {
                const u32 node                = node_counter++;
                graph->m_gates_to_nodes[g]    = node;
                graph->m_nodes_to_gates[node] = g;
            }
 
            // collect the edges before creating the shadow nodes, as a gate only gets one if it has incoming edges
            // within the graph. Nets are sorted by ID so that the graph does not depend on the addresses of the nets.
            std::vector<Net*> nets;
            std::unordered_set<Net*> visited_nets;
            for (auto* g : gates)
            {
                for (auto* n : g->get_fan_out_nets())
                {
                    if ((filter == nullptr || filter(n)) && visited_nets.insert(n).second)
                    {
                        nets.push_back(n);
                    }
                }
            }
            std::sort(nets.begin(), nets.end(), [](const Net* lhs, const Net* rhs) { return lhs->get_id() < rhs->get_id(); });
 
            std::vector<std::pair<Gate*, Gate*>> edges;
            std::unordered_set<Gate*> has_incoming_edge;
            for (const auto* net : nets)
            {
                for (const auto* src_ep : net->get_sources())
                {
                    auto* src_gate = src_ep->get_gate();
                    if (in_scope.find(src_gate) == in_scope.end())
                    {
                        continue;
                    }
 
                    for (const auto* dst_ep : net->get_destinations())
                    {
                        auto* dst_gate = dst_ep->get_gate();
                        if (in_scope.find(dst_gate) == in_scope.end())
                        {
                            continue;
                        }
 
                        edges.push_back({src_gate, dst_gate});
                        has_incoming_edge.insert(dst_gate);
                    }
                }
            }
 
            // a gate is only split if it actually has incoming edges, as an isolated shadow node would merely show up
            // as a spurious connected component. Iterate `gates` rather than `split_gates` to keep node numbering
            // independent of the addresses of the gates.
            std::unordered_map<Gate*, u32> shadow_of;
            for (auto* g : gates)
            {
                if (split_gates.find(g) == split_gates.end() || has_incoming_edge.find(g) == has_incoming_edge.end())
                {
                    continue;
                }
 
                const u32 shadow_node                       = node_counter++;
                graph->m_nodes_to_gates[shadow_node]        = g;
                graph->m_shadow_nodes_to_nodes[shadow_node] = graph->m_gates_to_nodes.at(g);
                shadow_of[g]                                = shadow_node;
            }
 
            igraph_vector_int_t igraph_edges;
            auto err = igraph_vector_int_init(&igraph_edges, 2 * edges.size());
            if (err != IGRAPH_SUCCESS)
            {
                return ERR(igraph_strerror(err));
            }
 
            // an edge always leaves the primary node of its source and arrives at the shadow node of its destination if
            // there is one, which turns a split gate into a pure source plus a pure sink
            u32 edge_index = 0;
            for (const auto& [src_gate, dst_gate] : edges)
            {
                const auto shadow_it               = shadow_of.find(dst_gate);
                VECTOR(igraph_edges)[edge_index++] = graph->m_gates_to_nodes.at(src_gate);
                VECTOR(igraph_edges)[edge_index++] = (shadow_it != shadow_of.end()) ? shadow_it->second : graph->m_gates_to_nodes.at(dst_gate);
            }
 
            graph->m_graph_ptr = &(graph->m_graph);
            err                = igraph_create(graph->m_graph_ptr, &igraph_edges, node_counter, IGRAPH_DIRECTED);
 
            igraph_vector_int_destroy(&igraph_edges);
 
            if (err != IGRAPH_SUCCESS)
            {
                return ERR(igraph_strerror(err));
            }
 
            graph->m_graph_initialized = true;
 
            return OK(std::move(graph));
        }
 
        Result<std::unique_ptr<NetlistGraph>> NetlistGraph::from_netlist(Netlist* nl, bool create_dummy_vertices, const std::function<bool(const Net*)>& filter)
        {
            if (!nl)
            {
                return ERR("netlist is a nullptr");
            }
 
            auto graph = std::unique_ptr<NetlistGraph>(new NetlistGraph(nl));
 
            // count all edges as this number is needed to create a new graph
            u32 edge_counter = 0;
            for (const auto* net : graph->m_nl->get_nets(filter))
            {
                std::vector<Gate*> src_gates;
                for (const auto* src_ep : net->get_sources())
                {
                    src_gates.push_back(src_ep->get_gate());
                }
 
                std::vector<Gate*> dst_gates;
                for (const auto* dst_ep : net->get_destinations())
                {
                    dst_gates.push_back(dst_ep->get_gate());
                }
 
                if (src_gates.empty() && create_dummy_vertices)
                {
                    // if no sources, add one dummy edge for every destination
                    // all dummy edges will come from the same dummy node
                    edge_counter += dst_gates.size();
                }
                else if (dst_gates.empty() && create_dummy_vertices)
                {
                    // if no destinations, add one dummy edge for every source
                    // all dummy edges will go to the same dummy node
                    edge_counter += src_gates.size();
                }
                else
                {
                    // add one edge for every source-destination pair
                    edge_counter += dst_gates.size() * src_gates.size();
                }
            }
 
            // initialize edge vector
            igraph_vector_int_t edges;
            auto err = igraph_vector_int_init(&edges, 2 * edge_counter);
            if (err != IGRAPH_SUCCESS)
            {
                return ERR(igraph_strerror(err));
            }
 
            // we need dummy gates for input/outputs
            u32 node_counter = 0;
            u32 edge_index   = 0;
 
            for (auto* g : graph->m_nl->get_gates())
            {
                const u32 node                = node_counter++;
                graph->m_gates_to_nodes[g]    = node;
                graph->m_nodes_to_gates[node] = g;
            }
 
            for (const auto* net : graph->m_nl->get_nets(filter))
            {
                std::vector<Gate*> src_gates;
                for (const auto* src_ep : net->get_sources())
                {
                    src_gates.push_back(src_ep->get_gate());
                }
 
                std::vector<Gate*> dst_gates;
                for (const auto* dst_ep : net->get_destinations())
                {
                    dst_gates.push_back(dst_ep->get_gate());
                }
 
                if (src_gates.empty() && create_dummy_vertices)
                {
                    // if no sources, add one dummy node
                    const u32 dummy_node                = node_counter++;
                    graph->m_nodes_to_gates[dummy_node] = nullptr;
                    for (auto* dst_gate : dst_gates)
                    {
                        VECTOR(edges)[edge_index++] = dummy_node;
                        VECTOR(edges)[edge_index++] = graph->m_gates_to_nodes.at(dst_gate);
                    }
                }
                else if (dst_gates.empty() && create_dummy_vertices)
                {
                    // if no destinations, add one dummy node
                    const u32 dummy_node                = node_counter++;
                    graph->m_nodes_to_gates[dummy_node] = nullptr;
                    for (auto* src_gate : src_gates)
                    {
                        VECTOR(edges)[edge_index++] = dummy_node;
                        VECTOR(edges)[edge_index++] = graph->m_gates_to_nodes.at(src_gate);
                    }
                }
                else
                {
                    for (auto* dst_gate : dst_gates)
                    {
                        for (auto* src_gate : src_gates)
                        {
                            VECTOR(edges)[edge_index++] = graph->m_gates_to_nodes.at(src_gate);
                            VECTOR(edges)[edge_index++] = graph->m_gates_to_nodes.at(dst_gate);
                        }
                    }
                }
            }
 
            graph->m_graph_ptr = &(graph->m_graph);
            err                = igraph_create(graph->m_graph_ptr, &edges, node_counter, IGRAPH_DIRECTED);
 
            igraph_vector_int_destroy(&edges);
 
            if (err != IGRAPH_SUCCESS)
            {
                return ERR(igraph_strerror(err));
            }
 
            graph->m_graph_initialized = true;
 
            return OK(std::move(graph));
        }
 
        Result<std::unique_ptr<NetlistGraph>> NetlistGraph::from_netlist_no_edges(Netlist* nl, const std::vector<Gate*>& gates)
        {
            if (!nl)
            {
                return ERR("netlist is a nullptr");
            }
 
            auto graph = std::unique_ptr<NetlistGraph>(new NetlistGraph(nl));
 
            const auto& graph_gates = gates.empty() ? graph->m_nl->get_gates() : gates;
 
            u32 node_counter = 0;
            for (auto* g : graph_gates)
            {
                const u32 node                = node_counter++;
                graph->m_gates_to_nodes[g]    = node;
                graph->m_nodes_to_gates[node] = g;
            }
 
            graph->m_graph_ptr = &(graph->m_graph);
            auto err           = igraph_empty(graph->m_graph_ptr, node_counter, IGRAPH_DIRECTED);
            if (err != IGRAPH_SUCCESS)
            {
                return ERR(igraph_strerror(err));
            }
 
            graph->m_graph_initialized = true;
 
            return OK(std::move(graph));
        }
 
        Result<std::unique_ptr<NetlistGraph>> NetlistGraph::copy() const
        {
            auto graph = std::unique_ptr<NetlistGraph>(new NetlistGraph(m_nl));
 
            if (const auto res = igraph_copy(&(graph->m_graph), &(this->m_graph)); res != IGRAPH_SUCCESS)
            {
                return ERR(igraph_strerror(res));
            }
 
            graph->m_graph_initialized = true;
            graph->m_graph_ptr         = &(graph->m_graph);
            graph->m_gates_to_nodes    = this->m_gates_to_nodes;
            graph->m_nodes_to_gates    = this->m_nodes_to_gates;
 
            return OK(std::move(graph));
        }
 
        Netlist* NetlistGraph::get_netlist() const
        {
            return m_nl;
        }
 
        igraph_t* NetlistGraph::get_graph() const
        {
            return m_graph_ptr;
        }
 
        Result<std::vector<Gate*>> NetlistGraph::get_gates_from_vertices(const std::vector<u32>& vertices) const
        {
            std::vector<Gate*> res;
            for (const auto& vertex : vertices)
            {
                if (const auto it = m_nodes_to_gates.find(vertex); it != m_nodes_to_gates.end())
                {
                    Gate* g = it->second;
 
                    res.push_back(g);
                    if (!g)
                    {
                        log_warning("graph_algorithm", "no gate exists for dummy vertex {}, added nullptr", vertex);
                    }
                }
                else
                {
                    return ERR("no gate for vertex " + std::to_string(vertex) + " exists in netlist with ID " + std::to_string(m_nl->get_id()));
                }
            }
            return OK(res);
        }
 
        Result<std::vector<Gate*>> NetlistGraph::get_gates_from_vertices(const std::set<u32>& vertices) const
        {
            std::vector<Gate*> res;
            for (const auto& vertex : vertices)
            {
                if (const auto it = m_nodes_to_gates.find(vertex); it != m_nodes_to_gates.end())
                {
                    Gate* g = it->second;
 
                    res.push_back(g);
                    if (!g)
                    {
                        log_warning("graph_algorithm", "no gate exists for dummy vertex {}, added nullptr", vertex);
                    }
                }
                else
                {
                    return ERR("no gate for vertex " + std::to_string(vertex) + " exists in netlist with ID " + std::to_string(m_nl->get_id()));
                }
            }
            return OK(res);
        }
 
        Result<std::vector<Gate*>> NetlistGraph::get_gates_from_vertices_igraph(const igraph_vector_int_t* vertices) const
        {
            std::vector<Gate*> res;
            const u32 num_vertices = igraph_vector_int_size(vertices);
            for (u32 i = 0; i < num_vertices; i++)
            {
                u32 vertex = VECTOR(*vertices)[i];
                if (const auto it = m_nodes_to_gates.find(vertex); it != m_nodes_to_gates.end())
                {
                    Gate* g = it->second;
 
                    res.push_back(g);
                    if (!g)
                    {
                        log_warning("graph_algorithm", "no gate exists for dummy vertex {}, added nullptr", vertex);
                    }
                }
                else
                {
                    return ERR("no gate for vertex " + std::to_string(vertex) + " exists in netlist with ID " + std::to_string(m_nl->get_id()));
                }
            }
            return OK(res);
        }
 
        Result<std::set<Gate*>> NetlistGraph::get_gates_set_from_vertices(const std::vector<u32>& vertices) const
        {
            std::set<Gate*> res;
            for (const auto& vertex : vertices)
            {
                if (const auto it = m_nodes_to_gates.find(vertex); it != m_nodes_to_gates.end())
                {
                    Gate* g = it->second;
 
                    if (!g)
                    {
                        log_warning("graph_algorithm", "no gate exists for dummy vertex {}, skipping vertex", vertex);
                        continue;
                    }
                    res.insert(g);
                }
                else
                {
                    return ERR("no gate for vertex " + std::to_string(vertex) + " exists in netlist with ID " + std::to_string(m_nl->get_id()));
                }
            }
            return OK(res);
        }
 
        Result<std::set<Gate*>> NetlistGraph::get_gates_set_from_vertices(const std::set<u32>& vertices) const
        {
            std::set<Gate*> res;
            for (const auto& vertex : vertices)
            {
                if (const auto it = m_nodes_to_gates.find(vertex); it != m_nodes_to_gates.end())
                {
                    Gate* g = it->second;
 
                    if (!g)
                    {
                        log_warning("graph_algorithm", "no gate exists for dummy vertex {}, skipping vertex", vertex);
                        continue;
                    }
                    res.insert(g);
                }
                else
                {
                    return ERR("no gate for vertex " + std::to_string(vertex) + " exists in netlist with ID " + std::to_string(m_nl->get_id()));
                }
            }
            return OK(res);
        }
 
        Result<std::set<Gate*>> NetlistGraph::get_gates_set_from_vertices_igraph(const igraph_vector_int_t* vertices) const
        {
            std::set<Gate*> res;
            const u32 num_vertices = igraph_vector_int_size(vertices);
            for (u32 i = 0; i < num_vertices; i++)
            {
                u32 vertex = VECTOR(*vertices)[i];
                if (const auto it = m_nodes_to_gates.find(vertex); it != m_nodes_to_gates.end())
                {
                    Gate* g = it->second;
 
                    if (!g)
                    {
                        log_warning("graph_algorithm", "no gate exists for dummy vertex {}, skipping vertex", vertex);
                        continue;
                    }
                    res.insert(g);
                }
                else
                {
                    return ERR("no gate for vertex " + std::to_string(vertex) + " exists in netlist with ID " + std::to_string(m_nl->get_id()));
                }
            }
            return OK(res);
        }
 
        Result<Gate*> NetlistGraph::get_gate_from_vertex(const u32 vertex) const
        {
            const auto res = get_gates_from_vertices(std::vector<u32>({vertex}));
            if (res.is_error())
            {
                return ERR(res.get_error());
            }
 
            return OK(res.get().front());
        }
 
        Result<std::vector<u32>> NetlistGraph::get_vertices_from_gates(const std::vector<Gate*>& gates) const
        {
            std::vector<u32> res;
            for (u32 i = 0; i < gates.size(); i++)
            {
                auto* g = gates.at(i);
 
                if (!g)
                {
                    return ERR("gate at index " + std::to_string(i) + " is a nullptr");
                }
 
                if (const auto it = m_gates_to_nodes.find(g); it != m_gates_to_nodes.end())
                {
                    res.push_back(it->second);
                }
                else
                {
                    return ERR("no node for gate '" + g->get_name() + "' with ID " + std::to_string(g->get_id()) + " exists in graph for netlist with ID " + std::to_string(m_nl->get_id()));
                }
            }
            return OK(res);
        }
 
        Result<std::vector<u32>> NetlistGraph::get_vertices_from_gates(const std::set<Gate*>& gates) const
        {
            std::vector<u32> res;
            for (auto* g : gates)
            {
                if (!g)
                {
                    return ERR("set of gates contains a nullptr");
                }
 
                if (const auto it = m_gates_to_nodes.find(g); it != m_gates_to_nodes.end())
                {
                    res.push_back(it->second);
                }
                else
                {
                    return ERR("no node for gate '" + g->get_name() + "' with ID " + std::to_string(g->get_id()) + " exists in graph for netlist with ID " + std::to_string(m_nl->get_id()));
                }
            }
            return OK(res);
        }
 
        Result<igraph_vector_int_t> NetlistGraph::get_vertices_from_gates_igraph(const std::vector<Gate*>& gates) const
        {
            igraph_vector_int_t out;
            if (auto res = igraph_vector_int_init(&out, gates.size()); res != IGRAPH_SUCCESS)
            {
                return ERR(igraph_strerror(res));
            }
 
            for (u32 i = 0; i < gates.size(); i++)
            {
                auto* g = gates.at(i);
 
                if (!g)
                {
                    return ERR("gate at index " + std::to_string(i) + " is a nullptr");
                }
 
                if (const auto it = m_gates_to_nodes.find(g); it != m_gates_to_nodes.end())
                {
                    VECTOR(out)[i] = it->second;
                }
                else
                {
                    return ERR("no node for gate '" + g->get_name() + "' with ID " + std::to_string(g->get_id()) + " exists in graph for netlist with ID " + std::to_string(m_nl->get_id()));
                }
            }
            return OK(std::move(out));
        }
 
        Result<igraph_vector_int_t> NetlistGraph::get_vertices_from_gates_igraph(const std::set<Gate*>& gates) const
        {
            igraph_vector_int_t out;
            if (auto res = igraph_vector_int_init(&out, gates.size()); res != IGRAPH_SUCCESS)
            {
                return ERR(igraph_strerror(res));
            }
 
            u32 i = 0;
            for (auto gates_it = gates.begin(); gates_it != gates.end(); gates_it++)
            {
                auto* g = *gates_it;
 
                if (!g)
                {
                    return ERR("gate at index " + std::to_string(i) + " is a nullptr");
                }
 
                if (const auto nodes_it = m_gates_to_nodes.find(g); nodes_it != m_gates_to_nodes.end())
                {
                    VECTOR(out)[i] = nodes_it->second;
                }
                else
                {
                    return ERR("no node for gate '" + g->get_name() + "' with ID " + std::to_string(g->get_id()) + " exists in graph for netlist with ID " + std::to_string(m_nl->get_id()));
                }
 
                i++;
            }
            return OK(std::move(out));
        }
 
        Result<u32> NetlistGraph::get_vertex_from_gate(Gate* g) const
        {
            const auto res = get_vertices_from_gates(std::vector<Gate*>({g}));
            if (res.is_error())
            {
                return ERR(res.get_error());
            }
 
            return OK(res.get().front());
        }
 
        bool NetlistGraph::is_shadow_vertex(const u32 vertex) const
        {
            return m_shadow_nodes_to_nodes.find(vertex) != m_shadow_nodes_to_nodes.end();
        }
 
        Result<std::vector<u32>> NetlistGraph::get_all_vertices_from_gate(Gate* g) const
        {
            const auto node_it = m_gates_to_nodes.find(g);
            if (node_it == m_gates_to_nodes.end())
            {
                return ERR("no vertex exists for gate '" + g->get_name() + "' with ID " + std::to_string(g->get_id()));
            }
 
            std::vector<u32> res = {node_it->second};
            for (const auto& [shadow_node, node] : m_shadow_nodes_to_nodes)
            {
                if (node == node_it->second)
                {
                    res.push_back(shadow_node);
                }
            }
            return OK(res);
        }
 
        u32 NetlistGraph::get_num_vertices(bool only_connected) const
        {
            u32 num_vertices = igraph_vcount(&m_graph);
 
            if (!only_connected)
            {
                return num_vertices;
            }
            else
            {
                u32 num_connected_vertices = 0;
 
                igraph_vector_int_t degrees;
                igraph_vector_int_init(&degrees, num_vertices);
 
                igraph_vs_t v_sel = igraph_vss_all();
                igraph_degree(&m_graph, &degrees, v_sel, IGRAPH_ALL, IGRAPH_LOOPS);
 
                for (u32 i = 0; i < num_vertices; i++)
                {
                    if (VECTOR(degrees)[i] != 0)
                    {
                        num_connected_vertices++;
                    }
                }
 
                igraph_vector_int_destroy(&degrees);
                igraph_vs_destroy(&v_sel);
 
                return num_connected_vertices;
            }
        }
 
        u32 NetlistGraph::get_num_edges() const
        {
            return igraph_ecount(&m_graph);
        }
 
        Result<std::vector<u32>> NetlistGraph::get_vertices(bool only_connected) const
        {
            u32 num_vertices = igraph_vcount(&m_graph);
 
            if (!only_connected)
            {
                std::vector<u32> vertices(num_vertices);
                for (u32 i = 0; i < num_vertices; i++)
                {
                    vertices[i] = i;
                }
                return OK(vertices);
            }
            else
            {
                std::vector<u32> vertices;
 
                igraph_vector_int_t degrees;
                if (auto res = igraph_vector_int_init(&degrees, num_vertices); res != IGRAPH_SUCCESS)
                {
                    return ERR(igraph_strerror(res));
                }
 
                igraph_vs_t v_sel = igraph_vss_all();
                if (auto res = igraph_degree(&m_graph, &degrees, v_sel, IGRAPH_ALL, IGRAPH_LOOPS); res != IGRAPH_SUCCESS)
                {
                    igraph_vs_destroy(&v_sel);
                    igraph_vector_int_destroy(&degrees);
                    return ERR(igraph_strerror(res));
                }
 
                for (u32 i = 0; i < num_vertices; i++)
                {
                    if (VECTOR(degrees)[i] != 0)
                    {
                        vertices.push_back(i);
                    }
                }
 
                igraph_vector_int_destroy(&degrees);
                igraph_vs_destroy(&v_sel);
 
                return OK(vertices);
            }
        }
 
        Result<std::vector<std::pair<u32, u32>>> NetlistGraph::get_edges() const
        {
            const u32 ecount = igraph_ecount(&m_graph);
 
            igraph_vector_int_t edges;
            if (auto res = igraph_vector_int_init(&edges, 2 * ecount); res != IGRAPH_SUCCESS)
            {
                return ERR(igraph_strerror(res));
            }
 
            if (auto res = igraph_get_edgelist(&m_graph, &edges, false); res != IGRAPH_SUCCESS)
            {
                igraph_vector_int_destroy(&edges);
                return ERR(igraph_strerror(res));
            }
 
            std::vector<std::pair<u32, u32>> e_vec(ecount);
            for (u32 i = 0; i < ecount; i++)
            {
                const u32 src_vertex = (u32)VECTOR(edges)[2 * i];
                const u32 dst_vertex = (u32)VECTOR(edges)[2 * i + 1];
 
                e_vec[i] = std::make_pair(src_vertex, dst_vertex);
            }
 
            return OK(e_vec);
        }
 
        Result<std::vector<std::pair<Gate*, Gate*>>> NetlistGraph::get_edges_in_netlist() const
        {
            const u32 ecount = igraph_ecount(&m_graph);
 
            igraph_vector_int_t edges;
            if (auto res = igraph_vector_int_init(&edges, 2 * ecount); res != IGRAPH_SUCCESS)
            {
                return ERR(igraph_strerror(res));
            }
 
            if (auto res = igraph_get_edgelist(&m_graph, &edges, false); res != IGRAPH_SUCCESS)
            {
                igraph_vector_int_destroy(&edges);
                return ERR(igraph_strerror(res));
            }
 
            std::vector<std::pair<Gate*, Gate*>> e_vec(ecount);
            for (u32 i = 0; i < ecount; i++)
            {
                const u32 src_vertex = (u32)VECTOR(edges)[2 * i];
                const u32 dst_vertex = (u32)VECTOR(edges)[2 * i + 1];
                Gate *src_gate, *dst_gate;
 
                if (const auto it = m_nodes_to_gates.find(src_vertex); it != m_nodes_to_gates.end())
                {
                    src_gate = it->second;
                    if (src_gate == nullptr)
                    {
                        log_warning("graph_algorithm",
                                    "ignored edge (" + std::to_string(src_vertex) + "," + std::to_string(dst_vertex) + ") at dummy source vertex '" + std::to_string(src_vertex) + "'");
                        continue;
                    }
                }
 
                if (const auto it = m_nodes_to_gates.find(dst_vertex); it != m_nodes_to_gates.end())
                {
                    dst_gate = it->second;
                    if (dst_gate == nullptr)
                    {
                        log_warning("graph_algorithm",
                                    "ignored edge (" + std::to_string(src_vertex) + "," + std::to_string(dst_vertex) + ") at dummy destination vertex '" + std::to_string(dst_vertex) + "'");
                        continue;
                    }
                }
 
                e_vec[i] = std::make_pair(src_gate, dst_gate);
            }
 
            return OK(e_vec);
        }
 
        Result<std::monostate> NetlistGraph::add_edges(const std::vector<std::pair<Gate*, Gate*>>& edges)
        {
            igraph_vector_int_t e_vec;
            if (auto res = igraph_vector_int_init(&e_vec, 2 * edges.size()); res != IGRAPH_SUCCESS)
            {
                return ERR(igraph_strerror(res));
            }
 
            u32 edge_index = 0;
            for (const auto& [src_gate, dst_gate] : edges)
            {
                if (auto it = m_gates_to_nodes.find(src_gate); it != m_gates_to_nodes.end())
                {
                    VECTOR(e_vec)[edge_index++] = it->second;
                }
                else
                {
                    igraph_vector_int_destroy(&e_vec);
                    return ERR("no node for gate '" + src_gate->get_name() + "' with ID " + std::to_string(src_gate->get_id()) + " exists in graph for netlist with ID "
                               + std::to_string(m_nl->get_id()));
                }
 
                if (auto it = m_gates_to_nodes.find(dst_gate); it != m_gates_to_nodes.end())
                {
                    VECTOR(e_vec)[edge_index++] = it->second;
                }
                else
                {
                    igraph_vector_int_destroy(&e_vec);
                    return ERR("no node for gate '" + dst_gate->get_name() + "' with ID " + std::to_string(dst_gate->get_id()) + " exists in graph for netlist with ID "
                               + std::to_string(m_nl->get_id()));
                }
            }
 
            if (auto res = igraph_add_edges(&m_graph, &e_vec, nullptr); res != IGRAPH_SUCCESS)
            {
                igraph_vector_int_destroy(&e_vec);
                return ERR(igraph_strerror(res));
            }
 
            return OK({});
        }
 
        Result<std::monostate> NetlistGraph::add_edges(const std::vector<std::pair<u32, u32>>& edges)
        {
            igraph_vector_int_t e_vec;
            if (auto err = igraph_vector_int_init(&e_vec, 2 * edges.size()); err != IGRAPH_SUCCESS)
            {
                return ERR(igraph_strerror(err));
            }
 
            u32 vcount = igraph_vcount(&m_graph);
 
            u32 edge_index = 0;
            for (const auto& [src_vertex, dst_vertex] : edges)
            {
                if (src_vertex >= vcount)
                {
                    igraph_vector_int_destroy(&e_vec);
                    return ERR("source vertex '" + std::to_string(src_vertex) + "' does not exist in graph for netlist with ID " + std::to_string(m_nl->get_id()));
                }
                if (dst_vertex >= vcount)
                {
                    igraph_vector_int_destroy(&e_vec);
                    return ERR("destination vertex '" + std::to_string(dst_vertex) + "' does not exist in graph for netlist with ID " + std::to_string(m_nl->get_id()));
                }
 
                VECTOR(e_vec)[edge_index++] = src_vertex;
                VECTOR(e_vec)[edge_index++] = dst_vertex;
            }
 
            if (auto err = igraph_add_edges(&m_graph, &e_vec, nullptr); err != IGRAPH_SUCCESS)
            {
                igraph_vector_int_destroy(&e_vec);
                return ERR(igraph_strerror(err));
            }
 
            return OK({});
        }
 
        Result<std::monostate> NetlistGraph::add_edges(const std::map<Gate*, std::set<Gate*>>& edges)
        {
            u32 edge_count = 0;
            for (const auto& [_, dst_gates] : edges)
            {
                edge_count += dst_gates.size();
            }
 
            igraph_vector_int_t e_vec;
            if (auto err = igraph_vector_int_init(&e_vec, 2 * edge_count); err != IGRAPH_SUCCESS)
            {
                return ERR(igraph_strerror(err));
            }
 
            u32 edge_index = 0;
            for (const auto& [src_gate, dst_gates] : edges)
            {
                u32 src_vertex;
                if (auto it = m_gates_to_nodes.find(src_gate); it != m_gates_to_nodes.end())
                {
                    src_vertex = it->second;
                }
                else
                {
                    igraph_vector_int_destroy(&e_vec);
                    return ERR("no node for gate '" + src_gate->get_name() + "' with ID " + std::to_string(src_gate->get_id()) + " exists in graph for netlist with ID "
                               + std::to_string(m_nl->get_id()));
                }
 
                for (auto* dst_gate : dst_gates)
                {
                    if (auto it = m_gates_to_nodes.find(dst_gate); it != m_gates_to_nodes.end())
                    {
                        VECTOR(e_vec)[edge_index++] = src_vertex;
                        VECTOR(e_vec)[edge_index++] = it->second;
                    }
                    else
                    {
                        igraph_vector_int_destroy(&e_vec);
                        return ERR("no node for gate '" + dst_gate->get_name() + "' with ID " + std::to_string(dst_gate->get_id()) + " exists in graph for netlist with ID "
                                   + std::to_string(m_nl->get_id()));
                    }
                }
            }
 
            if (auto err = igraph_add_edges(&m_graph, &e_vec, nullptr); err != IGRAPH_SUCCESS)
            {
                igraph_vector_int_destroy(&e_vec);
                return ERR(igraph_strerror(err));
            }
 
            return OK({});
        }
 
        Result<std::monostate> NetlistGraph::delete_edges(const std::vector<std::pair<Gate*, Gate*>>& edges)
        {
            igraph_vector_int_t e_vec;
            if (auto err = igraph_vector_int_init(&e_vec, 2 * edges.size()); err != IGRAPH_SUCCESS)
            {
                return ERR(igraph_strerror(err));
            }
 
            u32 vcount = igraph_vcount(&m_graph);
 
            u32 edge_index = 0;
            for (const auto& [src_gate, dst_gate] : edges)
            {
                if (auto it = m_gates_to_nodes.find(src_gate); it != m_gates_to_nodes.end())
                {
                    VECTOR(e_vec)[edge_index++] = it->second;
                }
                else
                {
                    igraph_vector_int_destroy(&e_vec);
                    return ERR("no node for gate '" + src_gate->get_name() + "' with ID " + std::to_string(src_gate->get_id()) + " exists in graph for netlist with ID "
                               + std::to_string(m_nl->get_id()));
                }
 
                if (auto it = m_gates_to_nodes.find(dst_gate); it != m_gates_to_nodes.end())
                {
                    VECTOR(e_vec)[edge_index++] = it->second;
                }
                else
                {
                    igraph_vector_int_destroy(&e_vec);
                    return ERR("no node for gate '" + dst_gate->get_name() + "' with ID " + std::to_string(dst_gate->get_id()) + " exists in graph for netlist with ID "
                               + std::to_string(m_nl->get_id()));
                }
            }
 
            igraph_es_t e_sel;
            if (auto res = igraph_es_pairs(&e_sel, &e_vec, IGRAPH_DIRECTED); res != IGRAPH_SUCCESS)
            {
                igraph_vector_int_destroy(&e_vec);
                return ERR(igraph_strerror(res));
            }
 
            if (auto res = igraph_delete_edges(&m_graph, e_sel); res != IGRAPH_SUCCESS)
            {
                igraph_es_destroy(&e_sel);
                igraph_vector_int_destroy(&e_vec);
                return ERR(igraph_strerror(res));
            }
 
            igraph_es_destroy(&e_sel);
            igraph_vector_int_destroy(&e_vec);
 
            return OK({});
        }
 
        Result<std::monostate> NetlistGraph::delete_edges(const std::vector<std::pair<u32, u32>>& edges)
        {
            igraph_vector_int_t e_vec;
            if (auto err = igraph_vector_int_init(&e_vec, 2 * edges.size()); err != IGRAPH_SUCCESS)
            {
                return ERR(igraph_strerror(err));
            }
 
            u32 vcount = igraph_vcount(&m_graph);
 
            u32 edge_index = 0;
            for (const auto& [src_vertex, dst_vertex] : edges)
            {
                if (src_vertex >= vcount)
                {
                    igraph_vector_int_destroy(&e_vec);
                    return ERR("source vertex '" + std::to_string(src_vertex) + "' does not exist in graph for netlist with ID " + std::to_string(m_nl->get_id()));
                }
                if (dst_vertex >= vcount)
                {
                    igraph_vector_int_destroy(&e_vec);
                    return ERR("destination vertex '" + std::to_string(dst_vertex) + "' does not exist in graph for netlist with ID " + std::to_string(m_nl->get_id()));
                }
 
                VECTOR(e_vec)[edge_index++] = src_vertex;
                VECTOR(e_vec)[edge_index++] = dst_vertex;
            }
 
            igraph_es_t e_sel;
            if (auto res = igraph_es_pairs(&e_sel, &e_vec, IGRAPH_DIRECTED); res != IGRAPH_SUCCESS)
            {
                igraph_vector_int_destroy(&e_vec);
                return ERR(igraph_strerror(res));
            }
 
            if (auto res = igraph_delete_edges(&m_graph, e_sel); res != IGRAPH_SUCCESS)
            {
                igraph_es_destroy(&e_sel);
                igraph_vector_int_destroy(&e_vec);
                return ERR(igraph_strerror(res));
            }
 
            igraph_es_destroy(&e_sel);
            igraph_vector_int_destroy(&e_vec);
 
            return OK({});
        }
 
        void NetlistGraph::print() const
        {
            igraph_write_graph_edgelist(&m_graph, stdout);
        }
    }    // namespace graph_algorithm
 
    template<>
    std::map<graph_algorithm::NetlistGraph::Direction, std::string> EnumStrings<graph_algorithm::NetlistGraph::Direction>::data = {{graph_algorithm::NetlistGraph::Direction::NONE, "NONE"},
                                                                                                                                   {graph_algorithm::NetlistGraph::Direction::IN, "IN"},
                                                                                                                                   {graph_algorithm::NetlistGraph::Direction::OUT, "OUT"},
                                                                                                                                   {graph_algorithm::NetlistGraph::Direction::ALL, "ALL"}};
}    // namespace hal