Aleph::Random_Graph< GT, Init_Node, Init_Arc > Class Template Reference

#include <random_graph.H>

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

Public Member Functions
	Random_Graph (unsigned long seed, const Init_Node &__init_node, const Init_Arc &__init_arc)
	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)
GT	operator() (const size_t &__num_nodes, const double &p, bool connected=true)
GT	eulerian (const size_t &__num_nodes, const size_t &__num_arcs)
GT	eulerian (const size_t &__num_nodes, const double &p)
GT	sufficient_hamiltonian (const size_t &__num_nodes, const double &p=0.5)

Protected Member Functions
GT_Arc *	insert_arc (GT_Node *src, GT_Node *tgt)
GT_Node *	select_random_node (GT_Node *excluded=nullptr) noexcept
GT_Node *	select_random_node (DynList< GT_Node *> &list) noexcept
void	initialize_and_create_nodes (const size_t &__num_nodes, const size_t &__num_arcs)
GT	create (const size_t &__num_nodes, const size_t &__num_arcs, bool connected)

Protected Attributes
gsl_rng *	r
Init_Node &	init_node
Init_Arc &	init_arc
unique_ptr< DynArray< GT_Node * > >	nodes
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 >

Generador de grafos aleatorios.

Random_Graph es una clase generadora de grafos aleatorios de num_nodes y según el tipo de operación que se invoque de num_arcs.

La clase exporta dos métodos de generación, a través del operador paréntesis, destinados a la generación de grafos esparcidos y densos respectivamente.

Para que la clase compile deben existir los constructores GT::Node_Type y GT::Arc_Type.

Los parámetros de la clase son:

• GT: el tipo de grafo a construir.
• Init_Node: clase de inicialización de los datos del nodo.
• Init_Arc: clase de inicialización de los datos del arco.

La clase Init_Node tiene la siguiente estructura:

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

La clase Init_Arc tiene la siguiente estructura:

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

Las rutinas de generación contienen un parámetro lógico que determina si el grafo debe ser o no conexo. Por omisión el parámetro es true. Tómese eso en consideración si no es necesario que el grafo sea conexo, pues para hacer el grafo conexo se requiere determinar los componentes inconexos, lo cual requiere más tiempo y consumo de memoria.

Author

Leandro Rabindranath León

Constructor & Destructor Documentation

Random_Graph()

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	semilla del generador de números aleatorios
[in]	__init_node	clase de inicialización de nodo
[in]	__init_arc	clase de inicialización de arco

Member Function Documentation

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 size_t &  __num_arcs  )

inline

Crea un grafo aleatorio que es euleriano.

Esta versión construye un grafo aleatorio esparcido que se garantiza es euleriano; es decir, que contiene ciclos eulerianos.

El proceso primero genera un grafo esparcido aleatorio, luego examina el grafo resultante y crea nuevos arcos de modo que el resultado contenga un ciclo euleriano.

Parameters

[in]	__num_nodes	cantidad de nodos que debe tener el grafo.
[in]	__num_arcs	cantidad de arcos que debe tener el grafo.

Returns

puntero al grafo aleatorio creado.

Exceptions

bad_alloc

si no hay suficiente memoria.

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 double &  p  )

inline

Crea un grafo aleatorio euleriano.

Esta versión construye un grafo aleatorio euleriano con probabilidad p de existencia de arco entre cualquier par de nodos.

Úsese esta rutina para generar grafos densos. En este caso, empléese un valor de p mayor o igual a 0.5.

Warning

El procedimiento puede ser extremadamente lento y goloso en memoria conforme aumento el valor de __num_nodes.

Parameters

[in]	__num_nodes	cantidad de nodos que debe tener el grafo.
[in]	p	probabilidad de existencia de arco entre cualquier par de nodos.

Returns

puntero al grafo aleatorio creado.

Exceptions

bad_alloc	si no hay suficiente memoria.
domain_error	si el valor de p no está entre 0 y 1.

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 size_t &  __num_arcs, bool  connected = true  )

inline

Crea un grafo aleatorio esparcido.

Esta versión construye un grafo aleatorio de aproximadamente __num_arcs. El grafo no contiene arcos paralelos.

El procedimiento de aleatorización es seleccionar al azar dos nodos e insertar un arco entre ellos en caso de que éste no exista. La rutina es lineal, proporcional a __num_arcs.

Parameters

[in]	__num_nodes	cantidad de nodos que debe tener el grafo.
[in]	__num_arcs	cantidad de arcos que debe tener el grafo.
[in]	connected	si el grafo a generar debe ser conexo o no. Por omisión lo es.

Returns

puntero al grafo aleatorio creado.

Exceptions

bad_alloc

si no hay suficiente memoria.

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 double &  p, bool  connected = true  )

inline

Crea un grafo aleatorio.

Esta versión construye un grafo aleatorio con probabilidad p de existencia de arco entre cualquier par de nodos.

Úsese esta rutina para generar grafos densos. En este caso, empléese un valor de p mayor o igual a 0.5.

El procedimiento es cuadrático. Se generan todas las combinaciones de nodos y por cada par de nodos (i,j) se sortea con probabilidad p si debe haber un arco entre i y j.

Warning

El procedimiento puede ser extremadamente lento y goloso en memoria conforme aumento el valor de __num_nodes.

Parameters

[in]	__num_nodes	cantidad de nodos que debe tener el grafo.
[in]	p	probabilidad de existencia de arco entre cualquier par de nodos.
[in]	connected	si el grafo a generar debe ser conexo o no. Por omisión lo es.

Returns

puntero al grafo aleatorio creado.

Exceptions

bad_alloc	si no hay suficiente memoria.
domain_error	si el valor de p no está entre 0 y 1.

Here is the call graph for this function:

---

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

• random_graph.H