Grafos.

Aleph permite modelizar grafos, representar la mayoría de problemas combinatorios conocidos y ejecutar la inmensa mayoría de algoritmos conocidos. Más...

Clases

class  Ady_Mat
 Matriz de adyacencia auxiliar. Más...
class  Agent_Arc
 Arco para un Agent_Graph. Más...
class  Agent_Graph
 Grafo de agentes "caminantes". Más...
class  Agent_Graph::Agent
 Agente de un grafo. Más...
struct  Agent_Graph::Agent::Critical_Section
 Sección crítica del agente. Más...
class  Agent_Graph::Node_to_Node_Agent
 Agente que transita de nodo a nodo (sin permanecer en los arcos). Más...
class  Agent_Node
 Nodo para un Agent_Graph. Más...
class  Bit_Fields
 Mascara de bits para marcar partes de un grafo. Más...
class  Bit_Mat_Graph
 Matriz de bit de adyacencia de un grafo. Más...
struct  Concurrent_Arc
 Arco de un grafo concurrente. Más...
class  Concurrent_Arc::Critical_Section
 Toma la sección crítica del arco. Más...
class  Concurrent_Graph
 Clase grafo concurrente implementado con listas de adyacencia. Más...
class  Concurrent_Graph::Arc_Iterator
 Iterador sobre los arcos de un grafo concurrente. Más...
class  Concurrent_Graph::Node_Iterator
 Iterador sobre nodos de un grafo concurrente. Más...
struct  Concurrent_Node
 Nodo de un grafo concurrente. Más...
class  Concurrent_Node::Critical_Section
 Toma sección crítica del nodo; la libera en destructor. Más...
class  Graph_Arc
 Arco de grafo implantado con listas de adyacencia. Más...
class  Graph_Node
 Nodo de grafo implantado con listas de adyacencia. Más...
class  List_Digraph
 Clase digrafo (grafo dirigido) implementado con listas de adyacencia. Más...
class  List_Graph
 Clase grafo implementado con listas de adyacencia. Más...
class  List_Graph::Node_Arc_Iterator
 Iterador de arcos de un nodo de grafo. Más...
class  List_Graph::Node_Iterator
 Iterador de nodos de un grafo. Más...
class  Map_Matrix_Graph
 Matriz de adyacencia de un grafo mapeada a un grafo representado mediante una variante de List_Graph. Más...
class  Matrix_Graph
 Matriz de adyacencia de un grafo extraída de un grafo representado con listas de adyacencia. Más...
class  Path
 Camino sobre un grafo. Más...
class  Path::Iterator
 Iterador sobre nodos y arcos de un camino. Más...

Definiciones

#define ARC_BITS(p)   ((p)->control_bits)
 Obtiene los bits de control de un arco.
#define ARC_COOKIE(p)   ((p)->cookie)
 Retorna el cookie del arco.
#define ARC_COUNTER(p)   ((p)->counter)
 Obtiene los bits de control de un arco.
#define IS_ARC_VISITED(p, bit)   (ARC_BITS(p).get_bit(bit))
 Determina si el un bit de arco está marcado.
#define IS_NODE_VISITED(p, bit)   (NODE_BITS(p).get_bit(bit))
 Determina si el un bit de nodo está marcado.
#define NODE_BITS(p)   ((p)->control_bits)
 Obtiene los bits de control de un nodo.
#define NODE_COOKIE(p)   ((p)->cookie)
 Retorna el cookie del nodo.
#define NODE_COUNTER(p)   ((p)->counter)
 Obtiene el contador de un nodo.

Funciones

template<class GT, class Distance, class Compare, class Plus>
bool bellman_ford_min_spanning_tree (GT &g, typename GT::Node *start_node, GT &tree)
 Calcula un árbol abarcador de todos los caminos mínimos desde un nodo dado según el algoritmo de Bellman-Ford.
template<class GT>
size_t breadth_first_traversal (GT &g, bool(*visit)(GT &, typename GT::Node *, typename GT::Arc *))
 Recorrido genérico en amplitud de un grafo.
template<class GT>
size_t breadth_first_traversal (GT &g, typename GT::Node *start, bool(*visit)(GT &, typename GT::Node *, typename GT::Arc *))
 Recorrido genérico en amplitud de un grafo.
template<class GT>
void build_subgraph (GT &g,GT &sg,typename GT::Node *g_src,size_t &node_count)
 Construye un subgrafo mapeado del grafo g a partir de uno de sus nodos.
template<typename GT>
void compute_cut_nodes (GT &g, DynDlist< typename GT::Node * > &list)
 Calcula los puntos de corte de un grafo.
template<typename GT>
void compute_cut_nodes (GT &g, typename GT::Node *start, DynDlist< typename GT::Node * > &list)
 Calcula los puntos de corte de un grafo.
template<class GT>
size_t depth_first_traversal (GT &g, bool(*visit)(GT &, typename GT::Node *, typename GT::Arc *))
 Recorrido genérico en profundidad de un grafo.
template<class GT>
size_t depth_first_traversal (GT &g, typename GT::Node *start_node, bool(*visit)(GT &g, typename GT::Node *, typename GT::Arc *))
 Recorrido genérico en profundidad de un grafo.
template<class GT, class Distance, class Compare, class Plus>
void dijkstra_min_path (GT &g, typename GT::Node *start_node, typename GT::Node *end_node, Path< GT > &min_path)
 Calcula el camino mínimo desde un nodo origen start_node hasta un nodo destino end_node según el algoritmo de Dijkstra.
template<class GT, class Distance, class Compare, class Plus>
void dijkstra_min_spanning_tree (GT &g, typename GT::Node *start_node, GT &tree)
 Calcula un árbol abarcador de todos los caminos mínimos desde un nodo dado según el algoritmo de Dijkstra.
template<class GT>
void find_breadth_first_spanning_tree (GT &g, typename GT::Node *gnode, GT &tree)
 Calcula un árbol abarcador en amplitud de un grafo a partir de un nodo.
template<class GT>
GT::Node * find_depth_first_spanning_tree (GT &g, GT &tree)
 Calcula un árbol abarcador en profundidad de un grafo.
template<class GT>
bool find_depth_first_spanning_tree (GT &g, typename GT::Node *gnode, GT &tree)
 Calcula un árbol abarcador en profundidad de un grafo a partir de un nodo.
template<class GT>
bool find_path_breadth_first (GT &g, typename GT::Node *start, typename GT::Node *end, Path< GT > &path)
 Busca en amplitud un camino entre start_node y end_node; construye el camino visto si se encuentra el camino.
template<class GT>
bool find_path_depth_first (GT &g, typename GT::Node *start_node, typename GT::Node *end_node, Path< GT > &path)
 Busca en profundidad un camino entre start_node y end_node; construye el camino visto si se encuentra el camino.
template<class GT, class Distance, class Compare, class Plus>
void floyd_all_shortest_paths (GT &g, Ady_Mat< GT, typename Distance::Distance_Type > &dist, Ady_Mat< GT, long > &path)
 Calcula las matriz de costes de los caminos mínimos entre todos pares de nodos de un grafo g y la matriz de caminos mínimos según el algoritmo de Floy-Warshall.
template<typename GT, class Write_Node, class Write_Arc, class Shade_Node, class Shade_Arc>
void generate_cross_graph (GT &g, const size_t &nodes_by_level, const double &xdist, const double &ydist, std::ofstream &output)
 Genera una especificación para el programa de dibujado de grafos graphpic de tipo grafo cruzado.
template<typename GT, class Write_Node, class Write_Arc, class Shade_Node, class Shade_Arc>
void generate_net_graph (GT &g, const size_t &nodes_by_level, const double &xdist, const double &ydist, std::ofstream &output)
 Genera una especificación para el programa de dibujado de grafos graphpic de tipo red.
template<typename GT, typename Key, class Convert>
static Tree_Node< Key > * graph_to_tree_node (GT &g, typename GT::Node *groot)
 Convierte un árbol representado en una representación de grafo a un árbol Tree_Node.
template<typename GT>
bool has_cycle (GT &g)
 Retorna true si el grafo no es acíclico (contiene al menos un ciclo).
template<class GT>
void inconnected_components (GT &g, DynDlist< GT > &list)
 Calcula los componentes inconexos de un grafo.
template<class GT>
void invert_digraph (GT &sg, GT &rg)
 Calcula el digrafo inverso y lo mapea.
template<typename GT>
bool is_acyclique (GT &g)
 Retorna true si el grafo es acíclico (no contiene ciclos).
template<typename GT>
bool is_acyclique (GT &g, typename GT::Node *start_node)
 Retorna true si el grafo es acíclico (no contiene ciclos).
template<class GT>
bool is_reachable (GT &g, typename GT::Node *src, typename GT::Node *tgt)
 Retorna true si existe el nodo tgt es alcanzable desde src.
template<class GT, class Distance, class Compare>
void kruskal_min_spanning_tree (GT &g, GT &tree)
 Calcula el árbol abarcador mínimo de un grafo según el algoritmo de Kruskal.
template<typename GT>
void map_cut_graph (GT &g, DynDlist< typename GT::Node * > &cut_node_list, GT &cut_graph, DynDlist< typename GT::Arc * > &cross_arc_list)
 Efectúa una copia mapeada del grafo de corte de un grafo.
template<typename GT>
void map_subgraph (GT &g, GT &sg, const long &color)
 Copia mapeada de un subgrafo según un color.
template<typename GT>
long paint_subgraphs (GT &g, const DynDlist< typename GT::Node * > &cut_node_list)
 Pinta un grafo conexo según sus nodos de corte.
template<class GT, class Distance, class Compare>
void prim_min_spanning_tree (GT &g, GT &tree)
 Calcula el árbol abarcador mínimo de un grafo según el algoritmo de Prim.
template<class GT, class Distance, class Compare, class Plus>
bool q_bellman_ford_min_spanning_tree (GT &g, typename GT::Node *start_node, GT &tree)
 Calcula un árbol abarcador de todos los caminos mínimos desde un nodo dado según el algoritmo de Bellman-Ford con uso de un heap exclusivo.
template<class GT>
void q_topological_sort (GT &g, DynDlist< typename GT::Node * > &list)
 Calcula un ordenamiento topológico para el digrafo g y lo guarda en la lista list.
template<class GT>
void strongly_connected_components (GT &g, DynDlist< GT > &list)
 Calcula los componentes fuertemente conexos de un digrafo.
template<class GT>
bool test_connectivity (GT &g)
 Retorna true si el grafo g es conexo.
template<class GT>
bool test_cycle (GT &g, typename GT::Node *src_node)
 Retorna true si existe un ciclo desde el nodo src_node.
template<class GT>
bool test_path (GT &g, typename GT::Node *start_node, typename GT::Node *end_node)
 Retorna true si existe un camino entre el nodo start_node y end_node.
template<class GT>
void topological_sort (GT &g, DynDlist< typename GT::Node * > &list)
 Calcula un ordenamiento topológico para el digrafo g y lo guarda en la lista list.
template<class GT>
void warshall_compute_transitive_clausure (GT &g, Bit_Mat_Graph< GT > &mat)
 Cálculo de la clausura transitiva de una matriz de adyacencia.

Descripción detallada

Todo objeto de tipo grafo maneja dos objetos adicionales que son parte de la definición de un grafo:

Hay varios tipos de grafos (o digrafos) modelizadas por distintas clases:

La clases que manejan agentes tienen la capacidad de cambiar dinámicamente el grafo, lo que es conocido en los predios de modelización como "cambio estructural".

Hay tres fases en el manejo de un grafo:

  1. Definición de los tipos de nodos y arcos. En el caso de los grafos tradicionales, se modelizan los nodos y los arcos. Supongamos, por ejemplo, que se tiene un problema de transporte en el cual se deseen modelizar diversos medios de transporte. En este caso, los atributos de los nodos serían los nombres de ciudades, junto con otros atributos pertinentes. En el caso de los arcos, éstos contendría parámetros comunes tales como la duración, distancia y coste. Para modelizar comunicaciones de diversos tipos, automóvil, fluvial, marítima, férrea y aérea, se puede lograr por derivación de la clase __Graph_Arc<Arc_Info>.

  1. Construcción del grafo: esta es la fase en la cual se define la forma del grafo mediante las operaciones fundamentales sobre nodos y arcos.

  1. Ejecución de solución de un problema: una vez definido y construido el grafo, entonces se procede a la resolución del problema específico.

Documentación de las definiciones

#define IS_ARC_VISITED ( p,
bit   )     (ARC_BITS(p).get_bit(bit))

Parámetros:
p puntero al arco
bit número de bit a leer
Devuelve:
true si el bit es 1; false si es 0

Definición en la línea 169 del archivo tpl_graph.H.

Referenciado por Aleph::breadth_first_traversal(), Aleph::build_subgraph(), Aleph::compute_cut_nodes(), Aleph::dijkstra_min_path(), Aleph::dijkstra_min_spanning_tree(), Aleph::find_breadth_first_spanning_tree(), Aleph::find_depth_first_spanning_tree(), Aleph::find_path_breadth_first(), Aleph::prim_min_spanning_tree(), y Aleph::test_cycle().

#define IS_NODE_VISITED ( p,
bit   )     (NODE_BITS(p).get_bit(bit))

Parámetros:
p puntero al nodo
bit número de bit a leer
Devuelve:
true si el bit es 1; false si es 0

Definición en la línea 146 del archivo tpl_graph.H.

Referenciado por Aleph::bellman_ford_min_spanning_tree(), Aleph::breadth_first_traversal(), Aleph::build_subgraph(), Aleph::compute_cut_nodes(), Aleph::dijkstra_min_path(), Aleph::dijkstra_min_spanning_tree(), Aleph::find_breadth_first_spanning_tree(), Aleph::find_depth_first_spanning_tree(), Aleph::find_path_breadth_first(), Aleph::find_path_depth_first(), Aleph::inconnected_components(), Aleph::is_acyclique(), Aleph::kruskal_min_spanning_tree(), Aleph::prim_min_spanning_tree(), Aleph::q_bellman_ford_min_spanning_tree(), y Aleph::topological_sort().

Documentación de las funciones

bool bellman_ford_min_spanning_tree ( GT &  g,
typename GT::Node *  start_node,
GT &  tree 
) [inline]

Este procedimiento utiliza el algoritmo de Bellman-Ford para calcular un árbol abarcador de todos los caminos mínimos desde un nodo start_node del grafo g y almacenarlo en el grafo tree.

El árbol abarcador tree de todos los caminos mínimos desde start_node está completamente mapeado con g. Por tanto, una búsqueda de camino en profundidad, mediante find_path_depth_first() sobre tree, encontrará y construirá cualquier camino mínimo desde start_node hasta un nodo cualquiera.

Aunque el algoritmo de Bellman-Ford exhibe peor desempeño que el de Dijkstra, el primero maneja pesos negativos y detecta la presencia de ciclos negativos. Es por tanto el algoritmo recomendado para la mayoría de aplicaciones de caminos s que manejen pesos negativos.

El procedimiento es parametrizado con las siguientes especificaciones:

  1. GT: el tipo de grafo basado en List_Graph.
  2. Distance<GT>: La clase de lectura del peso del arco que debe exportar los siguientes atributos:
    1. typedef Distance<GT>::Distance_Type: el tipo de dato que representa un peso en un arco.
    2. Distance<GT>::Distance_Type operator()(typename GT::Arc *a): que retorna el valor del peso en el arco a.
    3. Distance<GT>::Max_Distance: constante estática correspondiente al valor de distancia máximo que un algoritmo consideraría como valor infinito.
    4. typename Distance<GT>::Zero_Distance: constante estática correspondiente al elemento neutro de la suma. Tradicionalmente, en la inmensa mayoría de casos, este será el cero.
  3. Compare<GT>: clase que realiza la comparación entre dos pesos y cuyo prototipo es:
    • bool operator()(const typename Distance<GT>::Distance_Type & op1, const typename Distance<GT>::Distance_Type & op2) const
  4. Plus<GT>: clase que realiza la suma de distancias con el siguiente prototipo:
    • typename Distance<GT>::Distance_Type operator()(const typename Distance<GT>::Distance_Type & op1, const typename Distance<GT>::Distance_Type & op2) const
    Hay una especialización de bellman_ford_min_spanning_tree<GT,Compare>() con parámetros tipo por omisión de comparación la relación "menor que" y la suma.

Parámetros:
[in] g el grafo al cual se desea calcular el árbol abarcador mínimo.
[in] start_node nodo inicio de los caminos mínimos.
[out] tree el grafo donde se desea guardar el árbol abarcador resultado de todos los caminos mínimos que parten desde el nodo start_node. Este grafo es limpiado antes del comienzo del algoritmo.
Excepciones:
bad_alloc si no hay suficiente memoria para construir tree; bien sea porque falla tree o por la cola interna. En este caso el valor de tree es indeterminado y no está limpio.
Ver también:
dijkstra_min_path() find_path_depth_first() floyd_all_shortest_paths() find_min_path() dijkstra_min_spanning_tree() q_bellman_ford_min_spanning_tree()

Definición en la línea 134 del archivo Bellman_Ford.H.

Hace referencia a ARC_BITS, IS_NODE_VISITED, NODE_BITS, y NODE_COOKIE.

size_t Aleph::breadth_first_traversal ( GT &  g,
bool(*)(GT &, typename GT::Node *, typename GT::Arc *)  visit 
) [inline]

Esta función recorre en amplitud el grafo g a partir de un nodo cualquiera.

El nodo de inicio es indeterminado y no se deben hacer suposiciones sobre cuál será este nodo.

Por cada nodo visitado, se invoca a una función cuyo prototipo debe ser:

bool visitar(GT & g, typename GT::Node * p, typename GT::Arc * a)

Cuyos parámetros se describen a continuación:

  1. g: el grafo.
  2. p: el nodo actual que se está visitando en amplitud.
  3. a: el arco que conduce al nodo actual p.

Si la función retorna true, entonces el recorrido se detiene; es decir, no se prosigue el recorrido sobre el grafo. Si la función retorna false, entonces el recorrido en amplitud prosigue y se detendría una vez que todos los arcos del grafo hayan sido vistos.

El recorrido utiliza el bit breadth_first. Este bit es iniciado al principio del algoritmo.

Parámetros:
[in] g el grafo a explorar.
[in] visit la función de visita.
Devuelve:
el número de nodos que fueron visitados
Excepciones:
bad_alloc si no hay memoria para la cola interna que utiliza el algoritmo
Ver también:
breadth_first_traversal() test_connectivity()

Definición en la línea 325 del archivo tpl_graph_utils.H.

size_t Aleph::breadth_first_traversal ( GT &  g,
typename GT::Node *  start,
bool(*)(GT &, typename GT::Node *, typename GT::Arc *)  visit 
) [inline]

Esta función recorre en amplitud el grafo g a partir del nodo start_node. Por cada nodo visitado, se invoca a una función cuyo prototipo debe ser:

bool visitar(GT & g, typename GT::Node * p, typename GT::Arc * a)

Cuyos parámetros se describen a continuación:

  1. g: el grafo.
  2. p: el nodo actual que se está visitando en amplitud.
  3. a: el arco que conduce al nodo actual p.

Si la función retorna true, entonces el recorrido se detiene; es decir, no se prosigue el recorrido sobre el grafo. Si la función retorna false, entonces el recorrido en amplitud prosigue y se detendría una vez que todos los arcos del grafo hayan sido vistos.

El recorrido utiliza el bit breadth_first, el cual es iniciado al principio del algoritmo.

Parámetros:
[in] g el grafo a explorar.
[in] start el nodo por donde se inicia el recorrido.
[in] visit la función de visita.
Devuelve:
el número de nodos que fueron visitados
Excepciones:
bad_alloc si no hay memoria para la cola interna que utiliza el algoritmo
Ver también:
depth_first_traversal() test_connectivity()

Definición en la línea 221 del archivo tpl_graph_utils.H.

Hace referencia a ARC_BITS, DynListQueue::get(), IS_ARC_VISITED, ListQueue::is_empty(), IS_NODE_VISITED, NODE_BITS, y DynListQueue::put().

void build_subgraph ( GT &  g,
GT &  sg,
typename GT::Node *  g_src,
size_t &  node_count 
) [inline]

El método build_subgraph() recorre en profundidad el grafo g a partir del nodo origen g_src y construye en el sg una copia mapeada de todos el grafo (o subgrafo si g es inconexo) visto en el recorrido.

El parámetro node_count es un contador que se incrementa a la cantidad de nodos que fueron visitados y mapeados.

El método se sirve del bit build_subtree para marcar los nodos y arcos ya visitados.

build_subgraph() es utilizado por el método inconnected_components() para mapear los diversos bloques.

Parámetros:
[in] g el grafo a mapear
[out] sg un grafo vacío donde colocar la copia mapeada a partir de g_src.
[in] g_src el nodo origen desde donde se origina el recorrido y mapeo.
[in,out] node_count la cantidad actual de nodos visitados antes de la llamada; este valor se incrementa a la cantidad total de nodos que logró visitar build_subgraph().
Excepciones:
bad_alloc si no hay memoria para construir sg.
domain_error si sg no es un grafo vacío.
Ver también:
inconnected_components() List_Graph::copy_graph()

Definición en la línea 912 del archivo tpl_graph_utils.H.

Hace referencia a ARC_BITS, IS_ARC_VISITED, IS_NODE_VISITED, NODE_BITS, y NODE_COOKIE.

Referenciado por Aleph::inconnected_components().

void Aleph::compute_cut_nodes ( GT &  g,
DynDlist< typename GT::Node * > &  list 
) [inline]

compute_cut_nodes() toma un grafo conexo g, efectúa un recorrido en profundidad en búsqueda de sus nodos de corte y añade a una lista dinámica list cada nodo de corte que contenga el grafo.

Un nodo de corte se define como un nodo tal que al suprimirlo (juntos con sus arcos) el grafo deviene inconexo.

El algoritmo utiliza el bit depth_first para marcar los nodos y arcos que han sido visitados.

El resultado de esta función puede combinarse con paint_subgraphs() para pintar los diversos bloques que separarían los puntos de corte. A su vez, mapeo de los bloques y de los nodos y arcos de corte del grafo pueden obtenerse mediante llamadas a map_subgraph() y map_cut_graph() sobre un grafo previamente pintado.

Luego de la operación, cada nodo de corte del grafo queda marcado con el bit cut. Si se requieren cálculos posteriores sobre los nodos de corte, entonces es extremadamente importante no modificar este bit, pues, para evitar uso de tablas los algoritmos de esta biblioteca distinguen los nodos de corte mediante el valor de este bit. En general, los resultados son impredecibles si se realizan modificaciones de cualquier atributo de nodo o arco (bits, contador o cookie).

Se asume que g es conexo y no se realiza ninguna verificación al respecto.

Parámetros:
[in] g el grafo a calcular los puntos de corte.
[out] list lista dinámica donde se guardan punteros a nodos de corte del grafo.
Excepciones:
bad_alloc si no hay memoria para insertar en la lista dinámica o si no hay memoria para los datos de cálculo interno del algoritmo.
Ver también:
paint_subgraphs() map_subgraph() map_cut_graph()

Definición en la línea 1445 del archivo tpl_graph_utils.H.

void Aleph::compute_cut_nodes ( GT &  g,
typename GT::Node *  start,
DynDlist< typename GT::Node * > &  list 
) [inline]

compute_cut_nodes() toma un grafo conexo g, efectúa un recorrido en profundidad a partir de un nodo start y añade a una lista dinámica list cada nodo de corte que contenga el grafo.

Un nodo de corte se define como un nodo tal que al suprimirlo (juntos con sus arcos) el grafo deviene inconexo.

El algoritmo utiliza el bit depth_first para marcar los nodos y arcos que han sido visitados.

El resultado de esta función puede combinarse con paint_subgraphs() para pintar los diversos bloques que separarían los puntos de corte. A su vez, mapeo de los bloques y de los nodos y arcos de corte del grafo pueden obtenerse mediante llamadas a map_subgraph() y map_cut_graph() sobre un grafo previamente pintado.

Se asume que g es conexo y no se realiza ninguna verificación al respecto.

Parámetros:
[in] g el grafo a calcular los puntos de corte.
[in] start el nodo origen por donde iniciar el recorrido en profundidad.
[out] list lista dinámica donde se guardan punteros a nodos de corte del grafo.
Excepciones:
bad_alloc si no hay memoria para insertar en la lista dinámica o si no hay memoria para los datos de cálculo interno del algoritmo.
Ver también:
paint_subgraphs() map_subgraph() map_cut_graph()

Definición en la línea 1312 del archivo tpl_graph_utils.H.

Hace referencia a DynDlist::append(), ARC_BITS, IS_ARC_VISITED, IS_NODE_VISITED, y NODE_BITS.

size_t Aleph::depth_first_traversal ( GT &  g,
bool(*)(GT &, typename GT::Node *, typename GT::Arc *)  visit 
) [inline]

Esta función recorre en profundidad el grafo g a partir de un nodo cualquiera.

El nodo de inicio es indeterminado y no se deben hacer suposiciones sobre cuál será este nodo.

Por cada nodo visitado, se invoca a una función cuyo prototipo debe ser:

bool visitar(GT & g, typename GT::Node * p, typename GT::Arc * a)

Cuyos parámetros se describen a continuación:

  1. g: el grafo.
  2. p: el nodo actual que se está visitando en profundidad.
  3. a: el arco que conduce al nodo actual p.

Si la función retorna true, entonces el recorrido se detiene; es decir, no se prosigue el recorrido sobre el grafo. Si la función retorna false, entonces el recorrido en profundidad prosigue y se detendría una vez que todos los arcos del grafo hayan sido vistos.

El recorrido utiliza el bit Bit_Fields::depth_first. Este bit es iniciado al principio del algoritmo.

Parámetros:
[in] g el grafo a explorar.
[in] visit la función de visita.
Devuelve:
el número de nodos que fueron visitados
Ver también:
breadth_first_traversal() test_connectivity()

Definición en la línea 143 del archivo tpl_graph_utils.H.

size_t Aleph::depth_first_traversal ( GT &  g,
typename GT::Node *  start_node,
bool(*)(GT &g, typename GT::Node *, typename GT::Arc *)  visit 
) [inline]

Esta función recorre en profundidad el grafo g a partir del nodo start_node. Por cada nodo visitado, se invoca a una función cuyo prototipo debe ser:

bool visitar(GT & g, typename GT::Node * p, typename GT::Arc * a)

Cuyos parámetros se describen a continuación:

  1. g: el grafo.
  2. p: el nodo actual que se está visitando en profundidad.
  3. a: el arco que conduce al nodo actual p.

Si la función retorna true, entonces el recorrido se detiene; es decir, no se prosigue el recorrido sobre el grafo. Si la función retorna false, entonces el recorrido en profundidad prosigue y se detendría una vez que todos los arcos del grafo hayan sido vistos.

El recorrido utiliza el bit depth_first, el cual es iniciado al principio del algoritmo.

Parámetros:
[in] g el grafo a explorar.
[in] start_node el nodo por donde se inicia el recorrido.
[in] visit la función de visita.
Devuelve:
el número de nodos que fueron visitados
Ver también:
breadth_first_traversal() test_connectivity()

Definición en la línea 94 del archivo tpl_graph_utils.H.

void dijkstra_min_path ( GT &  g,
typename GT::Node *  start_node,
typename GT::Node *  end_node,
Path< GT > &  min_path 
) [inline]

Este procedimiento utiliza el algoritmo de Dijkstra para calcular el camino mínimo desde el nodo origen start_node hasta el nodo destino end_node según el algoritmo de Dijkstra.

El camino mínimo es almacenado en el parámetro de salida min_path.

Esencialmente, el algoritmo es el mismo que el descrito en dijkstra_min_spanning_tree(), con la excepción de que el cálculo se termina cuando se encuentra el nodo destino end_node. El tiempo esperado de ejecución y el consumo de memoria son la mitad del empleado por dijkstra_min_spanning_tree().

La descripción de los parámetros tipos es la misma que en dijkstra_min_spanning_tree().

La especialización de dijkstra_min_path<GT,Compare>() con parámetros tipo por omisión de comparación la relación "menor que" y la suma.

Parámetros:
[in] g el grafo al cual se desea calcular el árbol abarcador mínimo.
[in] start_node nodo inicio del camino mínimo a buscar.
[in] end_node nodo destino del camino mínimo a buscar.
[out] min_path donde se desea guardar el camino mínimo que parte desde start_node hasta end_node. Este camino es limpiado antes del comienzo del algoritmo.
Excepciones:
bad_alloc si no hay suficiente memoria para construir tree; bien sea porque falla tree, por la cola interna o por el camino. En este caso el valor de path es indeterminado y no está limpio.
Ver también:
dijkstra_min_spanning_tree() floyd_all_shortest_paths() find_min_path() bellman_ford_min_spanning_tree() q_bellman_ford_min_spanning_tree()

Definición en la línea 372 del archivo Dijkstra.H.

Hace referencia a Path::append(), ARC_BITS, Path::clear_path(), Aleph::find_path_depth_first(), Path::init(), IS_ARC_VISITED, IS_NODE_VISITED, NODE_BITS, y NODE_COOKIE.

void dijkstra_min_spanning_tree ( GT &  g,
typename GT::Node *  start_node,
GT &  tree 
) [inline]

Este procedimiento utiliza el algoritmo de Dijkstra para calcular un árbol abarcador de todos los caminos mínimos desde un nodo start_node del grafo g y almacenarlo en el grafo tree.

El árbol abarcador tree de todos los caminos mínimos desde start_node está completamente mapeado con g. Por tanto, una búsqueda de camino en profundidad, mediante find_path_depth_first(), sobre tree encontrará y construirá cualquier camino mínimo desde start_node hasta un nodo cualquiera.

El algoritmo utiliza una cola interna cuya longitud máxima es proporcional número de nodos del grafo.

El algoritmo de Dijkstra es el que exhibe mejor desempeño y es por tanto el recomendado para la mayoría de aplicaciones de caminos mínimos.

El algoritmo de Dijkstra no opera para grafos con pesos negativos.

El procedimiento es parametrizado con las siguientes especificaciones:

  1. GT: el tipo de grafo basado en List_Graph.
  2. Distance<GT>: La clase de lectura del peso del arco que debe exportar los siguientes atributos:
    1. typedef Distance<GT>::Distance_Type: el tipo de dato que representa un peso en un arco.
    2. Distance<GT>::Distance_Type operator()(typename GT::Arc *a): que retorna el valor del peso en el arco a.
    3. Distance<GT>::Max_Distance: constante estática correspondiente al valor de distancia máximo que un algoritmo consideraría como valor infinito.
    4. typename Distance<GT>::Zero_Distance: constante estática correspondiente al elemento neutro de la suma. Tradicionalmente, en la inmensa mayoría de casos, este será el cero.
  3. Compare<GT>: clase que realiza la comparación entre dos pesos y cuyo prototipo es:
    • bool operator()(const typename Distance<GT>::Distance_Type & op1, const typename Distance<GT>::Distance_Type & op2) const
  4. Plus<GT>: clase que realiza la suma de distancias con el siguiente prototipo:
    • typename Distance<GT>::Distance_Type operator()(const typename Distance<GT>::Distance_Type & op1, const typename Distance<GT>::Distance_Type & op2) const
    Hay una especialización de dijkstra_min_spanning_tree<GT,Compare>() con parámetros tipo por omisión de comparación la relación "menor que" y la suma.

Parámetros:
[in] g el grafo al cual se desea calcular el árbol abarcador mínimo.
[in] start_node nodo inicio de los caminos mínimos.
[out] tree el grafo donde se desea guardar el árbol abarcador resultado de todos los caminos mínimos que parten desde el nodo start_node. Este grafo es limpiado antes del comienzo del algoritmo.
Excepciones:
bad_alloc si no hay suficiente memoria para construir tree; bien sea porque falla tree o por la cola interna. En este caso el valor de tree es indeterminado y no está limpio.
Ver también:
dijkstra_min_path() find_path_depth_first() floyd_all_shortest_paths() find_min_path() bellman_ford_min_spanning_tree() q_bellman_ford_min_spanning_tree()

Definición en la línea 236 del archivo Dijkstra.H.

Hace referencia a ARC_BITS, IS_ARC_VISITED, IS_NODE_VISITED, NODE_BITS, y NODE_COOKIE.

void Aleph::find_breadth_first_spanning_tree ( GT &  g,
typename GT::Node *  gnode,
GT &  tree 
) [inline]

Esta función toma un grafo g, efectúa un recorrido en amplitud a partir del nodo gnode y construye el árbol abarcador según el orden de visita dado por el recorrido.

Luego de la operación el parámetro tree contiene el árbol abarcador en cuestión con sus arcos y nodos mapeados al grafo g.

Durante la ejecución, el algoritmo marca los nodos y arcos visitados con el bit el spanning_tree.

El orden de visita del grafo no necesariamente es el mismo que el de la primitiva breadth_first_traversal().

Parámetros:
[in] g el grafo sobre el cual se desea construir el árbol abarcador en amplitud.
[in] gnode puntero al nodo origen de la búsqueda en amplitud.
[out] tree grafo donde se colocará el árbol abarcador de amplitud.
Excepciones:
bad_alloc si no hay memoria para construir el árbol abarcador o para la cola interna que se utiliza para el recorrido en amplitud.
Ver también:
find_depth_first_spanning_tree() Tree_Node

graph_to_tree_node()

Definición en la línea 1176 del archivo tpl_graph_utils.H.

Hace referencia a ARC_BITS, IS_ARC_VISITED, IS_NODE_VISITED, NODE_BITS, y NODE_COOKIE.

GT::Node* Aleph::find_depth_first_spanning_tree ( GT &  g,
GT &  tree 
) [inline]

Esta función toma un grafo g, efectúa un recorrido en profundidad a partir del nodo seleccionado por la función y construye el árbol abarcador según el orden de visita dado por el recorrido.

Luego de la operación el parámetro tree contiene el árbol abarcador en cuestión con sus arcos y nodos mapeados al grafo g.

Durante la ejecución, el algoritmo marca los nodos y arcos visitados con el bit el spanning_tree.

El orden de visita del grafo no necesariamente es el mismo que el de la primitiva depth_first_traversal().

Parámetros:
[in] g el grafo sobre el cual se desea construir el árbol abarcador en profundidad.
[out] tree grafo donde se colocará el árbol abarcador de profundidad.
Excepciones:
bad_alloc si no hay memoria para construir el árbol abarcador.
Ver también:
find_breadth_first_spanning_tree() Tree_Node

graph_to_tree_node()

Definición en la línea 1092 del archivo tpl_graph_utils.H.

bool Aleph::find_depth_first_spanning_tree ( GT &  g,
typename GT::Node *  gnode,
GT &  tree 
) [inline]

Esta función toma un grafo g, efectúa un recorrido en profundidad a partir del nodo gnode y construye el árbol abarcador según el orden de visita dado por el recorrido.

Luego de la operación el parámetro tree contiene el árbol abarcador en cuestión con sus arcos y nodos mapeados al grafo g.

Durante la ejecución, el algoritmo marca los nodos y arcos visitados con el bit el spanning_tree.

El orden de visita del grafo no necesariamente es el mismo que el de la primitiva depth_first_traversal().

Parámetros:
[in] g el grafo sobre el cual se desea construir el árbol abarcador en profundidad.
[in] gnode puntero al nodo origen de la búsqueda en profundidad.
[out] tree grafo donde se colocará el árbol abarcador de profundidad.
Excepciones:
bad_alloc si no hay memoria para construir el árbol abarcador.
Ver también:
find_breadth_first_spanning_tree() Tree_Node

graph_to_tree_node()

Definición en la línea 1033 del archivo tpl_graph_utils.H.

Hace referencia a IS_ARC_VISITED, IS_NODE_VISITED, y NODE_BITS.

bool Aleph::find_path_breadth_first ( GT &  g,
typename GT::Node *  start,
typename GT::Node *  end,
Path< GT > &  path 
) [inline]

find_path_breadth_first() busca en amplitud un camino entre start_node y end_node, a la vez que va construyendo un camino hacia el nodo destino. Si el se encuentra un camino, entonces el método retorna true y el parámetro path alberga el camino en cuestión; de lo contrario, la función retorna false y valor del camino es indeterminado.

Parámetros:
[in] g el grafo sobre el cual se desea buscar el camino.
[in] start puntero al nodo inicio del camino.
[in] end puntero al nodo destino del camino.
[out] path el camino visto durante la búsqueda en amplitud; sólo tiene sentido si el valor de retorno es true.
Excepciones:
bad_alloc si no hay memoria para continuar construyendo el camino o para la cola interna del recorrido en amplitud.
Ver también:
find_path_depth_first()

dijkstra_min_spanning_tree() dijkstra_min_path()

bellman_ford_min_spanning_tree() q_bellman_ford_min_spanning_tree()

Definición en la línea 377 del archivo tpl_graph_utils.H.

Hace referencia a ARC_BITS, Path::clear_path(), DynListQueue::get(), Path::get_last_arc(), Path::get_last_node(), Path::inside_graph(), IS_ARC_VISITED, ListQueue::is_empty(), IS_NODE_VISITED, NODE_BITS, y Path::swap().

bool find_path_depth_first ( GT &  g,
typename GT::Node *  start_node,
typename GT::Node *  end_node,
Path< GT > &  path 
) [inline]

find_path_depth_first() busca en profundidad un camino entre start_node y end_node, a la vez que va construyendo un camino equivalente a la profundidad recursiva de la búsqueda. Si el se encuentra un camino, entonces el método retorna true y el parámetro path alberga el camino en cuestión; de lo contrario, la función retorna false y valor del camino es indeterminado.

Parámetros:
[in] g el grafo sobre el cual se desea buscar el camino.
[in] start_node puntero al nodo inicio del camino.
[in] end_node puntero al nodo destino del camino.
[out] path el camino visto durante la búsqueda en profundidad; sólo tiene sentido si el valor de retorno es true.
Excepciones:
bad_alloc si no hay memoria para continuar construyendo el camino
Ver también:
find_path_breadth_first()

dijkstra_min_spanning_tree() dijkstra_min_path()

bellman_ford_min_spanning_tree() q_bellman_ford_min_spanning_tree()

Definición en la línea 1074 del archivo tpl_graph.H.

Hace referencia a ARC_BITS, Path::clear_path(), Path::init(), Path::inside_graph(), IS_NODE_VISITED, y NODE_BITS.

Referenciado por Aleph::dijkstra_min_path().

void floyd_all_shortest_paths ( GT &  g,
Ady_Mat< GT, typename Distance::Distance_Type > &  dist,
Ady_Mat< GT, long > &  path 
) [inline]

Este procedimiento utiliza el algoritmo de Floy-Warshall para calcular dos matrices de tipo Ady_Mat que se especifican del siguiente modo:

  1. dist: matriz de costes mínimos entre todos los pares de nodos. Cada entrada dist(i,j) almacena el coste total mínimo para ir del nodo con índice i hacia el nodo con índice j.
    Recuérdese que un índice de nodo en la matriz dist puede calcularse mediante dist(node), donde node es un puntero a nodo en una representación con listas enlzadas derivada del tipo List_Graph.

  1. path: matriz de caminos mínimos. Cada entrada path(i,j) almacena el nodo k que permitió al algoritmo de Floyd-Warshall encontrar el mínimo valor de dist(i,j). De este modo, inspecciones sucesivas a dist(k,j) permiten encontrar y construir el camino hacia el nodo j.
    La función find_min_path(g,i,j,path) realiza la función anterior.

El algoritmo de Floyd-Warshall maneja pesos negativos, pero no opera correctamente si el grafo contiene ciclos negativos. Úsese el algoritmo de Bellman-Ford q_bellman_ford_min_spanning_tree() si se sospecha su presencia.

El algoritmo utiliza dos matrices internas adicionales.

El procedimiento es parametrizado con las siguientes especificaciones:

  1. GT: el tipo de grafo basado en List_Graph.
  2. Distance<GT>: La clase de lectura del peso del arco que debe exportar los siguientes atributos:
    1. typedef Distance<GT>::Distance_Type: el tipo de dato que representa un peso en un arco.
    2. Distance<GT>::Distance_Type operator()(typename GT::Arc *a): que retorna el valor del peso en el arco a.
    3. Distance<GT>::Max_Distance: constante estática correspondiente al valor de distancia máximo que un algoritmo consideraría como valor infinito.
    4. typename Distance<GT>::Zero_Distance: constante estática correspondiente al elemento neutro de la suma. Tradicionalmente, en la inmensa mayoría de casos, este será el cero.
  3. Compare<GT>: clase que realiza la comparación entre dos pesos y cuyo prototipo es:
    • bool operator()(const typename Distance<GT>::Distance_Type & op1, const typename Distance<GT>::Distance_Type & op2) const
  4. Plus<GT>: clase que realiza la suma de distancias con el siguiente prototipo:
    • typename Distance<GT>::Distance_Type operator()(const typename Distance<GT>::Distance_Type & op1, const typename Distance<GT>::Distance_Type & op2) const
    Hay una especialización de floyd_all_shortest_paths<GT,Compare>() con parámetros tipo por omisión de comparación la relación "menor que" y la suma.

Parámetros:
[in] g el grafo al cual se desea calcular el árbol abarcador mínimo.
[in] dist matriz donde se almacenan los costes mínimos.
[out] path matriz de índices de caminos mínimos que permite su recuperación.
Excepciones:
bad_alloc si no hay suficiente memoria para construir las matrices internas
Ver también:
dijkstra_min_spanning_tree() dijkstra_min_path() find_path_depth_first() find_min_path() bellman_ford_min_spanning_tree() q_bellman_ford_min_spanning_tree()

Definición en la línea 60 del archivo Floyd.H.

void generate_cross_graph ( GT &  g,
const size_t &  nodes_by_level,
const double &  xdist,
const double &  ydist,
std::ofstream &  output 
) [inline]

En un dibujo de grafo cruzado, se distribuyen nodes_by_level - 1 nodos los niveles pares y num_nodes_by_level en los impares.

generate_cross_graph(g,nodes_by_level,xdist,ydist,output) genera una entrada a graphpic de un grafo cruzado de nodes_by_level, separados horizontalmente por xdist y verticalmente por ydist. La salida se emite al archivo asociado a output.

Para tratar con los contenidos de los nodos y arcos y lo que se desee generar, se emplean los siguientes parámetros tipo:

  1. GT: el tipo de grafo o digrafo.
  2. Write_Node: convierte el contenido de un nodo a un string correspondiente al texto que se desea emitir.
  3. Write_Arc: convierte el contenido de un arco a un string correspondiente al texto que se desea emitir.
  4. Shade_Node: comando a emitir para un nodo oscuro. Si no se desea oscurecer, entonces se debe generar la cadena vacía; de lo contrario, generar el comando graphpic (por lo general Shadow-Node.
  5. Shade_Arc: comando a emitir para un arco oscuro. Si no se desea oscurecer, entonces se debe generar la cadena vacía; de lo contrario, generar el comando graphpic (por lo general Shadow-Arc.

Parámetros:
[in] g grafo o digrafo del que se desea generar el dibujo.
[in] nodes_by_level cantidad de nodos por nivel. El número de nodos del último nivel dependerá de la cantidad de nodos que contenga el grafo.
[in] xdist separación horizontal entre los nodos.
[in] ydist separación vertical entre los nodos.
[out] output archivo hacia donde se emitirá la salida.

Definición en la línea 170 del archivo generate_graph.H.

void generate_net_graph ( GT &  g,
const size_t &  nodes_by_level,
const double &  xdist,
const double &  ydist,
std::ofstream &  output 
) [inline]

En un dibujo de red, siempre se distribuyen nodes_by_level nodos por nivel.

generate_net_graph(g,nodes_by_level,xdist,ydist,output) genera una entrada a graphpic de un grafo red de nodes_by_level, separados horizontalmente por xdist y verticalmente por ydist. La salida se emite al archivo asociado a output.

Para tratar con los contenidos de los nodos y arcos y lo que se desee generar, se emplean los siguientes parámetros tipo:

  1. GT: el tipo de grafo o digrafo.
  2. Write_Node: convierte el contenido de un nodo a un string correspondiente al texto que se desea emitir.
  3. Write_Arc: convierte el contenido de un arco a un string correspondiente al texto que se desea emitir.
  4. Shade_Node: comando a emitir para un nodo oscuro. Si no se desea oscurecer, entonces se debe generar la cadena vacía; de lo contrario, generar el comando graphpic (por lo general Shadow-Node.
  5. Shade_Arc: comando a emitir para un arco oscuro. Si no se desea oscurecer, entonces se debe generar la cadena vacía; de lo contrario, generar el comando graphpic (por lo general Shadow-Arc.

Parámetros:
[in] g grafo o digrafo del que se desea generar el dibujo.
[in] nodes_by_level cantidad de nodos por nivel. El número de nodos del último nivel dependerá de la cantidad de nodos que contenga el grafo.
[in] xdist separación horizontal entre los nodos.
[in] ydist separación vertical entre los nodos.
[out] output archivo hacia donde se emitirá la salida.

Definición en la línea 229 del archivo generate_graph.H.

Tree_Node< Key > * graph_to_tree_node ( GT &  g,
typename GT::Node *  groot 
) [inline, static]

graph_to_tree_node() toma un árbol representado mediante algún tipo de grafo representado con listas de adyacencia y un nodo groot que se asume raíz del árbol y lo convierte a un árbol representado con el tipo Tree_Node<Key>.

El interés de esta rutina es obtener una representación del árbol en la cual se puedan aplicar otras técnicas, clases y algoritmos. Un ejemplo representativo es el dibujado de árboles inherentes a los grafos; en la ocurrencia, árboles abarcadores.

El procedimiento utiliza el bit spanning_tree para marcar los nodos y arcos ya visitados.

Como medio de representación, el tipo Tree_Node<Key> es menos versátil que cualquier tipo basado en un grafo representado con listas de adyacencia; por ejemplo, List_graph. Note, por instancia, que List_Graph<Node,Arc> estipula un tipo para los arcos, mientras que no ocurre lo mismo para Tree_Node<Key>. En este sentido, como representación, Tree_Node<Key> no tiene ningún medio para guardar los datos asociados a los arcos. Consecuentemente, sólo se podría manejar los datos contenidos en los nodos. Por otra parte, el tipo guardado en GT::Node puede ser de índole distinta al guardado en Tree_Node<Key>.

A menudo (ese es el caso típico del dibujado), el tipo de dato a guardar en Tree_Node<Key> es de índole distinta al guardado en GT::Node. Otras veces, lo que se desea guardar en cada Tree_Node<Key> es un subconjunto de lo que está guardado en GT::Node. Puesto que es imposible generizar todos los casos posibles, la escritura de cada Tree_Node<Key> se delega a una clase cuyo operador ()() es invocado por la rutina de conversión para cada nodo del grafo. La clase en cuestión es el parámetro tipo Convert.

La clase Convert se invoca de la siguiente manera:

void Convert::operator () (gnode, tnode)

donde:

  1. gnode es de tipo GT::Node
  2. tnode de tipo Tree_Node<Key>

La rutina hace una prueba de aciclicidad sobre g mediante la función is_acyclique(), lo que no afecta la complejidad algorítmica de pero que toma tiempo adicional.

El procedimiento maneja los siguientes tipos parametrizados:

  1. GT: el tipo de grafo.
  2. Key: el tipo de dato que albergará el árbol en su representación Tree_Node<Key>.
  3. Convert: clase de conversión de GT::Node a Key, cuyo operador ()(gnode,tnode) es invocado por cada nodo de g cuando se realiza la conversión a uno Tree_Node.

Parámetros:
[in] g el árbol de tipo GT (derivado de List_Graph) que se desea convertir.
[in] groot el nodo de g que se considera raíz del árbol.
Devuelve:
la raíz de un árbol de tipo Tree_Node<Key> correspondiente a la conversión
Excepciones:
bad_alloc si no hay memoria para apartar el árbol de tipo Tree_Node<Key>
Ver también:
Tree_Node is_acyclique()

Definición en la línea 127 del archivo graph_to_tree.H.

Hace referencia a Aleph::is_acyclique().

bool Aleph::has_cycle ( GT &  g  )  [inline]

has_clique(g) explora en profundidad en grafo g y verifica si el grafo tiene al menos un ciclo.

La función es el negado de la is_acyclique().

Si g es un grafo (no un digrafo) entonces el algoritmo compara la cantidad de arcos con la de nodos. Si el grafo tiene menos arcos que nodos, entonces se concluye que el grafo es acíclico. Consecuentemente, esta técnica no opera para multigrafos.

Parámetros:
[in] g el grafo a probar. en profundidad.
Devuelve:
true si el grafo no contiene ningún ciclo; false de lo contrario.
Nota:
Debido a la prueba inicial con la cantidad de arcos, esta rutina es preferible que test_cycle(), aún bajo el conocimiento de que el grafo es conexo, pues esta última rutina siempre realiza la exploración en profundidad, mientras que is_acyclique() no.
Ver también:
test_cycle() is_acyclique()

Definición en la línea 735 del archivo tpl_graph_utils.H.

Hace referencia a Aleph::is_acyclique().

Referenciado por Aleph::kruskal_min_spanning_tree().

void inconnected_components ( GT &  g,
DynDlist< GT > &  list 
) [inline]

La función inconnected_components() toma un grafo g, "supuestamente inconexo" calcula sus subgrafos o componentes inconexos y los almacena en una lista dinámica list de subgrafos mapeados, tanto en los nodos como en los arcos. El énfasis en el supuesto carácter conexo del grafo se debe a que si el grafo no fuese conexo, entonces la lista resultante contendría un solo elemento correspondiente al grafo copia mapeado de g. Si este fuese el caso, entonces es preferible hacerlo con el método List_Graph::copy_graph().

La función se vale del bit build_subtree para marcar nodos y arcos visitados.

El algoritmo internamente descubre los componentes mediante búsquedas en profundidad.

Parámetros:
[in] g el grafo sobre el cual se desea calcular sus bloques.
[out] list lista de subgrafos mapeados a g con los subgrafos o componentes inconexos de g.
Excepciones:
bad_alloc si no hay memoria para construir algún bloque o insertar en la lista.
Ver también:
List_Graph::copy_graph()

Definición en la línea 854 del archivo tpl_graph_utils.H.

Hace referencia a DynDlist::append(), Aleph::build_subgraph(), DynDlist::get_last(), y IS_NODE_VISITED.

Referenciado por Aleph::strongly_connected_components().

void Aleph::invert_digraph ( GT &  sg,
GT &  rg 
) [inline]

invert_digraph(sg,rg) calcula el digrafo inverso del digrafo sg. El resultado es colocado en el digrafo rg, el cual es limpiado al inicio del algoritmo.

El digrafo inverso de sg es uno con los mismo nodos pero sus arcos dirigidos están invertidos.

Parámetros:
[in] sg el digrafo a invertir.
[in] rg el digrafo invertido de sg.
Excepciones:
bad_alloc si no hay memoria para crear a rg.
domain_error si sg o rg no son digrafos.

Definición en la línea 1955 del archivo tpl_graph.H.

Hace referencia a NODE_COOKIE.

bool Aleph::is_acyclique ( GT &  g  )  [inline]

is_acyclique(g) explora en profundidad en grafo g y verifica si el grafo es acíclico; es decir, que no contenga ningún ciclo.

La función usa el bit is_acyclique y lo reinicia al principio del algoritmo para marcar los nodos y arcos ya visitados.

Si g es un grafo (no un digrafo) entonces el algoritmo compara la cantidad de arcos con la de nodos. Si el grafo tiene menos arcos que nodos, entonces se concluye que el grafo es acíclico. Consecuentemente, esta técnica no opera para multigrafos.

Parámetros:
[in] g el grafo a probar. en profundidad.
Devuelve:
true si el grafo no contiene ningún ciclo; false de lo contrario.
Nota:
Debido a la prueba inicial con la cantidad de arcos, esta rutina es preferible que test_cycle(), aún bajo el conocimiento de que el grafo es conexo, pues esta última rutina siempre realiza la exploración en profundidad, mientras que is_acyclique() no.
Ver también:
test_cycle() has_cycle()

Definición en la línea 690 del archivo tpl_graph_utils.H.

Hace referencia a IS_NODE_VISITED.

Referenciado por Aleph::graph_to_tree_node(), y Aleph::has_cycle().

bool Aleph::is_acyclique ( GT &  g,
typename GT::Node *  start_node 
) [inline]

is_acyclique(g, start_node) explora en profundidad en grafo g, a partir del nodo start_node, y verifica si el grafo es acíclico; es decir, que no contenga ningún ciclo.

La función usa el bit is_acyclique y lo reinicia al principio del algoritmo para marcar los nodos y arcos ya visitados.

Si g es un grafo (no un digrafo) entonces el algoritmo compara la cantidad de arcos con la de nodos. Si el grafo tiene menos arcos que nodos, entonces se concluye que el grafo es acíclico. Consecuentemente, esta técnica no opera para multigrafos.

Parámetros:
[in] g el grafo a probar.
[in] start_node el nodo a partir del cual comenzar la búsqueda en profundidad.
Devuelve:
true si el grafo no contiene ningún ciclo; false de lo contrario.
Nota:
Debido a la prueba inicial con la cantidad de arcos, esta rutina es preferible que test_cycle(), aún bajo el conocimiento de que el grafo es conexo, pues esta última rutina siempre realiza la exploración en profundidad, mientras que is_acyclique() no.

Definición en la línea 656 del archivo tpl_graph_utils.H.

bool Aleph::is_reachable ( GT &  g,
typename GT::Node *  src,
typename GT::Node *  tgt 
) [inline]

is_reachable() explora en profundidad el grafo g a partir del nodo src en búsqueda de un camino que depare en tgt. Si durante la exploración se ve a tgt, entonces se concluye que existe un camino y se retorna true. Si se recorre enteramente a g sin ver a tgt, entonces la función retorna false.

El bit test_path es utilizado para marcar los nodos y arcos visitados durante la búsqueda. de hecho, esta rutina subyace sobre test_path().

Parámetros:
[in] g el grafo a buscar camino.
[in] src puntero al nodo origen del camino.
[in] tgt puntero a nodo destino del camino.
Devuelve:
true si existe un camino entre src y tgt.
Ver también:
find_path_depth_first() find_path_breadth_first() test_path()
Excepciones:
domain_error si g es un grafo (no un digrafo)

Definición en la línea 520 del archivo tpl_graph_utils.H.

Hace referencia a Aleph::test_path().

void kruskal_min_spanning_tree ( GT &  g,
GT &  tree 
) [inline]

Este procedimiento utiliza el algoritmo de Kruskal para calcular el árbol abarcador mínimo del grafo g almacenarlo en el grafo tree.

El árbol abarcador mínimo tree está completamente mapeado con g.

El algoritmo de Kruskal es el recomendado para grafos esparcidos.

El procedimiento es parametrizado con las siguientes especificaciones:

  1. GT: el tipo de grafo basado en List_Graph.
  2. Distance<GT>: La clase de lectura del peso del arco que debe exportar los siguientes atributos:
    1. typedef Distance<GT>::Distance_Type: el tipo de dato que representa un peso en un arco.
    2. Distance<GT>::Distance_Type operator()(typename GT::Arc *a): que retorna el valor del peso en el arco a.
    3. Distance<GT>::Max_Distance: constante estática correspondiente al valor de distancia máximo que un algoritmo consideraría como valor infinito.
    4. typename Distance<GT>::Zero_Distance: constante estática correspondiente al elemento neutro de la suma. Tradicionalmente, en la inmensa mayoría de casos, este será el cero.
  3. Compare<GT>: clase que realiza la comparación entre dos pesos y cuyo prototipo es:
    • bool operator () (const typename Distance<GT>::Distance_Type & op1, const typename Distance<GT>::Distance_Type & op2) const . Por omisión, esta clase implanta el operador relacional menor que.

Parámetros:
[in] g el grafo al cual se desea calcular el árbol abarcador mínimo.
[out] tree el grafo donde se desea guardar el árbol abarcador mínimo resultado. Este grafo es limpiado antes del comienzo del algoritmo.
Excepciones:
bad_alloc si no hay suficiente memoria para construir tree. En este caso el valor de tree es indeterminado y no está limpio.
Ver también:
prim_min_spanning_tree()

Definición en la línea 104 del archivo Kruskal.H.

Hace referencia a Aleph::has_cycle(), IS_NODE_VISITED, NODE_BITS, NODE_COOKIE, y Aleph::test_connectivity().

void Aleph::map_cut_graph ( GT &  g,
DynDlist< typename GT::Node * > &  cut_node_list,
GT &  cut_graph,
DynDlist< typename GT::Arc * > &  cross_arc_list 
) [inline]

map_cut_graph() toma un grafo y su lista de nodos de corte -la cual debería de haber sido previamente calculada mediante compute_cut_nodes()- y realiza una copia mapeada del grafo de corte.

El grafo de corte se define por aquel compuesto por los nodos y arcos de corte. Un arco de corte se define como un arco que relaciona a dos nodos de corte.

Los arcos que involucran a un nodo de corte y a otro nodo parte de un bloque son llamados "arcos de cruce". Por su índole, estos arcos no pueden estar ni en los bloques ni el en grafo de corte. Para tratar con esta situación, el cuarto parámetro, llamado cross_arc_list guarda una lista de punteros a los arcos de cruce.

El procedimiento exige que los nodos y arcos estén marcados por sus correspondientes bits, así como también que estén pintados. Esto requiere llamadas previas a compute_cut_nodes() y luego a paint_subgraphs(). Los resultados son indeterminados si no se sigue este protocolo.

Parámetros:
[in] g el grafo al cual se le desea copiar y mapear sus nodos y arcos de corte y arcos de cruce.
[in] cut_node_list lista con los nodos de corte la cual debería de ser la resultante de la llamada a compute_cut_nodes().
[out] cut_graph grafo donde se copia el grafo de corte; es decir el grafo compuesto por los nodos y arcos de corte. Este grafo es a menudo inconexo.
[out] cross_arc_list lista de punteros a los arcos de cruce; es decir, a los arcos que involucran a un nodo de corte y a un nodo que es parte de un bloque.
Excepciones:
bad_alloc si no hay memoria para construir cut_graph o insertar en la lista cross_arc_list.
Ver también:
map_subgraph() compute_cut_nodes() paint_subgraphs()

Definición en la línea 1815 del archivo tpl_graph_utils.H.

Hace referencia a DynDlist::append(), y NODE_COOKIE.

void Aleph::map_subgraph ( GT &  g,
GT &  sg,
const long &  color 
) [inline]

map_subgraph() toma un grafo g, un color (un entero a comparar con el contador de nodo y arco) y recorre en profundidad en búsqueda de los nodos y arcos cuyo color corresponda con el dado en parámetro. Los nodos y arcos con el color en cuestión son copiados y mapeados en el subgrafo sg.

map_subgraph() no necesariamente recorre en totalidad el grafo, pues éste no explora en profundidad los nodos con color distinto al dado en parámetro ni se adentra por arcos con otro color. De hecho, la rutina asume que el color se corresponde a un subgrafo conexo de g.

map_subgraph() se destina a extraer un subgrafo bloque de un punto de corte previamente pintado mediante paint_subgraphs(). Sin embargo, eventualmente, map_subgraph() puede usarse independientemente de los puntos de corte. Basta con que los nodos y arcos estén pintados y formen un componente conexo para que la función opere y extraiga el subgrafo.

Parámetros:
[in] g el grafo sobre el cual extraer el subgrafo del color específico.
[out] sg un grafo donde colocar la copia del bloque según el color; este grafo es limpiado antes de comenzar el procedimiento.
[in] color el color que se desea extraer.
Excepciones:
bad_alloc si no hay memoria para construir el subgrafo sg; en este caso, sg queda vacío, independientemente del estado en que haya ocurrido la excepción.
Ver también:
paint_subgraphs() compute_cut_nodes() map_cut_graph()

Definición en la línea 1741 del archivo tpl_graph_utils.H.

Hace referencia a NODE_BITS.

long Aleph::paint_subgraphs ( GT &  g,
const DynDlist< typename GT::Node * > &  cut_node_list 
) [inline]

paint_subgraphs() toma una lista de nodos de corte cut_node_list sobre el grafo g, previamente calculada con compute_cut_nodes(), y efectúa recorridos en profundidad desde cada nodo de corte pintando los bloques mediante el contador presente en cada nodo y arco.

El color se define como el valor del contador del nodo y del arco. Los colores comienzan a partir del valor 1 y habrán tantos colores como la cantidad de bloques separados por los puntos de corte del grafo. Los colores de todos los nodos y arcos del grafo son reiniciados a cero antes de ejecutar el algoritmo.

No se realizan verificaciones sobre el contenido de cut_node_list y de conectividad del grafo.

paint_subgraphs() utiliza el bit cut para distinguir los nodos y arcos de corte. Del mismo modo, para identificar nodos y arcos ya mapeados el procedimiento usa el bit build_subtree para marcarlos.

Los nodos de corte deben haberse calculado previamente mediante compute_cut_nodes().

Por lo general, una vez pintado el grafo, sus bloques se pueden distinguir mediante los colores y esto puede ser suficiente para muchos algoritmos; los de planaridad o dibujado, por ejemplo. Si se desea más seguridad, en detrimento de un poco de tiempo y de espacio, entonces pueden realizarse copias mapeadas de los bloques mediante map_subgraph() especificando un color. Del mismo modo, el subgrafo de corte (los nodos y arcos de corte) pueden obtenerse mediante map_cut_graph(), así como los arcos de cruce (arcos adyacentes a un punto de corte).

Si el protocolo es respetado, entonces paint_subgraphs() no debe fallar, pues no aparta memoria.

Parámetros:
[in] g el grafo a pintar.
[in] cut_node_list lista de punteros a los nodos de corte previamente calculada (idóneamente mediante compute_cut_node()).
Devuelve:
total de colores empleados para pintar los bloques; esto es equivalente a la cantidad total de bloques que tiene el grafo según la delimitación de los puntos de corte.
Ver también:
compute_cut_nodes() map_subgraph() map_cut_graph()

Definición en la línea 1640 del archivo tpl_graph_utils.H.

void prim_min_spanning_tree ( GT &  g,
GT &  tree 
) [inline]

Este procedimiento utiliza el algoritmo de Prim para calcular el árbol abarcador mínimo del grafo g almacenarlo en el grafo tree.

El árbol abarcador mínimo tree está completamente mapeado con g.

El algoritmo utiliza una cola interna cuya longitud máxima es proporcional número de nodos del grafo.

El algoritmo de Prim es el recomendado para grafos densos.

El procedimiento es parametrizado con las siguientes especificaciones:

  1. GT: el tipo de grafo basado en List_Graph.
  2. Distance<GT>: La clase de lectura del peso del arco que debe exportar los siguientes atributos:
    1. typedef Distance<GT>::Distance_Type: el tipo de dato que representa un peso en un arco.
    2. Distance<GT>::Distance_Type operator()(typename GT::Arc *a): que retorna el valor del peso en el arco a.
    3. Distance<GT>::Max_Distance: constante estática correspondiente al valor de distancia máximo que un algoritmo consideraría como valor infinito.
    4. typename Distance<GT>::Zero_Distance: constante estática correspondiente al elemento neutro de la suma. Tradicionalmente, en la inmensa mayoría de casos, este será el cero.
  3. Compare<GT>: clase que realiza la comparación entre dos pesos y cuyo prototipo es:
    • bool operator () (const typename Distance<GT>::Distance_Type & op1, const typename Distance<GT>::Distance_Type & op2) const . Por omisión, esta clase implanta el operador relacional menor que.

Parámetros:
[in] g el grafo al cual se desea calcular el árbol abarcador mínimo.
[out] tree el grafo donde se desea guardar el árbol abarcador mínimo resultado. Este grafo es limpiado antes del comienzo del algoritmo.
Excepciones:
bad_alloc si no hay suficiente memoria para construir tree. En este caso el valor de tree es indeterminado y no está limpio.
Ver también:
kruskal_min_spanning_tree()

Definición en la línea 146 del archivo Prim.H.

Hace referencia a ARC_BITS, IS_ARC_VISITED, IS_NODE_VISITED, NODE_BITS, y Aleph::test_connectivity().

bool q_bellman_ford_min_spanning_tree ( GT &  g,
typename GT::Node *  start_node,
GT &  tree 
) [inline]

Este procedimiento utiliza el algoritmo de Bellman-Ford, mejorado con el uso de un heap exclusivo, para calcular un árbol abarcador de todos los caminos mínimos desde un nodo start_node del grafo g y almacenarlo en el grafo tree.

En la práctica, este algoritmo se desempeña mejor que la versión pura del algoritmo. Sin embargo, el heap exclusivo acarrea mayor consumo de espacio.

El árbol abarcador tree de todos los caminos mínimos desde start_node está completamente mapeado con g. Por tanto, una búsqueda de camino en profundidad, mediante find_path_depth_first() sobre tree, encontrará y construirá cualquier camino mínimo desde start_node hasta un nodo cualquiera.

Aunque el algoritmo de Bellman-Ford exhibe peor desempeño que el de Dijkstra, el primero maneja pesos negativos y detecta la presencia de ciclos negativos. Es por tanto el algoritmo recomendado para la mayoría de aplicaciones de caminos s que manejen pesos negativos.

El procedimiento es parametrizado con las siguientes especificaciones:

  1. GT: el tipo de grafo basado en List_Graph.
  2. Distance<GT>: La clase de lectura del peso del arco que debe exportar los siguientes atributos:
    1. typedef Distance<GT>::Distance_Type: el tipo de dato que representa un peso en un arco.
    2. Distance<GT>::Distance_Type operator()(typename GT::Arc *a): que retorna el valor del peso en el arco a.
    3. Distance<GT>::Max_Distance: constante estática correspondiente al valor de distancia máximo que un algoritmo consideraría como valor infinito.
    4. typename Distance<GT>::Zero_Distance: constante estática correspondiente al elemento neutro de la suma. Tradicionalmente, en la inmensa mayoría de casos, este será el cero.
  3. Compare<GT>: clase que realiza la comparación entre dos pesos y cuyo prototipo es:
    • bool operator()(const typename Distance<GT>::Distance_Type & op1, const typename Distance<GT>::Distance_Type & op2) const
  4. Plus<GT>: clase que realiza la suma de distancias con el siguiente prototipo:
    • typename Distance<GT>::Distance_Type operator()(const typename Distance<GT>::Distance_Type & op1, const typename Distance<GT>::Distance_Type & op2) const
    Hay una especialización de q_bellman_ford_min_spanning_tree<GT,Compare>() con parámetros tipo por omisión de comparación la relación "menor que" y la suma.

Parámetros:
[in] g el grafo al cual se desea calcular el árbol abarcador mínimo.
[in] start_node nodo inicio de los caminos mínimos.
[out] tree el grafo donde se desea guardar el árbol abarcador resultado de todos los caminos mínimos que parten desde el nodo start_node. Este grafo es limpiado antes del comienzo del algoritmo.
Excepciones:
bad_alloc si no hay suficiente memoria para construir tree; bien sea porque falla tree o por la cola interna. En este caso el valor de tree es indeterminado y no está limpio.
Ver también:
dijkstra_min_path() find_path_depth_first() floyd_all_shortest_paths() find_min_path() dijkstra_min_spanning_tree() bellman_ford_min_spanning_tree()

Definición en la línea 367 del archivo Bellman_Ford.H.

Hace referencia a ARC_BITS, IS_NODE_VISITED, NODE_BITS, y NODE_COOKIE.

void Aleph::q_topological_sort ( GT &  g,
DynDlist< typename GT::Node * > &  list 
) [inline]

q_topdological_sort(g,list) recorre en amplitud los nodos de g y efectúa un ordenamiento topológico cuyo resultado lo almacena la lista list.

Parámetros:
[in] g el digrafo acíclico.
[out] list lista de nodos correspondiente al ordenamiento topológico.
Excepciones:
bad_alloc si no hay suficiente memoria para insertar en list o en la cola interna que se requiere para recorrer el digrafo en amplitud.
domain_error si g no es un digrafo.
Nota:
La rutina no verifica si g es en efecto un digrafo acíclico.

Definición en la línea 1965 del archivo tpl_graph_utils.H.

Hace referencia a DynDlist::append(), DynListQueue::get(), ListQueue::is_empty(), NODE_COUNTER, y DynListQueue::put().

void Aleph::strongly_connected_components ( GT &  g,
DynDlist< GT > &  list 
) [inline]

strongly_connected_components() toma un digrafo g, "supuestamente débilemente conexo", calcula sus subgrafos o componentes inconexos y los almacena en una lista dinámica list de subdigrafos mapeados, tanto en los nodos como en los arcos. El énfasis en el supuesto carácter conexo del grafo se debe a que si el grafo no fuese conexo, entonces la lista resultante contendría un solo elemento correspondiente al digrafo copia mapeado de g. Si este fuese el caso, entonces es preferible hacerlo con el método List_Graph::copy_graph().

La función se vale del bit build_subtree para marcar nodos y arcos visitados.

El algoritmo internamente descubre los componentes mediante búsquedas en profundidad.

Parámetros:
[in] g el grafo sobre el cual se desea calcular sus bloques.
[out] list lista de subgrafos mapeados a g con los subgrafos o componentes inconexos de g.
Excepciones:
bad_alloc si no hay memoria para construir algún bloque o insertar en la lista.
Ver también:
List_Graph::copy_graph()
Excepciones:
domain_error si g es un grafo (no un digrafo)

Definición en la línea 996 del archivo tpl_graph_utils.H.

Hace referencia a Aleph::inconnected_components().

bool Aleph::test_connectivity ( GT &  g  )  [inline]

Esta función realiza una prueba de conectividad del grafo g. La prueba apela a un recorrido en profundidad.

En caso de que g no sea un digrafo la función verifica la cantidad de arcos. Si esta cantidad es menor que el número de nodos, entonces el grafo se considera inconexo.

Parámetros:
[in] g el grafo o digrafo a verificar.
Devuelve:
true si el grafo es conexo; false de lo contrario.
Nota:
Debido a la prueba con el número de arcos, esta función es incorrecta para multigrafos.
Ver también:
depth_first_traversal()

Definición en la línea 490 del archivo tpl_graph_utils.H.

Referenciado por Aleph::kruskal_min_spanning_tree(), y Aleph::prim_min_spanning_tree().

bool Aleph::test_cycle ( GT &  g,
typename GT::Node *  src_node 
) [inline]

test_cycle() explora en profundidad el grafo g a partir del nodo start_node y verifica si existe algún ciclo a partir de él.

El bit test_cycle es usado e iniciado al principio del algoritmo para marcar los nodos y arcos visitados.

Nota:
La rutina sólo verifica existencia de ciclo, no dice nada en absoluto sobre la composición del ciclo.
Parámetros:
[in] g el grafo a verificar.
[in] src_node el nodo que se quiere verificar.
Devuelve:
true si existe un ciclo; false de lo contrario.

Definición en la línea 550 del archivo tpl_graph_utils.H.

Hace referencia a ARC_BITS, y IS_ARC_VISITED.

bool Aleph::test_path ( GT &  g,
typename GT::Node *  start_node,
typename GT::Node *  end_node 
) [inline]

test_path() explora en profundidad el grafo g a partir del nodo start_node en búsqueda de un camino que depare en end_node. Si durante la exploración se ve a end_node, entonces se concluye que existe un camino y se retorna true. Si se recorre enteramente a g sin ver a end_node, entonces la función retorna false.

El bit test_path es utilizado para marcar los nodos y arcos visitados durante la búsqueda.

Parámetros:
[in] g el grafo a buscar camino.
[in] start_node puntero al nodo origen del camino.
[in] end_node puntero a nodo destino del camino.
Devuelve:
true si existe un camino entre start_node y end_node.
Ver también:
find_path_depth_first() find_path_breadth_first()

Definición en la línea 763 del archivo tpl_graph_utils.H.

Hace referencia a ARC_BITS.

Referenciado por Aleph::is_reachable().

void Aleph::topological_sort ( GT &  g,
DynDlist< typename GT::Node * > &  list 
) [inline]

topological_sort(g,list) recorre recursivamente en profundidad y en sufijo los nodos de g y efectúa un ordenamiento topológico cuyo resultado lo almacena la lista list.

Parámetros:
[in] g el digrafo acíclico.
[out] list lista de nodos correspondiente al ordenamiento topológico.
Excepciones:
bad_alloc si no hay suficiente memoria para insertar en list.
domain_error si g no es un digrafo.
Nota:
La rutina no verifica si g es en efecto un digrafo acíclico.

Definición en la línea 1930 del archivo tpl_graph_utils.H.

Hace referencia a IS_NODE_VISITED, y DynDlist::size().

void Aleph::warshall_compute_transitive_clausure ( GT &  g,
Bit_Mat_Graph< GT > &  mat 
) [inline]

Esta función calcula la clausura transitiva del grafo g mediante el algoritmo de Warshall. El resultado se almacena en la matriz de bits mat.

Cada entrada mat(i,j) indica existencia de un camino entre el nodo origen con índice i y el nodo destino con índice j. Un valor cero indica que no hay ningún camino; un valor 1 que existe al menos un camino.

El procedimiento utiliza dos matrices de bits; una de uso interno que es liberada al término del procedimiento y la propia matriz mat.

Parámetros:
[in] g el grafo representado mediante una variante de List_Graph.
[out] mat matriz de bits donde se coloca el resultado.
Excepciones:
bad_alloc si no hay suficiente memoria.
Ver también:
List_Graph Bit_Mat_Graph

Definición en la línea 76 del archivo warshall.H.

Hace referencia a Bit_Mat_Graph::get_list_graph(), Bit_Mat_Graph::get_num_nodes(), y Bit_Mat_Graph::set_list_graph().

Leandro R. León