graph/graph.hpp

struct ClusterItem

struct gviz::graph::Graph::EdgeItem

Public Members

std::size_t n

std::size_t m

NodeId node_a_id

NodeId node_b_id

template<typename Registry, GraphDir DirV = GraphDir::undirected> class gviz::graph::Graph

#include <graph.hpp>

an adjancency-matrix implementation of graph using registry for id generation and attribute management, with support of clustering nodes.

node, edge, and cluster are called entity.

creating any kind of entity returns a unqiue id of type NodeId, EdgeId, ClusterId respectively for node, edge, cluster. using a removed id results in undefined behavior.

NOTE: use proxy methods to get/set/emplace/remove an entity’s attribute instead of get_raw_registry.

Public Types

using entity_type = typename Registry::entity_type

using registry_type = Registry 

using NodeId = entity_type 

using EdgeId = entity_type : always convertible to entity_type

using ClusterId = entity_type : always convertible to entity_type

Public Functions

inline auto &get_raw_registry()

inline const auto &get_raw_registry() const

inline constexpr bool is_directed_graph() const

inline constexpr bool is_undirected_graph() const

template<typename Attr> inline auto get_entity_attr(entity_type entity_id) -> utils::OptionalRef<Attr>

get an entity_id entity’s attribute Attr

Returns: an optional reference to Attr of entity_id if entity_id exists and Attr is set or otherwise utils::nulloptref.

template<typename Attr> inline auto get_entity_attr(entity_type entity_id) const -> utils::OptionalRef<const Attr>

get an entity_id entity’s attribute Attr

Returns: a const optional reference to Attr of entity_id if entity_id exists and Attr is set or otherwise utils::nulloptref.

template<typename Attr> inline bool has_entity_attr(entity_type entity_id) const

checks if entity_id is valid and has its attribute Attr set.

Parameters: entity_id – entity’s id.
Returns: true if entity_id exists and Attr is set, otherwise false.

template<typename Attr, typename ValT> inline auto set_entity_attr(entity_type entity_id, ValT &&value) -> utils::OptionalRef<Attr>

sets an entity’s attribute if entity_id is valid.

Parameters

entity_id – entity’s id.
value – the value to be set, it’ll be converted to Attr explicitly.

Returns

utils::nulloptref if entity_id is invalid, otherwise an optional reference to the residing Attr which was set in registry.

template<typename Attr, typename ...Args> inline auto emplace_entity_attr(entity_type entity_id, Args&&... args) -> utils::OptionalRef<Attr>

constructs an entity’s attribute in-place by given args if entity_id is valid.

Parameters

entity_id – entity’s id.
args – arguments to be passed to Attr constructor.

Returns

utils::nulloptref if entity_id is invalid, otherwise an optional reference to the constructed Attr which was placed in registry.

template<typename Attr> inline bool remove_entity_attr(entity_type entity_id)

unsets/removes Attr attribute of entity if entity_id is valid and has Attr.

Parameters

entity_id – entity’s id.
args – arguments to be passed to Attr constructor.

Returns

true if entity_id is valid or has Attr, otherwise false.

inline auto create_cluster() -> ClusterId 

creates a new cluster.

Returns: id of created cluster.

inline bool add_to_cluster(ClusterId cluster_id, NodeId node_id)

adds a node to a cluster.

if node was already in a cluster, it’ll be detached and added to given cluster.

Parameters

cluster_id – target cluster’s id to add node to.
node_id – node’s id to add to cluster.

Returns

true if cluster_id and node_id are both valid, otherwise false.

inline auto create_node() -> NodeId 

creates a new node.

Returns: id of the created node.

inline auto create_node_in(ClusterId cluster_id) -> std::optional<NodeId>

creates a node in the given cluster.

Parameters: cluster_id – cluster’s id to create node in.
Returns: an optional containing NodeId if cluster_id is valid, otherwise std::nullopt.

inline auto create_edge(NodeId node_a_id, NodeId node_b_id) -> std::optional<EdgeId>

creates an edge between two given nodes.

if graph is directed, first node is source and second is dest.

if the same edge existed between these two nodes, the id of existing edge will be returned.

Parameters

node_a_id – first (or source) node’s id.
node_b_id – second (or dest) node’s id.

Returns

an optional containing EdgeId if both nodes’ id are valid, otherwise std::nullopt.

inline auto get_cluster_nodes(ClusterId cluster_id) const

returns an iterable view to node ids of given cluster.

Parameters: cluster_id – target cluster’s id.
Returns: an iterable view to cluster’s nodes. if cluster_id is invalid, the view will be empty.

inline auto get_edge_id(NodeId node_a_id, NodeId node_b_id) const -> std::optional<EdgeId>

retrieves given two nodes’ edge. direction is determined by order of given arguments.

Parameters

node_a_id – first node’s id.
node_b_id – second node’s id.

Returns

an optional containing EdgeId if both nodes’ id are valid and an edge (desired direction) is between them, otherwise std::nullopt.

inline auto get_edge_nodes(EdgeId edge_id) const -> std::optional<std::pair<NodeId, NodeId>>

retrieves given edge’s pair of nodes.

Parameters: edge_id – target edge’s id.
Returns: an optional containing a pair of NodeId if edge_id is valid, otherwise std::nullopt.

inline bool remove_cluster(ClusterId cluster_id)

detaches given cluster’s nodes from it, and then removes the cluster.

Parameters: cluster_id – target cluster’s id.
Returns: true if cluster_id is valid, otherwise false.

inline bool remove_node(NodeId node_id)

removes a node.

Parameters: node_id – target node’s id.
Returns: true if node_id is valid, otherwise false.

inline bool detach_clustered_node(NodeId node_id)

detaches a node from its cluster if it is attached to one.

Parameters: node_id – target node’s id.
Returns: true if node_id is valid, otherwise false.

inline bool remove_edge(NodeId node_a_id, NodeId node_b_id)

removes an edge between given two nodes.

if directed graph, first node is source and second is dest of the edge.

Parameters

node_a_id – first (source) node’s id.
node_b_id – second (dest) node’s id.

Returns

true if both nodes’ id are valid and an edge exists between, otherwise false.

inline bool remove_edge(EdgeId edge_id)

removes an edge by given id.

Parameters: edge_id – target edge’s id.
Returns: true if edge_id is valid, otherwise false.

inline auto get_degree(NodeId node_id, EdgeDir dir = EdgeDir::inout) const -> std::optional<std::size_t>

count of edges of given node’s node_id in given direction dir.

direction dir is irrelevant when graph is undirected.

Parameters: node_id – target node’s id.
Returns: an optional containing size_t count number if node_id is valid, otherwise std::nullopt.

inline auto get_edges_of(NodeId node_id, EdgeDir dir = EdgeDir::inout) const

returns view of edges of a given node’s node_id in direction dir.

to get 1st order neighbours of a node, combine this with get_edge_nodes.

Parameters: node_id – target node’s id.
Returns: a CallbackView to edges of target node, if node_id is valid, otherwise an empty CallbackView.

inline auto nodes_view() const

view of all nodes in graph.

Returns: a CallbackView to all nodes in graph.

inline auto edges_view() const

view of all edges in graph.

Returns: a CallbackView to all edges in graph.

inline auto clusters_view() const

view of all clusters in graph.

Returns: a CallbackView to all clusters in graph.

inline std::size_t node_count() const noexcept

inline std::size_t edge_count() const noexcept

inline std::size_t cluster_count() const noexcept

Private Types

using optional_entity_type = std::optional<entity_type>

using matrix_type = std::conditional_t<is_undirected, detail::DynamicSquareMatrix<optional_entity_type>, detail::DynamicHalfSquareMatrix<optional_entity_type>>

using map_type = std::map<entity_type, Item>

Private Members

matrix_type matrix_ = {}

map_type entities_map_ = {}

registry_type registry_ = {}

std::size_t nodes_count_ = 0

std::size_t edges_count_ = 0

std::size_t clusters_count_ = 0

Private Static Attributes

static constexpr bool is_undirected = DirV == GraphDir::undirected 

class gviz::graph::Graph::Item

Public Functions

inline Item()

inline constexpr Item(NodeItem node) noexcept

inline constexpr Item(EdgeItem edge) noexcept

inline constexpr Item(ClusterItem cluster) noexcept

inline constexpr EntityTypeEnum type() const noexcept

inline constexpr bool is_node() const noexcept

inline constexpr bool is_edge() const noexcept

inline constexpr bool is_cluster() const noexcept

inline constexpr NodeItem &as_node()

inline constexpr const NodeItem &as_node() const

inline constexpr EdgeItem &as_edge()

inline constexpr const EdgeItem &as_edge() const

inline constexpr ClusterItem &as_cluster()

inline constexpr const ClusterItem &as_cluster() const

Public Members

NodeItem node_

EdgeItem edge_

ClusterItem cluster_

Private Members

EntityTypeEnum type_

union gviz::graph::Graph::Item::[anonymous] [anonymous]

struct no_view_t

struct gviz::graph::Graph::NodeItem

always convertible to entity_type

Public Members

std::size_t idx

std::optional<ClusterId> cluster_id = std::nullopt

namespace gviz

namespace gviz::graph

Enums

enum class EntityTypeEnum

Values:

enumerator unknown

enumerator node

enumerator edge

enumerator cluster

enum class GraphDir : int

Values:

enumerator undirected

enumerator directed

enum class EdgeDir : int

Values:

enumerator in

enumerator out

enumerator inout

file graph.hpp: #include <>

#include <>

#include <>

#include <>

#include <>

#include <>

#include <>

#include <>

#include <>

#include <>

#include “”

#include “”

#include “”

#include “”

dir /home/cthulhu/projects/repos/libgvizard/include/gvizard/graph

dir /home/cthulhu/projects/repos/libgvizard/include/gvizard

dir /home/cthulhu/projects/repos/libgvizard/include