Program Listing for File graph.hpp¶
↰ Return to documentation for file (xnetwork/classes/graph.hpp)
#pragma once
#include <boost/any.hpp>
#include <boost/utility/string_view.hpp>
#include <cassert>
#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
namespace xn
{
struct object : py::dict<const char*, boost::any>
{
};
template <typename __nodeview_t,
typename adjlist_t = py::set<Value_type<__nodeview_t>>>
class Graph : public object
{
public:
using nodeview_t = __nodeview_t;
using Node = typename nodeview_t::value_type; // luk
using dict = py::dict<const char*, boost::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 adjlist_outer_dict_factory = std::vector<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;
public:
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; // empty adjacency dict
// 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(Nodes.size())
{
}
explicit Graph(int num_nodes)
: _node {py::range<int>(num_nodes)}
, _adj(num_nodes)
{
}
Graph(const Graph&) = delete; // don't copy
Graph& operator=(const Graph&) = delete; // don't copy
Graph(Graph&&) noexcept = default;
static edge_t& end_points(edge_t& e)
{
return e;
}
static const edge_t& end_points(const edge_t& e)
{
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
{
return py::enumerate(this->_adj);
}
Node null_vertex() const
{
return *(this->_node.end());
}
auto get_name()
{
if (!this->graph.contains("name"))
{
return "";
}
return boost::any_cast<const char*>(this->graph["name"]);
}
// @name.setter
auto set_name(boost::string_view s)
{
this->graph["name"] = boost::any(s);
}
auto begin() const
{
return std::begin(this->_node);
}
auto end() const
{
return std::end(this->_node);
}
bool contains(const Node& n)
{
return this->_node.contains(n);
}
const auto& operator[](const Node& n) const
{
return this->adj()[n];
}
auto& operator[](const Node& n)
{
return this->adj()[n];
}
auto nodes()
{
using T = decltype(*this);
auto nodes = NodeView<T>(*this);
// Lazy View creation: overload the (class) property on the instance
// Then future G.nodes use the existing View
// setattr doesn"t work because attribute already exists
this->operator[]("nodes") = boost::any(nodes);
return nodes;
}
auto number_of_nodes() const
{
return this->_node.size();
}
auto number_of_edges() const
{
return this->_num_of_edges;
}
auto order()
{
return this->_node.size();
}
auto has_node(const Node& n)
{
return this->_node.contains(n);
}
template <typename U = key_type>
typename std::enable_if<std::is_same<U, value_type>::value>::type add_edge(
const Node& u, const Node& v)
{
// auto [u, v] = u_of_edge, v_of_edge;
// add nodes
assert(this->_node.contains(u));
assert(this->_node.contains(v));
// add the edge
// datadict = this->_adj[u].get(v, this->edge_attr_dict_factory());
// datadict.update(attr);
// set
this->_adj[u].insert(v);
this->_adj[v].insert(u);
this->_num_of_edges += 1;
}
template <typename U = key_type>
typename std::enable_if<!std::is_same<U, value_type>::value>::type add_edge(
const Node& u, const Node& v)
{
// auto [u, v] = u_of_edge, v_of_edge;
// add nodes
assert(this->_node.contains(u));
assert(this->_node.contains(v));
// add the edge
// datadict = this->_adj[u].get(v, this->edge_attr_dict_factory());
// datadict.update(attr);
using T = typename adjlist_t::mapped_type;
auto data = this->_adj[u].get(v, T {});
this->_adj[u][v] = data;
this->_adj[v][u] = data; // ???
this->_num_of_edges += 1;
}
template <typename T>
auto add_edge(const Node& u, const Node& v, const T& data)
{
assert(this->_node.contains(u));
assert(this->_node.contains(v));
this->_adj[u][v] = data;
this->_adj[v][u] = data;
this->_num_of_edges += 1;
}
template <typename C1, typename C2>
auto add_edges_from(const C1& edges, const C2& data)
{
auto N = edges.size();
for (auto i = 0; i != N; ++i)
{
const auto& e = edges[i];
this->add_edge(e.first, e.second, data[i]);
}
}
auto has_edge(const Node& u, const Node& v) -> bool
{
return this->_adj[u].contains(v);
}
auto degree(const Node& n) const
{
return this->_adj[n].size();
}
// auto edges() {
// auto edges = EdgeView(*this);
// this->operator[]("edges") = boost::any(edges);
// return edges;
// }
// /// @property
// auto degree() {
// /*! A DegreeView for the Graph as G.degree or G.degree().
// The node degree is the number of edges adjacent to the node.
// The weighted node degree is the sum of the edge weights for
// edges incident to that node.
// This object provides an iterator for (node, degree) as well as
// lookup for the degree for a single node.
// Parameters
// ----------
// nbunch : single node, container, or all nodes (default= all nodes);
// The view will only report edges incident to these nodes.
// weight : string or None, optional (default=None);
// The name of an edge attribute that holds the numerical value used
// as a weight. If None, then each edge has weight 1.
// The degree is the sum of the edge weights adjacent to the node.
// Returns
// -------
// If a single node is requested
// deg : int
// Degree of the node
// OR if (multiple nodes are requested
// nd_view : A DegreeView object capable of iterating (node, degree)
// pairs
// Examples
// --------
// >>> G = xn::path_graph(4); // or DiGraph, MultiGraph, MultiDiGraph,
// etc
// >>> G.degree[0]; // node 0 has degree 1
// 1
// >>> list(G.degree([0, 1, 2]));
// [(0, 1), (1, 2), (2, 2)];
// */
// auto degree = DegreeView(*this);
// this->operator[]("degree") = boost::any(degree);
// return degree;
// }
auto clear()
{
this->_adj.clear();
// this->_node.clear();
this->graph.clear();
}
auto is_multigraph()
{
return false;
}
auto is_directed()
{
return false;
}
};
using SimpleGraph = Graph<decltype(py::range<int>(1)), py::set<int>>;
// template <typename nodeview_t,
// typename adjlist_t> Graph(int )
// -> Graph<decltype(py::range<int>(1)), py::set<int>>;
} // namespace xn