Random directed graph (digraph) generator. More...

#include <random_graph.H>

Inheritance diagram for Aleph::Random_Digraph< GT, Init_Node, Init_Arc >:

Collaboration diagram for Aleph::Random_Digraph< GT, Init_Node, Init_Arc >:

Public Member Functions
	Random_Digraph (unsigned long seed, const Init_Node &__init_node, const Init_Arc &__init_arc)
	Constructor.

	Random_Digraph (unsigned long seed=time(nullptr), const Init_Node &&__init_node=Init_Node(), const Init_Arc &&__init_arc=Init_Arc())

	Random_Digraph (const Init_Node &__init_node, const Init_Arc &__init_arc)

	~Random_Digraph ()

GT	operator() (const size_t &__num_nodes, const size_t &__num_arcs, bool connected=true)
	Create a sparse random digraph.

GT	operator() (const size_t &__num_nodes, const double &p, bool connected=true)
	Create a random digraph with arc probability.

Public Member Functions inherited from Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >
GT	eulerian (const size_t &__num_nodes, const size_t &__num_arcs)
	Create a random Eulerian graph (sparse version).

GT	eulerian (const size_t &__num_nodes, const double &p)
	Create a random Eulerian graph (dense version).

GT	sufficient_hamiltonian (const size_t &__num_nodes, const double &p=0.5)
	Create a random Hamiltonian graph.

Private Types
typedef GT::Node	GT_Node

typedef GT::Arc	GT_Arc

Private Member Functions
bool	verify_tables ()

virtual void	update_parity_after_arc_insertion (GT_Node src, GT_Node tgt)

void	create_nodes_and_initialize_arc_index () override

void	connect () override

GT	create_p (const size_t &__num_nodes, const double &p, bool connected) override

void	make_eulerian () override

void	balance_digraph_node (GT_Node *p)

void	balance_digraph_nodes_degree (GT_Node src, GT_Node tgt)

void	make_hamiltonian () override

Private Attributes
DynSetRandTree< GT_Node * >	greater

DynSetRandTree< GT_Node * >	smaller

DynSetRandTree< GT_Node * >	equal

Additional Inherited Members
Protected Types inherited from Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >
typedef GT::Node	GT_Node

typedef GT::Arc	GT_Arc

Protected Member Functions inherited from Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >
GT_Arc *	insert_arc (GT_Node src, GT_Node tgt)

GT_Node *	select_random_node (GT_Node *excluded=nullptr) noexcept
	Select a random node different from `excluded`.

GT_Node *	select_random_node (DynList< GT_Node * > &list) noexcept
	Select a random node from the given list.

void	initialize_and_create_nodes (const size_t &__num_nodes, const size_t &__num_arcs)

	Random_Graph_Base (const unsigned long seed, const Init_Node &__init_node, const Init_Arc &__init_arc)

virtual	~Random_Graph_Base ()

GT	create (const size_t &__num_nodes, const size_t &__num_arcs, const bool connected)
	Create a sparse random graph.

Protected Attributes inherited from Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >
gsl_rng *	r

Init_Node &	init_node

Init_Arc &	init_arc

std::unique_ptr< DynArray< GT_Node * > >	nodes

std::unique_ptr< IndexArc< GT > >	idx_arc

size_t	num_nodes

size_t	num_arcs

unsigned long	rand_max

GT	g

bool	save_parity

Detailed Description

template<AlephGraph GT, class Init_Node = Dft_Init_Rand_Node<GT>, class Init_Arc = Dft_Init_Rand_Arc<GT>>
class Aleph::Random_Digraph< GT, Init_Node, Init_Arc >

Random directed graph (digraph) generator.

Random_Digraph is a class for generating random directed graphs with a specified number of nodes and, depending on the invoked operation, a specified number of arcs or arc probability.

The class exports two generation methods via the function-call operator, intended for generating sparse and dense digraphs respectively.

Template parameters:

GT: The graph type to construct (must be directed).
Init_Node: Functor class for initializing node data.
Init_Arc: Functor class for initializing arc data.

Author: Leandro Rabindranath Leon

Definition at line 741 of file random_graph.H.

Member Typedef Documentation

◆ GT_Arc

template<AlephGraph GT, class Init_Node = Dft_Init_Rand_Node<GT>, class Init_Arc = Dft_Init_Rand_Arc<GT>>

typedef GT::Arc Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::GT_Arc

private

Definition at line 744 of file random_graph.H.

◆ GT_Node

template<AlephGraph GT, class Init_Node = Dft_Init_Rand_Node<GT>, class Init_Arc = Dft_Init_Rand_Arc<GT>>

typedef GT::Node Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::GT_Node

private

Definition at line 743 of file random_graph.H.

Constructor & Destructor Documentation

◆ Random_Digraph() [1/3]

template<AlephGraph GT, class Init_Node = Dft_Init_Rand_Node<GT>, class Init_Arc = Dft_Init_Rand_Arc<GT>>

Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::Random_Digraph	(	unsigned long	seed,
		const Init_Node &	__init_node,
		const Init_Arc &	__init_arc
	)

inline

Constructor.

Parameters

[in]	seed	Seed for the random number generator.
[in]	__init_node	Node initialization functor.
[in]	__init_arc	Arc initialization functor.

Definition at line 996 of file random_graph.H.

References Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::g, and GraphCommon< GT, Node, Arc >::set_digraph().

◆ Random_Digraph() [2/3]

template<AlephGraph GT, class Init_Node = Dft_Init_Rand_Node<GT>, class Init_Arc = Dft_Init_Rand_Arc<GT>>

Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::Random_Digraph	(	unsigned long	seed = `time(nullptr)`,
		const Init_Node &&	__init_node = `Init_Node()`,
		const Init_Arc &&	__init_arc = `Init_Arc()`
	)

inline

Definition at line 1004 of file random_graph.H.

◆ Random_Digraph() [3/3]

template<AlephGraph GT, class Init_Node = Dft_Init_Rand_Node<GT>, class Init_Arc = Dft_Init_Rand_Arc<GT>>

Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::Random_Digraph	(	const Init_Node &	__init_node,
		const Init_Arc &	__init_arc
	)

inline

Definition at line 1012 of file random_graph.H.

◆ ~Random_Digraph()

template<AlephGraph GT, class Init_Node = Dft_Init_Rand_Node<GT>, class Init_Arc = Dft_Init_Rand_Arc<GT>>

Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::~Random_Digraph ( )

inline

Definition at line 1019 of file random_graph.H.

References Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::g, and GraphCommon< GT, Node, Arc >::set_digraph().

Member Function Documentation

◆ balance_digraph_node()

template<AlephGraph GT, class Init_Node = Dft_Init_Rand_Node<GT>, class Init_Arc = Dft_Init_Rand_Arc<GT>>

void Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::balance_digraph_node ( GT_Node * p )

inlineprivate

Definition at line 1112 of file random_graph.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::g, GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::idx_arc, Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::insert_arc(), NODE_COUNTER, Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::nodes, and Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::r.

Referenced by Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::balance_digraph_nodes_degree().

◆ balance_digraph_nodes_degree()

template<AlephGraph GT, class Init_Node = Dft_Init_Rand_Node<GT>, class Init_Arc = Dft_Init_Rand_Arc<GT>>

void Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::balance_digraph_nodes_degree	(	GT_Node *	src,
		GT_Node *	tgt
	)

inlineprivate

Definition at line 1139 of file random_graph.H.

References Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::balance_digraph_node(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::g, GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::idx_arc, Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::insert_arc(), NODE_COUNTER, Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::nodes, and Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::r.

Referenced by Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::make_hamiltonian().

◆ connect()

template<AlephGraph GT, class Init_Node = Dft_Init_Rand_Node<GT>, class Init_Arc = Dft_Init_Rand_Arc<GT>>

void Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::connect ( )

inlineoverrideprivatevirtual

Implements Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >.

Definition at line 908 of file random_graph.H.

References Aleph::DynArray< T >::access(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::g, GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::idx_arc, Aleph::in_degree(), Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::insert_arc(), NODE_COUNTER, Aleph::DynArray< T >::reserve(), and Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::select_random_node().

Referenced by Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::create_p().

◆ create_nodes_and_initialize_arc_index()

template<AlephGraph GT, class Init_Node = Dft_Init_Rand_Node<GT>, class Init_Arc = Dft_Init_Rand_Arc<GT>>

void Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::create_nodes_and_initialize_arc_index ( )

inlineoverrideprivatevirtual

Implements Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >.

Definition at line 885 of file random_graph.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::g, Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::idx_arc, Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::init_node, Aleph::DynSetTree< Key, Tree, Compare >::insert(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), NODE_COUNTER, Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::nodes, Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::num_nodes, and Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::save_parity.

◆ create_p()

template<AlephGraph GT, class Init_Node = Dft_Init_Rand_Node<GT>, class Init_Arc = Dft_Init_Rand_Arc<GT>>

GT Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::create_p	(	const size_t &	__num_nodes,
		const double &	p,
		bool	connected
	)

inlineoverrideprivatevirtual

Implements Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >.

Definition at line 964 of file random_graph.H.

Referenced by Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::operator()().

◆ make_eulerian()

template<AlephGraph GT, class Init_Node = Dft_Init_Rand_Node<GT>, class Init_Arc = Dft_Init_Rand_Arc<GT>>

void Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::make_eulerian ( )

inlineoverrideprivatevirtual

Implements Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >.

Definition at line 1077 of file random_graph.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::idx_arc, Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::insert_arc(), Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::r, Aleph::DynSetTree< Key, Tree, Compare >::select(), and Aleph::DynSetTree< Key, Tree, Compare >::size().

◆ make_hamiltonian()

template<AlephGraph GT, class Init_Node = Dft_Init_Rand_Node<GT>, class Init_Arc = Dft_Init_Rand_Arc<GT>>

void Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::make_hamiltonian ( )

inlineoverrideprivatevirtual

Implements Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >.

Definition at line 1176 of file random_graph.H.

References Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::balance_digraph_nodes_degree(), Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::g, GraphCommon< GT, Node, Arc >::get_num_nodes(), NODE_COUNTER, Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::nodes, and GraphCommon< GT, Node, Arc >::reset_counter_nodes().

◆ operator()() [1/2]

template<AlephGraph GT, class Init_Node = Dft_Init_Rand_Node<GT>, class Init_Arc = Dft_Init_Rand_Arc<GT>>

GT Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::operator()	(	const size_t &	__num_nodes,
		const double &	p,
		bool	connected = `true`
	)

inline

Create a random digraph with arc probability.

This version builds a random digraph with probability p of an arc existing between any ordered pair of nodes.

Use this routine to generate dense digraphs. In this case, use a value of p greater than or equal to 0.5.

The procedure is quadratic: all ordered node pairs are enumerated, and for each pair (i, j) a random draw with probability p determines whether an arc is created.

Warning: The procedure can be extremely slow and memory-intensive as __num_nodes increases.

Parameters

[in]	__num_nodes	Number of nodes the digraph should have.
[in]	p	Probability of an arc existing between any ordered pair of nodes.
[in]	connected	Whether the generated digraph should be strongly connected. Defaults to `true`.

Returns: The randomly created digraph.

Exceptions

bad_alloc	if there is not enough memory.
domain_error	if `p` is not in the range (0, 1].

Definition at line 1070 of file random_graph.H.

References Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::create_p().

◆ operator()() [2/2]

template<AlephGraph GT, class Init_Node = Dft_Init_Rand_Node<GT>, class Init_Arc = Dft_Init_Rand_Arc<GT>>

GT Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::operator()	(	const size_t &	__num_nodes,
		const size_t &	__num_arcs,
		bool	connected = `true`
	)

inline

Create a sparse random digraph.

This version builds a random digraph with approximately __num_arcs arcs. The digraph contains no parallel arcs.

The randomization procedure selects two nodes at random and inserts an arc between them if one does not already exist. The routine is linear, proportional to __num_arcs.

Parameters

[in]	__num_nodes	Number of nodes the digraph should have.
[in]	__num_arcs	Number of arcs the digraph should have.
[in]	connected	Whether the generated digraph should be strongly connected. Defaults to `true`.

Returns: The randomly created digraph.

Exceptions

bad_alloc if there is not enough memory.

Definition at line 1040 of file random_graph.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::create().

◆ update_parity_after_arc_insertion()

template<AlephGraph GT, class Init_Node = Dft_Init_Rand_Node<GT>, class Init_Arc = Dft_Init_Rand_Arc<GT>>

virtual void Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::update_parity_after_arc_insertion	(	GT_Node *	src,
		GT_Node *	tgt
	)

inlineprivatevirtual

Implements Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >.

Definition at line 835 of file random_graph.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::g, GraphCommon< GT, Node, Arc >::get_num_arcs(), Aleph::DynSetTree< Key, Tree, Compare >::insert(), NODE_COUNTER, Aleph::DynSetTree< Key, Tree, Compare >::remove(), Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::save_parity, and Aleph::DynSetTree< Key, Tree, Compare >::search().

◆ verify_tables()

template<AlephGraph GT, class Init_Node = Dft_Init_Rand_Node<GT>, class Init_Arc = Dft_Init_Rand_Arc<GT>>

bool Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::verify_tables ( )

inlineprivate

Definition at line 750 of file random_graph.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::equal, Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::g, GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), NODE_COUNTER, Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::nodes, Aleph::DynSetTree< Key, Tree, Compare >::search(), Aleph::DynSetTree< Key, Tree, Compare >::size(), and Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::smaller.

Member Data Documentation

◆ equal

template<AlephGraph GT, class Init_Node = Dft_Init_Rand_Node<GT>, class Init_Arc = Dft_Init_Rand_Arc<GT>>

DynSetRandTree<GT_Node *> Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::equal

private

Definition at line 748 of file random_graph.H.

Referenced by Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::verify_tables().

◆ greater

template<AlephGraph GT, class Init_Node = Dft_Init_Rand_Node<GT>, class Init_Arc = Dft_Init_Rand_Arc<GT>>

DynSetRandTree<GT_Node *> Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::greater

private

Definition at line 746 of file random_graph.H.

◆ smaller

template<AlephGraph GT, class Init_Node = Dft_Init_Rand_Node<GT>, class Init_Arc = Dft_Init_Rand_Arc<GT>>

DynSetRandTree<GT_Node *> Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::smaller

private

Definition at line 747 of file random_graph.H.

Referenced by Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::verify_tables().

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

random_graph.H

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ GT_Arc

◆ GT_Node

Constructor & Destructor Documentation

◆ Random_Digraph() [1/3]

◆ Random_Digraph() [2/3]

◆ Random_Digraph() [3/3]

◆ ~Random_Digraph()

Member Function Documentation

◆ balance_digraph_node()

◆ balance_digraph_nodes_degree()

◆ connect()

◆ create_nodes_and_initialize_arc_index()

◆ create_p()

◆ make_eulerian()

◆ make_hamiltonian()

◆ operator()() [1/2]

◆ operator()() [2/2]

◆ update_parity_after_arc_insertion()

◆ verify_tables()

Member Data Documentation

◆ equal

◆ greater

◆ smaller