Aleph-w  1.5a.2
Biblioteca general de algoritmos y estructuras de datos
 Todo Clases Archivos Funciones Variables 'typedefs' Enumeraciones Amigas Grupos Páginas
Clases | 'defines' | Funciones
Grafos.
+ Diagrama de colaboración para Grafos.:

Clases

class  Aleph::Bit_Fields
 
class  Aleph::Bellman_Ford_Min_Spanning_Tree< GT, Distance, Compare, Plus, SA >
 
class  Aleph::Q_Bellman_Ford_Min_Spanning_Tree< GT, Distance, Compare, Plus, SA >
 
class  Aleph::Search_Cycle< GT >
 
class  Aleph::Bellman_Ford_Negative_Cycle< GT, Distance, Compare, Plus, SA >
 
class  Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >
 
class  Aleph::Test_Eulerian< GT, SN, SA >
 
class  Aleph::Floyd_All_Shortest_Paths< GT, Distance, SA >
 
class  Aleph::To_Graphviz< GT, Node_Attr, Arc_Attr, SN, SA >
 
class  Aleph::Generate_Graphviz< GT, Write_Node, Write_Arc, Shade_Node, Shade_Arc, Dashed_Node, Dashed_Arc, SA, SN >
 
class  Aleph::Graph_To_Tree_Node< GT, Key, Convert, SA >
 
class  Aleph::Build_Grid< GT, Operation_On_Node, Operation_On_Arc >
 
class  Aleph::Test_Hamiltonian_Sufficiency< GT, SN, SA >
 
class  Aleph::IO_Graph< GT, Load_Node, Store_Node, Load_Arc, Store_Arc, NF, AF >
 
class  Aleph::Kosaraju_Connected_Components< GT, SA >
 
class  Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >
 
class  Aleph::Prim_Min_Spanning_Tree< GT, Distance, SA >
 
class  Aleph::Random_Graph< GT, Init_Node, Init_Arc >
 
class  Aleph::Test_Single_Graph< GT, SN, SA >
 
class  Aleph::Tarjan_Connected_Components< GT, SA >
 
class  Aleph::Compute_Cycle_In_Digraph< GT, SA >
 
class  Aleph::Topological_Sort< GT, SA >
 
class  Aleph::Q_Topological_Sort< GT, SA >
 
struct  Aleph::Walking_Agent< Agent_Info >
 
class  Aleph::Agent_Node< Agents_Node_Info >
 
class  Aleph::Agent_Arc< Agents_Arc_Info >
 
class  Aleph::Agent_Graph< __GT, __Node, __Arc, __Agent >
 
class  Aleph::Array_Digraph< __Graph_Node, __Graph_Arc >
 
class  Aleph::Compute_Bipartite< GT, SA >
 
class  Aleph::Compute_Maximum_Cardinality_Bipartite_Matching< GT, Max_Flow, SA >
 
class  Aleph::Build_Subgraph< GT, SA >
 
class  Aleph::Inconnected_Components< GT, SA >
 
class  Aleph::Lock_Object< Base_Object >
 
class  Aleph::Lock_Object< Base_Object >::Critical_Section
 
class  Aleph::Concurrent_Graph< GT, __Node, __Arc >
 
class  Aleph::Concurrent_Graph< GT, __Node, __Arc >::Node_Iterator
 
class  Aleph::Concurrent_Graph< GT, __Node, __Arc >::Arc_Iterator
 
class  Aleph::Compute_Cut_Nodes< GT, SA >
 
class  Aleph::Dyn_Graph< GT >
 
class  Aleph::Euclidian_Node< Node_Info >
 
class  Aleph::Find_Path_Depth_First< GT, SA >
 
class  Aleph::Find_Path_Breadth_First< GT, SA >
 
class  Aleph::Graph_Node< Node_Info >
 
class  Aleph::Graph_Arc< Arc_Info >
 
class  Aleph::List_Graph< __Graph_Node, __Graph_Arc >
 
class  Aleph::List_Graph< __Graph_Node, __Graph_Arc >::Node_Arc_Iterator
 
struct  Aleph::Dft_Show_Arc< GT >
 
struct  Aleph::Dft_Show_Node< GT >
 
class  Aleph::List_Digraph< __Graph_Node, __Graph_Arc >
 
class  Aleph::Out_Iterator< GT, Show_Arc >
 
class  Aleph::In_Iterator< GT, Show_Arc >
 
class  Aleph::Operate_On_Nodes< GT, Operation, SN >
 
class  Aleph::Operate_On_Arcs< GT, Operation, SA >
 
class  Aleph::Path< GT >
 
class  Aleph::Path< GT >::Iterator
 
class  Aleph::Copy_Graph< GT, SN, SA >
 
class  Aleph::Nodes_Index< GT, Compare, Tree, SN >
 
class  Aleph::Arcs_Index< GT, Compare, Tree, SA >
 
struct  Aleph::Default_Visit_Op< GT >
 
class  Aleph::Depth_First_Traversal< GT, Operation, SA >
 
class  Aleph::Breadth_First_Traversal< GT, Operation, SA >
 
struct  Aleph::Distance_Compare< GT, Distance >
 
class  Aleph::Is_Reachable< GT, SA >
 
class  Aleph::Invert_Digraph< GT, SA >
 
class  Aleph::Dft_Dist< GT >
 
class  Aleph::Total_Cost< GT, Distance, Plus, SA >
 
class  Aleph::IndexArc< GT, Tree, SA >
 
class  Aleph::Index_Graph< GT, Compare, Tree >
 
class  Aleph::IndexNode< GT, Compare, Tree, SN >
 
class  Aleph::Edge_Connectivity< GT, Max_Flow >
 
class  Aleph::Compute_Min_Cut< GT, Max_Flow, SA >
 
class  Aleph::Map_Matrix_Graph< GT, SA >
 
class  Aleph::Matrix_Graph< GT, SA >
 
class  Aleph::Ady_Mat< GT, __Entry_Type, SA >
 
class  Aleph::Bit_Mat_Graph< GT, SA >
 
class  Aleph::Net_Cost_Arc< Arc_Info, F_Type >
 
class  Aleph::Max_Flow_Min_Cost< Net >
 
class  Aleph::Net_Sup_Dem_Node< Node_Info, F_Type >
 
class  Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >
 
class  Aleph::Net_Cap_Node< Node_Info, F_Type >
 
class  Aleph::Graph_Snode< Node_Info >
 
class  Aleph::Graph_Sarc< Arc_Info >
 
class  Aleph::List_SGraph< __Graph_Node, __Graph_Arc >
 
class  Aleph::List_SDigraph< __Graph_Node, __Graph_Arc >
 
class  Aleph::Find_Depth_First_Spanning_Tree< GT, SA >
 
class  Aleph::Find_Breadth_First_Spanning_Tree< GT, SA >
 
class  Aleph::Build_Spanning_Tree< GT >
 
class  Aleph::Is_Graph_Acyclique< GT, SA >
 
class  Aleph::Has_Cycle< GT, SA >
 
class  Test_Connectivity< GT, SA >
 
class  Aleph::Test_For_Cycle< GT, SA >
 
class  Aleph::Test_For_Path< GT, SA >
 
class  Aleph::Warshall_Compute_Transitive_Clausure< GT, SA >
 

'defines'

#define NODE_BITS(p)   ((p)->attrs.control_bits)
 
#define NODE_COUNTER(p)   ((p)->attrs.counter)
 
#define NODE_COLOR(p)   ((p)->attrs.counter)
 
#define IS_NODE_VISITED(p, bit)   (NODE_BITS(p).get_bit(bit))
 
#define NODE_COOKIE(p)   ((p)->attrs.cookie)
 
#define ARC_COUNTER(p)   ((p)->attrs.counter)
 
#define ARC_COLOR(p)   ((p)->attrs.counter)
 
#define ARC_BITS(p)   ((p)->attrs.control_bits)
 
#define IS_ARC_VISITED(p, bit)   (ARC_BITS(p).get_bit(bit))
 
#define ARC_COOKIE(p)   ((p)->attrs.cookie)
 
#define NODE_BITS(p)   ((p)->attrs.control_bits)
 
#define NODE_COUNTER(p)   ((p)->attrs.counter)
 
#define NODE_COLOR(p)   ((p)->attrs.counter)
 
#define IS_NODE_VISITED(p, bit)   (NODE_BITS(p).get_bit(bit))
 
#define NODE_COOKIE(p)   ((p)->attrs.cookie)
 
#define ARC_COUNTER(p)   ((p)->attrs.counter)
 
#define ARC_COLOR(p)   ((p)->attrs.counter)
 
#define ARC_BITS(p)   ((p)->attrs.control_bits)
 
#define IS_ARC_VISITED(p, bit)   (ARC_BITS(p).get_bit(bit))
 
#define ARC_COOKIE(p)   ((p)->attrs.cookie)
 

Funciones

template<class GT , class Distance , class Compare = Aleph::less<typename Distance::Distance_Type>, class Plus = Aleph::plus<typename Distance::Distance_Type>, class SA = Dft_Show_Arc<GT>>
bool Aleph::bellman_ford_min_spanning_tree (GT &g, typename GT::Node *start_node, GT &tree)
 TODO: acelerar los algoritmos con reserve. Revisar bien la interfaz. Más...
 
template<class GT , class Distance , class Compare = Aleph::less<typename Distance::Distance_Type>, class Plus = Aleph::plus<typename Distance::Distance_Type>, class SA = Dft_Show_Arc<GT>>
bool Aleph::q_bellman_ford_min_spanning_tree (GT &g, typename GT::Node *start_node, GT &tree)
 
template<class GT >
bool Aleph::search_cycle (GT &g, DynArray< typename GT::Node * > &pred, DynArray< typename GT::Arc * > &arcs, Path< GT > &cycle)
 
template<class GT , class Distance , class Compare = Aleph::less<typename Distance::Distance_Type>, class Plus = Aleph::plus<typename Distance::Distance_Type>, class SA = Dft_Show_Arc<GT>>
bool Aleph::bellman_ford_negative_cycle (GT &g, typename GT::Node *start_node, Path< GT > &cycle)
 
template<class GT , class Distance , class Compare = Aleph::less<typename Distance::Distance_Type>, class Plus = Aleph::plus<typename Distance::Distance_Type>, class SA = Dft_Show_Arc<GT>>
bool Aleph::bellman_ford_negative_cycle (GT &g, typename GT::Node *start_node, GT &tree, Path< GT > &cycle)
 
template<class GT , class Distance , class Compare = Aleph::less<typename Distance::Distance_Type>, class Plus = Aleph::plus<typename Distance::Distance_Type>, class SA = Dft_Show_Arc<GT>>
bool Aleph::bellman_ford_negative_cycle (GT &g, Path< GT > &cycle)
 
template<class GT , class Write_Node , class Write_Arc , class Shade_Node , class Shade_Arc , class SA >
void Aleph::generate_graphpic (GT &g, const double &xdist, const double &, std::ostream &output)
 
template<class GT , class Write_Node , class Write_Arc , class Shade_Node , class Shade_Arc , class Dashed_Node , class Dashed_Arc , class SA , class SN >
void Aleph::generate_graphviz (GT &g, std::ostream &output, const string &rankdir="TB", float ranksep=0.2, float nodesep=0.2)
 
template<class GT , class Node_Attr , class Arc_Attr , class SN , class SA >
void Aleph::generate_graphviz (GT &g, std::ostream &out, Node_Attr node_attr=Node_Attr(), Arc_Attr arc_attr=Arc_Attr(), const string &rankdir="TB")
 
template<class GT , class Write_Node , class Write_Arc , class Shade_Node , class Shade_Arc , class SA >
void Aleph::generate_cross_graph (GT &g, const size_t &nodes_by_level, const double &xdist, const double &ydist, std::ostream &out)
 
template<class GT , class Write_Node , class Write_Arc , class Shade_Node , class Shade_Arc , class SA >
void Aleph::generate_net_graph (GT &g, const size_t &nodes_by_level, const double &xdist, const double &ydist, std::ostream &out)
 
template<class GT , typename Key , class Convert , class SA = Dft_Show_Arc<GT>>
Tree_Node< Key > * Aleph::graph_to_tree_node (GT &g, typename GT::Node *groot)
 
template<class GT , class SA >
void Aleph::kosaraju_connected_components (GT &g, DynDlist< GT > &blk_list, DynDlist< typename GT::Arc * > &arc_list)
 
template<class GT , class SA >
void Aleph::kosaraju_connected_components (GT &g, DynDlist< DynDlist< typename GT::Node * > > &list)
 
template<class Mat >
void find_min_path (Mat &p, typename Mat::Node *src_node, typename Mat::Node *tgt_node, Path< typename Mat::Graph_Type > &path)
 
template<class Mat >
void find_min_path (Mat &p, const long &src_index, const long &tgt_index, Path< typename Mat::Graph_Type > &path)
 
GT Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::sufficient_hamiltonian (const size_t &__num_nodes, const double &p=0.5)
 
GT Aleph::Random_Graph< GT, Init_Node, Init_Arc >::sufficient_hamiltonian (const size_t &__num_nodes, const double &p=0.5)
 
template<class GT , class SA = Dft_Show_Arc<GT>>
void Aleph::compute_bipartite (GT &g, DynDlist< typename GT::Node * > &l, DynDlist< typename GT::Node * > &r)
 
template<class GT , template< class > class Max_Flow = Ford_Fulkerson_Maximum_Flow, class SA = Dft_Show_Arc<GT>>
void Aleph::compute_maximum_cardinality_bipartite_matching (GT &g, DynDlist< typename GT::Arc * > &matching)
 
template<class GT , class SA >
GT::Arc * Aleph::search_arc (GT &g, typename GT::Node *src_node, typename GT::Node *tgt_node)
 
template<class GT >
void Aleph::copy_graph (GT &gtgt, GT &gsrc, const bool cookie_map=false)
 
template<class GT >
void Aleph::clear_graph (GT &g)
 
template<class GT , class SA = Dft_Show_Arc<GT>>
bool Aleph::find_path_depth_first (GT &g, typename GT::Node *start_node, typename GT::Node *end_node, Path< GT > &path)
 
template<class GTT , class GTS , class Copy_Node = Dft_Copy_Node<GTT, GTS>, class Copy_Arc = Dft_Copy_Arc<GTT, GTS>>
void Aleph::inter_copy_graph (GTT &gtgt, GTS &gsrc, const bool cookie_map=false)
 
template<class GT , class SA = Dft_Show_Arc<GT>>
size_t Aleph::depth_first_traversal (GT &g, typename GT::Node *start_node, bool(*visit)(GT &g, typename GT::Node *, typename GT::Arc *), SA sa=SA())
 
template<class GT , class SA = Dft_Show_Arc<GT>>
size_t Aleph::depth_first_traversal (GT &g, bool(*visit)(GT &, typename GT::Node *, typename GT::Arc *), SA sa=SA())
 
template<class GT , class SA = Dft_Show_Arc<GT>>
size_t Aleph::breadth_first_traversal (GT &g, typename GT::Node *start, bool(*visit)(GT &, typename GT::Node *, typename GT::Arc *))
 
template<class GT , class SA = Dft_Show_Arc<GT>>
size_t Aleph::breadth_first_traversal (GT &g, bool(*visit)(GT &, typename GT::Node *, typename GT::Arc *))
 
template<class GT , class SA = Dft_Show_Arc<GT>>
bool Aleph::find_path_breadth_first (GT &g, typename GT::Node *start, typename GT::Node *end, Path< GT > &path)
 
template<class GT , class SA = Dft_Show_Arc<GT>>
bool Aleph::test_connectivity (GT &g)
 
template<class GT , class SA = Dft_Show_Arc<GT>>
bool Aleph::test_for_cycle (GT &g, typename GT::Node *src_node)
 
template<class GT , class SA = Dft_Show_Arc<GT>>
bool Aleph::is_graph_acyclique (GT &g, typename GT::Node *start_node)
 
template<class GT , class SA = Dft_Show_Arc<GT>>
bool Aleph::is_graph_acyclique (GT &g)
 
template<class GT , class SA = Dft_Show_Arc<GT>>
bool Aleph::has_cycle (GT &g)
 
template<class GT , class SA = Dft_Show_Arc<GT>>
bool Aleph::test_for_path (GT &g, typename GT::Node *start_node, typename GT::Node *end_node)
 
template<class GT , class SA = Dft_Show_Arc<GT>>
void Aleph::inconnected_components (GT &g, DynDlist< GT > &list)
 
template<class GT , class SA = Dft_Show_Arc<GT>>
void Aleph::build_subgraph (GT &g, GT &sg, typename GT::Node *g_src, size_t &node_count)
 
template<class GT , class SA = Dft_Show_Arc<GT>>
void Aleph::find_depth_first_spanning_tree (GT &g, typename GT::Node *gnode, GT &tree)
 
template<class GT , class SA = Dft_Show_Arc<GT>>
void Aleph::find_depth_first_spanning_tree (GT &g, GT &tree)
 
template<class GT , class SA = Dft_Show_Arc<GT>>
void Aleph::find_breadth_first_spanning_tree (GT &g, typename GT::Node *gp, GT &tree)
 
template<class GT >
void Aleph::build_spanning_tree (GT &g, GT &tree, DynArray< typename GT::Arc > *arcs, const bool with_map=false)
 
template<class GT , class SA = Dft_Show_Arc<GT>>
void Aleph::compute_cut_nodes (GT &g, typename GT::Node *start, DynDlist< typename GT::Node * > &list)
 
template<class GT , class SA = Dft_Show_Arc<GT>>
long Aleph::paint_subgraphs (GT &g, const DynDlist< typename GT::Node * > &cut_node_list)
 
template<class GT , class SA = Dft_Show_Arc<GT>>
void Aleph::map_subgraph (GT &g, GT &sg, const long &color)
 
template<class GT , class SA = Dft_Show_Arc<GT>>
void Aleph::map_cut_graph (GT &g, DynDlist< typename GT::Node * > &cut_node_list, GT &cut_graph, DynDlist< typename GT::Arc * > &cross_arc_list)
 
template<class GT , class SA = Dft_Show_Arc<GT>>
bool Aleph::is_reachable (GT &g, typename GT::Node *src, typename GT::Node *tgt)
 
template<class GT , class SA = Dft_Show_Arc<GT>>
void Aleph::invert_digraph (GT &g, GT &gi, SA &&sa=SA())
 
template<class GT , template< class > class Max_Flow = Random_Preflow_Maximum_Flow, class SA = Dft_Show_Arc<GT>>
long Aleph::edge_connectivity (GT &g)
 
template<class GT , template< class > class Max_Flow = Heap_Preflow_Maximum_Flow, class SA = Dft_Show_Arc<GT>>
long Aleph::compute_min_cut (GT &g, Aleph::set< typename GT::Node * > &l, Aleph::set< typename GT::Node * > &r, DynDlist< typename GT::Arc * > &cut)
 
template<class GT , template< class > class Max_Flow = Random_Preflow_Maximum_Flow, class SA = Dft_Show_Arc<GT>>
long Aleph::vertex_connectivity (GT &g)
 
template<class GT , class SA = Dft_Show_Arc<GT>>
void Aleph::warshall_compute_transitive_clausure (GT &g, Bit_Mat_Graph< GT, SA > &mat)
 
template<class Mat >
void Aleph::find_min_path (Mat &p, const long &src_index, const long &tgt_index, Path< typename Mat::Graph_Type > &path)
 

Descripción detallada

Grafos

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

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

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

    Grafos

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

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>.
  2. 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.
  3. 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 los 'defines'

#define ARC_BITS (   p)    ((p)->attrs.control_bits)

Obtiene los bits de control de un arco.

Referenciado por Aleph::bellman_ford_min_spanning_tree(), Aleph::bellman_ford_negative_cycle(), Aleph::breadth_first_traversal(), Aleph::build_spanning_tree(), Aleph::build_subgraph(), Aleph::compute_cut_nodes(), Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >::compute_min_paths_tree(), Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >::compute_partial_min_paths_tree(), Aleph::Compute_Cut_Nodes< GT, SA >::cut_nodes(), Aleph::find_breadth_first_spanning_tree(), Aleph::find_path_breadth_first(), Aleph::find_path_depth_first(), Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >::paint_min_paths_tree(), Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >::paint_partial_min_paths_tree(), Aleph::Bellman_Ford< GT, Distance, SA >::paint_spanning_tree(), Aleph::q_bellman_ford_min_spanning_tree(), Aleph::test_for_cycle() y Aleph::test_for_path().

#define ARC_BITS (   p)    ((p)->attrs.control_bits)

Obtiene los bits de control de un arco.

#define ARC_COLOR (   p)    ((p)->attrs.counter)

Obtiene el color de un arco.

#define ARC_COLOR (   p)    ((p)->attrs.counter)

Obtiene el color de un arco.

#define ARC_COOKIE (   p)    ((p)->attrs.cookie)

Retorna el cookie del arco.

Referenciado por Aleph::Bellman_Ford< GT, Distance, SA >::build_tree(), Aleph::Net_Cap_Graph< NodeT, ArcT >::compute_aux_net(), Aleph::compute_maximum_cardinality_bipartite_matching(), Aleph::compute_min_cut(), Aleph::search_cycle() y Aleph::Net_Cap_Graph< NodeT, ArcT >::update().

#define ARC_COOKIE (   p)    ((p)->attrs.cookie)

Retorna el cookie del arco.

#define ARC_COUNTER (   p)    ((p)->attrs.counter)

Obtiene el contador de un arco.

#define ARC_COUNTER (   p)    ((p)->attrs.counter)

Obtiene el contador de un arco.

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

Determina si el un bit de arco está marcado.

Parámetros
ppuntero al arco
bitnúmero de bit a leer
Devuelve
true si el bit es 1; false si es 0

Referenciado por Aleph::breadth_first_traversal(), Aleph::build_subgraph(), Aleph::compute_cut_nodes(), Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >::compute_min_paths_tree(), Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >::compute_partial_min_paths_tree(), Aleph::Compute_Cut_Nodes< GT, SA >::cut_nodes(), Aleph::find_breadth_first_spanning_tree(), Aleph::find_depth_first_spanning_tree(), Aleph::find_path_breadth_first(), Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >::paint_min_paths_tree(), Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >::paint_partial_min_paths_tree() y Aleph::test_for_cycle().

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

Determina si el un bit de arco está marcado.

Parámetros
ppuntero al arco
bitnúmero de bit a leer
Devuelve
true si el bit es 1; false si es 0
#define IS_NODE_VISITED (   p,
  bit 
)    (NODE_BITS(p).get_bit(bit))

Determina si el un bit de nodo está marcado.

Parámetros
ppuntero al nodo
bitnúmero de bit a leer
Devuelve
true si el bit es 1; false si es 0

Referenciado por Aleph::bellman_ford_min_spanning_tree(), Aleph::bellman_ford_negative_cycle(), Aleph::breadth_first_traversal(), Aleph::build_spanning_tree(), Aleph::build_subgraph(), Aleph::Compute_Cut_Nodes< GT, SA >::compute_blocks(), Aleph::compute_cut_nodes(), Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >::compute_min_paths_tree(), Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >::compute_partial_min_paths_tree(), Aleph::Tarjan_Connected_Components< GT, SA >::connected_components(), Aleph::Compute_Cut_Nodes< GT, SA >::cut_nodes(), Aleph::find_breadth_first_spanning_tree(), Aleph::find_depth_first_spanning_tree(), Aleph::find_path_breadth_first(), Aleph::find_path_depth_first(), Aleph::Tarjan_Connected_Components< GT, SA >::has_cycle(), Aleph::inconnected_components(), Aleph::is_graph_acyclique(), Aleph::kosaraju_connected_components(), Aleph::min_cut(), Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >::paint_min_paths_tree(), Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >::paint_partial_min_paths_tree(), Aleph::Topological_Sort< GT, SA >::perform() y Aleph::q_bellman_ford_min_spanning_tree().

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

Determina si el un bit de nodo está marcado.

Parámetros
ppuntero al nodo
bitnúmero de bit a leer
Devuelve
true si el bit es 1; false si es 0
#define NODE_BITS (   p)    ((p)->attrs.control_bits)

Obtiene los bits de control de un nodo.

Referenciado por Aleph::bellman_ford_min_spanning_tree(), Aleph::bellman_ford_negative_cycle(), Aleph::breadth_first_traversal(), Aleph::build_spanning_tree(), Aleph::build_subgraph(), Aleph::compute_cut_nodes(), Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >::compute_min_paths_tree(), Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >::compute_partial_min_paths_tree(), Aleph::Compute_Cut_Nodes< GT, SA >::cut_nodes(), Aleph::find_breadth_first_spanning_tree(), Aleph::find_depth_first_spanning_tree(), Aleph::find_path_breadth_first(), Aleph::find_path_depth_first(), Aleph::map_subgraph(), Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >::paint_min_paths_tree(), Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >::paint_partial_min_paths_tree(), Aleph::Bellman_Ford< GT, Distance, SA >::paint_spanning_tree() y Aleph::q_bellman_ford_min_spanning_tree().

#define NODE_BITS (   p)    ((p)->attrs.control_bits)

Obtiene los bits de control de un nodo.

#define NODE_COLOR (   p)    ((p)->attrs.counter)

Obtiene el color de un nodo.

Referenciado por Aleph::kosaraju_connected_components().

#define NODE_COLOR (   p)    ((p)->attrs.counter)

Obtiene el color de un nodo.

#define NODE_COOKIE (   p)    ((p)->attrs.cookie)

Retorna el cookie del nodo.

Referenciado por Aleph::bellman_ford_min_spanning_tree(), Aleph::bellman_ford_negative_cycle(), Aleph::Bellman_Ford< GT, Distance, SA >::build_tree(), Aleph::Net_Cap_Graph< NodeT, ArcT >::compute_aux_net(), Aleph::compute_maximum_cardinality_bipartite_matching(), Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >::compute_min_paths_tree(), Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >::compute_partial_min_paths_tree(), Aleph::edge_connectivity(), Aleph::find_path_breadth_first(), Aleph::Find_Depth_First_Spanning_Tree< GT, SA >::operator()(), Aleph::Bellman_Ford< GT, Distance, SA >::paint_spanning_tree(), Aleph::q_bellman_ford_min_spanning_tree(), Aleph::search_cycle() y Aleph::vertex_connectivity().

#define NODE_COOKIE (   p)    ((p)->attrs.cookie)

Retorna el cookie del nodo.

#define NODE_COUNTER (   p)    ((p)->attrs.counter)

Obtiene el contador de un nodo.

Referenciado por Aleph::Tarjan_Connected_Components< GT, SA >::connected_components(), Aleph::Q_Topological_Sort< GT, SA >::perform() y Aleph::Q_Topological_Sort< GT, SA >::ranks().

#define NODE_COUNTER (   p)    ((p)->attrs.counter)

Obtiene el contador de un nodo.

Documentación de las funciones

template<class GT , class Distance , class Compare = Aleph::less<typename Distance::Distance_Type>, class Plus = Aleph::plus<typename Distance::Distance_Type>, class SA = Dft_Show_Arc<GT>>
bool Aleph::bellman_ford_min_spanning_tree ( GT &  g,
typename GT::Node *  start_node,
GT &  tree 
)
inline

TODO: acelerar los algoritmos con reserve. Revisar bien la interfaz.

Calcula un árbol abarcador de todos los caminos mínimos desde un nodo dado según el algoritmo de Bellman-Ford.

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
  5. SA: filtro de arcos.
Parámetros
[in]gel grafo al cual se desea calcular el árbol abarcador mínimo.
[in]start_nodenodo inicio de los caminos mínimos.
[out]treeel 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.
Devuelve
false si el grafo no tiene ciclos negativos. De lo contrario, se retorna true
Excepciones
bad_allocsi 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()

Hace referencia a ARC_BITS, Aleph::clear_graph(), IS_NODE_VISITED, Aleph::Filter_Iterator< Container, It, Show_Item >::next(), NODE_BITS y NODE_COOKIE.

+ Gráfico de llamadas para esta función:

template<class GT , class Distance , class Compare = Aleph::less<typename Distance::Distance_Type>, class Plus = Aleph::plus<typename Distance::Distance_Type>, class SA = Dft_Show_Arc<GT>>
bool Aleph::bellman_ford_negative_cycle ( GT &  g,
typename GT::Node *  start_node,
Path< GT > &  cycle 
)
inline

Detecta si existe un ciclo negativo y eventualmente lo calcula.

Esta rutina toma un digrafo y un nodo destino, ejecuta el algoritmo de Bellman-Ford y si se detecta un ciclo negativo entonces lo almacena en un camino.

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
  5. SA: filtro de arcos.
Parámetros
[in]gel grafo.
[in]start_nodeel nodo inicio.
[out]cycleel camino donde se guarda el ciclo en caso de que se detecte ciclo negativo.
Devuelve
true si existe un ciclo negativo; false de lo contrario.
Excepciones
bad_allocsi no hay suficiente memoria.

Hace referencia a Aleph::Filter_Iterator< Container, It, Show_Item >::next(), NODE_BITS y NODE_COOKIE.

+ Gráfico de llamadas para esta función:

template<class GT , class Distance , class Compare = Aleph::less<typename Distance::Distance_Type>, class Plus = Aleph::plus<typename Distance::Distance_Type>, class SA = Dft_Show_Arc<GT>>
bool Aleph::bellman_ford_negative_cycle ( GT &  g,
typename GT::Node *  start_node,
GT &  tree,
Path< GT > &  cycle 
)
inline

Detecta si existe un ciclo negativo y eventualmente lo calcula.

Esta rutina toma un digrafo y un nodo destino, ejecuta el algoritmo de Bellman-Ford y si se detecta un ciclo negativo entonces lo almacena en un camino.

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
  5. SA: filtro de arcos.
Parámetros
[in]gel grafo.
[in]start_nodeel nodo inicio.
[out]cycleel camino donde se guarda el ciclo en caso de que se detecte ciclo negativo.
[out]treeel árbol abarcador de caminos mínimos desde el nodo start_node (en caso de que no exista ciclo negativo)
Devuelve
true si existe un ciclo negativo; false de lo contrario.
Excepciones
bad_allocsi no hay suficiente memoria.

Hace referencia a ARC_BITS, Aleph::clear_graph(), IS_NODE_VISITED, Aleph::Filter_Iterator< Container, It, Show_Item >::next(), NODE_BITS y NODE_COOKIE.

+ Gráfico de llamadas para esta función:

template<class GT , class Distance , class Compare = Aleph::less<typename Distance::Distance_Type>, class Plus = Aleph::plus<typename Distance::Distance_Type>, class SA = Dft_Show_Arc<GT>>
bool Aleph::bellman_ford_negative_cycle ( GT &  g,
Path< GT > &  cycle 
)
inline

Detecta si existe un ciclo negativo y eventualmente lo calcula.

Esta rutina toma un digrafo g y verifica si existe un ciclo negativo mediante el algoritmo de Bellman-Ford. un nodo destino, ejecuta el algoritmo de Bellman-Ford y si se detecta un ciclo negativo entonces lo almacena en un camino.

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
  5. SA: filtro de arcos.

Esta operación primero calcula los componentes fuertemente conexos del digrafo.Luego, sobre cada uno de ellos (con 2 o más nodos), se ejecuta el algoritmo de Bellman-Ford en búsqueda de un ciclo negativo. Si se encuentra un ciclo negativo, entonces el proceso se detiene, el ciclo se guarda en el parámetro cycle, y se retorna true. Si, por el contrario, se recorren todos los componentes fuertemente conexos si encontrar un ciclo negativo, entonces se retorna false.

Parámetros
[in]gel grafo.
[out]cycleel camino donde se guarda el ciclo en caso de que se detecte ciclo negativo.
Devuelve
true si existe un ciclo negativo; false de lo contrario.
Excepciones
bad_allocsi no hay suficiente memoria.

Hace referencia a Aleph::DynDlist< T >::get_first() y Aleph::DynDlist< T >::size().

+ Gráfico de llamadas para esta función:

template<class GT , class SA = Dft_Show_Arc<GT>>
size_t Aleph::breadth_first_traversal ( GT &  g,
typename GT::Node *  start,
bool(*)(GT &, typename GT::Node *, typename GT::Arc *)  visit 
)
inline

Recorrido genérico en amplitud de un grafo.

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.

La función toma dos parámetros tipo:

  1. GT: el tipo de grafo, el cual debe ser derivado de List_Graph.
  2. SA: clase que se encarga de mostrar el arco. Internamente, la función emplea el iterador filtro Node_Arc_Iterator (basado en Filter_Iterator) para recorrer los arcos de cada nodo. SA es el la clase que determina si el arco debe o no mostrarse al recorrido.

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

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

Hace referencia a ARC_BITS, Aleph::DynListQueue< T >::get(), IS_ARC_VISITED, IS_NODE_VISITED, Aleph::Filter_Iterator< Container, It, Show_Item >::next(), NODE_BITS y Aleph::DynListQueue< T >::put().

+ Gráfico de llamadas para esta función:

template<class GT , class SA = Dft_Show_Arc<GT>>
size_t Aleph::breadth_first_traversal ( GT &  g,
bool(*)(GT &, typename GT::Node *, typename GT::Arc *)  visit 
)
inline

Recorrido genérico en amplitud de un grafo.

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.

La función toma dos parámetros tipo:

  1. GT: el tipo de grafo, el cual debe ser derivado de List_Graph.
  2. SA: clase que se encarga de mostrar el arco. Internamente, la función emplea el iterador filtro Node_Arc_Iterator (basado en Filter_Iterator) para recorrer los arcos de cada nodo. SA es el la clase que determina si el arco debe o no mostrarse al recorrido.

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

Parámetros
[in]gel grafo a explorar.
[in]visitla función de visita.
Devuelve
el número de nodos que fueron visitados
Excepciones
bad_allocsi no hay memoria para la cola interna que utiliza el algoritmo
Ver también
breadth_first_traversal() test_connectivity()
template<class GT >
void Aleph::build_spanning_tree ( GT &  g,
GT &  tree,
DynArray< typename GT::Arc > *  arcs,
const bool  with_map = false 
)

Construye un árbol abarcador de un grafo representado con arreglos.

build_spanning_tree() toma un grafo g y un árbol abarcador representado mediante el arreglo de arcos arcs. Entonces construye en tree el árbol abarcador.

Parámetros
[in]gel grafo sobre el cual se desea construir el árbol abarcador alterno.
[out]treeel árbol abarcador alterno obtenido de los arreglos pred y arcs.
[in]arcsel arreglo de punteros a arcos.
[in]with_mapindica si el árbol abarcador tree debe mapearse con el grafo g.
Excepciones
bad_allocsi no hay suficiente memoria para construir el árbol abarcado tree.

Hace referencia a ARC_BITS, IS_NODE_VISITED y NODE_BITS.

Referenciado por Aleph::Build_Spanning_Tree< GT >::operator()().

+ Gráfico de llamadas a esta función:

template<class GT , class SA = Dft_Show_Arc<GT>>
void Aleph::build_subgraph ( GT &  g,
GT &  sg,
typename GT::Node *  g_src,
size_t &  node_count 
)
inline

Construye un subgrafo mapeado del grafo g a partir de uno de sus nodos.

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]gel grafo a mapear
[out]sgun grafo vacío donde colocar la copia mapeada a partir de g_src.
[in]g_srcel nodo origen desde donde se origina el recorrido y mapeo.
[in,out]node_countla 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_allocsi no hay memoria para construir sg.
Ver también
inconnected_components() copy_graph()

Hace referencia a ARC_BITS, IS_ARC_VISITED, IS_NODE_VISITED, Aleph::Filter_Iterator< Container, It, Show_Item >::next() y NODE_BITS.

+ Gráfico de llamadas para esta función:

template<class GT >
void Aleph::clear_graph ( GT &  g)
inline

Limpia todo el grafo g (todos sus nodos y arcos son eliminados y la memoria es liberada).

Referenciado por Aleph::bellman_ford_min_spanning_tree(), Aleph::bellman_ford_negative_cycle(), Aleph::Bellman_Ford< GT, Distance, SA >::build_tree(), Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >::compute_min_paths_tree(), Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >::compute_partial_min_paths_tree(), Aleph::copy_graph(), Aleph::find_breadth_first_spanning_tree(), Aleph::find_depth_first_spanning_tree(), Aleph::Net_Cap_Graph< NodeT, ArcT >::free_aux_net(), Aleph::inter_copy_graph(), Aleph::invert_digraph(), Aleph::Compute_Cut_Nodes< GT, SA >::map_cut_graph(), Aleph::map_cut_graph(), Aleph::Compute_Cut_Nodes< GT, SA >::map_subgraph(), Aleph::map_subgraph(), Aleph::q_bellman_ford_min_spanning_tree() y Aleph::List_Graph< __Graph_Node, __Graph_Arc >::~List_Graph().

+ Gráfico de llamadas a esta función:

template<class GT , class SA = Dft_Show_Arc<GT>>
void Aleph::compute_bipartite ( GT &  g,
DynDlist< typename GT::Node * > &  l,
DynDlist< typename GT::Node * > &  r 
)

Toma un grafo bipartido y calcula los conjuntos de partición.

Un grafo es bipartido si puede dividirse en dos subconjuntos l y r tal que todo nodo de l sólo tiene arcos hacia nodos de r y viceversa.

compute_bipartite(g,l,r) toma un grafo bipartido g y calcula los conjuntos de bipartición nombrados por los parámetros l y r, respectivamente.

Parámetros
[in]gel grafo bipartido.
[out]lun conjunto partición.
[out]run conjunto partición.
Excepciones
domain_errorsi durante el cálculo se determina que el grafo no es bipartido.
bad_allocsi no hay suficiente memoria.

Hace referencia a Aleph::DynDlist< T >::get(), Aleph::Dlink::is_empty(), Aleph::Filter_Iterator< Container, It, Show_Item >::next() y Aleph::DynDlist< T >::put().

Referenciado por Aleph::compute_maximum_cardinality_bipartite_matching().

+ Gráfico de llamadas para esta función:

+ Gráfico de llamadas a esta función:

template<class GT , class SA = Dft_Show_Arc<GT>>
void Aleph::compute_cut_nodes ( GT &  g,
typename GT::Node *  start,
DynDlist< typename GT::Node * > &  list 
)

Calcula los puntos de corte de un grafo.

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]gel grafo a calcular los puntos de corte.
[in]startel nodo origen por donde iniciar el recorrido en profundidad.
[out]listlista dinámica donde se guardan punteros a nodos de corte del grafo.
Excepciones
bad_allocsi 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()

Hace referencia a Aleph::DynDlist< T >::append(), ARC_BITS, IS_ARC_VISITED, IS_NODE_VISITED, Aleph::Filter_Iterator< Container, It, Show_Item >::next() y NODE_BITS.

+ Gráfico de llamadas para esta función:

template<class GT , template< class > class Max_Flow = Ford_Fulkerson_Maximum_Flow, class SA = Dft_Show_Arc<GT>>
void Aleph::compute_maximum_cardinality_bipartite_matching ( GT &  g,
DynDlist< typename GT::Arc * > &  matching 
)

Calcula el emparejamiento de cardinalidad máxima de un grafo bipartido.

compute_maximum_cardinality_bipartite_matching(g,matching) recibe un grafo bipartido g y calcula el máximo emparejamiento bipartido en la lista matching.

El procedimiento calcula los conjuntos de bipartición, luego construye una red capacitada unitaria equivalente y sobre ella invoca a un algoritmo de maximización de flujo.

La rutina maneja dos parámetros tipo:

  1. GT el tipo de grafo bipartido
  2. Max_Flow el algoritmo de maximización de flujo a emplear para realizar el cálculo
Parámetros
[in]gel grafo bipartido.
[out]matchinglista de arcos componentes del emparejamiento.
Excepciones
bad_allocsi no hay suficiente memoria.

Hace referencia a Aleph::DynDlist< T >::append(), ARC_COOKIE, Aleph::compute_bipartite(), Aleph::Filter_Iterator< Container, It, Show_Item >::next() y NODE_COOKIE.

+ Gráfico de llamadas para esta función:

template<class GT , template< class > class Max_Flow = Heap_Preflow_Maximum_Flow, class SA = Dft_Show_Arc<GT>>
long Aleph::compute_min_cut ( GT &  g,
Aleph::set< typename GT::Node * > &  l,
Aleph::set< typename GT::Node * > &  r,
DynDlist< typename GT::Arc * > &  cut 
)

Calcula el corte mínimo de un grafo.

compute_min_cut(g, l, r, cut) indaga la conectividad en arcos del grafo g y retorna los conjuntos de nodos y arcos que conforman el corte.

El algoritmo construye una red capacitada unitaria equivalente y mediante sucesivas maximizaciones de flujo indaga la conectividad en arcos.

La rutina recibe dos paráetros tipo:

  1. GT: el tipo grafo sobre al cual se le desea averiguar su conectividad.
  2. Max_Flow el algoritmo de maximización de flujo a emplear para averiguar conectividad.
Parámetros
[in]gel grafo sobre el cual se desea calcular el corte mínimo.
[out]lun conjunto de nodos origen que involucra los arcos parte del corte.
[out]run conjunto de nodos destino que involucra los arcos parte del corte y que son destino de los nodos en l.
[out]cutel conjunto de arcos parte del corte.
Devuelve
la conectividad en arcos del grafo.
Excepciones
bad_allocsi no hay suficiente memoria.

Hace referencia a Aleph::DynDlist< T >::append(), ARC_COOKIE, Aleph::set< T, Compare, Tree >::begin(), Aleph::set< T, Compare, Tree >::end(), Aleph::DynDlist< T >::get(), Aleph::Dlink::Iterator::has_current(), Aleph::set< T, Compare, Tree >::insert(), Aleph::Dlink::is_empty(), Aleph::Filter_Iterator< Container, It, Show_Item >::next(), Aleph::DynDlist< T >::swap() y Aleph::set< T, Compare, Tree >::swap().

+ Gráfico de llamadas para esta función:

template<class GT >
void Aleph::copy_graph ( GT &  gtgt,
GT &  gsrc,
const bool  cookie_map = false 
)

Copia explícita de grafos.

La rutina primero limpia el grafo this (se eliminan sus nodos arcos y se libera toda la memoria); luego copia enteramente el grafo (o digrafo) g a this. Si el valor lógico cookie_map es cierto, entonces la copia es mapeada; es decir, todos los cookies de los nodos y arcos de ambos grafos quedan mapeados entre sí.

Parámetros
[in]gsrcgrafo o digrafo a ser copiado.
[in]gtgtgrafo o digrafo destino de la copia.
[in]cookie_mapsi el valor es true, entonces la copia es mapeada. Por omisión no se realiza copia mapeada.
Excepciones
bad_allocsi no hay suficiente memoria para la copia.
Nota
La copia no incluye los atributos de control del grafo (bit, contador y cookies)

Hace referencia a Aleph::clear_graph() y Aleph::DynMapTree< Key, Type, Avl_Tree, Compare >::insert().

Referenciado por Aleph::List_Graph< __Graph_Node, __Graph_Arc >::List_Graph(), Aleph::Net_Graph< NodeT, ArcT >::Net_Graph() y Aleph::List_Graph< __Graph_Node, __Graph_Arc >::operator=().

+ Gráfico de llamadas para esta función:

+ Gráfico de llamadas a esta función:

template<class GT , class SA = Dft_Show_Arc<GT>>
size_t Aleph::depth_first_traversal ( GT &  g,
typename GT::Node *  start_node,
bool(*)(GT &g, typename GT::Node *, typename GT::Arc *)  visit,
SA  sa = SA() 
)
inline

Recorrido genérico en profundidad de un grafo.

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

La función toma dos parámetros tipo:

  1. GT: el tipo de grafo, el cual debe ser derivado de List_Graph
  2. SA: clase que se encarga de mostrar el arco. Internamente, la función emplea el iterador filtro Node_Arc_Iterator (basado en Filter_Iterator) para recorrer los arcos de cada nodo. SA es el la clase que determina si el arco debe o no mostrarse al recorrido. Mediante esta clase, el recorrido en profundidad se puede especializar para procese los arcos según algún criterio; arcos residuales de una red residual de flujo, por ejemplo

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.

Una versión sin el parámetro tipo SA especializa mostrar todos los arcos.

Parámetros
[in]gel grafo a explorar.
[in]start_nodeel nodo por donde se inicia el recorrido.
[in]visitla función de visita.
[in]safiltro de arcos.
Devuelve
el número de nodos que fueron visitados
Ver también
breadth_first_traversal() test_connectivity() Filter_Iterator
template<class GT , class SA = Dft_Show_Arc<GT>>
size_t Aleph::depth_first_traversal ( GT &  g,
bool(*)(GT &, typename GT::Node *, typename GT::Arc *)  visit,
SA  sa = SA() 
)
inline

Recorrido genérico en profundidad de un grafo.

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]gel grafo a explorar.
[in]visitla función de visita.
Devuelve
el número de nodos que fueron visitados
Parámetros
[in]safiltro de arcos.
Ver también
breadth_first_traversal() test_connectivity()
template<class GT , template< class > class Max_Flow = Random_Preflow_Maximum_Flow, class SA = Dft_Show_Arc<GT>>
long Aleph::edge_connectivity ( GT &  g)

Calcula la conectividad en arcos de un grafo.

edge_connectivity(g) calcula la conectividad en arcos de un grafo mediante maximizaciones sucesivas de flujo sobre una red alterna capacitada unitaria.

La rutina recibe dos paráetros tipo:

  1. GT: el tipo grafo sobre al cual se le desea averiguar su conectividad.
  2. Max_Flow el algoritmo de maximización de flujo a emplear para averiguar conectividad.
Parámetros
[in]gel grafo.
Devuelve
la conectividad en arcos del grafo g.
Excepciones
bad_allocsi no hay suficiente memoria.

Hace referencia a Aleph::DynDlist< T >::append(), Aleph::DynDlist< T >::get(), Aleph::Dlink::Iterator::has_current(), Aleph::Dlink::is_empty(), Aleph::Filter_Iterator< Container, It, Show_Item >::next() y NODE_COOKIE.

+ Gráfico de llamadas para esta función:

template<class GT , class SA = Dft_Show_Arc<GT>>
void Aleph::find_breadth_first_spanning_tree ( GT &  g,
typename GT::Node *  gp,
GT &  tree 
)
inline

Calcula un árbol abarcador en amplitud de un grafo a partir de un nodo.

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.

La función toma dos parámetros tipo:

  1. GT: el tipo de grafo, el cual debe ser derivado de List_Graph.
  2. SA: clase que se encarga de mostrar el arco. Internamente, la función emplea el iterador filtro Node_Arc_Iterator (basado en Filter_Iterator) para recorrer los arcos de cada nodo. SA es el la clase que determina si el arco debe o no mostrarse al recorrido.

Una especialización prescinde del parámetro tipo SA y muestra todos los arcos del grafo sin filtrado alguno.

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]gel grafo sobre el cual se desea construir el árbol abarcador en amplitud.
[in]gppuntero al nodo origen de la búsqueda en amplitud.
[out]treegrafo donde se colocará el árbol abarcador de amplitud.
Excepciones
bad_allocsi 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()

Hace referencia a ARC_BITS, Aleph::clear_graph(), IS_ARC_VISITED, IS_NODE_VISITED, Aleph::Filter_Iterator< Container, It, Show_Item >::next(), NODE_BITS y Aleph::DynListQueue< T >::put().

+ Gráfico de llamadas para esta función:

template<class GT , class SA = Dft_Show_Arc<GT>>
void Aleph::find_depth_first_spanning_tree ( GT &  g,
typename GT::Node *  gnode,
GT &  tree 
)
inline

Calcula un árbol abarcador en profundidad de un grafo a partir de un nodo.

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.

La función toma dos parámetros tipo:

  1. GT: el tipo de grafo, el cual debe ser derivado de List_Graph.
  2. SA: clase que se encarga de mostrar el arco. Internamente, la función emplea el iterador filtro Node_Arc_Iterator (basado en Filter_Iterator) para recorrer los arcos de cada nodo. SA es el la clase que determina si el arco debe o no mostrarse al recorrido.

Una especialización prescinde del parámetro tipo SA y muestra todos los arcos del grafo sin filtrado alguno.

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]gel grafo sobre el cual se desea construir el árbol abarcador en profundidad.
[in]gnodepuntero al nodo origen de la búsqueda en profundidad.
[out]treegrafo donde se colocará el árbol abarcador de profundidad.
Devuelve
true si el grafo es conexo y existe árbol abarcador; false de lo contrario.
Excepciones
bad_allocsi no hay memoria para construir el árbol abarcador.
Ver también
find_breadth_first_spanning_tree() Tree_Node
graph_to_tree_node()

Hace referencia a Aleph::clear_graph(), IS_ARC_VISITED, IS_NODE_VISITED, Aleph::Filter_Iterator< Container, It, Show_Item >::next() y NODE_BITS.

+ Gráfico de llamadas para esta función:

template<class GT , class SA = Dft_Show_Arc<GT>>
void Aleph::find_depth_first_spanning_tree ( GT &  g,
GT &  tree 
)
inline

Calcula un árbol abarcador en profundidad de un grafo.

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.

La función toma dos parámetros tipo:

  1. GT: el tipo de grafo, el cual debe ser derivado de List_Graph.
  2. SA: clase que se encarga de mostrar el arco. Internamente, la función emplea el iterador filtro Node_Arc_Iterator (basado en Filter_Iterator) para recorrer los arcos de cada nodo. SA es el la clase que determina si el arco debe o no mostrarse al 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]gel grafo sobre el cual se desea construir el árbol abarcador en profundidad.
[out]treegrafo donde se colocará el árbol abarcador de profundidad.
Excepciones
bad_allocsi no hay memoria para construir el árbol abarcador.
Ver también
find_breadth_first_spanning_tree() Tree_Node
graph_to_tree_node()
template<class Mat >
void find_min_path ( Mat &  p,
const long &  src_idx,
const long &  tgt_idx,
Path< typename Mat::Graph_Type > &  path 
)

Construye un camino mínimo desde un nodo a otro a partir de una matriz de caminos calculada por el algoritmo de Floyd-Warshall.

Este procedimiento toma una matriz p que contiene los índices de caminos mínimos calculados por el algoritmo de Floyd-Warshall, dos enteros i y j en la matriz correspondientes a los índices del nodo origen y destino respectivamente, y calcula el camino mínimo en la representación con listas de adyacencia usada en el algoritmo de Floyd-Warshall.

Este procedimiento está concebido para llamarse después de ejecutar floyd_all_shortest_paths(), el cual calcula la matriz p.

Resultados son completamente indeterminados si la matriz p es inválida.

Una versión sobrecargada de este método toma como parámetros punteros a nodos, en lugar de índices sobre la matriz.

Parámetros
[in]pmatriz de índices de caminos mínimos.
[in]src_idxíndice del nodo origen dentro de la matriz de caminos mínimos.
[in]tgt_idxíndice del nodo destino dentro de la matriz de caminos mínimos.
[out]pathel camino mínimo en el grafo representado con listas de adyacencia usado cuando se ejecutó floyd_all_shortest_paths().
Excepciones
bad_allocsi no hay suficiente memoria para construir el camino.
Ver también
floyd_all_shortest_paths()

Hace referencia a Aleph::Path< GT >::append() y Aleph::Path< GT >::set_graph().

Referenciado por find_min_path().

+ Gráfico de llamadas para esta función:

+ Gráfico de llamadas a esta función:

template<class Mat >
void find_min_path ( Mat &  p,
typename Mat::Node *  src_node,
typename Mat::Node *  tgt_node,
Path< typename Mat::Graph_Type > &  path 
)

Construye un camino mínimo desde un nodo a otro a partir de una matriz de caminos calculada por el algoritmo de Floyd-Warshall.

Este procedimiento toma una matriz p que contiene los índices de caminos mínimos calculados por el algoritmo de Floyd-Warshall, dos punteros correspondientes a los nodos origen y destino respectivamente en la representación con listas de adyacencia usada cuando se invocó a floyd_all_shortest_paths(), y calcula el camino mínimo.

Este procedimiento está concebido para llamarse después de ejecutar floyd_all_shortest_paths(), el cual calcula la matriz p.

Resultados son completamente indeterminados si la matriz p es inválida.

Parámetros
[in]pmatriz de índices de caminos mínimos.
[in]src_nodepuntero al nodo origen dentro de la representación con listas de adyacencia.
[in]tgt_nodepuntero al nodo destino dentro de la representación con listas de adyacencia.
[out]pathel camino mínimo en el grafo representado con listas de adyacencia usado cuando se ejecutó floyd_all_shortest_paths().
Excepciones
bad_allocsi no hay suficiente memoria para construir el camino.
Ver también
floyd_all_shortest_paths()

Hace referencia a find_min_path().

+ Gráfico de llamadas para esta función:

template<class Mat >
void find_min_path ( Mat &  p,
const long &  src_idx,
const long &  tgt_idx,
Path< typename Mat::Graph_Type > &  path 
)

Construye un camino mínimo desde un nodo a otro a partir de una matriz de caminos calculada por el algoritmo de Floyd-Warshall.

Este procedimiento toma una matriz p que contiene los índices de caminos mínimos calculados por el algoritmo de Floyd-Warshall, dos enteros i y j en la matriz correspondientes a los índices del nodo origen y destino respectivamente, y calcula el camino mínimo en la representación con listas de adyacencia usada en el algoritmo de Floyd-Warshall.

Este procedimiento está concebido para llamarse después de ejecutar floyd_all_shortest_paths(), el cual calcula la matriz p.

Resultados son completamente indeterminados si la matriz p es inválida.

Una versión sobrecargada de este método toma como parámetros punteros a nodos, en lugar de índices sobre la matriz.

Parámetros
[in]pmatriz de índices de caminos mínimos.
[in]src_idxíndice del nodo origen dentro de la matriz de caminos mínimos.
[in]tgt_idxíndice del nodo destino dentro de la matriz de caminos mínimos.
[out]pathel camino mínimo en el grafo representado con listas de adyacencia usado cuando se ejecutó floyd_all_shortest_paths().
Excepciones
bad_allocsi no hay suficiente memoria para construir el camino.
Ver también
floyd_all_shortest_paths()

Hace referencia a Aleph::Path< GT >::append() y Aleph::Path< GT >::set_graph().

+ Gráfico de llamadas para esta función:

template<class GT , class SA = Dft_Show_Arc<GT>>
bool Aleph::find_path_breadth_first ( GT &  g,
typename GT::Node *  start,
typename GT::Node *  end,
Path< GT > &  path 
)
inline

Busca en amplitud un camino entre start_node y end_node; construye el camino visto si se encuentra el camino.

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

La función toma dos parámetros tipo:

  1. GT: el tipo de grafo, el cual debe ser derivado de List_Graph
  2. SA: clase que se encarga de mostrar el arco. Internamente, la función emplea el iterador filtro Node_Arc_Iterator (basado en Filter_Iterator) para recorrer los arcos de cada nodo. SA es el la clase que determina si el arco debe o no mostrarse al recorrido
Parámetros
[in]gel grafo sobre el cual se desea buscar el camino.
[in]startpuntero al nodo inicio del camino.
[in]endpuntero al nodo destino del camino.
[out]pathel camino visto durante la búsqueda en amplitud; sólo tiene sentido si el valor de retorno es true.
Excepciones
bad_allocsi 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()

Hace referencia a ARC_BITS, Aleph::Path< GT >::clear_path(), Aleph::DynListQueue< T >::get(), Aleph::Path< GT >::insert(), Aleph::Path< GT >::inside_graph(), IS_ARC_VISITED, IS_NODE_VISITED, Aleph::Filter_Iterator< Container, It, Show_Item >::next(), NODE_BITS, NODE_COOKIE y Aleph::DynListQueue< T >::put().

+ Gráfico de llamadas para esta función:

template<class GT , class SA = Dft_Show_Arc<GT>>
bool Aleph::find_path_depth_first ( GT &  g,
typename GT::Node *  start_node,
typename GT::Node *  end_node,
Path< GT > &  path 
)
inline

Busca en profundidad un camino entre start_node y end_node; construye el camino visto si se encuentra el camino.

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.

La función toma dos parámetros tipo:

  1. GT: el tipo de grafo, el cual debe ser derivado de List_Graph.
  2. SA: clase que se encarga de mostrar el arco. Internamente, la función emplea el iterador filtro Node_Arc_Iterator (basado en Filter_Iterator) para recorrer los arcos de cada nodo. SA es el la clase que determina si el arco debe o no mostrarse al recorrido.
Parámetros
[in]gel grafo sobre el cual se desea buscar el camino.
[in]start_nodepuntero al nodo inicio del camino.
[in]end_nodepuntero al nodo destino del camino.
[out]pathel camino visto durante la búsqueda en profundidad; sólo tiene sentido si el valor de retorno es true.
Excepciones
bad_allocsi 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()

Hace referencia a ARC_BITS, Aleph::Path< GT >::clear_path(), Aleph::Path< GT >::init(), Aleph::Path< GT >::inside_graph(), IS_NODE_VISITED, Aleph::Filter_Iterator< Container, It, Show_Item >::next() y NODE_BITS.

+ Gráfico de llamadas para esta función:

template<class GT , class Write_Node , class Write_Arc , class Shade_Node , class Shade_Arc , class SA >
void Aleph::generate_cross_graph ( GT &  g,
const size_t &  nodes_by_level,
const double &  xdist,
const double &  ydist,
std::ostream &  out 
)

Genera una especificación para el programa de dibujado de grafos graphpic de tipo grafo cruzado.

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,out) 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 out.

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. SA: clase filtro de arcos.
  3. Write_Node: convierte el contenido de un nodo a un string correspondiente al texto que se desea emitir.
  4. Write_Arc: convierte el contenido de un arco a un string correspondiente al texto que se desea emitir.
  5. 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).
  6. 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]ggrafo o digrafo del que se desea generar el dibujo.
[in]nodes_by_levelcantidad de nodos por nivel. El número de nodos del último nivel dependerá de la cantidad de nodos que contenga el grafo.
[in]xdistseparación horizontal entre los nodos.
[in]ydistseparación vertical entre los nodos.
[out]outarchivo hacia donde se emitirá la salida.
template<class GT , class Write_Node , class Write_Arc , class Shade_Node , class Shade_Arc , class SA >
void Aleph::generate_graphpic ( GT &  g,
const double &  xdist,
const double &  ,
std::ostream &  output 
)

Genera una especificación para el programa de dibujado de grafos graphpic de tipo grafo cruzado.

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. SA: clase filtro de arcos.
  3. Write_Node: convierte el contenido de un nodo a un string correspondiente al texto que se desea emitir.
  4. Write_Arc: convierte el contenido de un arco a un string correspondiente al texto que se desea emitir.
  5. 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).
  6. 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.
  7. SA: filtro para el iterador de arcos
Parámetros
[in]ggrafo o digrafo del que se desea generar el dibujo.
[in]xdistseparación horizontal entre los nodos.
[out]outputarchivo hacia donde se emitirá la salida.
Ver también
Filter_Iterator

Hace referencia a Aleph::Filter_Iterator< Container, It, Show_Item >::next().

+ Gráfico de llamadas para esta función:

template<class GT , class Write_Node , class Write_Arc , class Shade_Node , class Shade_Arc , class Dashed_Node , class Dashed_Arc , class SA , class SN >
void Aleph::generate_graphviz ( GT &  g,
std::ostream &  output,
const string &  rankdir = "TB",
float  ranksep = 0.2,
float  nodesep = 0.2 
)

Genera una especificación para el programa de dibujado de grafos graphpic de tipo grafo cruzado.

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.
  5. Shade_Arc: comando a emitir para un arco oscuro. Si no se desea oscurecer, entonces se debe generar la cadena vacía.
  6. Dashed_Node: comando para generar línea del nodo punteada.
  7. Dashed_Arc: comando para generar línea del arco punteada.
  8. SA: filtro para el iterador de arcos.
  9. SN: filtro para el iterador de nodos.
Parámetros
[in]ggrafo o digrafo del que se desea generar el dibujo.
[out]outputarchivo hacia donde se emitirá la salida.
[in]rankdirdirección del dibujado entre los valores "TB", "BT", "LR" y "RL"
[in]ranksepseparación entre rangos topológicos (cuando aplique)
[in]nodesepseparación entre los nodos
Ver también
Filter_Iterator

Hace referencia a Aleph::Filter_Iterator< GT, GT::Node_Iterator, Show_Node >::next().

+ Gráfico de llamadas para esta función:

template<class GT , class Node_Attr , class Arc_Attr , class SN , class SA >
void Aleph::generate_graphviz ( GT &  g,
std::ostream &  out,
Node_Attr  node_attr = Node_Attr(),
Arc_Attr  arc_attr = Arc_Attr(),
const string &  rankdir = "TB" 
)

Genera una especificación para el programa de dibujado de grafos graphpic de tipo grafo cruzado.

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. Node_Attr: genera la especifcación dot de un nodo
  3. Arc_attr: genera la especifcación dot de un arco correspondiente al texto que se desea emitir.
  4. SN: filtro para el iterador de nodos
  5. SA: filtro para el iterador de arcos
Parámetros
[in]ggrafo o digrafo del que se desea generar el dibujo.
[out]outarchivo hacia donde se emitirá la salida.
[in]rankdirdirección del dibujado entre los valores "TB", "BT", "LR" y "RL"
Ver también
Filter_Iterator

Hace referencia a Aleph::Filter_Iterator< GT, GT::Node_Iterator, Show_Node >::next().

Referenciado por Aleph::Generate_Graphviz< GT, Write_Node, Write_Arc, Shade_Node, Shade_Arc, Dashed_Node, Dashed_Arc, SA, SN >::operator()().

+ Gráfico de llamadas para esta función:

+ Gráfico de llamadas a esta función:

template<class GT , class Write_Node , class Write_Arc , class Shade_Node , class Shade_Arc , class SA >
void Aleph::generate_net_graph ( GT &  g,
const size_t &  nodes_by_level,
const double &  xdist,
const double &  ydist,
std::ostream &  out 
)

Genera una especificación para el programa de dibujado de grafos graphpic de tipo red.

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

generate_net_graph(g,nodes_by_level,xdist,ydist,out) 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 out.

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. SA: clase filtro de arcos.
  3. Write_Node: convierte el contenido de un nodo a un string correspondiente al texto que se desea emitir.
  4. Write_Arc: convierte el contenido de un arco a un string correspondiente al texto que se desea emitir.
  5. 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.
  6. 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]ggrafo o digrafo del que se desea generar el dibujo.
[in]nodes_by_levelcantidad de nodos por nivel. El número de nodos del último nivel dependerá de la cantidad de nodos que contenga el grafo.
[in]xdistseparación horizontal entre los nodos.
[in]ydistseparación vertical entre los nodos.
[out]outarchivo hacia donde se emitirá la salida.
template<class GT , typename Key , class Convert , class SA = Dft_Show_Arc<GT>>
Tree_Node<Key>* Aleph::graph_to_tree_node ( GT &  g,
typename GT::Node *  groot 
)
inline

Convierte un árbol representado en una representación de grafo a un árbol Tree_Node.

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:
-# gnode es de tipo GT::Node
-# tnode de tipo Tree_Node<Key>

La rutina hace una prueba de aciclicidad sobre g mediante la función is_graph_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, el cual debe ser derivado de List_Graph.
  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.
  4. SA: filtro de arcos.
Parámetros
[in]gel árbol de tipo GT (derivado de List_Graph) que se desea convertir.
[in]grootel 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_allocsi no hay memoria para apartar el árbol de tipo Tree_Node<Key>
Ver también
Tree_Node is_graph_acyclique()
template<class GT , class SA = Dft_Show_Arc<GT>>
bool Aleph::has_cycle ( GT &  g)
inline

Retorna true si el grafo no es acíclico (contiene al menos un ciclo).

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_graph_acyclique().

La función toma dos parámetros tipo:

  1. GT: el tipo de grafo, el cual debe ser derivado de List_Graph.
  2. SA: clase que se encarga de mostrar el arco. Internamente, la función emplea el iterador filtro Node_Arc_Iterator (basado en Filter_Iterator) para recorrer los arcos de cada nodo. SA es el la clase que determina si el arco debe o no mostrarse al recorrido.

Una especialización prescinde del parámetro tipo SA y muestra todos los arcos del grafo sin filtrado alguno.

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]gel 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_for_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_graph_acyclique() no.
Ver también
test_for_cycle() is_graph_acyclique()
template<class GT , class SA = Dft_Show_Arc<GT>>
void Aleph::inconnected_components ( GT &  g,
DynDlist< GT > &  list 
)
inline

Calcula los componentes inconexos de un grafo.

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 la función copy_graph().

La función toma dos parámetros tipo:

  1. GT: el tipo de grafo, el cual debe ser derivado de List_Graph.
  2. SA: clase que se encarga de mostrar el arco. Internamente, la función emplea el iterador filtro Node_Arc_Iterator (basado en Filter_Iterator) para recorrer los arcos de cada nodo. SA es el la clase que determina si el arco debe o no mostrarse al recorrido.

Una especialización prescinde del parámetro tipo SA y muestra todos los arcos del grafo sin filtrado alguno.

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]gel grafo sobre el cual se desea calcular sus bloques.
[out]listlista de subgrafos mapeados a g con los subgrafos o componentes inconexos de g.
Excepciones
bad_allocsi no hay memoria para construir algún bloque o insertar en la lista.
Ver también
copy_graph()

Hace referencia a Aleph::DynDlist< T >::append(), Aleph::count(), Aleph::DynDlist< T >::get_last() y IS_NODE_VISITED.

+ Gráfico de llamadas para esta función:

template<class GTT , class GTS , class Copy_Node = Dft_Copy_Node<GTT, GTS>, class Copy_Arc = Dft_Copy_Arc<GTT, GTS>>
void Aleph::inter_copy_graph ( GTT &  gtgt,
GTS &  gsrc,
const bool  cookie_map = false 
)

Copia entre distinta clases de grafos.

Hace referencia a Aleph::clear_graph() y Aleph::DynMapTree< Key, Type, Avl_Tree, Compare >::insert().

+ Gráfico de llamadas para esta función:

template<class GT , class SA = Dft_Show_Arc<GT>>
void Aleph::invert_digraph ( GT &  g,
GT &  gi,
SA &&  sa = SA() 
)

Calcula el digrafo inverso y lo mapea.

invert_digraph(sg,gi) calcula el digrafo inverso del digrafo sg. El resultado es colocado en el digrafo gi, 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.

Después de la llamada el grafo inverso queda mapeado al original.

Parámetros
[in]gel digrafo a invertir.
[in]giel digrafo invertido de sg.
Excepciones
bad_allocsi no hay memoria para crear a gi.
domain_errorsi sg o gi no son digrafos.

Hace referencia a Aleph::clear_graph() y Aleph::Filter_Iterator< Container, It, Show_Item >::next().

+ Gráfico de llamadas para esta función:

template<class GT , class SA = Dft_Show_Arc<GT>>
bool Aleph::is_graph_acyclique ( GT &  g,
typename GT::Node *  start_node 
)
inline

Retorna true si el grafo es acíclico (no contiene ciclos).

is_graph_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 toma dos parámetros tipo:

  1. GT: el tipo de grafo, el cual debe ser derivado de List_Graph
  2. SA: clase que se encarga de mostrar el arco. Internamente, la función emplea el iterador filtro Node_Arc_Iterator (basado en Filter_Iterator) para recorrer los arcos de cada nodo. SA es el la clase que determina si el arco debe o no mostrarse al recorrido

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]gel grafo a probar.
[in]start_nodeel 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_for_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_graph_acyclique() no.
template<class GT , class SA = Dft_Show_Arc<GT>>
bool Aleph::is_graph_acyclique ( GT &  g)
inline

Retorna true si el grafo es acíclico (no contiene ciclos).

is_graph_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]gel grafo a probar.
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_for_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_graph_acyclique() no.
Ver también
test_for_cycle() has_cycle()

Hace referencia a IS_NODE_VISITED y Aleph::Filter_Iterator< Container, It, Show_Item >::next().

+ Gráfico de llamadas para esta función:

template<class GT , class SA = Dft_Show_Arc<GT>>
bool Aleph::is_reachable ( GT &  g,
typename GT::Node *  src,
typename GT::Node *  tgt 
)

Retorna true si existe el nodo tgt es alcanzable desde src.

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

Parámetros
[in]gel grafo a buscar camino.
[in]srcpuntero al nodo origen del camino.
[in]tgtpuntero 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_For_Path Test_Connectivity
Excepciones
domain_errorsi g es un grafo (no un digrafo)
template<class GT , class SA >
void Aleph::kosaraju_connected_components ( GT &  g,
DynDlist< GT > &  blk_list,
DynDlist< typename GT::Arc * > &  arc_list 
)
inline

Calcula los componentes fuertemente conexos de un grafo según el algoritmo de Kosaraju.

kosaraju_connected_components() toma un digrafo g, "supuestamente débilmente 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 la función copy_graph().

La función se basa en el algoritmo de Tarjan.

La función emplea dos parámetros tipo:

  1. GT: la clase digrafo.
  2. SA: el filtro de arcos que emplea el iterador interno.

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]gel grafo.
[out]blk_listlista de sub-grafos mapeados a g correspondiente a los componentes fuertemente conexos de g.
[out]arc_listlista de arcos de cruce entre los componentes.
Ver también
tarjan_connected_components()

Hace referencia a Aleph::DynArray< T >::access(), Aleph::DynDlist< T >::append(), IS_NODE_VISITED, Aleph::Filter_Iterator< Container, It, Show_Item >::next(), NODE_COLOR y Aleph::DynArray< T >::size().

+ Gráfico de llamadas para esta función:

template<class GT , class SA >
void Aleph::kosaraju_connected_components ( GT &  g,
DynDlist< DynDlist< typename GT::Node * > > &  list 
)
inline

Calcula los componentes fuertemente conexos de un grafo según el algoritmo de Kosaraju.

kosaraju_connected_components() toma un digrafo g, "supuestamente débilmente 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 la función copy_graph().

La función se basa en el algoritmo de Kosaraju, el cual no es el más eficiente conocido pero sí es el más simple.

La función emplea dos parámetros tipo:

  1. GT: la clase digrafo.
  2. SA: el filtro de arcos que emplea el iterador interno.

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.

La diferencia y ventaja de esta rutina respecto a la versiòn que calcula los bloques directos es su rapidez; los bloque son comprendidos en listas de listas de nodos y no en lista de subgrafos.

Parámetros
[in]gel grafo.
[out]listlista de listas de nodos que conforman los componentes. Cada lista es una listas de los nodos del componente.
Ver también
tarjan_connected_components()

Hace referencia a Aleph::DynArray< T >::access(), Aleph::DynDlist< T >::append(), IS_NODE_VISITED y Aleph::DynArray< T >::size().

+ Gráfico de llamadas para esta función:

template<class GT , class SA = Dft_Show_Arc<GT>>
void Aleph::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.

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]gel grafo al cual se le desea copiar y mapear sus nodos y arcos de corte y arcos de cruce.
[in]cut_node_listlista con los nodos de corte la cual debería de ser la resultante de la llamada a compute_cut_nodes().
[out]cut_graphgrafo 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_listlista 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_allocsi 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()

Hace referencia a Aleph::DynDlist< T >::append(), Aleph::clear_graph() y Aleph::Filter_Iterator< Container, It, Show_Item >::next().

+ Gráfico de llamadas para esta función:

template<class GT , class SA = Dft_Show_Arc<GT>>
void Aleph::map_subgraph ( GT &  g,
GT &  sg,
const long &  color 
)

Copia mapeada de un subgrafo según un color.

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]gel grafo sobre el cual extraer el subgrafo del color específico.
[out]sgun grafo donde colocar la copia del bloque según el color; este grafo es limpiado antes de comenzar el procedimiento.
[in]colorel color que se desea extraer.
Excepciones
bad_allocsi 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()

Hace referencia a Aleph::clear_graph() y NODE_BITS.

+ Gráfico de llamadas para esta función:

template<class GT , class SA = Dft_Show_Arc<GT>>
long Aleph::paint_subgraphs ( GT &  g,
const DynDlist< typename GT::Node * > &  cut_node_list 
)
inline

Pinta un grafo conexo según sus nodos de corte.

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]gel grafo a pintar.
[in]cut_node_listlista 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()
template<class GT , class Distance , class Compare = Aleph::less<typename Distance::Distance_Type>, class Plus = Aleph::plus<typename Distance::Distance_Type>, class SA = Dft_Show_Arc<GT>>
bool Aleph::q_bellman_ford_min_spanning_tree ( GT &  g,
typename GT::Node *  start_node,
GT &  tree 
)
inline

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.

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]gel grafo al cual se desea calcular el árbol abarcador mínimo.
[in]start_nodenodo inicio de los caminos mínimos.
[out]treeel 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.
Devuelve
false si el grafo no tiene ciclos negativos. De lo contrario, se retorna true
Excepciones
bad_allocsi 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()

Hace referencia a ARC_BITS, Aleph::clear_graph(), IS_NODE_VISITED, Aleph::Filter_Iterator< Container, It, Show_Item >::next(), NODE_BITS y NODE_COOKIE.

+ Gráfico de llamadas para esta función:

template<class GT , class SA >
GT::Arc * Aleph::search_arc ( GT &  g,
typename GT::Node *  src_node,
typename GT::Node *  tgt_node 
)

Búsqueda de arco que conecta a dos nodos.

Esta función genérica recibe dos nodos y retorna el primer arco que los conecte si en efecto los nodos están conectados; de lo contrario, la rutina retorna el valor NULL.

La función toma dos parámetros tipo:

  1. GT: el tipo de grafo, el cual debe ser derivado de List_Graph.
  2. SA: clase que se encarga de mostrar el arco. Internamente, la función emplea el iterador filtro Node_Arc_Iterator (basado en Filter_Iterator) para recorrer los arcos de cada nodo. SA es el la clase que determina si el arco debe o no mostrarse al recorrido.

Una especialización prescinde del parámetro tipo SA y muestra todos los arcos del grafo sin filtrado alguno.

Si se trata de un digrafo (grafo dirigido), entonces la rutina considera la dirección del arco; es decir, que exista un arco dirigido desde src_node hacia tgt_node.

La búsqueda sólo se remite los arcos de los nodos involucrados. Por tanto, este tipo de búsqueda es mucho rápido que la búsqueda de arco basada en otro criterio.

Si el grafo no es dirigido, entonces la rutina selecciona el nodo de menor grado para buscar entre sus arcos.

La rutina utiliza el iterador Node_Arc_Iterator para recorrer los arcos de uno de los nodos.

Eventualmente, el iterador Node_Arc_Iterator puede sobrecargarse para descartar, según la índole del problema, arcos que no se desea mostrar. El uso típico de esta técnica es para representaciones extendidas que añaden arcos que no son parte del grafo modelo; por ejemplo, un grafo residual para el problema del flujo máximo.

Parámetros
[in]gel grafo o digrafo donde se realiza la búsqueda.
[in]src_nodenodo origen del arco.
[in]tgt_nodenodo origen del arco.
Devuelve
puntero al primer arco encontrado; NULL de lo contrario.

Hace referencia a Aleph::Filter_Iterator< Container, It, Show_Item >::next().

Referenciado por Aleph::Path< GT >::append(), Aleph::Path< GT >::insert() y Aleph::Concurrent_Graph< List_Graph, Ant_Node, Ant_Arc >::search_arc().

+ Gráfico de llamadas para esta función:

+ Gráfico de llamadas a esta función:

template<class GT >
bool Aleph::search_cycle ( GT &  g,
DynArray< typename GT::Node * > &  pred,
DynArray< typename GT::Arc * > &  arcs,
Path< GT > &  cycle 
)

Busca un ciclo negativo según los resultados parciales de algoritmo de Bellman-Ford.

El método search_cycle() examina los arreglos empleados por el algoritmo de Bellman-Ford y determina si el grafo contiene o no.

Eventualmente, el método puede emplearse independientemente del algoritmo de Bellman-Ford, sobre los arreglos (a condición de que sean válidos) para detectar si existe o no un ciclo y calcularlo.

El algoritmo de Bellman-Ford se emplea para calcular un árbol abarcador de todos los caminos mínimos desde el nodo start pertenenciente al digrafo g.

Durante la ejecución del algoritmo de Bellman-Ford se emplean los arreglos pred y arcs para definir el árbol abarcador. Si el grafo contiene un ciclo negativo, entonce esta representación contiene el ciclo. En ese sentido, search_cycle() examina los arreglos y determina si g contiene o no un ciclo negativo.

Parámetros
[in]gel grafo sobre el cual se calcula un árbol abarcador de todos los caminos mínimos.
[in]predarreglo de nodos padre del árbol abarcador.
[in]arcsarreglo de arcos que conforman el árbol abarcador.
[out]cycleun ciclo negativo contenido en g. El valor de cycle sólo tiene sentido si el grafo en efecto contiene un ciclo.
Devuelve
true si el grafo contiene un ciclo; false de lo contrario.
Excepciones
bad_allocsi no hay suficiente memoria para construir las estructuras alternas de cálculo.
Nota
Los arreglos pred y arcs deben corresponderse a los generados por cualquiera de las rutinas de caminos mínimos basadas en el algoritmo de Bellman-Ford.
Ver también
bellman_ford_min_spanning_tree() q_bellman_ford_min_spanning_tree()

Hace referencia a Aleph::DynArray< T >::access(), Aleph::Path< GT >::append(), ARC_COOKIE, Aleph::DynMapTree< Key, Type, Avl_Tree, Compare >::find(), Aleph::Dlink::Iterator::has_current(), Aleph::DynMapTree< Key, Type, Avl_Tree, Compare >::insert(), NODE_COOKIE, Aleph::Path< GT >::set_graph() y Aleph::DynArray< T >::size().

+ Gráfico de llamadas para esta función:

template<class GT , class Init_Node , class Init_Arc >
GT Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::sufficient_hamiltonian ( const size_t &  __num_nodes,
const double &  p = 0.5 
)
inline

Crea un grafo aleatorio hamiltoniano.

Esta versión construye un grafo aleatorio hamiltoniano.

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

Atención
El procedimiento puede ser extremadamente lento y goloso en memoria conforme aumente el valor de __num_nodes.
El grafo se asegura a ser hamiltoniano por los teoremas de Ore y Dirac. En este sentido, nótese que que la condición de hamiltoniano es de suficiencia, lo cual significa que no se trata de un grafo mínimo. De hecho, el grafo generado tiende a ser denso.
Parámetros
[in]__num_nodescantidad de nodos que debe tener el grafo.
[in]pprobabilidad de existencia de arco entre cualquier par de nodos. Por omisión este parámetro tiene valor 0.5, valor que intuitiva y empíricamente tiende a generar menor arcos y consumir menos tiempo.
Devuelve
puntero al grafo aleatorio creado.
Excepciones
bad_allocsi no hay suficiente memoria.
domain_errorsi 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 >::sufficient_hamiltonian ( const size_t &  __num_nodes,
const double &  p = 0.5 
)
inline

Crea un grafo aleatorio hamiltoniano.

Esta versión construye un grafo aleatorio hamiltoniano.

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

Atención
El procedimiento puede ser extremadamente lento y goloso en memoria conforme aumente el valor de __num_nodes.
El grafo se asegura a ser hamiltoniano por los teoremas de Ore y Dirac. En este sentido, nótese que que la condición de hamiltoniano es de suficiencia, lo cual significa que no se trata de un grafo mínimo. De hecho, el grafo generado tiende a ser denso.
Parámetros
[in]__num_nodescantidad de nodos que debe tener el grafo.
[in]pprobabilidad de existencia de arco entre cualquier par de nodos. Por omisión este parámetro tiene valor 0.5, valor que intuitiva y empíricamente tiende a generar menor arcos y consumir menos tiempo.
Devuelve
puntero al grafo aleatorio creado.
Excepciones
bad_allocsi no hay suficiente memoria.
domain_errorsi el valor de p no está entre 0 y 1.
template<class GT , class SA = Dft_Show_Arc<GT>>
bool Aleph::test_connectivity ( GT &  g)
inline

Retorna true si el grafo g es conexo.

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

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.

La función toma dos parámetros tipo:

  1. GT: el tipo de grafo, el cual debe ser derivado de List_Graph
  2. SA: clase que se encarga de mostrar el arco. Internamente, la función emplea el iterador filtro Node_Arc_Iterator (basado en Filter_Iterator) para recorrer los arcos de cada nodo. SA es el la clase que determina si el arco debe o no mostrarse al recorrido.
Parámetros
[in]gel 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.
Excepciones
domain_errorsi la rutina es invocada sobre un digrafo.
Ver también
depth_first_traversal() is_reachable()
template<class GT , class SA = Dft_Show_Arc<GT>>
bool Aleph::test_for_cycle ( GT &  g,
typename GT::Node *  src_node 
)
inline

Retorna true si existe un ciclo desde el nodo src_node.

test_for_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]gel grafo a verificar.
[in]src_nodeel nodo que se quiere verificar.
Devuelve
true si existe un ciclo; false de lo contrario.

Hace referencia a ARC_BITS, IS_ARC_VISITED y Aleph::Filter_Iterator< Container, It, Show_Item >::next().

+ Gráfico de llamadas para esta función:

template<class GT , class SA = Dft_Show_Arc<GT>>
bool Aleph::test_for_path ( GT &  g,
typename GT::Node *  start_node,
typename GT::Node *  end_node 
)
inline

Retorna true si existe un camino entre el nodo start_node y end_node.

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

La función toma dos parámetros tipo:

  1. GT: el tipo de grafo, el cual debe ser derivado de List_Graph.
  2. SA: clase que se encarga de mostrar el arco. Internamente, la función emplea el iterador filtro Node_Arc_Iterator (basado en Filter_Iterator) para recorrer los arcos de cada nodo. SA es el la clase que determina si el arco debe o no mostrarse al recorrido.

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

Parámetros
[in]gel grafo a buscar camino.
[in]start_nodepuntero al nodo origen del camino.
[in]end_nodepuntero 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()

Hace referencia a ARC_BITS y Aleph::Filter_Iterator< Container, It, Show_Item >::next().

+ Gráfico de llamadas para esta función:

template<class GT , template< class > class Max_Flow = Random_Preflow_Maximum_Flow, class SA = Dft_Show_Arc<GT>>
long Aleph::vertex_connectivity ( GT &  g)

Calcula la conectividad en nodos o vértices de un grafo.

Esta rutina se vale de un algoritmo de maximización de flujo para calcular la conectividad en nodos de un grafo. Como tal, su segundo parámetro plantilla es el algoritmo de maximización de flujo.

Parámetros
[in]gel grafo.

Hace referencia a Aleph::DynDlist< T >::append(), Aleph::DynMapTree< Key, Type, Treap, Compare >::find(), Aleph::DynDlist< T >::get(), Aleph::Dlink::Iterator::has_current(), Aleph::DynMapTree< Key, Type, Treap, Compare >::insert(), Aleph::Dlink::is_empty(), Aleph::Filter_Iterator< GT, GT::Node_Iterator, Show_Node >::next(), Aleph::Filter_Iterator< Container, It, Show_Item >::next() y NODE_COOKIE.

+ Gráfico de llamadas para esta función:

template<class GT , class SA = Dft_Show_Arc<GT>>
void Aleph::warshall_compute_transitive_clausure ( GT &  g,
Bit_Mat_Graph< GT, SA > &  mat 
)

Cálculo de la clausura transitiva de una matriz de adyacencia.

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]gel grafo representado mediante una variante de List_Graph.
[out]matmatriz de bits donde se coloca el resultado.
Excepciones
bad_allocsi no hay suficiente memoria.
Ver también
List_Graph Bit_Mat_Graph

Hace referencia a Aleph::Bit_Mat_Graph< GT, SA >::get_list_graph(), Aleph::Bit_Mat_Graph< GT, SA >::get_num_nodes() y Aleph::Bit_Mat_Graph< GT, SA >::set_list_graph().

+ Gráfico de llamadas para esta función:

Leandro Rabindranath León