Class for very sparse graphs, especially designed for the molecular graphs. More...

#include <nuri/core/graph/graph.h>

Classes
struct	StoredEdge

Public Types
using	node_data_type = NT
using	edge_data_type = ET
using	iterator = internal::NodeIterator<Graph, false>
using	node_iterator = iterator
using	const_iterator = internal::NodeIterator<Graph, true>
using	const_node_iterator = const_iterator
using	NodeRef = internal::NodeWrapper<Graph, false>
using	ConstNodeRef = internal::NodeWrapper<Graph, true>
using	edge_iterator = internal::EdgeIterator<Graph, false>
using	const_edge_iterator = internal::EdgeIterator<Graph, true>
using	EdgeRef = internal::EdgeWrapper<Graph, false>
using	ConstEdgeRef = internal::EdgeWrapper<Graph, true>
using	adjacency_iterator = internal::AdjIterator<Graph, false>
using	const_adjacency_iterator = internal::AdjIterator<Graph, true>
using	AdjRef = internal::AdjWrapper<Graph, false>
using	ConstAdjRef = internal::AdjWrapper<Graph, true>

Public Member Functions
	Graph ()=default
	Graph (const Graph &)=default
	Graph (Graph &&) noexcept=default
Graph &	operator= (const Graph &)=default
Graph &	operator= (Graph &&) noexcept=default
	~Graph () noexcept=default
	Graph (int num_nodes)
	Create a graph with `num_nodes` nodes.
	Graph (int num_nodes, const NT &data)
	Create a graph with `num_nodes` nodes, each initialized with `data`.
bool	empty () const
int	size () const
int	num_nodes () const
bool	edge_empty () const
int	num_edges () const
int	degree (int id) const
void	reserve (int num_nodes)
void	reserve_edges (int num_edges)
int	add_node (const NT &data)
	Add a node to the graph.
int	add_node (NT &&data) noexcept
	Add a node to the graph.
template<class Iterator, internal::enable_if_compatible_iter_t< Iterator, NT > = 0>
int	add_nodes (Iterator begin, Iterator end)
	Add multiple nodes to the graph.
int	add_edge (int src, int dst, const ET &data)
	Add an edge to the graph.
int	add_edge (int src, int dst, ET &&data) noexcept
	Add an edge to the graph.
template<class Iterator, internal::enable_if_compatible_iter_t< Iterator, StoredEdge > = 0>
int	add_edges (Iterator begin, Iterator end)
	Add multiple edges to the graph.
NodeRef	operator[] (int id)
ConstNodeRef	operator[] (int id) const
NodeRef	node (int id)
ConstNodeRef	node (int id) const
NT &	node_data (int id)
const NT &	node_data (int id) const
void	clear ()
NodesErased	erase_nodes (const_iterator begin, const_iterator end)
	Erase nodes and all its associated edge(s) from the graph.
template<class UnaryPred>
NodesErased	erase_nodes (const_iterator begin, const_iterator end, UnaryPred pred)
	Erase matching nodes and all its associated edge(s) from the graph.
template<class Iterator, class = internal::enable_if_compatible_iter_t<Iterator, int>>
NodesErased	erase_nodes (Iterator begin, Iterator end)
	Erase nodes and all its associated edge(s) from the graph.
iterator	begin ()
iterator	end ()
const_iterator	begin () const
const_iterator	end () const
const_iterator	cbegin () const
const_iterator	cend () const
EdgeRef	edge (int id)
ConstEdgeRef	edge (int id) const
NodeRef	edge_src (int id)
ConstNodeRef	edge_src (int id) const
NodeRef	edge_dst (int id)
ConstNodeRef	edge_dst (int id) const
ET &	edge_data (int id)
const ET &	edge_data (int id) const
edge_iterator	find_edge (int src, int dst)
	Find an edge between two nodes.
const_edge_iterator	find_edge (int src, int dst) const
	Find an edge between two nodes.
edge_iterator	find_edge (ConstNodeRef src, ConstNodeRef dst)
	Find an edge between two nodes.
const_edge_iterator	find_edge (ConstNodeRef src, ConstNodeRef dst) const
	Find an edge between two nodes.
void	clear_edges ()
	Remove all edges from the graph.
void	erase_edge (int id)
	Erase an edge from the graph.
bool	erase_edge_between (int src, int dst)
	Erase an edge from the graph between two nodes.
bool	erase_edge_between (ConstNodeRef src, ConstNodeRef dst)
	Erase an edge from the graph between two nodes.
std::pair< int, std::vector< int > >	erase_edges (const_edge_iterator begin, const_edge_iterator end)
	Erase edges from the graph.
template<class UnaryPred>
std::pair< int, std::vector< int > >	erase_edges (const_edge_iterator begin, const_edge_iterator end, UnaryPred pred)
	Erase matching edges from the graph.
template<class Iterator, class = internal::enable_if_compatible_iter_t<Iterator, int>>
std::pair< int, std::vector< int > >	erase_edges (Iterator begin, Iterator end)
	Erase edges from the graph.
internal::EdgesWrapper< Graph, false >	edges ()
internal::EdgesWrapper< Graph, true >	edges () const
internal::EdgesWrapper< Graph, true >	cedges () const
edge_iterator	edge_begin ()
edge_iterator	edge_end ()
const_edge_iterator	edge_begin () const
const_edge_iterator	edge_end () const
const_edge_iterator	edge_cbegin () const
const_edge_iterator	edge_cend () const
adjacency_iterator	find_adjacent (int src, int dst)
	Find an adjacency entry between two nodes.
const_adjacency_iterator	find_adjacent (int src, int dst) const
	Find an adjacency entry between two nodes.
adjacency_iterator	find_adjacent (ConstNodeRef src, ConstNodeRef dst)
	Find an adjacency entry between two nodes.
const_adjacency_iterator	find_adjacent (ConstNodeRef src, ConstNodeRef dst) const
	Find an adjacency entry between two nodes.
adjacency_iterator	adj_begin (int nid)
adjacency_iterator	adj_end (int nid)
const_adjacency_iterator	adj_begin (int nid) const
const_adjacency_iterator	adj_end (int nid) const
const_adjacency_iterator	adj_cbegin (int nid) const
const_adjacency_iterator	adj_cend (int nid) const
template<class GraphLike>
void	merge (const GraphLike &other)
	Merge another graph-like object into this graph.

Friends
class	Subgraph< NT, ET, false >
class	Subgraph< NT, ET, true >

Detailed Description

template<class NT, class ET>
class nuri::Graph< NT, ET >

Class for very sparse graphs, especially designed for the molecular graphs.

Template Parameters

NT	node data type.
ET	edge data type.

For all time complexity specifications, \(V\) denotes the number of nodes (vertices) and \(E\) denotes the number of edges. If present, \(N\) is the size of the user-supplied range (such as an iterator range; see, e.g., erase_nodes()).

Member Typedef Documentation

◆ adjacency_iterator

template<class NT, class ET>

using nuri::Graph< NT, ET >::adjacency_iterator = internal::AdjIterator<Graph, false>

◆ AdjRef

template<class NT, class ET>

using nuri::Graph< NT, ET >::AdjRef = internal::AdjWrapper<Graph, false>

◆ const_adjacency_iterator

template<class NT, class ET>

using nuri::Graph< NT, ET >::const_adjacency_iterator = internal::AdjIterator<Graph, true>

◆ const_edge_iterator

template<class NT, class ET>

using nuri::Graph< NT, ET >::const_edge_iterator = internal::EdgeIterator<Graph, true>

◆ const_iterator

template<class NT, class ET>

using nuri::Graph< NT, ET >::const_iterator = internal::NodeIterator<Graph, true>

◆ const_node_iterator

template<class NT, class ET>

using nuri::Graph< NT, ET >::const_node_iterator = const_iterator

◆ ConstAdjRef

template<class NT, class ET>

using nuri::Graph< NT, ET >::ConstAdjRef = internal::AdjWrapper<Graph, true>

◆ ConstEdgeRef

template<class NT, class ET>

using nuri::Graph< NT, ET >::ConstEdgeRef = internal::EdgeWrapper<Graph, true>

◆ ConstNodeRef

template<class NT, class ET>

using nuri::Graph< NT, ET >::ConstNodeRef = internal::NodeWrapper<Graph, true>

◆ edge_data_type

template<class NT, class ET>

using nuri::Graph< NT, ET >::edge_data_type = ET

◆ edge_iterator

template<class NT, class ET>

using nuri::Graph< NT, ET >::edge_iterator = internal::EdgeIterator<Graph, false>

◆ EdgeRef

template<class NT, class ET>

using nuri::Graph< NT, ET >::EdgeRef = internal::EdgeWrapper<Graph, false>

◆ iterator

template<class NT, class ET>

using nuri::Graph< NT, ET >::iterator = internal::NodeIterator<Graph, false>

◆ node_data_type

template<class NT, class ET>

using nuri::Graph< NT, ET >::node_data_type = NT

◆ node_iterator

template<class NT, class ET>

using nuri::Graph< NT, ET >::node_iterator = iterator

◆ NodeRef

template<class NT, class ET>

using nuri::Graph< NT, ET >::NodeRef = internal::NodeWrapper<Graph, false>

Constructor & Destructor Documentation

◆ Graph() [1/5]

template<class NT, class ET>

nuri::Graph< NT, ET >::Graph ( )

default

◆ Graph() [2/5]

template<class NT, class ET>

nuri::Graph< NT, ET >::Graph ( const Graph< NT, ET > & )

default

◆ Graph() [3/5]

template<class NT, class ET>

nuri::Graph< NT, ET >::Graph ( Graph< NT, ET > && )

defaultnoexcept

◆ ~Graph()

template<class NT, class ET>

nuri::Graph< NT, ET >::~Graph ( )

defaultnoexcept

◆ Graph() [4/5]

template<class NT, class ET>

nuri::Graph< NT, ET >::Graph ( int num_nodes )

inline

Create a graph with num_nodes nodes.

Parameters

num_nodes The number of nodes in the graph. All node data will be default-constructed.

◆ Graph() [5/5]

template<class NT, class ET>

nuri::Graph< NT, ET >::Graph	(	int	num_nodes,
		const NT &	data )

inline

Create a graph with num_nodes nodes, each initialized with data.

Parameters

num_nodes	The number of nodes in the graph.
data	The data to copy-initialize each node with.

Member Function Documentation

◆ add_edge() [1/2]

template<class NT, class ET>

int nuri::Graph< NT, ET >::add_edge	(	int	src,
		int	dst,
		const ET &	data )

inline

Add an edge to the graph.

Parameters

src	The source node id.
dst	The destination node id.
data	The data to copy-construct the edge with.

Returns: The id of the newly added edge.

Note: Time complexity: \(O(V+E)\) in the worst case; \(O(V-v_\min)\) when \(v_\min = \min(\mathtt{src}, \mathtt{dst})\) is at least the number of nodes that existed before the last edge addition (the merge() hot path).; If src or dst is out of range, src equals dst, or an edge between src and dst already exists, the behavior is undefined.

Deprecated: Slow, due to CSR recompilation; prefer add_edges() / merge().

◆ add_edge() [2/2]

template<class NT, class ET>

int nuri::Graph< NT, ET >::add_edge	(	int	src,
		int	dst,
		ET &&	data )

inlinenoexcept

Add an edge to the graph.

Parameters

src	The source node id.
dst	The destination node id.
data	The data to move-construct the edge with.

Returns: The id of the newly added edge.

Note: Time complexity: same as add_edge(int, int, const ET&).; If src or dst is out of range, src equals dst, or an edge between src and dst already exists, the behavior is undefined.

Deprecated: Slow, due to CSR recompilation; prefer add_edges() / merge().

◆ add_edges()

template<class NT, class ET>

template<class Iterator, internal::enable_if_compatible_iter_t< Iterator, StoredEdge > = 0>

int nuri::Graph< NT, ET >::add_edges	(	Iterator	begin,
		Iterator	end )

inline

Add multiple edges to the graph.

Template Parameters

Iterator The type of the iterator for edges. Must be dereferenceable to a value type implicitly convertible to StoredEdge.

Parameters

begin	The beginning of the range of edges to be added.
end	The end of the range of edges to be added.

Returns: The first edge id among the newly added edges, or num_edges() if no edges are added.

Note: Time complexity: \(O(V + E')\) in general, where \(E'\) is the length of [begin, end). Degenerates to \(O(E')\) when every new edge's endpoints are among the nodes added since the last edge publish (the merge() hot path).

◆ add_node() [1/2]

template<class NT, class ET>

int nuri::Graph< NT, ET >::add_node ( const NT & data )

inline

Add a node to the graph.

Parameters

data	The data to copy-construct the node with.

Returns: The id of the newly added node.

Note: Time complexity: \(O(1)\) amortized.

◆ add_node() [2/2]

template<class NT, class ET>

int nuri::Graph< NT, ET >::add_node ( NT && data )

inlinenoexcept

Add a node to the graph.

Parameters

data	The data to move-construct the node with.

Returns: The id of the newly added node.

Note: Time complexity: \(O(1)\) amortized.

◆ add_nodes()

template<class NT, class ET>

template<class Iterator, internal::enable_if_compatible_iter_t< Iterator, NT > = 0>

int nuri::Graph< NT, ET >::add_nodes	(	Iterator	begin,
		Iterator	end )

inline

Add multiple nodes to the graph.

Template Parameters

Iterator The type of the iterator. Must be dereferenceable to a value type implicitly convertible to NT.

Parameters

begin	The beginning of the range of nodes to be added.
end	The end of the range of nodes to be added.

Returns: The first node id among the newly added nodes, or num_nodes() if no nodes are added.

Note: Time complexity: \(O(N)\).

◆ adj_begin() [1/2]

template<class NT, class ET>

adjacency_iterator nuri::Graph< NT, ET >::adj_begin ( int nid )

inline

◆ adj_begin() [2/2]

template<class NT, class ET>

const_adjacency_iterator nuri::Graph< NT, ET >::adj_begin ( int nid ) const

inline

◆ adj_cbegin()

template<class NT, class ET>

const_adjacency_iterator nuri::Graph< NT, ET >::adj_cbegin ( int nid ) const

inline

◆ adj_cend()

template<class NT, class ET>

const_adjacency_iterator nuri::Graph< NT, ET >::adj_cend ( int nid ) const

inline

◆ adj_end() [1/2]

template<class NT, class ET>

adjacency_iterator nuri::Graph< NT, ET >::adj_end ( int nid )

inline

◆ adj_end() [2/2]

template<class NT, class ET>

const_adjacency_iterator nuri::Graph< NT, ET >::adj_end ( int nid ) const

inline

◆ begin() [1/2]

template<class NT, class ET>

iterator nuri::Graph< NT, ET >::begin ( )

inline

◆ begin() [2/2]

template<class NT, class ET>

const_iterator nuri::Graph< NT, ET >::begin ( ) const

inline

◆ cbegin()

template<class NT, class ET>

const_iterator nuri::Graph< NT, ET >::cbegin ( ) const

inline

◆ cedges()

template<class NT, class ET>

internal::EdgesWrapper< Graph, true > nuri::Graph< NT, ET >::cedges ( ) const

inline

◆ cend()

template<class NT, class ET>

const_iterator nuri::Graph< NT, ET >::cend ( ) const

inline

◆ clear()

template<class NT, class ET>

void nuri::Graph< NT, ET >::clear ( )

inline

◆ clear_edges()

template<class NT, class ET>

void nuri::Graph< NT, ET >::clear_edges ( )

inline

Remove all edges from the graph.

Note: Time complexity: \(O(V)\).

◆ degree()

template<class NT, class ET>

int nuri::Graph< NT, ET >::degree ( int id ) const

inline

◆ edge() [1/2]

template<class NT, class ET>

EdgeRef nuri::Graph< NT, ET >::edge ( int id )

inline

◆ edge() [2/2]

template<class NT, class ET>

ConstEdgeRef nuri::Graph< NT, ET >::edge ( int id ) const

inline

◆ edge_begin() [1/2]

template<class NT, class ET>

edge_iterator nuri::Graph< NT, ET >::edge_begin ( )

inline

◆ edge_begin() [2/2]

template<class NT, class ET>

const_edge_iterator nuri::Graph< NT, ET >::edge_begin ( ) const

inline

◆ edge_cbegin()

template<class NT, class ET>

const_edge_iterator nuri::Graph< NT, ET >::edge_cbegin ( ) const

inline

◆ edge_cend()

template<class NT, class ET>

const_edge_iterator nuri::Graph< NT, ET >::edge_cend ( ) const

inline

◆ edge_data() [1/2]

template<class NT, class ET>

ET & nuri::Graph< NT, ET >::edge_data ( int id )

inline

◆ edge_data() [2/2]

template<class NT, class ET>

const ET & nuri::Graph< NT, ET >::edge_data ( int id ) const

inline

◆ edge_dst() [1/2]

template<class NT, class ET>

NodeRef nuri::Graph< NT, ET >::edge_dst ( int id )

inline

◆ edge_dst() [2/2]

template<class NT, class ET>

ConstNodeRef nuri::Graph< NT, ET >::edge_dst ( int id ) const

inline

◆ edge_empty()

template<class NT, class ET>

bool nuri::Graph< NT, ET >::edge_empty ( ) const

inline

◆ edge_end() [1/2]

template<class NT, class ET>

edge_iterator nuri::Graph< NT, ET >::edge_end ( )

inline

◆ edge_end() [2/2]

template<class NT, class ET>

const_edge_iterator nuri::Graph< NT, ET >::edge_end ( ) const

inline

◆ edge_src() [1/2]

template<class NT, class ET>

NodeRef nuri::Graph< NT, ET >::edge_src ( int id )

inline

◆ edge_src() [2/2]

template<class NT, class ET>

ConstNodeRef nuri::Graph< NT, ET >::edge_src ( int id ) const

inline

◆ edges() [1/2]

template<class NT, class ET>

internal::EdgesWrapper< Graph, false > nuri::Graph< NT, ET >::edges ( )

inline

◆ edges() [2/2]

template<class NT, class ET>

internal::EdgesWrapper< Graph, true > nuri::Graph< NT, ET >::edges ( ) const

inline

◆ empty()

template<class NT, class ET>

bool nuri::Graph< NT, ET >::empty ( ) const

inline

◆ end() [1/2]

template<class NT, class ET>

iterator nuri::Graph< NT, ET >::end ( )

inline

◆ end() [2/2]

template<class NT, class ET>

const_iterator nuri::Graph< NT, ET >::end ( ) const

inline

◆ erase_edge()

template<class NT, class ET>

void nuri::Graph< NT, ET >::erase_edge ( int id )

inline

Erase an edge from the graph.

Parameters

id	The id of the edge to be erased.

See also: erase_edge_between(), erase_edges()

Note: Time complexity: \(O(V+E)\).; If id is out of range, the behavior is undefined.

◆ erase_edge_between() [1/2]

template<class NT, class ET>

bool nuri::Graph< NT, ET >::erase_edge_between	(	ConstNodeRef	src,
		ConstNodeRef	dst )

inline

Erase an edge from the graph between two nodes.

Parameters

src	The source node, interchangeable with `dst`.
dst	The destination node, interchangeable with `src`.

Returns: Whether the edge is erased.

See also: erase_edge(), erase_edges()

Note: Time complexity: same as erase_edge().; If src or dst does not belong to this graph, the behavior is undefined.

◆ erase_edge_between() [2/2]

template<class NT, class ET>

bool nuri::Graph< NT, ET >::erase_edge_between	(	int	src,
		int	dst )

Erase an edge from the graph between two nodes.

Parameters

src	The source node, interchangeable with `dst`.
dst	The destination node, interchangeable with `src`.

Returns: Whether the edge is erased.

See also: erase_edge(), erase_edges()

Note: Time complexity: same as erase_edge().; If src or dst is out of range, the behavior is undefined.

◆ erase_edges() [1/3]

template<class NT, class ET>

std::pair< int, std::vector< int > > nuri::Graph< NT, ET >::erase_edges	(	const_edge_iterator	begin,
		const_edge_iterator	end )

inline

Erase edges from the graph.

Parameters

begin	The beginning of the range of nodes to be erased.
end	The end of the range of nodes to be erased.

Returns: A pair of (new end id, mapping of old edge id -> new edge id). If only trailing edges are erased, new end id will be set to the first erased edge id, and the mapping will be in a valid but unspecified state. If no edges are erased (special case of trailing edge removal), new end id will be equal to the size of the graph before this operation. Otherwise, new end id will be set to -1 and erased edges will be marked as -1 in the mapping.

See also: erase_edge(), erase_edge_between()

Note: Time complexity: \(O(E)\) if no edges were removed, \(O(V+E)\) otherwise.; If any of the iterators in range [begin, end`)` is out of range, the behavior is undefined.

◆ erase_edges() [2/3]

template<class NT, class ET>

template<class UnaryPred>

std::pair< int, std::vector< int > > nuri::Graph< NT, ET >::erase_edges	(	const_edge_iterator	begin,
		const_edge_iterator	end,
		UnaryPred	pred )

Erase matching edges from the graph.

Template Parameters

UnaryPred A unary predicate that takes a ConstEdgeRef and returns bool.

Parameters

begin	The beginning of the range of edges to be erased.
end	The end of the range of edges to be erased.
pred	A unary predicate that takes a ConstEdgeRef and returns true if the edge should be erased.

Returns: A pair of (new end id, mapping of old edge id -> new edge id). If only trailing edges are erased, new end id will be set to the first erased edge id, and the mapping will be in a valid but unspecified state. If no edges are erased (special case of trailing edge removal), new end id will be equal to the size of the graph before this operation. Otherwise, new end id will be set to -1 and erased edges will be marked as -1 in the mapping.

See also: erase_edge(), erase_edge_between()

Note: Time complexity: same as erase_edges(const_edge_iterator, const_edge_iterator).; If any of the iterators in range [begin, end`)` is out of range, the behavior is undefined.

◆ erase_edges() [3/3]

template<class NT, class ET>

template<class Iterator, class>

std::pair< int, std::vector< int > > nuri::Graph< NT, ET >::erase_edges	(	Iterator	begin,
		Iterator	end )

Erase edges from the graph.

Template Parameters

Iterator An iterator type that dereferences to a value compatible with int.

Parameters

begin	The beginning of the range of edge ids to be erased.
end	The end of the range of edge ids to be erased.

Returns: A pair of (new end id, mapping of old edge id -> new edge id). If only trailing edges are erased, new end id will be set to the first erased edge id, and the mapping will be in a valid but unspecified state. If no edges are erased (special case of trailing edge removal), new end id will be equal to the size of the graph before this operation. Otherwise, new end id will be set to -1 and erased edges will be marked as -1 in the mapping.

See also: erase_edge(), erase_edge_between()

Note: Time complexity: same as erase_edges(const_edge_iterator, const_edge_iterator).; If any iterator in range [begin, end`)` references an invalid edge id, the behavior is undefined.

◆ erase_nodes() [1/3]

template<class NT, class ET>

NodesErased nuri::Graph< NT, ET >::erase_nodes	(	const_iterator	begin,
		const_iterator	end )

inline

Erase nodes and all its associated edge(s) from the graph.

Parameters

begin	The beginning of the range of nodes to be erased.
end	The end of the range of nodes to be erased.

Returns: A pair for node and edge erasure result. Each pair contains a pair of (new end id, mapping of old id -> new id). For nodes, if only trailing nodes are erased, new end id will be set to the first erased node id, and the mapping will be in a valid but unspecified state. If no nodes are erased (special case of trailing node removal), new end id will be equal to the size of the graph before this operation. Otherwise, new end id will be set to -1 and erased nodes will be marked as -1 in the mapping. The same rule applies to edges.

Note

Time complexity:

\(O(V)\) if no nodes are erased,
\(O(V+E)\) otherwise.

If any of the iterators in range [begin, end`)` is out of range, the behavior is undefined.

◆ erase_nodes() [2/3]

template<class NT, class ET>

template<class UnaryPred>

NodesErased nuri::Graph< NT, ET >::erase_nodes	(	const_iterator	begin,
		const_iterator	end,
		UnaryPred	pred )

Erase matching nodes and all its associated edge(s) from the graph.

Template Parameters

UnaryPred A unary predicate that takes a ConstNodeRef and returns bool.

Parameters

begin	The beginning of the range of nodes to be erased.
end	The end of the range of nodes to be erased.
pred	A unary predicate that takes a ConstNodeRef and returns true if the node should be erased.

Returns: A pair for node and edge erasure result. Each pair contains a pair of (new end id, mapping of old id -> new id). For nodes, if only trailing nodes are erased, new end id will be set to the first erased node id, and the mapping will be in a valid but unspecified state. If no nodes are erased (special case of trailing node removal), new end id will be equal to the size of the graph before this operation. Otherwise, new end id will be set to -1 and erased nodes will be marked as -1 in the mapping. The same rule applies to edges.

Note: Time complexity: same as erase_nodes(const_iterator, const_iterator).; If any of the iterators in range [begin, end`)` is out of range, the behavior is undefined.

◆ erase_nodes() [3/3]

template<class NT, class ET>

template<class Iterator, class>

NodesErased nuri::Graph< NT, ET >::erase_nodes	(	Iterator	begin,
		Iterator	end )

Erase nodes and all its associated edge(s) from the graph.

Template Parameters

Iterator An iterator type that dereferences to a value compatible with int.

Parameters

begin	The beginning of the range of node ids to be erased.
end	The end of the range of node ids to be erased.

Returns: A pair for node and edge erasure result. Each pair contains a pair of (new end id, mapping of old id -> new id). For nodes, if only trailing nodes are erased, new end id will be set to the first erased node id, and the mapping will be in a valid but unspecified state. If no nodes are erased (special case of trailing node removal), new end id will be equal to the size of the graph before this operation. Otherwise, new end id will be set to -1 and erased nodes will be marked as -1 in the mapping. The same rule applies to edges.

Note: Time complexity: same as erase_nodes(const_iterator, const_iterator).; If any of the iterators in range [begin, end`)` points to an invalid node id, the behavior is undefined.

◆ find_adjacent() [1/4]

template<class NT, class ET>

adjacency_iterator nuri::Graph< NT, ET >::find_adjacent	(	ConstNodeRef	src,
		ConstNodeRef	dst )

inline

Find an adjacency entry between two nodes.

Parameters

src	The source node.
dst	The destination node.

Returns: Iterator to the adjacency entry if found, otherwise the end iterator of the adjacency list of src.

Note: Time complexity: \(O(E/V)\).; If src or dst does not belong to this graph, the behavior is undefined.

◆ find_adjacent() [2/4]

template<class NT, class ET>

const_adjacency_iterator nuri::Graph< NT, ET >::find_adjacent	(	ConstNodeRef	src,
		ConstNodeRef	dst ) const

inline

Find an adjacency entry between two nodes.

Parameters

src	The source node.
dst	The destination node.

Returns: Iterator to the adjacency entry if found, otherwise the end iterator of the adjacency list of src.

Note: Time complexity: \(O(E/V)\).; If src or dst does not belong to this graph, the behavior is undefined.

◆ find_adjacent() [3/4]

template<class NT, class ET>

adjacency_iterator nuri::Graph< NT, ET >::find_adjacent	(	int	src,
		int	dst )

inline

Find an adjacency entry between two nodes.

Parameters

src	The source node id.
dst	The destination node id.

Returns: Iterator to the adjacency entry if found, otherwise the end iterator of the adjacency list of src.

Note: Time complexity: \(O(E/V)\).; If src or dst is out of range, the behavior is undefined.

◆ find_adjacent() [4/4]

template<class NT, class ET>

const_adjacency_iterator nuri::Graph< NT, ET >::find_adjacent	(	int	src,
		int	dst ) const

inline

Find an adjacency entry between two nodes.

Parameters

src	The source node id.
dst	The destination node id.

Returns: Iterator to the adjacency entry if found, otherwise the end iterator of the adjacency list of src.

Note: Time complexity: \(O(E/V)\).; If src or dst is out of range, the behavior is undefined.

◆ find_edge() [1/4]

template<class NT, class ET>

edge_iterator nuri::Graph< NT, ET >::find_edge	(	ConstNodeRef	src,
		ConstNodeRef	dst )

inline

Find an edge between two nodes.

Parameters

src	The source node.
dst	The destination node.

Returns: Iterator to the edge if found, otherwise the end iterator.

Note: Time complexity: same as find_edge(int, int).; If src or dst does not belong to this graph, the behavior is undefined.

◆ find_edge() [2/4]

template<class NT, class ET>

const_edge_iterator nuri::Graph< NT, ET >::find_edge	(	ConstNodeRef	src,
		ConstNodeRef	dst ) const

inline

Find an edge between two nodes.

Parameters

src	The source node.
dst	The destination node.

Returns: Iterator to the edge if found, otherwise the end iterator.

Note: Time complexity: same as find_edge(int, int).; If src or dst does not belong to this graph, the behavior is undefined.

◆ find_edge() [3/4]

template<class NT, class ET>

edge_iterator nuri::Graph< NT, ET >::find_edge	(	int	src,
		int	dst )

inline

Find an edge between two nodes.

Parameters

src	The source node id.
dst	The destination node id.

Returns: Iterator to the edge if found, otherwise the end iterator.

Note: Time complexity: \(O(E/V)\).; If src or dst is out of range, the behavior is undefined.

◆ find_edge() [4/4]

template<class NT, class ET>

const_edge_iterator nuri::Graph< NT, ET >::find_edge	(	int	src,
		int	dst ) const

inline

Find an edge between two nodes.

Parameters

src	The source node id.
dst	The destination node id.

Returns: Iterator to the edge if found, otherwise the end iterator.

Note: Time complexity: same as find_edge(int, int).; If src or dst is out of range, the behavior is undefined.

◆ merge()

template<class NT, class ET>

template<class GraphLike>

void nuri::Graph< NT, ET >::merge ( const GraphLike & other )

inline

Merge another graph-like object into this graph.

Template Parameters

GraphLike The type of the graph-like object to be merged.

Parameters

other The graph to be merged.

Note: Time complexity: \(O(V'+E')\) addition cost, where \(V'\) and \(E'\) are the number of nodes and edges in other, respectively. The actual time complexity may vary depending on the implementation of the graph-like object.

◆ node() [1/2]

template<class NT, class ET>

NodeRef nuri::Graph< NT, ET >::node ( int id )

inline

◆ node() [2/2]

template<class NT, class ET>

ConstNodeRef nuri::Graph< NT, ET >::node ( int id ) const

inline

◆ node_data() [1/2]

template<class NT, class ET>

NT & nuri::Graph< NT, ET >::node_data ( int id )

inline

◆ node_data() [2/2]

template<class NT, class ET>

const NT & nuri::Graph< NT, ET >::node_data ( int id ) const

inline

◆ num_edges()

template<class NT, class ET>

int nuri::Graph< NT, ET >::num_edges ( ) const

inline

◆ num_nodes()

template<class NT, class ET>

int nuri::Graph< NT, ET >::num_nodes ( ) const

inline

◆ operator=() [1/2]

template<class NT, class ET>

Graph & nuri::Graph< NT, ET >::operator= ( const Graph< NT, ET > & )

default

◆ operator=() [2/2]

template<class NT, class ET>

Graph & nuri::Graph< NT, ET >::operator= ( Graph< NT, ET > && )

defaultnoexcept

◆ operator[]() [1/2]

template<class NT, class ET>

NodeRef nuri::Graph< NT, ET >::operator[] ( int id )

inline

◆ operator[]() [2/2]

template<class NT, class ET>

ConstNodeRef nuri::Graph< NT, ET >::operator[] ( int id ) const

inline

◆ reserve()

template<class NT, class ET>

void nuri::Graph< NT, ET >::reserve ( int num_nodes )

inline

◆ reserve_edges()

template<class NT, class ET>

void nuri::Graph< NT, ET >::reserve_edges ( int num_edges )

inline

◆ size()

template<class NT, class ET>

int nuri::Graph< NT, ET >::size ( ) const

inline

◆ Subgraph< NT, ET, false >

template<class NT, class ET>

friend class Subgraph< NT, ET, false >

friend

◆ Subgraph< NT, ET, true >

template<class NT, class ET>

friend class Subgraph< NT, ET, true >

friend

The documentation for this class was generated from the following file:

include/nuri/core/graph/graph.h

Classes

Public Types

Public Member Functions

Friends

Detailed Description

Member Typedef Documentation

◆ adjacency_iterator

◆ AdjRef

◆ const_adjacency_iterator

◆ const_edge_iterator

◆ const_iterator

◆ const_node_iterator

◆ ConstAdjRef

◆ ConstEdgeRef

◆ ConstNodeRef

◆ edge_data_type

◆ edge_iterator

◆ EdgeRef

◆ iterator

◆ node_data_type

◆ node_iterator

◆ NodeRef

Constructor & Destructor Documentation

◆ Graph() [1/5]

◆ Graph() [2/5]

◆ Graph() [3/5]

◆ ~Graph()

◆ Graph() [4/5]

◆ Graph() [5/5]

Member Function Documentation

◆ add_edge() [1/2]

◆ add_edge() [2/2]

◆ add_edges()

◆ add_node() [1/2]

◆ add_node() [2/2]

◆ add_nodes()

◆ adj_begin() [1/2]

◆ adj_begin() [2/2]

◆ adj_cbegin()

◆ adj_cend()

◆ adj_end() [1/2]

◆ adj_end() [2/2]

◆ begin() [1/2]

◆ begin() [2/2]

◆ cbegin()

◆ cedges()

◆ cend()

◆ clear()

◆ clear_edges()

◆ degree()

◆ edge() [1/2]

◆ edge() [2/2]

◆ edge_begin() [1/2]

◆ edge_begin() [2/2]

◆ edge_cbegin()

◆ edge_cend()

◆ edge_data() [1/2]

◆ edge_data() [2/2]

◆ edge_dst() [1/2]

◆ edge_dst() [2/2]

◆ edge_empty()

◆ edge_end() [1/2]

◆ edge_end() [2/2]

◆ edge_src() [1/2]

◆ edge_src() [2/2]

◆ edges() [1/2]

◆ edges() [2/2]

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ erase_edge()

◆ erase_edge_between() [1/2]

◆ erase_edge_between() [2/2]

◆ erase_edges() [1/3]

◆ erase_edges() [2/3]

◆ erase_edges() [3/3]

◆ erase_nodes() [1/3]

◆ erase_nodes() [2/3]

◆ erase_nodes() [3/3]

◆ find_adjacent() [1/4]