Random undirected graph generator. More...

#include <random_graph.H>

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

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

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

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

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

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

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.

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
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, const bool connected) override

void	make_eulerian () override

void	balance_graph_nodes_degree (GT_Node src, GT_Node tgt)

void	make_hamiltonian () override

Private Attributes
DynSetRandTree< GT_Node * >	odd_nodes

DynSetRandTree< GT_Node * >	even_nodes

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<class GT, class Init_Node = Dft_Init_Rand_Node<GT>, class Init_Arc = Dft_Init_Rand_Arc<GT>>
class Aleph::Random_Graph< GT, Init_Node, Init_Arc >

Random undirected graph generator.

Random_Graph is a class for generating random undirected 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 graphs respectively.

For this class to compile, GT::Node_Type and GT::Arc_Type must have default constructors.

Template parameters:

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

The Init_Node class must have the following structure:

struct Init_Node
{
  void operator () (GT & g, GT::Node * p) { ... }
};

The Init_Arc class must have the following structure:

struct Init_Arc
{
  void operator () (GT & g, GT::Arc * a) { ... }
};

The generation routines include a boolean parameter that determines whether the graph should be connected. By default, this parameter is true. Consider setting it to false if connectivity is not required, since ensuring connectivity requires computing connected components, which adds time and memory overhead.

Author: Leandro Rabindranath Leon

Definition at line 368 of file random_graph.H.

Member Typedef Documentation

◆ GT_Arc

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

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

private

Definition at line 371 of file random_graph.H.

◆ GT_Node

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

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

private

Definition at line 370 of file random_graph.H.

Constructor & Destructor Documentation

◆ Random_Graph() [1/2]

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

Aleph::Random_Graph< GT, Init_Node, Init_Arc >::Random_Graph	(	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 485 of file random_graph.H.

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

◆ Random_Graph() [2/2]

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

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

inline

Definition at line 494 of file random_graph.H.

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

Member Function Documentation

◆ balance_graph_nodes_degree()

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

void Aleph::Random_Graph< GT, Init_Node, Init_Arc >::balance_graph_nodes_degree	(	GT_Node *	src,
		GT_Node *	tgt
	)

inlineprivate

Definition at line 595 of file random_graph.H.

References 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(), Aleph::maps(), 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_Graph< GT, Init_Node, Init_Arc >::make_hamiltonian().

◆ connect()

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

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

inlineoverrideprivatevirtual

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

Definition at line 426 of file random_graph.H.

References Aleph::DynList< T >::append(), Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::g, Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::insert_arc(), Aleph::maps(), and Aleph::HTList::size().

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

◆ create_nodes_and_initialize_arc_index()

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

void Aleph::Random_Graph< 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 404 of file random_graph.H.

References 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(), Aleph::maps(), 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<class GT , class Init_Node = Dft_Init_Rand_Node<GT>, class Init_Arc = Dft_Init_Rand_Arc<GT>>

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

inlineoverrideprivatevirtual

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

Definition at line 453 of file random_graph.H.

References ah_domain_error_if, Aleph::Random_Graph< GT, Init_Node, Init_Arc >::connect(), Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::g, Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::initialize_and_create_nodes(), Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::insert_arc(), Aleph::maps(), 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 >::r.

Referenced by Aleph::Random_Graph< GT, Init_Node, Init_Arc >::eulerian(), Aleph::Random_Graph< GT, Init_Node, Init_Arc >::operator()(), and Aleph::Random_Graph< GT, Init_Node, Init_Arc >::sufficient_hamiltonian().

◆ eulerian() [1/2]

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

GT Aleph::Random_Graph< GT, Init_Node, Init_Arc >::eulerian	(	const size_t &	__num_nodes,
		const double &	p
	)

inline

Create a random Eulerian graph (dense version).

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

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

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

Parameters

[in]	__num_nodes	Number of nodes the graph should have.
[in]	p	Probability of an arc existing between any pair of nodes.

Returns: The randomly created graph.

Exceptions

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

Definition at line 671 of file random_graph.H.

References Aleph::Random_Graph< GT, Init_Node, Init_Arc >::create_p(), Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::g, Aleph::Random_Graph< GT, Init_Node, Init_Arc >::make_eulerian(), and Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::save_parity.

◆ eulerian() [2/2]

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

GT Aleph::Random_Graph< GT, Init_Node, Init_Arc >::eulerian	(	const size_t &	__num_nodes,
		const size_t &	__num_arcs
	)

inline

Create a random Eulerian graph (sparse version).

This version builds a sparse random graph that is guaranteed to be Eulerian; that is, it contains Eulerian cycles.

The process first generates a sparse random graph, then examines the result and creates new arcs so that the output contains an Eulerian cycle.

Parameters

[in]	__num_nodes	Number of nodes the graph should have.
[in]	__num_arcs	Number of arcs the graph should have.

Returns: The randomly created graph.

Exceptions

bad_alloc if there is not enough memory.

Definition at line 645 of file random_graph.H.

References Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::create(), Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::g, Aleph::Random_Graph< GT, Init_Node, Init_Arc >::make_eulerian(), Aleph::maps(), and Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::save_parity.

◆ make_eulerian()

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

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

inlineoverrideprivatevirtual

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

Definition at line 556 of file random_graph.H.

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

Referenced by Aleph::Random_Graph< GT, Init_Node, Init_Arc >::eulerian(), and Aleph::Random_Graph< GT, Init_Node, Init_Arc >::eulerian().

◆ make_hamiltonian()

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

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

inlineoverrideprivatevirtual

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

Definition at line 619 of file random_graph.H.

References Aleph::Random_Graph< GT, Init_Node, Init_Arc >::balance_graph_nodes_degree(), Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::g, GraphCommon< GT, Node, Arc >::get_num_nodes(), and Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::nodes.

Referenced by Aleph::Random_Graph< GT, Init_Node, Init_Arc >::sufficient_hamiltonian().

◆ operator()() [1/2]

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

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

inline

Create a random graph with arc probability.

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

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

The procedure is quadratic: all 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 graph should have.
[in]	p	Probability of an arc existing between any pair of nodes.
[in]	connected	Whether the generated graph should be connected. Defaults to `true`.

Returns: The randomly created graph.

Exceptions

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

Definition at line 549 of file random_graph.H.

References Aleph::Random_Graph< GT, Init_Node, Init_Arc >::create_p(), and Aleph::maps().

◆ operator()() [2/2]

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

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

inline

Create a sparse random graph.

This version builds a random graph with approximately __num_arcs arcs. The graph 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 graph should have.
[in]	__num_arcs	Number of arcs the graph should have.
[in]	connected	Whether the generated graph should be connected. Defaults to `true`.

Returns: The randomly created graph.

Exceptions

bad_alloc if there is not enough memory.

Definition at line 520 of file random_graph.H.

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

◆ update_parity_after_arc_insertion()

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

virtual void Aleph::Random_Graph< 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 376 of file random_graph.H.

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

Member Data Documentation

◆ even_nodes

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

DynSetRandTree<GT_Node *> Aleph::Random_Graph< GT, Init_Node, Init_Arc >::even_nodes

private

Definition at line 374 of file random_graph.H.

◆ odd_nodes

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

DynSetRandTree<GT_Node *> Aleph::Random_Graph< GT, Init_Node, Init_Arc >::odd_nodes

private

Definition at line 373 of file random_graph.H.

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_Graph() [1/2]

◆ Random_Graph() [2/2]

Member Function Documentation

◆ balance_graph_nodes_degree()

◆ connect()

◆ create_nodes_and_initialize_arc_index()

◆ create_p()

◆ eulerian() [1/2]

◆ eulerian() [2/2]

◆ make_eulerian()

◆ make_hamiltonian()

◆ operator()() [1/2]

◆ operator()() [2/2]

◆ update_parity_after_arc_insertion()

Member Data Documentation

◆ even_nodes

◆ odd_nodes