graph.hpp

Go to the documentation of this file.

 
#pragma once
 
#include <cassert>
#include <cstdint>
#include <py2cpp/py2cpp.hpp>
#include <type_traits>
#include <vector>
#include <xnetwork/classes/coreviews.hpp>    // import AtlasView, AdjacencyView
#include <xnetwork/classes/reportviews.hpp>  // import NodeView, EdgeView, DegreeView
 
template <typename T> using Value_type = typename T::value_type;
 
namespace xnetwork {
 
    // struct object : py::dict<const char*, std::any> {};
 
    template <typename _nodeview_t, typename adjlist_t = py::set<Value_type<_nodeview_t>>,
              typename adjlist_outer_dict_factory = py::dict<Value_type<_nodeview_t>, adjlist_t>>
    class Graph {
      public:
        using nodeview_t = _nodeview_t;
        using Node = typename nodeview_t::value_type;  // luk
        // using dict = py::dict<const char*, std::any>;
        // using graph_attr_dict_factory = dict;
        // using edge_attr_dict_factory = dict;
        // using node_attr_dict_factory = dict;
        // using node_dict_factory = py::dict<Node, node_attr_dict_factory>;
        // using adjlist_inner_dict_factory = py::dict<Node,
        // edge_attr_dict_factory>;
        using adjlist_inner_dict_factory = adjlist_t;
        using key_type = typename adjlist_t::key_type;
        using value_type = typename adjlist_t::value_type;
        using edge_t = std::pair<Node, Node>;
        using node_t = Node;
 
        size_t _num_of_edges = 0;  
 
        // std::vector<Node > _Nodes{}
        nodeview_t _node;  
        // graph_attr_dict_factory graph{};  // dictionary for graph attributes
        // node_dict_factory _node{};  // empty node attribute dict
        adjlist_outer_dict_factory _adj;  
 
        // auto __getstate__() {
        //     attr = this->__dict__.copy();
        //     // remove lazy property attributes
        //     if ("nodes" : attr) {
        //         del attr["nodes"];
        //     }
        //     if ("edges" : attr) {
        //         del attr["edges"];
        //     }
        //     if ("degree" : attr) {
        //         del attr["degree"];
        //     }
        //     return attr;
        // }
 
        explicit Graph(const nodeview_t& Nodes)
            : _node{Nodes},
              _adj{}  // py::dict???
        {}
 
        explicit Graph(uint32_t num_nodes)
            : _node{py::range<uint32_t>(num_nodes)},
              _adj(num_nodes)  // std::vector
        {}
 
        // Graph(const Graph&) = delete;            // don't copy
        // Graph& operator=(const Graph&) = delete; // don't copy
        // Graph(Graph&&) noexcept = default;
 
        static auto end_points(edge_t& e) -> edge_t& { return e; }
 
        static auto end_points(const edge_t& e) -> const edge_t& { return e; }
 
        auto adj() const {
            using T = std::remove_reference_t<decltype(this->_adj)>;
            return AdjacencyView<const T&>(this->_adj);
        }
 
        auto adj() {
            using T = std::remove_cv_t<decltype(this->_adj)>;
            return AdjacencyView<T>(this->_adj);
        }
 
        auto _nodes_nbrs() const {
            // @TODO support py:dict
            return py::enumerate(this->_adj);
        }
 
        // auto null_vertex() const -> const Node&
        // {
        //     return *(this->_node.end());
        // }
 
        // Node& null_vertex()
        // {
        //     return *(this->_node.end());
        // }
 
        // auto get_name() {
        //     if (!this->graph.contains("name")) {
        //         return "";
        //     }
        //     return std::any_cast<const char*>(this->graph["name"]);
        // }
 
        // // @name.setter
        // auto set_name(std::string_view s) { this->graph["name"] = std::any(s); }
 
        auto begin() const { return std::begin(this->_node); }
 
        auto end() const { return std::end(this->_node); }
 
        auto contains(const Node& node) const -> bool { return this->_node.contains(node); }
 
        auto operator[](const Node& node) const -> const auto& { return this->adj().at(node); }
 
        auto at(const Node& node) const -> const auto& { return this->adj().at(node); }
 
        auto operator[](const Node& node) -> auto& { return this->adj()[node]; }
 
        auto nodes() {
            using T = std::remove_reference_t<decltype(*this)>;
            auto nodes = NodeView<T>(*this);
            // Lazy View creation: overload the (class) property on the instance
            // Then future gra.nodes use the existing View
            // setattr doesn"t work because attribute already exists
            // this->operator[]("nodes") = std::any(nodes);
            return nodes;
        }
 
        auto number_of_nodes() const -> size_t { return this->_node.size(); }
 
        auto order() const { return this->_node.size(); }
 
        auto size() const -> size_t { return this->_node.size(); }
 
        auto number_of_edges() const -> size_t { return this->_num_of_edges; }
 
        auto edges() const -> std::vector<edge_t> {
            std::vector<edge_t> result;
            for (const auto& node : this->_node) {
                for (const auto& nbr : this->_adj[node]) {
                    if (node < nbr) {
                        result.emplace_back(node, nbr);
                    }
                }
            }
            return result;
        }
 
        auto has_node(const Node& node) const -> bool { return this->_node.contains(node); }
 
        template <typename U = key_type> auto add_edge(const Node& node_u, const Node& node_v) ->
            typename std::enable_if<std::is_same<U, value_type>::value>::type {
            this->_adj[node_u].insert(node_v);
            this->_adj[node_v].insert(node_u);
            ++this->_num_of_edges;
        }
 
        template <typename U = key_type> auto add_edge(const Node& node_u, const Node& node_v) ->
            typename std::enable_if<!std::is_same<U, value_type>::value>::type {
            using T = typename adjlist_t::mapped_type;
            auto data = this->_adj[node_u].get(node_v, T{});
            this->_adj[node_u][node_v] = data;
            this->_adj[node_v][node_u] = data;
            ++this->_num_of_edges;
        }
 
        template <typename T> auto add_edge(const Node& node_u, const Node& node_v, const T& data) {
            this->_adj[node_u][node_v] = data;
            this->_adj[node_v][node_u] = data;
            ++this->_num_of_edges;
        }
 
        template <typename C1> auto add_edges_from(const C1& edges) {
            for (const auto& e : edges) {
                this->add_edge(e.first, e.second);
            }
        }
 
        template <typename C1, typename C2> auto add_edges_from(const C1& edges, const C2& data) {
            auto it = data.begin();
            for (const auto& e : edges) {
                this->add_edge(e.first, e.second, *it);
                ++it;
            }
        }
 
        auto has_edge(const Node& node_u, const Node& node_v) const -> bool {
            return this->_adj.at(node_u).contains(node_v);
        }
 
        auto degree(const Node& node) const { return this->_adj[node].size(); }
 
        auto clear() {
            this->_adj.clear();
            // this->_node.clear();
            // this->graph.clear();
        }
 
        template <typename F> auto for_each_edge(F&& func) const -> void {
            for (const auto& node : this->_node) {
                for (const auto& nbr : this->_adj[node]) {
                    if (node < nbr) {
                        std::forward<F>(func)(node, nbr);
                    }
                }
            }
        }
 
        auto is_multigraph() const { return false; }
 
        auto is_directed() const { return false; }
    };
 
    using SimpleGraph = Graph<decltype(py::range<uint32_t>(uint32_t{})), py::set<uint32_t>,
                              std::vector<py::set<uint32_t>>>;
 
    // template <typename nodeview_t,
    //           typename adjlist_t> Graph(int )
    // -> Graph<decltype(py::range(1)), py::set<int>>;
 
}  // namespace xnetwork