Graph class implemented with singly-linked adjacency lists. More...

#include <tpl_sgraph.H>

Inheritance diagram for Aleph::List_SGraph< __Graph_Node, __Graph_Arc >:

Collaboration diagram for Aleph::List_SGraph< __Graph_Node, __Graph_Arc >:

Classes
class	Arc_Iterator
	Iterator over arcs of a graph. More...

class	Node_Arc_Iterator
	Arc iterator for a graph node. More...

class	Node_Iterator
	Node iterator for a graph. More...

Public Types
using	Node = __Graph_Node

using	Arc = __Graph_Arc

using	Node_Type = typename Node::Node_Type

using	Arc_Type = typename Arc::Arc_Type

using	CommonBase = GraphCommon< List_SGraph< __Graph_Node, __Graph_Arc >, __Graph_Node, __Graph_Arc >

Public Types inherited from GraphCommon< GT, Node, Arc >
using	Node_Type = typename Node::Node_Type

using	Arc_Type = typename Arc::Arc_Type

using	ArcPair = std::tuple< Arc , Node >
	Pair of arc and node (topologically related)

Public Member Functions
	List_SGraph ()=default

virtual	~List_SGraph ()

void	swap (List_SGraph &g) noexcept

	List_SGraph (const List_SGraph &g)
	Copy constructor.

	List_SGraph (List_SGraph &&g) noexcept
	Move constructor.

List_SGraph &	operator= (const List_SGraph &g)
	Copy assignment.

List_SGraph &	operator= (List_SGraph &&g) noexcept
	Move assignment.

virtual Node *	insert_node (Node *p)
	Insertion of a node whose memory has already been allocated.

virtual void	remove_arc (Arc *arc) noexcept
	Removes the arc.

virtual void	remove_node (Node *p) noexcept

Node *	get_first_node () const

Arc *	get_first_arc () const

Arc *	get_first_arc (Node *p) const
	Returns the first arc of node p.

template<class Compare >
void	sort_arcs (Compare &cmp)
	Sort all arcs of the graph according to a comparison criteria.

template<class Compare >
void	sort_arcs (Compare &&cmp=Compare())

Node *	insert_node (const Node_Type &node_info)
	Allocate a new node, set by copy its data content and insert it into the graph.

Node *	insert_node (Node_Type &&node_info=Node_Type())
	Allocate a new node, set by moving its data content and insert it into the graph.

Arc *	insert_arc (Node src, Node tgt, const Arc_Type &arc_info)
	Create and insert a new arc linking two nodes and copying data.

Arc *	insert_arc (Node src, Node tgt, Arc_Type &&arc_info=Arc_Type())
	Create and insert a new arc linking two nodes and moving the received data.

Public Member Functions inherited from GraphCommon< GT, Node, Arc >
void *&	get_cookie () noexcept
	Return a modifiable reference to graph's cookie.

void *	get_cookie () const noexcept
	Return a constant reference to graph's cookie.

bool	is_digraph () const noexcept
	Return true if the graph `this` is directed.

void	set_digraph (bool val)
	Temporal indication for preventing to other algorithms that an graph must be treated as a directed graph.

constexpr size_t	get_num_nodes () const noexcept
	Return the total of nodes of graph.

constexpr size_t	vsize () const noexcept

Node *	get_node () const
	Return any node in the graph.

Node *	get_arc () const
	Return any arc in the graph.

Node *	get_arc (Node *p)
	Return any arc adjacent to a node.

Node *	get_src_node (Arc *arc) const noexcept
	Return the source node of `arc` (only for directed graphs)

Node *	get_tgt_node (Arc *arc) const noexcept
	Return the target node of `arc` (only for directed graphs)

Node *	get_connected_node (Arc arc, Node node) const noexcept
	Return the adjacent node to `node` through `arc`.

constexpr size_t	get_num_arcs () const noexcept

size_t	get_num_arcs (Node *node) const noexcept
	Return the total of arcs of a node.

size_t	degree (Node *p) const noexcept
	Return the total of arcs (or degree) of a node.

size_t	esize () const noexcept
	Return the total of arcs of graph.

Bit_Fields &	get_control_bits (Node *node) const noexcept
	Return a reference to control fields of `node`

void	reset_bit (Node *node, int bit) const noexcept
	Reset the `bit` of `node` (to zero)

void	reset_bits (Node *node) const noexcept
	Reset all the control bits of `node`

int	get_bit (Node *node, int bit) const noexcept
	Get the control `bit` of `node`

void	set_bit (Node *node, int bit, int value) const noexcept
	Set the control `bit` of `node` to `value`

Bit_Fields &	get_control_bits (Arc *arc) const noexcept
	Return a reference to the control bits of `arc`

void	reset_bit (Arc *arc, int bit) const noexcept
	Reset the `bit` of `arc` to zero.

void	reset_bits (Arc *arc) const noexcept
	Reset all the control bits of `arc`

int	get_bit (Arc *arc, int bit) const noexcept
	Get the control `bit` of `arc`

void	set_bit (Arc *arc, int bit, int value) const noexcept
	Set the control `bit` of `arc` to `value`

void *&	get_cookie (Node *node) const noexcept
	Get a modifiable reference to the cookie pointer of `node`

void *&	get_cookie (Arc *arc) const noexcept
	Get a modifiable reference to the cookie pointer of `arc`

long &	get_counter (Node *node) const noexcept
	Get a modifiable reference to the counter of `node`

void	reset_counter (Node *node) const noexcept
	Reset the `node` counter to zero.

void	reset_node_counters () const noexcept
	Reset all the node counters of graph to zero.

void	reset_node (Node *p) const noexcept
	Reset all the control attributes of node `p`.

long &	get_counter (Arc *arc) const noexcept
	Get a modifiable reference to the counter of `arc`

void	reset_counter (Arc *arc) const noexcept
	Reset the `acr` counter to zero.

void	reset_arc_counters () const noexcept
	Reset all the arc counters of graph to zero.

void	reset_arc (Arc *arc) const noexcept
	Reset all the control attributes of `arc`.

void	reset_nodes () const
	Reset all the nodes of graph (the control bits, the state, the counter and the cookie)

void	reset_arcs () const
	Reset all the arcs of graph (the control bits, the state, the counter and the cookie)

void	reset_bit_nodes (int bit) const noexcept
	Reset `bit` to zero for all the nodes of graph.

void	reset_bit_arcs (int bit) const noexcept
	Reset `bit` to zero for all the arcs of graph.

void	reset_bit_nodes () const noexcept
	Reset all the bits for all the nodes of graph.

void	reset_bit_arcs () const noexcept
	Reset all the bits for all the arcs of graph.

void	reset_counter_nodes () const noexcept
	Reset all the counters to zero for all the nodes of graph.

void	reset_counter_arcs () const noexcept
	Reset all the counters to zero for all the arcs of graph.

void	reset_cookie_nodes () const noexcept
	Reset all the cookies to `nullptr for all the nodes of graph.

void	reset_cookie_arcs () const noexcept
	Reset all the cookies to `nullptr for all the arcs of graph.

Node *	insert_node (const Node_Type &node_info)
	Allocate a new node, set by copy its data content and insert it into the graph.

Node *	insert_node (Node_Type &&node_info=Node_Type())
	Allocate a new node, set by moving its data content and insert it into the graph.

template<typename... Args>
Node *	emplace_node (Args &&... args)
	Insert a new node in the graph by constructing it in-place with the given args.

Arc *	insert_arc (Node src, Node tgt, const Arc_Type &arc_info)
	Create and insert a new arc linking two nodes and copying data.

Arc *	insert_arc (Node src, Node tgt, Arc_Type &&arc_info=Arc_Type())
	Create and insert a new arc linking two nodes and moving the received data.

template<typename... Args>
Arc *	emplace_arc (Node src, Node tgt, Args &&... args)
	Insert a new arc in the graph by constructing its associated data in-place with the given args.

template<class Operation >
bool	traverse_nodes (Operation &op) const
	Conditioned traversal of all the nodes of a graph.

template<class Operation >
bool	traverse_nodes (Operation &&op=Operation()) const
	Overload of `traverse_nodes(Operation&)` that accepts rvalues.

template<class Operation >
bool	traverse_arcs (Operation &op) const
	Conditioned traversal of all the arcs of a graph.

template<class Operation >
bool	traverse_arcs (Operation &&op=Operation()) const
	Overload of `traverse_arcs(Operation&)` that accepts rvalues.

template<class Operation >
bool	traverse_arcs (Node *p, Operation &op) const
	Conditioned traversal of all the adjacent arcs of a node.

template<class Operation >
bool	traverse_arcs (Node *p, Operation &&op=Operation()) const
	Overload of `traverse_arcs(Node*, Operation&)` that accepts rvalues.

template<class Operation >
void	for_each_node (Operation &operation) const
	Unconditionally traverse all the nodes of graph and on each one perform an operation.

template<class Operation >
void	for_each_node (Operation &&operation=Operation()) const
	Overload of `for_each_node(Operation&)` that accepts rvalues.

template<class Operation >
void	for_each_arc (Operation &op) const
	Unconditionally traverse all the arcs of graph and on each one perform an operation.

template<class Operation >
void	for_each_arc (Operation &&operation=Operation()) const
	Overload of `for_each_arc(Operation&)` that accepts rvalues.

template<class Operation >
void	for_each_arc (Node *p, Operation &op) const
	Unconditionally traverse all the arcs adjacnt to a node and on each one perform an operation.

template<class Operation >
void	for_each_arc (Node *p, Operation &&op=Operation()) const
	Overload of `for_each_arc(Node*, Operation&)` that accepts rvalues.

template<class Operation >
bool	all_nodes (Operation &op) const
	Check if all the nodes of graph satisfy an boolean condition.

template<class Operation >
bool	all_nodes (Operation &&op=Operation()) const
	Overload of `all_nodes(Operation&)` that accepts rvalues.

template<class Operation >
bool	all_arcs (Operation &op) const
	Check if all the arcs of graph satisfy a boolean condition.

template<class Operation >
bool	all_arcs (Operation &&op=Operation()) const
	Overload of `all_arcs(Operation&)` that accepts rvalues.

template<class Operation >
bool	all_arcs (Node *p, Operation &op) const
	Check if all the arcs adjacent to a node satisfy an boolean condition.

template<class Operation >
bool	all_arcs (Node *p, Operation &&op=Operation()) const
	Overload of `all_arcs(Node*, Operation&)` that accepts rvalues.

template<typename T = Node_Type>
auto	nodes_map (std::function< T(Node *)> op) const
	Map the nodes of a graph to a specific range.

template<typename T = Arc_Type>
auto	arcs_map (std::function< T(Arc *)> operation) const
	Map the arcs of a graph to a specific range.

template<typename T = Arc_Type>
auto	arcs_map (Node p, std::function< T(Arc )> operation) const
	Map the adjacent arcs of a node to a specific range.

template<typename T = Node_Type>
T	foldl_nodes (const T &init, std::function< T(const T &, Node *)> op) const
	Folding of nodes on a graph.

template<typename T = Arc_Type>
T	foldl_arcs (const T &init, std::function< T(const T &, Arc *)> op) const
	Folding of arcs on a graph.

template<typename T = Arc_Type>
T	foldl_arcs (Node p, const T &init, std::function< T(const T &, Arc )> op) const
	Folding of arcs of a node.

template<class Op >
auto	filter_nodes (Op &op) const
	Filter the nodes satisfying a condition.

template<class Op >
auto	filter_nodes (Op &&op) const
	Overload of `filter_nodes(Op&)` that accepts rvalues.

template<class Op >
auto	filter_arcs (Op &op) const
	Filter the arcs of graph satisfying a condition.

template<class Op >
auto	filter_arcs (Op &&op) const
	Overload of `filter_arcs(Op&)` that accepts rvalues.

template<class Op >
auto	filter_arcs (Node *p, Op &op) const
	Filter the arcs adjacent to a node satisfying a condition.

template<class Op >
auto	filter_arcs (Node *p, Op &&op) const
	Overload of `filter_arcs(Node*, Op&)` that accepts rvalues.

template<class Operation >
bool	exists_node (Operation &op) const
	Determine if exists at least a node satisfying a condition.

template<class Operation >
bool	exists_node (Operation &&op=Operation()) const
	Overload of `exists_node(Operation&)` that accepts rvalues.

template<class Operation >
bool	exists_arc (Operation &op) const
	Determine if exists at least a arc satisfying a condition.

template<class Operation >
bool	exists_arc (Operation &&op=Operation()) const
	Overload of `exists_arc(Operation&)` that accepts rvalues.

template<class Operation >
bool	exists_arc (Node *p, Operation &op) const
	Determine if exists at least a arc adjacent to a node satisfying a condition.

template<class Operation >
bool	exists_arc (Node *p, Operation &&op=Operation()) const
	Overload of `exists_arc(Node*, Operation&)` that accepts rvalues.

template<class Operation >
bool	none_node (Operation &op) const
	Determine if no node satisfies a condition.

template<class Operation >
bool	none_node (Operation &&op) const
	Overload of `none_node(Operation&)` that accepts rvalues.

template<class Operation >
bool	none_arc (Operation &op) const
	Determine if no arc satisfies a condition.

template<class Operation >
bool	none_arc (Operation &&op) const
	Overload of `none_arc(Operation&)` that accepts rvalues.

template<class Operation >
bool	none_arc (Node *p, Operation &op) const
	Determine if no arc adjacent to a node satisfies a condition.

template<class Operation >
bool	none_arc (Node *p, Operation &&op) const
	Overload of `none_arc(Node*, Operation&)` that accepts rvalues.

template<class Operation = std::function<bool(Node*)>>
size_t	count_nodes (Operation op=[](Node *) { return true;}) const
	Count the nodes satisfying a condition.

template<class Operation = std::function<bool(Arc*)>>
size_t	count_arcs (Operation op=[](Arc *) { return true;}) const
	Count the arcs satisfying a condition.

template<class Operation = std::function<bool(Arc*)>>
size_t	count_arcs (Node p, Operation op=[](Arc ) { return true;}) const
	Count arcs adjacent to a node satisfying a condition.

template<typename T = double, class Extract >
T	sum_arcs (Node *p, Extract extract) const
	Sum values derived from arcs adjacent to a node.

template<typename T = double>
T	sum_arcs (Node *p) const
	Overload of `sum_arcs(Node*, Extract)` using the arc info as extractor.

template<class Compare = std::function<bool(Arc, Arc)>>
Arc *	min_arc (Node p, Compare cmp=[](Arc a, Arc *b) { return a->get_info()< b->get_info();}) const
	Find the minimum arc adjacent to a node.

template<class Compare = std::function<bool(Arc, Arc)>>
Arc *	max_arc (Node p, Compare cmp=[](Arc a, Arc *b) { return a->get_info()< b->get_info();}) const
	Find the maximum arc adjacent to a node.

template<class Compare = std::function<bool(Arc, Arc)>>
Arc *	min_arc (Compare cmp=[](Arc a, Arc b) { return a->get_info()< b->get_info();}) const
	Find the minimum arc in the entire graph.

template<class Compare = std::function<bool(Arc, Arc)>>
Arc *	max_arc (Compare cmp=[](Arc a, Arc b) { return a->get_info()< b->get_info();}) const
	Find the maximum arc in the entire graph.

template<class Operation >
std::pair< DynList< Node * >, DynList< Node * > >	partition_nodes (Operation op) const
	Partition nodes into two groups based on a predicate.

template<class Operation >
std::pair< DynList< Arc * >, DynList< Arc * > >	partition_arcs (Operation op) const
	Partition arcs into two groups based on a predicate.

DynList< Node * >	adjacent_nodes (Node *p) const
	Get all adjacent nodes (neighbors) of a node.

template<class Op >
Node *	search_node (Op &op) const
	Linear search of a node.

template<class Op >
Node *	search_node (Op &&op) const
	Overload of `search_node(Op&)` that accepts rvalues.

Node *	find_node (const Node_Type &info) const noexcept
	Find a node mathing a content.

template<class Op >
Arc *	search_arc (Op &op) const
	Linear search of an arc.

template<class Op >
Arc *	search_arc (Op &&op) const
	Overload of `search_arc(Op&)` that accepts rvalues.

Arc *	find_arc (const Arc_Type &info) const noexcept
	Find an arc mathing a content.

template<class Operation >
Arc *	search_arc (Node *p, Operation &op) const
	Linear search of an arc.

template<class Operation >
Arc *	search_arc (Node *p, Operation &&op=Operation()) const
	Overload of `search_arc(Node*, Operation&)` that accepts rvalues.

Arc *	search_arc (Node src, Node tgt) const noexcept
	Search an arc linking two nodes.

template<template< typename > class Container = Aleph::DynList>
Container< Node * >	nodes () const
	Return a container with all the nodes of the graph.

template<template< typename > class Container = Aleph::DynList>
Container< Arc * >	arcs () const
	Return a container with all the arcs of the graph.

template<template< typename > class Container = Aleph::DynList>
Container< Arc * >	arcs (Node *p) const
	Return a container with all the arcs adjacent to a node.

auto	get_node_it () const noexcept
	Obtains an iterator to the nodes of graph.

auto	get_arc_it () const noexcept
	Obtains an iterator to the arc of graph.

auto	get_arc_it (Node *p) const noexcept
	Obtains an iterator to the adjacent arcs of a node.

In_Iterator	get_in_it (Node *p) const noexcept
	Return an input iterator on the incoming arcs to `p`

Out_Iterator	get_out_it (Node *p) const noexcept
	Return an output iterator on the incoming nodes to `p`

Arc *	search_directed_arc (Node src, Node tgt) const noexcept
	Search a directed arc linking two nodes.

DynList< Node * >	in_nodes (Node *p) const
	Return a list with the incoming nodes to `p`

DynList< Node * >	out_nodes (Node *p) const
	Return a list with the outcoming nodes to `p`

DynList< Arc * >	out_arcs (Node *p) const
	Return a list with the outcoming arcs to p`.

DynList< Arc * >	in_arcs (Node *p) const
	Return a list with the incoming arcs to p`.

auto	in_pairs (Node *p) const
	Return a list of pair incoming arcs and nodes.

auto	out_pairs (Node *p) const
	Return a list of pair outcoming arcs and nodes.

size_t	in_degree (Node *p) const noexcept
	Compute the input degree of a node.

size_t	out_degree (Node *p) const noexcept
	Compute the output degree of a node.

template<class Itor , class Operation >
bool	traverse_arcs (Node *p, Operation &op) const
	Traverse of arcs of a node according to specific arcs iterator.

template<class Itor , class Operation >
void	for_each_arc (Node *p, Operation &op) const
	Perform `op` on each arc of node `p`

template<class Op >
bool	traverse_in_arcs (Node *p, Op &op) const
	Traverse the incoming arcs of node `p` executing the conditioned `operation`

template<class Op >
bool	traverse_in_arcs (Node *p, Op &&op=Op()) const
	Overload of `traverse_in_arcs(Node*, Op&)` that accepts rvalues.

template<class Op >
void	for_each_in_arc (Node *p, Op &op) const
	Perform `op` on each incoming arc of node `p`

template<class Op >
void	for_each_in_arc (Node *p, Op &&op=Op()) const
	Overload of `for_each_in_arc(Node*, Op&)` that accepts rvalues.

template<class Op >
bool	all_in_arcs (Node *p, Op &op) const
	Return `true` if `op` is true for all the incoming arcs to node `p`

template<class Op >
bool	all_in_arcs (Node *p, Op &&op=Op()) const
	Overload of `all_in_arcs(Node*, Op&)` that accepts rvalues.

template<class Op >
bool	exists_in_arc (Node *p, Op &op) const
	Return true if it exists a incoming arc to `p` returning `true` for `op`

template<class Op >
bool	exists_in_arc (Node *p, Op &&op=Op()) const
	Overload of `exists_in_arc(Node*, Op&)` that accepts rvalues.

template<class Op >
auto	search_in_arc (Node *p, Op &op) const
	Search an incoming arc to a node satisfaying a condition.

template<class Op >
auto	search_in_arc (Node *p, Op &&op=Op()) const
	Overload of `search_in_arc(Node*, Op&)` that accepts rvalues.

template<typename T >
auto	in_arcs_map (Node p, std::function< T(Arc )> op) const
	Return a list of incoming arcs of a node mapped to items of type given by transformation `op`.

template<typename T = Arc_Type>
T	foldl_in_arcs (Node p, const T &init, std::function< T(const T &, Arc )> op) const
	Fold the incoming arcs of a node.

template<class Op >
DynList< Arc * >	filter_in_arcs (Node *p, Op &op) const
	Filter the incoming arcs of a node.

template<class Op >
auto	filter_in_arcs (Node *p, Op &&op=Op()) const
	Overload of `filter_in_arcs(Node*, Op&)` that accepts rvalues.

template<class Op >
bool	traverse_out_arcs (Node *p, Op &op) const
	Traverse the outcoming arcs of node `p` executing the conditioned `operation`

template<class Op >
bool	traverse_out_arcs (Node *p, Op &&op=Op()) const
	Overload of `traverse_out_arcs(Node*, Op&)` that accepts rvalues.

template<class Op >
void	for_each_out_arc (Node *p, Op &op) const
	Perform `op` on each outcoming arc of node `p`

template<class Op >
void	for_each_out_arc (Node *p, Op &&op=Op()) const
	Overload of `for_each_out_arc(Node*, Op&)` that accepts rvalues.

template<class Op >
bool	all_out_arcs (Node *p, Op &op) const
	Return `true` if `op` is true for all the outcoming arcs to node `p`

template<class Op >
bool	all_out_arcs (Node *p, Op &&op=Op()) const
	Overload of `all_out_arcs(Node*, Op&)` that accepts rvalues.

template<class Op >
bool	exists_out_arc (Node *p, Op &op) const
	Return true if it exists a outcoming arc to `p` returning `true` for `op`

template<class Op >
bool	exists_out_arc (Node *p, Op &&op=Op()) const
	Overload of `exists_out_arc(Node*, Op&)` that accepts rvalues.

template<class Op >
auto	search_out_arc (Node *p, Op &op) const
	Search an outcoming arc to a node satisfaying a condition.

template<class Op >
auto	search_out_arc (Node *p, Op &&op=Op()) const
	Overload of `search_out_arc(Node*, Op&)` that accepts rvalues.

template<typename T = Arc_Type>
auto	out_arcs_map (Node p, std::function< T(Arc )> op) const
	Return a list of outcoming arcs of a node mapped to items of type given by transformation `op`.

template<typename T = Arc_Type>
T	foldl_out_arcs (Node p, const T &init, std::function< T(const T &, Arc )> op) const
	Fold-left over outcoming arcs of a node.

template<class Op >
DynList< Arc * >	filter_out_arcs (Node *p, Op &op) const
	Filter the outcoming arcs of a node.

template<class Op >
auto	filter_out_arcs (Node *p, Op &&op=Op()) const
	Overload of `filter_out_arcs(Node*, Op&)` that accepts rvalues.

template<class Compare > requires (has_node_dlink_v<GT>)
void	sort_nodes (Compare &cmp) noexcept

template<class Compare > requires (has_node_dlink_v<GT>)
void	sort_nodes (Compare &&cmp=Compare()) noexcept

template<class Compare > requires (has_arc_dlink_v<GT>)
void	sort_arcs (Compare &cmp) noexcept
	Sort all the arcs of the graph according to a specific criteria.

template<class Compare > requires (has_arc_dlink_v<GT>)
void	sort_arcs (Compare &&cmp=Compare()) noexcept

Private Types
using	DynSetNode = DynSetTree< Node *, Rand_Tree >

using	DynSetArc = DynSetTree< Arc *, Rand_Tree >

Private Member Functions
Arc *	insert_arc (Node src, Node tgt, void *a)

void	disconnect_arc (Arc *arc)

void	clear () noexcept

Private Attributes
DynSetNode	node_list
	Set of nodes in the graph.

DynSetArc	arc_list
	Set of arcs in the graph.

Friends
class	GraphCommon< List_SGraph< __Graph_Node, __Graph_Arc >, __Graph_Node, __Graph_Arc >

Additional Inherited Members
Static Public Member Functions inherited from GraphCommon< GT, Node, Arc >
template<class N1 , class N2 = N1>
static void	map_nodes (N1 p, N2 q) noexcept
	Map the nodes through their cookies.

template<class A1 , class A2 = A1>
static void	map_arcs (A1 p, A2 q) noexcept
	Map the arcs through their cookies.

Static Public Attributes inherited from GraphCommon< GT, Node, Arc >
template<class U >
static constexpr bool	has_node_dlink_v
	Sort all the nodes of the graph according to a specific criteria.

template<class U >
static constexpr bool	has_arc_dlink_v

Protected Member Functions inherited from GraphCommon< GT, Node, Arc >
void	init () noexcept

void	common_swap (GT &g) noexcept

template<class Predicate >
DynList< Arc * >	collect_arcs_if (Predicate pred) const
	Collect all arcs matching a predicate.

template<class Predicate >
void	remove_arcs_if (Predicate pred)
	Remove all arcs matching a predicate.

Protected Attributes inherited from GraphCommon< GT, Node, Arc >
void *	cookie = nullptr

size_t	num_nodes = 0

size_t	num_arcs = 0

bool	digraph = false

Detailed Description

template<typename __Graph_Node = Graph_Snode<unsigned long>, typename __Graph_Arc = Graph_Sarc<unsigned long>>
class Aleph::List_SGraph< __Graph_Node, __Graph_Arc >

Graph class implemented with singly-linked adjacency lists.

List_SGraph<Node, Arc> is a class that models graphs represented using adjacency lists.

The class handles two fundamental type parameters:

__Graph_Node: the node type that must be defined using the Graph_Snode class.
__Graph_Arc: the arc type that must be defined using the Graph_Sarc class.

These classes must have been previously defined.

Once a List_SGraph<Node, Arc> is instantiated, nodes and arcs must be accessed through the internal types:

Template Parameters

__Graph_Node	The node type. Must be defined from the Graph_Snode class, either by attribute inclusion, by derivation, or by a combination of both.
__Graph_Arc	The arc type. Must be defined from the Graph_Sarc class, either by attribute inclusion, by derivation, or by a combination of both.

See also: Graph_Snode Graph_Sarc; List_SDigraph Path

Definition at line 271 of file tpl_sgraph.H.

Member Typedef Documentation

◆ Arc

template<typename __Graph_Node = Graph_Snode<unsigned long>, typename __Graph_Arc = Graph_Sarc<unsigned long>>

using Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::Arc = __Graph_Arc

Definition at line 277 of file tpl_sgraph.H.

◆ Arc_Type

template<typename __Graph_Node = Graph_Snode<unsigned long>, typename __Graph_Arc = Graph_Sarc<unsigned long>>

using Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::Arc_Type = typename Arc::Arc_Type

Definition at line 279 of file tpl_sgraph.H.

◆ CommonBase

template<typename __Graph_Node = Graph_Snode<unsigned long>, typename __Graph_Arc = Graph_Sarc<unsigned long>>

using Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::CommonBase = GraphCommon<List_SGraph<__Graph_Node, __Graph_Arc>, __Graph_Node, __Graph_Arc>

Definition at line 284 of file tpl_sgraph.H.

◆ DynSetArc

template<typename __Graph_Node = Graph_Snode<unsigned long>, typename __Graph_Arc = Graph_Sarc<unsigned long>>

using Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::DynSetArc = DynSetTree<Arc *, Rand_Tree>

private

Definition at line 292 of file tpl_sgraph.H.

◆ DynSetNode

template<typename __Graph_Node = Graph_Snode<unsigned long>, typename __Graph_Arc = Graph_Sarc<unsigned long>>

using Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::DynSetNode = DynSetTree<Node *, Rand_Tree>

private

Definition at line 291 of file tpl_sgraph.H.

◆ Node

template<typename __Graph_Node = Graph_Snode<unsigned long>, typename __Graph_Arc = Graph_Sarc<unsigned long>>

using Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::Node = __Graph_Node

Definition at line 276 of file tpl_sgraph.H.

◆ Node_Type

template<typename __Graph_Node = Graph_Snode<unsigned long>, typename __Graph_Arc = Graph_Sarc<unsigned long>>

using Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::Node_Type = typename Node::Node_Type

Definition at line 278 of file tpl_sgraph.H.

Constructor & Destructor Documentation

◆ List_SGraph() [1/3]

template<typename __Graph_Node = Graph_Snode<unsigned long>, typename __Graph_Arc = Graph_Sarc<unsigned long>>

Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::List_SGraph ( )

default

◆ ~List_SGraph()

template<typename __Graph_Node = Graph_Snode<unsigned long>, typename __Graph_Arc = Graph_Sarc<unsigned long>>

virtual Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::~List_SGraph ( )

inlinevirtual

Definition at line 300 of file tpl_sgraph.H.

References Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::clear().

◆ List_SGraph() [2/3]

template<typename __Graph_Node = Graph_Snode<unsigned long>, typename __Graph_Arc = Graph_Sarc<unsigned long>>

Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::List_SGraph ( const List_SGraph< __Graph_Node, __Graph_Arc > & g )

inline

Copy constructor.

See also: ALEPH_GRAPH_COPY_MOVE_CTORS Creates a deep copy of the graph.

Definition at line 313 of file tpl_sgraph.H.

◆ List_SGraph() [3/3]

template<typename __Graph_Node = Graph_Snode<unsigned long>, typename __Graph_Arc = Graph_Sarc<unsigned long>>

Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::List_SGraph ( List_SGraph< __Graph_Node, __Graph_Arc > && g )

inlinenoexcept

Move constructor.

Transfers ownership from g.

Definition at line 313 of file tpl_sgraph.H.

Member Function Documentation

◆ clear()

template<typename __Graph_Node = Graph_Snode<unsigned long>, typename __Graph_Arc = Graph_Sarc<unsigned long>>

void Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::clear ( )

inlineprivatenoexcept

Definition at line 595 of file tpl_sgraph.H.

References FunctionalMethods< Container, T >::for_each().

Referenced by Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::~List_SGraph().

◆ disconnect_arc()

template<typename __Graph_Node = Graph_Snode<unsigned long>, typename __Graph_Arc = Graph_Sarc<unsigned long>>

void Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::disconnect_arc ( Arc * arc )

inlineprivate

Definition at line 518 of file tpl_sgraph.H.

References Aleph::maps().

◆ get_first_arc() [1/2]

template<typename __Graph_Node = Graph_Snode<unsigned long>, typename __Graph_Arc = Graph_Sarc<unsigned long>>

Arc * Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::get_first_arc ( ) const

inline

Definition at line 581 of file tpl_sgraph.H.

References Aleph::DynSetTree< Key, Tree, Compare >::get_first().

◆ get_first_arc() [2/2]

template<typename __Graph_Node = Graph_Snode<unsigned long>, typename __Graph_Arc = Graph_Sarc<unsigned long>>

Arc * Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::get_first_arc ( Node * p ) const

inline

Returns the first arc of node p.

Exceptions

range_error if node has no arcs

Definition at line 588 of file tpl_sgraph.H.

References ah_range_error_if.

◆ get_first_node()

template<typename __Graph_Node = Graph_Snode<unsigned long>, typename __Graph_Arc = Graph_Sarc<unsigned long>>

Node * Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::get_first_node ( ) const

inline

Definition at line 576 of file tpl_sgraph.H.

References Aleph::DynSetTree< Key, Tree, Compare >::get_first().

◆ insert_arc() [1/3]

template<typename __Graph_Node = Graph_Snode<unsigned long>, typename __Graph_Arc = Graph_Sarc<unsigned long>>

Arc * GraphCommon< GT, Node, Arc >::insert_arc	(	Node *	src,
		Node *	tgt,
		Arc_Type &&	arc_info = `Arc_Type()`
	)

inline

Create and insert a new arc linking two nodes and moving the received data.

Thi method firstallocates a new arc linking the nodes pointed by srcandtgt. Ifthisis a directed graph, thensrcis considered the source node andtgtthe target one. Once the arc has been effectively allocated, if possible, the data contained in arc_info` is moved to the node avoiding copy. Finally, the arc is inserted into the graph.

The pointers srcand tgt must be valid; that is, of course, they must correspond to real nodes already inserted in the graph. At this regard, no validation is done.

Remarks: If this method does not throw exception, then this always returns a valid pointer,

Parameters

[in]	src	pointer to the source node.
[in]	tgt	pointer to the target node.
[in]	arc_info	the data to be moved to the node.

Returns: a pointer to the arc already inserted into the graph

Exceptions

bad_alloc if there is no enough memory.

Definition at line 1223 of file graph-dry.H.

◆ insert_arc() [2/3]

template<typename __Graph_Node = Graph_Snode<unsigned long>, typename __Graph_Arc = Graph_Sarc<unsigned long>>

Arc * GraphCommon< GT, Node, Arc >::insert_arc	(	Node *	src,
		Node *	tgt,
		const Arc_Type &	arc_info
	)

inline

Create and insert a new arc linking two nodes and copying data.

insert_arc() allocates a new arc linking the nodes pointed by src and tgt. If this is a directed graph, then src is considered the source node and tgt the target one. When the arc has been effectively allocated, the data contained in arc_info is copied to the node. Finally, the arc is inserted into the graph.

The pointers srcand tgt must be valid; that is, of course, they must correspond to real nodes already inserted in the graph. At this regard, no validation is done.

Remarks: If this method does not throw exception, then this always returns a valid pointer,

Parameters

[in]	src	pointer to the source node.
[in]	tgt	pointer to the target node.
[in]	arc_info	the data to be copied to the node.

Returns: a pointer to the arc already inserted into the graph

Exceptions

bad_alloc if there is no enough memory.

Definition at line 1193 of file graph-dry.H.

◆ insert_arc() [3/3]

template<typename __Graph_Node = Graph_Snode<unsigned long>, typename __Graph_Arc = Graph_Sarc<unsigned long>>

Arc * Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::insert_arc	(	Node *	src,
		Node *	tgt,
		void *	a
	)

inlineprivate

Definition at line 497 of file tpl_sgraph.H.

References Aleph::DynSetTree< Key, Tree, Compare >::append(), and Aleph::maps().

Referenced by TEST(), and TEST().

◆ insert_node() [1/3]

template<typename __Graph_Node = Graph_Snode<unsigned long>, typename __Graph_Arc = Graph_Sarc<unsigned long>>

Node * GraphCommon< GT, Node, Arc >::insert_node ( const Node_Type & node_info )

inline

Allocate a new node, set by copy its data content and insert it into the graph.

This method perform several actions. First, it allocates memory for a graph node. Then the data node_info is copied to the data associated to the node. This copy is done via the copy constructor and assign operator. So, these functionalities must be present for the class Node_Type. Finally, the node is topologically inserted into the graph.

Remarks: If this method does not throw exception, then this always returns a valid pointer,

Parameters

[in] node_info info to copy to the new node. The copy constructor and the assign operator must be defined for the class Node_Type.

Returns: a pointer to the new inserted node.

Exceptions

bad_allod if there is no enough memory

Definition at line 1116 of file graph-dry.H.

◆ insert_node() [2/3]

template<typename __Graph_Node = Graph_Snode<unsigned long>, typename __Graph_Arc = Graph_Sarc<unsigned long>>

virtual Node * Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::insert_node ( Node * p )

inlinevirtual

Insertion of a node whose memory has already been allocated.

This method assumes a node of type List_SGraph::Node pointed to by the parameter p and inserts it into the graph.

Parameters

[in] p Pointer to an already created node that does not belong to any graph.

Returns: Pointer to the inserted node.

Note: Since when the node is removed or the graph is destroyed the delete operator will be invoked, p must have been imperatively allocated with new.; In general, this routine should not be used. Instead, use the other insertion method (which allocates memory automatically).

Definition at line 487 of file tpl_sgraph.H.

References Aleph::DynSetTree< Key, Tree, Compare >::append(), Aleph::maps(), and num_nodes.

Referenced by TEST(), and TEST().

◆ insert_node() [3/3]

template<typename __Graph_Node = Graph_Snode<unsigned long>, typename __Graph_Arc = Graph_Sarc<unsigned long>>

Node * GraphCommon< GT, Node, Arc >::insert_node ( Node_Type && node_info = Node_Type() )

inline

Allocate a new node, set by moving its data content and insert it into the graph.

This method perform several actions. First, it allocates memory for a graph node. Then the data node_info is moved to the data associated to the node. This movement is done via the move constructor and move assign operator. So, these functionalities must be present for the class Node_Type. Finally, the node is topologically inserted into the graph.

Remarks: If this method does not throw exception, then this always returns a valid pointer,

Parameters

[in] node_info info to move to the new node. The move constructor and the move assign operator must be defined for the class Node_Type.

Returns: a pointer to the new inserted node.

Exceptions

bad_allod if there is no enough memory.

Definition at line 1140 of file graph-dry.H.

◆ operator=() [1/2]

template<typename __Graph_Node = Graph_Snode<unsigned long>, typename __Graph_Arc = Graph_Sarc<unsigned long>>

List_SGraph & Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::operator= ( const List_SGraph< __Graph_Node, __Graph_Arc > & g )

inline

Copy assignment.

Replaces contents with a deep copy of g.

Definition at line 313 of file tpl_sgraph.H.

◆ operator=() [2/2]

template<typename __Graph_Node = Graph_Snode<unsigned long>, typename __Graph_Arc = Graph_Sarc<unsigned long>>

List_SGraph & Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::operator= ( List_SGraph< __Graph_Node, __Graph_Arc > && g )

inlinenoexcept

Move assignment.

Transfers ownership from g.

Definition at line 313 of file tpl_sgraph.H.

◆ remove_arc()

template<typename __Graph_Node = Graph_Snode<unsigned long>, typename __Graph_Arc = Graph_Sarc<unsigned long>>

virtual void Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::remove_arc ( Arc * arc )

inlinevirtualnoexcept

Removes the arc.

The operation removes the arc from the graph and then frees its memory.

The arc must belong to the graph and no verification is performed in this regard.

Parameters

[in] arc Pointer to the arc to remove.

Definition at line 544 of file tpl_sgraph.H.

References Aleph::DynSetTree< Key, Tree, Compare >::remove().

◆ remove_node()

template<typename __Graph_Node = Graph_Snode<unsigned long>, typename __Graph_Arc = Graph_Sarc<unsigned long>>

virtual void Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::remove_node ( Node * p )

inlinevirtualnoexcept

Definition at line 552 of file tpl_sgraph.H.

References Aleph::DynList< T >::append(), FunctionalMethods< Container, T >::for_each(), Aleph::maps(), num_nodes, and Aleph::DynSetTree< Key, Tree, Compare >::remove().

◆ sort_arcs() [1/2]

template<typename __Graph_Node = Graph_Snode<unsigned long>, typename __Graph_Arc = Graph_Sarc<unsigned long>>

template<class Compare >

void Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::sort_arcs ( Compare && cmp = Compare() )

inline

Definition at line 628 of file tpl_sgraph.H.

References cmp().

◆ sort_arcs() [2/2]

template<typename __Graph_Node = Graph_Snode<unsigned long>, typename __Graph_Arc = Graph_Sarc<unsigned long>>

template<class Compare >

Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::sort_arcs ( Compare & cmp )

inline

Sort all arcs of the graph according to a comparison criteria.

Note: This implementation uses a DynSetTree for arc storage, which maintains its own ordering. Sorting requires extracting arcs to a list, sorting, and rebuilding the set. This is O(E log E).

Template Parameters

Compare Comparison functor type with signature bool operator()(Arc*, Arc*).

Parameters

[in] cmp Comparison functor.

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 613 of file tpl_sgraph.H.

References Aleph::DynSetTree< Key, Tree, Compare >::append(), Aleph::DynList< T >::append(), cmp(), Aleph::DynSetTree< Key, Tree, Compare >::empty(), FunctionalMethods< Container, T >::for_each(), Aleph::maps(), and Aleph::mergesort().

◆ swap()

template<typename __Graph_Node = Graph_Snode<unsigned long>, typename __Graph_Arc = Graph_Sarc<unsigned long>>

void Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::swap ( List_SGraph< __Graph_Node, __Graph_Arc > & g )

inlinenoexcept

Definition at line 305 of file tpl_sgraph.H.

References Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::arc_list, GraphCommon< GT, Node, Arc >::common_swap(), Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::node_list, and Aleph::DynSetTree< Key, Tree, Compare >::swap().

Friends And Related Symbol Documentation

◆ GraphCommon< List_SGraph< __Graph_Node, __Graph_Arc >, __Graph_Node, __Graph_Arc >

template<typename __Graph_Node = Graph_Snode<unsigned long>, typename __Graph_Arc = Graph_Sarc<unsigned long>>

friend class GraphCommon< List_SGraph< __Graph_Node, __Graph_Arc >, __Graph_Node, __Graph_Arc >

friend

Definition at line 233 of file tpl_sgraph.H.

Member Data Documentation

◆ arc_list

template<typename __Graph_Node = Graph_Snode<unsigned long>, typename __Graph_Arc = Graph_Sarc<unsigned long>>

DynSetArc Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::arc_list

private

Set of arcs in the graph.

Definition at line 295 of file tpl_sgraph.H.

Referenced by Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::swap().

◆ node_list

template<typename __Graph_Node = Graph_Snode<unsigned long>, typename __Graph_Arc = Graph_Sarc<unsigned long>>

DynSetNode Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::node_list

private

Set of nodes in the graph.

Definition at line 294 of file tpl_sgraph.H.

Referenced by Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::swap().

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

tpl_sgraph.H

Classes

Public Types

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Friends

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ Arc

◆ Arc_Type

◆ CommonBase

◆ DynSetArc

◆ DynSetNode

◆ Node

◆ Node_Type

Constructor & Destructor Documentation

◆ List_SGraph() [1/3]

◆ ~List_SGraph()

◆ List_SGraph() [2/3]

◆ List_SGraph() [3/3]

Member Function Documentation

◆ clear()

◆ disconnect_arc()

◆ get_first_arc() [1/2]

◆ get_first_arc() [2/2]

◆ get_first_node()

◆ insert_arc() [1/3]

◆ insert_arc() [2/3]

◆ insert_arc() [3/3]

◆ insert_node() [1/3]

◆ insert_node() [2/3]

◆ insert_node() [3/3]

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ remove_arc()

◆ remove_node()

◆ sort_arcs() [1/2]

◆ sort_arcs() [2/2]

◆ swap()

Friends And Related Symbol Documentation

◆ GraphCommon< List_SGraph< __Graph_Node, __Graph_Arc >, __Graph_Node, __Graph_Arc >

Member Data Documentation

◆ arc_list

◆ node_list