Referencia de la plantilla de la Clase Aleph::Random_Graph< GT, Init_Node, Init_Arc >

#include <random_graph.H>

Diagrama de herencias de Aleph::Random_Graph< GT, Init_Node, Init_Arc >

Diagrama de colaboración para Aleph::Random_Graph< GT, Init_Node, Init_Arc >:

Métodos públicos
	Random_Graph (unsigned long seed, const Init_Node &__init_node, const Init_Arc &__init_arc)
	Random_Graph (unsigned long seed=time(NULL), 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)
Métodos públicos heredados desde Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >
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)

Otros miembros heredados
Tipos protegidos heredados desde Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >
typedef GT::Node	GT_Node
typedef GT::Arc	GT_Arc
Métodos protegidos heredados desde 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=NULL)
GT_Node *	select_random_node (DynList< GT_Node * > &list)
void	initialize_and_create_nodes (const size_t &__num_nodes, const size_t &__num_arcs)
	Random_Graph_Base (unsigned long seed, const Init_Node &__init_node, const Init_Arc &__init_arc)
GT	create (const size_t &__num_nodes, const size_t &__num_arcs, bool connected)
Atributos protegidos heredados desde Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >
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

Descripción detallada

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.

Autor

Leandro Rabindranath León

Documentación del constructor y destructor

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

Parámetros

[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

Documentación de las funciones miembro

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.

Parámetros

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

Devuelve

puntero al grafo aleatorio creado.

Excepciones

bad_alloc

si no hay suficiente memoria.

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.

Atención

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

Parámetros

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

Devuelve

puntero al grafo aleatorio creado.

Excepciones

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

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.

Parámetros

[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.

Devuelve

puntero al grafo aleatorio creado.

Excepciones

bad_alloc

si no hay suficiente memoria.

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.

Atención

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

Parámetros

[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.

Devuelve

puntero al grafo aleatorio creado.

Excepciones

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

---

La documentación para esta clase fue generada a partir del siguiente fichero:

• random_graph.H