Aleph-w  1.9
General library for algorithms and data structures
Public Types | Public Member Functions | Static Public Member Functions | Public Attributes | Protected Member Functions | Protected Attributes | List of all members
Aleph::Net_Sup_Dem_Graph< NodeT, ArcT > Class Template Reference
Graphs | Redes de Flujo.

#include <tpl_net_sup_dem.H>

+ Inheritance diagram for Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >:
+ Collaboration diagram for Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >:

Public Types

typedef Net_Graph< NodeT, ArcT > Net_Class
 La clase de red tradicional.
 
typedef ArcT Arc
 Tipo de arco.
 
typedef NodeT Node
 Tipo de node.
 
typedef Arc::Flow_Type Flow_Type
 Tipo que representa la capacidad y el flujo.
 
typedef Node::Node_Type Node_Type
 Tipo de atributo que almacena un nodo.
 
typedef Arc::Arc_Type Arc_Type
 Tipo de atributo que almacena un arco.
 
typedef Net_Sup_Dem_Graph Aux_Net
 El tipo de red capacitada auxiliar equivalente.
 
using Net = Net_Graph< NodeT, ArcT >
 
using Base = Array_Graph< NodeT, ArcT >
 
using Graph = Base
 
using CommonBase = GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc >, __Graph_Node, __Graph_Arc >
 
using Filter_Iterator = Digraph_Iterator< Filt >
 
using In_Iterator = Digraph_Iterator< In_Filt >
 
using Out_Iterator = Digraph_Iterator< Out_Filt >
 
using ArcPair = tuple< __Graph_Arc *, __Graph_Node *>
 Pair of arc and node (topologically related)
 

Public Member Functions

Node * insert_node (const Node_Type &node_info, const Flow_Type &supply=0)
 
Node * insert_node (const Flow_Type &supply=0)
 
bool exist_aux_net () const
 Retorna true si la red auxiliar ya ha sido creada.
 
Net_Sup_Dem_Graph * compute_aux_net ()
 
Net_Sup_Dem_Graph * get_aux_net ()
 
bool is_feasible () const
 
void non_feasible_nodes (DynDlist< Node *> &supply_list, DynDlist< Node *> &demand_list)
 
void set_supply_flow (Node *p, const Flow_Type &supply)
 
void free_aux_net ()
 Libera memoria de la red extendida.
 
DynList< Arc * > out_arcs (Node *p) const noexcept
 Arcos que salen desde p.
 
DynList< Node * > out_nodes (Node *p) const noexcept
 
DynList< Arc * > in_arcs (Node *p) const noexcept
 
DynList< Node * > in_nodes (Node *p) const noexcept
 
Flow_Type get_in_cap (Node *node) const noexcept
 Retorna la capacidad total de entrada del nodo node.
 
Flow_Type get_out_cap (Node *node) const noexcept
 Retorna la capacidad total de salida del nodo node.
 
size_t get_in_degree (Node *p) const noexcept
 
size_t get_out_degree (Node *p) const noexcept
 
Flow_Type get_out_flow (Node *node) const noexcept
 Retorna el valor de flujo de salida del nodo.
 
Flow_Type get_in_flow (Node *node) const noexcept
 Retorna el valor de flujo de entrada del nodo.
 
bool is_source (Node *node) noexcept
 Retorna true si node es fuente.
 
bool is_sink (Node *node) noexcept
 Retorna true si node es sumidero.
 
bool is_single_source () const noexcept
 Retorna true si la red es de un solo fuente.
 
bool is_single_sink () const noexcept
 Retorna true si la red es de un solo sumidero.
 
bool is_connected (Node *p) const noexcept
 
bool check_node (Node *node) noexcept
 
const DynSetTree< Node * > & get_src_nodes () const noexcept
 Retorna el conjunto de nodos fuente que contiene la red.
 
const DynSetTree< Node * > & get_sink_nodes () const noexcept
 Retorna el conjunto de nodos sumidero que contiene la red.
 
void make_super_source ()
 
void unmake_super_source () noexcept
 
void make_super_sink ()
 
void unmake_super_sink () noexcept
 
void make_super_nodes ()
 
void unmake_super_nodes ()
 
Node * get_source () const
 Retorna un nodo fuente de la red.
 
Node * get_sink () const
 Retorna un nodo sumidero de la red.
 
Node * insert_node (const Node_Type &node_info)
 
Node * insert_node (Node_Type &&info=Node_Type())
 
Node * insert_node (Node *p)
 
__Graph_Node * insert_node (const Node_Type &node_info)
 
__Graph_Node * insert_node (Node_Type &&node_info=Node_Type())
 
template<typename ... Args>
Node * emplace_node (Args &&... args)
 
Arc * insert_arc (Node *src_node, Node *tgt_node, const Flow_Type &cap, const Flow_Type &flow, const typename Arc::Arc_Type &arc_info=Arc_Type())
 
Arc * insert_arc (Node *src_node, Node *tgt_node, const Flow_Type &cap)
 
Arc * insert_arc (Node *src_node, Node *tgt_node, const typename Arc::Arc_Type &arc_info=Arc_Type())
 
__Graph_Arc * insert_arc (__Graph_Node *src, __Graph_Node *tgt, const Arc_Type &arc_info)
 
__Graph_Arc * insert_arc (__Graph_Node *src, __Graph_Node *tgt, Arc_Type &&arc_info=Arc_Type())
 
template<typename ... Args>
Arc * emplace_arc (Node *src_node, Node *tgt_node, const Flow_Type &cap, const Flow_Type &flow, Args &&... args)
 
__Graph_Arc * emplace_arc (__Graph_Node *src, __Graph_Node *tgt, Args &&... args)
 
Arc * connect_arc (Arc *arc)
 
virtual void remove_arc (Arc *arc)
 Elimina de la red el arco arc.
 
void disconnect_arc (Arc *arc) noexcept
 
virtual void remove_node (Node *p) noexcept
 Elimina un nodo de una red de flujo junto con todos sus arcos.
 
void set_cap (Arc *arc, const Flow_Type &cap)
 Coloca valor de capacidad a un arco.
 
void set_flow (Arc *arc, const Flow_Type &flow)
 
const Flow_Type & get_flow (Arc *arc) const noexcept
 retorna el valor de capacidad del arco.
 
const Flow_Type & get_cap (Arc *arc) const noexcept
 Retorna el valor de flujo de un arco.
 
void reset () noexcept
 
bool check_network ()
 
Flow_Type flow_value () const
 
void compress ()
 
Node * get_first_node () const
 
Arc * get_first_arc () const
 
Arc * get_first_arc (Node *p) const
 
void swap (Array_Graph &g) noexcept
 
template<class Compare >
void sort_nodes (Compare &cmp) noexcept
 
template<class Compare >
void sort_nodes (Compare &&cmp=Compare()) noexcept
 
template<class Compare >
void sort_arcs (Compare &cmp)
 
template<class Compare >
void sort_arcs (Compare &&cmp)
 
void *& get_cookie () noexcept
 Return a modifiable reference to graph's cookie.
 
void * get_cookie () const noexcept
 Return a constant reference to graph's cookie.
 
void *& get_cookie (__Graph_Node *node) const noexcept
 Get a modifiable reference to the cookie pointer of node
 
void *& get_cookie (__Graph_Arc *arc) const noexcept
 Get a modifiable reference to the cookie pointer of arc
 
bool is_digraph () const noexcept
 Return true if the graph this is directed.
 
void set_digraph (bool val)
 
size_t get_num_nodes () const noexcept
 Return the total of nodes of graph.
 
size_t vsize () const noexcept
 get_num_nodes()
 
__Graph_Node * get_node () const
 
__Graph_Node * get_arc () const
 
__Graph_Node * get_arc (__Graph_Node *p)
 
__Graph_Node * get_src_node (__Graph_Arc *arc) const noexcept
 Return the source node of arc (only for directed graphs)
 
__Graph_Node * get_tgt_node (__Graph_Arc *arc) const noexcept
 Return the target node of arc (only for directed graphs)
 
__Graph_Node * get_connected_node (__Graph_Arc *arc, __Graph_Node *node) const noexcept
 
size_t get_num_arcs () const noexcept
 
size_t get_num_arcs (__Graph_Node *node) const noexcept
 
size_t degree (__Graph_Node *p) const noexcept
 
size_t esize () const noexcept
 Return the total of arcs of graph.
 
Bit_Fields & get_control_bits (__Graph_Node *node) const noexcept
 Return a reference to control fields of node
 
Bit_Fields & get_control_bits (__Graph_Arc *arc) const noexcept
 Return a reference to the control bits of arc
 
void reset_bit (__Graph_Node *node, int bit) const noexcept
 Reset the bit of node (to zero)
 
void reset_bit (__Graph_Arc *arc, int bit) const noexcept
 Reset the bit of arc to zero.
 
void reset_bits (__Graph_Node *node) const noexcept
 Reset all the control bits of node
 
void reset_bits (__Graph_Arc *arc) const noexcept
 Reset all the control bits of arc
 
int get_bit (__Graph_Node *node, int bit) const noexcept
 Get the control bit of node
 
int get_bit (__Graph_Arc *arc, int bit) const noexcept
 Get the control bit of arc
 
void set_bit (__Graph_Node *node, int bit, int value) const noexcept
 Set the control bit of node to value
 
void set_bit (__Graph_Arc *arc, int bit, int value) const noexcept
 Set the control bit of arc to value
 
long & get_counter (__Graph_Node *node) const noexcept
 Get a modifiable reference to the counter of node
 
long & get_counter (__Graph_Arc *arc) const noexcept
 Get a modifiable reference to the counter of arc
 
void reset_counter (__Graph_Node *node) const noexcept
 Reset the node counter to zero.
 
void reset_counter (__Graph_Arc *arc) const noexcept
 Reset the acr counter to zero.
 
void reset_node_counters () const noexcept
 Reset all the node counters of graph to zero.
 
void reset_node (__Graph_Node *p) const noexcept
 
void reset_arc_counters () const noexcept
 Reset all the arc counters of graph to zero.
 
void reset_arc (__Graph_Arc *arc) const noexcept
 
void reset_nodes () const
 
void reset_arcs () const
 
void reset_bit_nodes (int bit) const noexcept
 Reset bit to zero for all the nodes of graph.
 
void reset_bit_nodes () const noexcept
 Reset all the bits for all the nodes of graph.
 
void reset_bit_arcs (int bit) const noexcept
 Reset bit to zero for all the arcs of graph.
 
void reset_bit_arcs () const noexcept
 Reset all the bits for all the arcs of graph.
 
void reset_counter_nodes () const noexcept
 Reset all the counters to zero for all the nodes of graph.
 
void reset_counter_arcs () const noexcept
 Reset all the counters to zero for all the arcs of graph.
 
void reset_cookie_nodes () const noexcept
 
void reset_cookie_arcs () const noexcept
 
bool traverse_nodes (Operation &op) const noexcept(noexcept(op))
 
bool traverse_nodes (Operation &&op=Operation()) const noexcept(noexcept(op))
 
bool traverse_arcs (Operation &op) const noexcept(noexcept(op))
 
bool traverse_arcs (Operation &&op=Operation()) const noexcept(noexcept(op))
 
bool traverse_arcs (__Graph_Node *p, Operation &op) const noexcept(noexcept(op))
 
bool traverse_arcs (__Graph_Node *p, Operation &&op=Operation()) const noexcept(noexcept(op))
 
bool traverse_arcs (__Graph_Node *p, Operation &op) const noexcept(noexcept(op))
 
void for_each_node (Operation &operation) const noexcept(noexcept(operation))
 
void for_each_node (Operation &&operation=Operation()) const
 
void for_each_arc (Operation &op) const noexcept(noexcept(op))
 
void for_each_arc (Operation &&operation=Operation()) const
 
void for_each_arc (__Graph_Node *p, Operation &op) const noexcept(noexcept(op))
 
void for_each_arc (__Graph_Node *p, Operation &&op=Operation()) const noexcept(noexcept(op))
 for_each_arc(Node * p, Operation & operation)
 
void for_each_arc (__Graph_Node *p, Operation &op) const noexcept(noexcept(op))
 Perform operation on each arc of node p
 
bool all_nodes (Operation &op) const noexcept(noexcept(op))
 
bool all_nodes (Operation &&op=Operation()) const noexcept(noexcept(op))
 
bool all_arcs (Operation &op) const noexcept(noexcept(op))
 
bool all_arcs (Operation &&op=Operation()) const noexcept(noexcept(op))
 
bool all_arcs (__Graph_Node *p, Operation &op) const noexcept(noexcept(op))
 
bool all_arcs (__Graph_Node *p, Operation &&op=Operation()) const noexcept(noexcept(op))
 
auto nodes_map (std::function< T(__Graph_Node *)> op) const
 
auto arcs_map (std::function< T(__Graph_Arc *)> operation) const
 
auto arcs_map (__Graph_Node *p, std::function< T(__Graph_Arc *)> operation) const
 
T foldl_nodes (const T &init, std::function< T(const T &, __Graph_Node *)> op) const
 
T foldl_arcs (const T &init, std::function< T(const T &, __Graph_Arc *)> op) const
 
T foldl_arcs (__Graph_Node *p, const T &init, std::function< T(const T &, __Graph_Arc *)> op) const
 
auto filter_nodes (Op &op) const
 
auto filter_nodes (Op &&op) const
 
auto filter_arcs (Op &op) const
 
auto filter_arcs (Op &&op) const
 
auto filter_arcs (__Graph_Node *p, Op &op) const
 
auto filter_arcs (__Graph_Node *p, Op &&op) const
 
bool exists_node (Operation &op) const noexcept(noexcept(op))
 
bool exists_node (Operation &&op=Operation()) const noexcept(noexcept(op))
 
bool exists_arc (Operation &op) const noexcept(noexcept(op))
 
bool exists_arc (Operation &&op=Operation()) const noexcept(noexcept(op))
 
bool exists_arc (__Graph_Node *p, Operation &op) const noexcept(noexcept(op))
 
bool exists_arc (__Graph_Node *p, Operation &&op=Operation()) const noexcept(noexcept(op))
 
__Graph_Node * search_node (Op &op) const noexcept(noexcept(op))
 
__Graph_Node * search_node (Op &&op) const noexcept(noexcept(op))
 
__Graph_Node * find_node (const Node_Type &info) const noexcept
 
__Graph_Arc * search_arc (Op &op) const noexcept(noexcept(op))
 
__Graph_Arc * search_arc (Op &&op) const noexcept(noexcept(op))
 
__Graph_Arc * search_arc (__Graph_Node *p, Operation &op) const noexcept(noexcept(op))
 
__Graph_Arc * search_arc (__Graph_Node *p, Operation &&op=Operation()) const noexcept(noexcept(op))
 
__Graph_Arc * search_arc (__Graph_Node *src, __Graph_Node *tgt) const noexcept
 
__Graph_Arc * find_arc (const Arc_Type &info) const noexcept
 
Container< __Graph_Node *> nodes () const
 
Container< __Graph_Arc *> arcs () const
 
Container< __Graph_Arc *> arcs (__Graph_Node *p) const
 
auto get_node_it () const noexcept
 
auto get_arc_it () const noexcept
 
auto get_arc_it (__Graph_Node *p) const noexcept
 
In_Iterator get_in_it (__Graph_Node *p) const noexcept
 
Out_Iterator get_out_it (__Graph_Node *p) const noexcept
 
__Graph_Arc * search_directed_arc (__Graph_Node *src, __Graph_Node *tgt) const noexcept
 
auto in_pairs (__Graph_Node *p) const
 
auto out_pairs (__Graph_Node *p) const
 
size_t in_degree (__Graph_Node *p) const noexcept
 
size_t out_degree (__Graph_Node *p) const noexcept
 
bool traverse_in_arcs (__Graph_Node *p, Op &op) const noexcept(noexcept(op))
 
bool traverse_in_arcs (__Graph_Node *p, Op &&op=Op()) const noexcept(noexcept(op))
 
void for_each_in_arc (__Graph_Node *p, Op &op) const noexcept(noexcept(op))
 Perform operation on each incoming arc of node p
 
void for_each_in_arc (__Graph_Node *p, Op &&op=Op()) const noexcept(noexcept(op))
 
bool all_in_arcs (__Graph_Node *p, Op &op) const noexcept(noexcept(op))
 Return true if op is true for all the incoming arcs to node p
 
bool all_in_arcs (__Graph_Node *p, Op &&op=Op()) const noexcept(noexcept(op))
 
bool exists_in_arc (__Graph_Node *p, Op &op) const noexcept(noexcept(op))
 
bool exists_in_arc (__Graph_Node *p, Op &&op=Op()) const noexcept(noexcept(op))
 
auto search_in_arc (__Graph_Node *p, Op &op) const noexcept(noexcept(op))
 
auto search_in_arc (__Graph_Node *p, Op &&op=Op()) const noexcept(noexcept(op))
 
auto in_arcs_map (__Graph_Node *p, std::function< T(__Graph_Arc *)> op) const noexcept(noexcept(op))
 
T foldl_in_arcs (__Graph_Node *p, const T &init, std::function< T(const T &, __Graph_Arc *)> op) const noexcept(noexcept(op))
 
DynList< __Graph_Arc *> filter_in_arcs (__Graph_Node *p, Op &op) const
 
auto filter_in_arcs (__Graph_Node *p, Op &&op=Op()) const
 
bool traverse_out_arcs (__Graph_Node *p, Op &op) const noexcept(noexcept(op))
 
bool traverse_out_arcs (__Graph_Node *p, Op &&op=Op()) const noexcept(noexcept(op))
 
void for_each_out_arc (__Graph_Node *p, Op &op) const noexcept(noexcept(op))
 Perform operation on each incoming arc of node p
 
void for_each_out_arc (__Graph_Node *p, Op &&op=Op()) const noexcept(noexcept(op))
 
bool all_out_arcs (__Graph_Node *p, Op &op) const noexcept(noexcept(op))
 Return true if op is true for all the outcoming arcs to node p
 
bool all_out_arcs (__Graph_Node *p, Op &&op=Op()) const noexcept(noexcept(op))
 
bool exists_out_arc (__Graph_Node *p, Op &op) const noexcept(noexcept(op))
 
bool exists_out_arc (__Graph_Node *p, Op &&op=Op()) const noexcept(noexcept(op))
 
auto search_out_arc (__Graph_Node *p, Op &op) const noexcept(noexcept(op))
 
auto search_out_arc (__Graph_Node *p, Op &&op=Op()) const noexcept(noexcept(op))
 
auto out_arcs_map (__Graph_Node *p, std::function< T(__Graph_Arc *)> op) const
 
T foldl_out_arcs (__Graph_Node *p, const T &init, std::function< T(const T &, __Graph_Arc *)> op) const noexcept(noexcept(op))
 
DynList< __Graph_Arc *> filter_out_arcs (__Graph_Node *p, Op &op) const noexcept(noexcept(op))
 
auto filter_out_arcs (__Graph_Node *p, Op &&op=Op()) const noexcept(noexcept(op))
 

Static Public Member Functions

static void map_nodes (N1 *p, N2 *q) noexcept
 
static void map_arcs (A1 *p, A2 *q) noexcept
 

Public Attributes

Flow_Type Infinity
 
bool with_super_source
 true si a la red se le ha añadido un supra fuente.
 
bool with_super_sink
 true si a la red se le ha añadido un supra sumidero.
 

Protected Member Functions

void init () noexcept
 
void common_swap (Array_Graph< __Graph_Node, __Graph_Arc > &g) noexcept
 

Protected Attributes

void * cookie
 
size_t num_nodes
 
size_t num_arcs
 
bool digraph
 

Detailed Description

template<class NodeT = Net_Sup_Dem_Node<Empty_Class, double>, class ArcT = Net_Arc<Empty_Class, double>>
class Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >

Red con provisiones de flujo.

Una red con provisiones de flujo es una en la cual algunos nodos tienen un valor de provisión de flujo. Si el valor es positivo, significa que el nodo provee un flujo máximo correspondiente al valor dado. Si el valor es negativo, significa que el nodo requiere recibir por sus arcos de entrada un flujo correspondiente al valor absoluto del valor dado.

En una red de provisiones, se dice que el flujo es factible si es posible satisfacer las demandas a partir de las provisiones. Para ello, se debe calcular una red capacitada equivalente y calcular el flujo máximo.

Member Typedef Documentation

◆ Filter_Iterator

using GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::Filter_Iterator = Digraph_Iterator<Filt>
inherited

Alias for Digraph_Iterator

◆ In_Iterator

using GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::In_Iterator = Digraph_Iterator<In_Filt>
inherited

Iterator on incoming arcs of node

◆ Out_Iterator

using GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::Out_Iterator = Digraph_Iterator<Out_Filt>
inherited

Iterator on incoming arcs of node

Member Function Documentation

◆ all_arcs() [1/4]

bool GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::all_arcs ( Operation &  op) const
inlinenoexceptinherited

Check if all the arcs of graph satisfy a boolean condition.

all_arcs() traverse each arc of graph and on each one the operation is tested. If operation returns true, then the next arc is inspected. Otherwise, the traversal stops and false is returned as result.

The operation must imperatively have the following structure: 

bool operation(Arc * p)

The idea is to perform a test and according to its result to return true is the test was passed, or false otherwise. For example, in order to check if all the arc content is odd you could do: 

g.all_arcs([] (auto a) { return a->get_info() % 2; });
Remarks
Note that all_arcs() is semantically equivalent to traverse_arcs().

The complexity for this primitive always is $O(E)$ worst case.

Parameters
[in]operationcondition to test on each arc.
Returns
true if all the arcs satisfy the condition; false otherwise.
See also
exists_arc()

◆ all_arcs() [2/4]

bool GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::all_arcs ( Operation &&  op = Operation()) const
inlinenoexceptinherited

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ all_arcs() [3/4]

bool GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::all_arcs ( __Graph_Node *  p,
Operation &  op 
) const
inlinenoexceptinherited

Check if all the arcs adjacent to a node satisfy an boolean condition.

all_arcs(p) traverse each arc adjacent to node p and on each one the operation is tested. If operation returns true, then the next arc is inspected. Otherwise, the traversal stops and false is returned as result.

The operation must imperatively have the following structure: 

bool operation(Arc * p)

The idea is to perform a test and according to its result to return true is the test was passed, or false otherwise. For example, in order to check if all the arc content is odd you could do:

g.all_arcs(p, [] (auto a) { return a->get_info() % 2; });

Remarks
Note that all_arcs(p) is semantically equivalent to traverse_arcs().

The complexity for this primitive always is $O(V)$ worst case for dense graphs.

Parameters
[in]pnode pointer
[in]operationcondition to test on each arc.
Returns
true if all the arcs satisfy the condition; false otherwise.
See also
bool exists_arc(Operation & operation)

◆ all_arcs() [4/4]

bool GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::all_arcs ( __Graph_Node *  p,
Operation &&  op = Operation() 
) const
inlinenoexceptinherited

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ all_in_arcs()

bool GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::all_in_arcs ( __Graph_Node *  p,
Op &&  op = Op() 
) const
inlinenoexceptinherited

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ all_nodes() [1/2]

bool GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::all_nodes ( Operation &  op) const
inlinenoexceptinherited

Check if all the nodes of graph satisfy an boolean condition.

all_nodes() traverse each node of graph and on each one operation is tested. If operation returns true, then the next node is inspected. Otherwise, the traversal stops and false is returned as result.

The operation must imperatively have the following structure: 

bool operation(Node * p)

The idea is to perform a test and according to its result to return true is the test was passed, or false otherwise. For example, in order to check if all the nodes content is even you could do: 

g.all_nodes([] (auto p) { return p->get_info() % 2 == 0; });
Remarks
Note that all_nodes() is semantically equivalent to traverse_nodes().

The complexity for this primitive always is $O(V)$ worst case.

Parameters
[in]operationcondition to test on each node.
Returns
true if all the nodes satisfy the condition; false otherwise.
See also
exists_node()

◆ all_nodes() [2/2]

bool GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::all_nodes ( Operation &&  op = Operation()) const
inlinenoexceptinherited

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ all_out_arcs()

bool GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::all_out_arcs ( __Graph_Node *  p,
Op &&  op = Op() 
) const
inlinenoexceptinherited

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ arcs() [1/2]

Container<__Graph_Arc *> GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::arcs ( ) const
inlineinherited

Return a container with all the arcs of the graph.

arcs() recollects all the arcs of the graph and builds a container with all them inserted. The container type is a template parameter, which by default is DynList.

Returns
a container, according the template parameter, with all the arcs into it.
Exceptions
bad_allocif there is no enough memory

◆ arcs() [2/2]

Container<__Graph_Arc *> GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::arcs ( __Graph_Node *  p) const
inlineinherited

Return a container with all the arcs adjacent to a node.

arcs() recollects all the arcs adjacent to node p and builds a container with all them inserted. The container type is a template parameter, which by default is DynList.

Returns
a container, according the template parameter, with all the arcs into it.
Exceptions
bad_allocif there is no enough memory

◆ arcs_map() [1/2]

auto GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::arcs_map ( std::function< T(__Graph_Arc *)>  operation) const
inlineinherited

Map the arcs of a graph to a specific range.

arcs_map(operation) produces a mapping list of the graph's arcs. The transformation is done by operation whose signature must imperatively be: 

T operation(Arc * a)

operation instruments a map from the arc to the range type T. By default, T is Arc_Type (the type associated to the arc's data). In this case, you do not require to specify the range type as template parameter. Otherwise, in order to the compiler can know the range type, you must specify it as template parameter.

Suppose by example that the arcs have integers and that you want to produce a mapping int –> string corresponding to string reprsentation of the data arc. Then you can do this as follows: 

auto l = g.map_arcs<string>([] (auto a) 
{
  return to_string(a->get_info());
});
Remarks
The name of this method (arcs_map() instead of map_arcs()) is due to the ambiguity that would cause with the map_arcs() intended for mapping the arcs through their cookies.
Note
In metaprogramming you will probably need add the template keyword before the name arcs_map<your-target-type>. 
g.template arcs_map<ulong>([] (auto p) { return p->get_info(); });
Parameters
[in]operationtransformation from ARc* to T to be performed on each arc.
Returns
a DynList<T> containing the mapping.
Exceptions
bad_allocif there is no enough memory for fuilding the dynamic list or anything else that can throw operation

◆ arcs_map() [2/2]

auto GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::arcs_map ( __Graph_Node *  p,
std::function< T(__Graph_Arc *)>  operation 
) const
inlineinherited

Map the adjacent arcs of a node to a specific range.

arcs_map(p, operation) produces a mapping list of the arcs adjacent to node p. The transformation is done by operation whose signature must imperatively be: 

T operation(Arc * a)

operation instruments a map from the arc to the range type T. By default, T is Arc_Type (the type associated to the arc's data). In this case, you do not require to specify the range type as template parameter. Otherwise, in order to compiler can know the range type, you must specify it as template parameter.

Suppose by example that the arcs have doubles and that you want to produce a mapping double –> $\sqrt double $. Then you can do this as follows: 

auto l = g.map_arcs([] (auto a) { return sqrt(a->get_info()); });

Since the return type is the same than the arc content, it would not be necessary to pass a template parameter indicating the range type. If this was not be the situation, then you would have to specify the range type as template parameter.

Remarks
The name of this method (arcs_map() instead of map_arcs()) is due to the ambiguity that would cause with the map_arcs() intended for mapping the arcs through their cookies.
Note
In metaprogramming you will probably need add the template keyword before the name arcs_map<your-target-type>. 
g.template arcs_map<ulong>([] (auto p) { return p->get_info(); });
Parameters
[in]operationtransformation from Arc* to T to be performed on each arc.
Returns
a DynList<T> containing the mapping.
Exceptions
bad_allocif there is no enough memory for fuilding the dynamic list or anything else that can throw operation

◆ check_network()

template<class NodeT = Net_Node<Empty_Class>, class ArcT = Net_Arc<Empty_Class, double>>
bool Aleph::Net_Graph< NodeT, ArcT >::check_network ( )
inlineinherited

Verifica si una red capacitada satisface las condiciones de definición.

check_network() recorre todos los nodos y arcos de una red capacitada en búsqueda de inconsistencias de definición. Básicamente, se verifica que para todo nodo no fuente o no sumidero la cantidad de flujo entrante sea igual a la saliente. Por cada arco inspeccionado se verifica que el flujo sea menor o igual que su capacidad.

Returns
true si la red es valida; false de lo contrario.
+ Here is the call graph for this function:

◆ check_node()

template<class NodeT = Net_Node<Empty_Class>, class ArcT = Net_Arc<Empty_Class, double>>
bool Aleph::Net_Graph< NodeT, ArcT >::check_node ( Node *  node)
inlinenoexceptinherited

Retorna true si el nodo node satisface las condiciones de flujo; es decir, que el flujo de entrada sea igual al de salida.

◆ compute_aux_net()

template<class NodeT = Net_Sup_Dem_Node<Empty_Class, double>, class ArcT = Net_Arc<Empty_Class, double>>
Net_Sup_Dem_Graph* Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::compute_aux_net ( )
inline

Calcula la red capacitada equivalente.

Dada una red con provisiones en los nodos (representada en this), compute_aux_net() calcula la red capacitada equivalente sobre la cual se pueden realizar cálculos de maximización de flujo, corte equivalente y, en particular, verificación de factibilidad de flujo.

La red capacitada equivalente se construye sobre la propia red de provisiones. Por esa razón, cualquier cálculo sobre la red equivalente es inmediatamente reflejado sobre la red con provisiones.

Returns
un puntero a la red equivalente.
Exceptions
bad_allocsi no hay suficiente memoria para crear la red equivalente.
domain_errorsi la red equivalente ya ha sido calculada.
domain_errorsi la red residual de la equivalente ya ha sido calculada.

◆ connect_arc()

template<class NodeT = Net_Node<Empty_Class>, class ArcT = Net_Arc<Empty_Class, double>>
Arc* Aleph::Net_Graph< NodeT, ArcT >::connect_arc ( Arc *  arc)
inlineinherited

Conecta un arco de red previamente insertado y desconectado.

Este método toma un puntero a un arco arc, previamente desconectado mediante, desconnect_arc(), y lo re-inserta en el grafo.

El arco, por supuesto, debe haber sido previamente insertado en el grafo. A este respecto, no se hace ninguna verificación.

No se realiza ninguna verificación de existencia previa de un arco entre los nodos involucrados (esto es necesario para operar con multigrafos).

Parameters
[in]arcpuntero al arco a re-insertar.
Returns
puntero al arco re-insertado
+ Here is the call graph for this function:

◆ degree()

size_t GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::degree ( __Graph_Node *  p) const
inlinenoexceptinherited

Return the total of arcs (or degree) of a node. Only has sense for non directed graphs

◆ disconnect_arc()

template<class NodeT = Net_Node<Empty_Class>, class ArcT = Net_Arc<Empty_Class, double>>
void Aleph::Net_Graph< NodeT, ArcT >::disconnect_arc ( Arc *  arc)
inlinenoexceptinherited

Desconecta de la red el arco arc.

La operación desconecta del grafo el arco arc. Eventualmente, el arco puede guardarse y luego reinsertarse mediante connect_arc().

El arco debe pertenecer al grafo y no se realiza ninguna verificación al respecto.

Parameters
[in]arcpuntero al arco a desconectar
+ Here is the call graph for this function:

◆ emplace_arc()

__Graph_Arc * GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::emplace_arc ( __Graph_Node *  src,
__Graph_Node *  tgt,
Args &&...  args 
)
inlineinherited

Insert a new arc in the graph by constructing its associated data in-place with the given args.

This method allows to insert a new arc in the graph bypassing innecesary copies. emplace_arc() allocates a new arc, takes the parameters received and calls to the constructor of data associated to the arc. Then the data is forwarded to the arc data constructor avoiding, if possible, innecessary copies. Once the arc is completely built, this is inserted, at this moment without any logic possibility of failure, into the graph.

Remarks
If this method does not throw exception, then this always returns a valid pointer,
Parameters
[in]srcpointer to the source node.
[in]tgtpointer to the target node.
[in]argsvariadic argument list for the construction of data associated to the arc.
Returns
a pointer to the new and inserted arc.
Exceptions
bad_allodif there is no enough memory.

◆ exists_arc() [1/4]

bool GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::exists_arc ( Operation &  op) const
inlinenoexceptinherited

Determine if exists at least a arc satisfying a condition.

exists_arc(op) returns true if at least a node of graph satisfies the condition expressed by operation.

The operation has $O(E)$ complexity for the worst case.

Remarks
Note that exists_arc() is the oppossite or complement of all_arcs(). In fact, exists_arc(op) could be written, in terms of all_arc(op) as follows: 
not g.all_arc([&op] (auto p) { return not op(p); });
Parameters
[in]operationfor testing existing condition
Returns
true if at least a node satisfaying the condition is found; false otherwise.
See also
all_arcs()

◆ exists_arc() [2/4]

bool GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::exists_arc ( Operation &&  op = Operation()) const
inlinenoexceptinherited

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ exists_arc() [3/4]

bool GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::exists_arc ( __Graph_Node *  p,
Operation &  op 
) const
inlinenoexceptinherited

Determine if exists at least a arc adjacent to a node satisfying a condition.

exists_arc(p, op) returns true if at least a node adjacent to p satisfies the condition expressed by operation.

The operation has $O(V)$ complexity for the worst case; concretely on dense graphs, but it trends to be much lesser for sparsed graphs.

Remarks
Note that exists_arc() is the oppossite or complement of all_arcs(). In fact, exists_arc(p, op) could be written, in terms of all_arc(p, op) as follows: 
not g.all_arc(p, [&op] (auto p) { return not op(p); });
Parameters
[in]pnode from which you want to access its arcs
[in]operationfor testing existing condition
Returns
true if at least a node satisfaying the condition is found; false otherwise.
See also
all_arcs(Node * p)

◆ exists_arc() [4/4]

bool GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::exists_arc ( __Graph_Node *  p,
Operation &&  op = Operation() 
) const
inlinenoexceptinherited

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ exists_in_arc() [1/2]

bool GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::exists_in_arc ( __Graph_Node *  p,
Op &  op 
) const
inlinenoexceptinherited

Return true if it exists a incoming arc to p returning true for op

◆ exists_in_arc() [2/2]

bool GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::exists_in_arc ( __Graph_Node *  p,
Op &&  op = Op() 
) const
inlinenoexceptinherited

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ exists_node() [1/2]

bool GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::exists_node ( Operation &  op) const
inlinenoexceptinherited

Determine if exists at least a node satisfying a condition.

exists_node(op) returns true if at least a node of graph satisfies the condition expressed by operation.

The operation has $O(V)$ complexity for the worst case.

Remarks
Note that exists_node() is the oppossite or complement of all_nodes(). In fact, exists_node(op) could be written, in terms of all_nodes(op) as follows: 
not g.all_nodes([&op] (auto p) { return not op(p); });
Parameters
[in]operationfor testing existing condition
Returns
true if at least a node satisfaying the condition is found; false otherwise.
See also
all_nodes()

◆ exists_node() [2/2]

bool GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::exists_node ( Operation &&  op = Operation()) const
inlinenoexceptinherited

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ exists_out_arc() [1/2]

bool GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::exists_out_arc ( __Graph_Node *  p,
Op &  op 
) const
inlinenoexceptinherited

Return true if it exists a outcoming arc to p returning true for op

◆ exists_out_arc() [2/2]

bool GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::exists_out_arc ( __Graph_Node *  p,
Op &&  op = Op() 
) const
inlinenoexceptinherited

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ filter_arcs() [1/4]

auto GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::filter_arcs ( Op &  op) const
inlineinherited

Filter the arcs of graph satisfying a condition.

filter_arcs(op) traverses each arc of graph and recolects those satisfying the condition expressed by op. op must match the following signature: 

bool op(Arc * a)

If op(p) returns true, then a is filtered (recollected) towards a final dynamic list containing the filtered arcs.

For example, if the arcs contain integers, then the following code snippet recollects those nodes whose value is greater than x: 

g.filter_arcs([x] (auto a) { return a->get_info() > x; });
Parameters
[in]opoperation implementing the filtering condition.
Returns
a DynList<Arc*> object containing the filtered arcs.
Exceptions
bad_allocif there is no enough memory for building the full returning list.

◆ filter_arcs() [2/4]

auto GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::filter_arcs ( Op &&  op) const
inlineinherited

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ filter_arcs() [3/4]

auto GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::filter_arcs ( __Graph_Node *  p,
Op &  op 
) const
inlineinherited

Filter the arcs adjacent to a node satisfying a condition.

filter_arcs(p, op) traverses each arc adjacent to node p and recolects those satisfying the condition expressed by op. op must match the following signature: 

bool op(Arc * a)

If op(p) returns true, then a is filtered (recollected) towards a final dynamic list containing the filtered arcs.

For example, in order to get the arcs whose target node have degree greater than n you could do it as follows: 

g.filter_arcs(p, [&g, p, n] (auto a) 
{
  return g.degree(g.get_connected_node(a, p)) > n;
});

Note the closure (or captured) data: the graph g, by reference in order to avoid copying it, the pointer p to te source node and the value of n.

Parameters
[in]ppointer to node wanted to explore and to filter its adjacent arcs.
[in]opoperation implementing the filtering condition.
Returns
a DynList<Arc*> object containing the filtered arcs.
Exceptions
bad_allocif there is no enough memory for building the full returning list.

◆ filter_arcs() [4/4]

auto GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::filter_arcs ( __Graph_Node *  p,
Op &&  op 
) const
inlineinherited

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ filter_in_arcs() [1/2]

DynList<__Graph_Arc *> GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::filter_in_arcs ( __Graph_Node *  p,
Op &  op 
) const
inlineinherited

Filter the incoming arcs of a node.

This method is analogous to filter_arcs() but only operates on the incoming arcs.

See also
filter_arcs(Node * p, Operation & operation)

◆ filter_in_arcs() [2/2]

auto GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::filter_in_arcs ( __Graph_Node *  p,
Op &&  op = Op() 
) const
inlineinherited

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ filter_nodes() [1/2]

auto GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::filter_nodes ( Op &  op) const
inlineinherited

Filter the nodes satisfying a condition.

filter_nodes(op) traverses each node of graph and recolects those satisfying the condition expressed by op. op must match the following signature: 

bool op(Node * p)

If op(p) returns true, then p is filtered (recollected) towards a final dynamic list containing the filtered nodes.

For example, if the nodes contain integer, then the following code snippet recollects those nodes whose value is greater than x: 

g.filter_nodes([x] (auto p) { return p->get_info() > x; });
Parameters
[in]opoperation implementing the filtering condition.
Returns
a DynList<Node*> object containing the filtered nodes.
Exceptions
bad_allocif there is no enough memory for building the full returning list.

◆ filter_nodes() [2/2]

auto GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::filter_nodes ( Op &&  op) const
inlineinherited

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ filter_out_arcs() [1/2]

DynList<__Graph_Arc *> GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::filter_out_arcs ( __Graph_Node *  p,
Op &  op 
) const
inlinenoexceptinherited

Filter the outcoming arcs of a node.

This method is analogous to filter_arcs() but only operates on the outcoming arcs.

See also
filter_arcs(Node * p, Operation & operation)

◆ filter_out_arcs() [2/2]

auto GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::filter_out_arcs ( __Graph_Node *  p,
Op &&  op = Op() 
) const
inlinenoexceptinherited

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ find_arc()

__Graph_Arc * GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::find_arc ( const Arc_Type &  info) const
inlinenoexceptinherited

Find an arc mathing a content.

find_arc(info), which is a wrapper to search_arc(), searches a arc whose get_info() result matches with the info parameter. The comparison is done via de operator == on the class Arc_Type, which is usually the case.

Parameters
[in]infoto be compared with arcs content
Returns
a valid pointer to a arc if there is one mathing info or nullptr otherwise.

◆ find_node()

__Graph_Node * GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::find_node ( const Node_Type &  info) const
inlinenoexceptinherited

Find a node mathing a content.

find_node(info), which is a wrapper to search_node(), search a nodo whose get_info() result matches with the info parameter. The comparison is done via de operator == on the class Node_Type, which is usually the case.

Parameters
[in]infoto be compared with nodes content
Returns
a valid pointer to a node if there is one mathing info or nullptr otherwise.

◆ flow_value()

template<class NodeT = Net_Node<Empty_Class>, class ArcT = Net_Arc<Empty_Class, double>>
Flow_Type Aleph::Net_Graph< NodeT, ArcT >::flow_value ( ) const
inlineinherited

Retorna el valor de flujo de la red visto desde el nodo fuente o sumidero p. Dispara excepción std::domain_error si p no es ni fuente ni sumidero.

◆ foldl_arcs() [1/2]

T GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::foldl_arcs ( const T &  init,
std::function< T(const T &, __Graph_Arc *)>  op 
) const
inlineinherited

Folding of arcs on a graph.

foldl_arcs(init, operation) traverse all arc of graph and maintain an accumulator value acc whose initial value is init. On each acr a, it performs operation(acu, a) which must match with the following signature: 

T operation(const T &, Arc * a)

So, on each call it is peformed: 

acc = operation(acc, a);

Therefore acc serve as an accumulator.

Since foldl_arcs() is defined via std::function wrapper, it is very important to match the expected signature of operation. A proper and sure way of quickly define operation is by using auto parameters.

For example, suppose that the arcs contain doubles and that you want to compute the total sum, then you could do it as follows: 

g.foldl_arcs(p, [] (auto acc, auto node)
{
  return acc + arc->get_info();
});
Parameters
[in]initinitial value of accumulator
[in]operationto be performed, which must match the signature previously explained.
Returns
the final value of accumulator after full traversal.

◆ foldl_arcs() [2/2]

T GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::foldl_arcs ( __Graph_Node *  p,
const T &  init,
std::function< T(const T &, __Graph_Arc *)>  op 
) const
inlineinherited

Folding of arcs of a node.

foldl_arcs(p, init, operation) traverse all the arcs adjacent to node p and maintain an accumulator value acc whose initial value is init. On each arc a, it performs operation(acu, a) which must match with the following signature: 

T operation(const T &, Arc * a)

So, on each call it is peformed: 

acc = operation(acc, a);

Therefore acc serves as an accumulator.

Since foldl_arcs() is defined via std::function wrapper, it is very important to match the expected signature of operation. A proper and sure way of quickly define operation is by using auto parameters.

For example, suppose that the arcs contain doubles and that you want to compute the total sum, then you could do it as follows: 

g.foldl_arcs(p, [] (auto acc, auto node)
{
  return acc + arc->get_info();
});
Parameters
[in]pnode from where to access its adjacent arcs
[in]initinitial value of accumulator
[in]operationto be performed, which must match the signature previously explained.
Returns
the final value of accumulator after full traversal.

◆ foldl_in_arcs()

T GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::foldl_in_arcs ( __Graph_Node *  p,
const T &  init,
std::function< T(const T &, __Graph_Arc *)>  op 
) const
inlinenoexceptinherited

Fold the incoming arcs of a node.

This method is analogous to foldl_arcs() but only operates on the incoming arcs.

See also
foldl_arcs(Node * p, const T & init, std::function<T(Arc *)> operation)

◆ foldl_nodes()

T GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::foldl_nodes ( const T &  init,
std::function< T(const T &, __Graph_Node *)>  op 
) const
inlineinherited

Folding of nodes on a graph.

foldl_nodes(init, operation) traverse all node of graph and maintain an accumulator value acc whose initial value is init. On each node p, it performs operation(acu, p) which must match with the following signature: 

T operation(const T &, Node * p)

So, on each call it is peformed: 

acc = operation(acc, p);

Therefore acc serve as an accumulator.

Since foldl_nodes() is defined via std::function wrapper, it is very important to match the expected signature of operation. A proper and sure way of quickly define operation is by using auto parameters.

For example, suppose that the nodes contain integers and that you want to compute the maximum value. Then you could do it as follows: 

g.foldl_nodes(numeric_limits<int>::min(), [] (auto acc, auto node)
{
  return max(acc, node->get_info();
});
Parameters
[in]initinitial value of accumulator
[in]operationto be performed, which must match the signature previously explained.
Returns
the final value of accumulator after full traversal.

◆ foldl_out_arcs()

T GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::foldl_out_arcs ( __Graph_Node *  p,
const T &  init,
std::function< T(const T &, __Graph_Arc *)>  op 
) const
inlinenoexceptinherited

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ for_each_arc() [1/3]

void GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::for_each_arc ( Operation &  op) const
inlinenoexceptinherited

Unconditionally traverse all the arcs of graph and on each one perform an operation.

for_each_arc() unconditionally traverse all the arcs of a graph and on each one performs operation, which must have the following signature: 

void operation(Arc * p)

The operation could be a function pointer matching that signature, a functor or a lambda. Note that the operation does not require return anything.

Your algorithm should not assume any particular order of visit.

If your goal is to initialize control state of the arcs, then don't use this method. Instead, use reset_arcs() or their derivatives according your situation.

The complexity for this primitive always is $O(E)$.

Parameters
[in]operationto be performed on each node.
Exceptions
anythingthat can throw operation.

◆ for_each_arc() [2/3]

void GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::for_each_arc ( Operation &&  operation = Operation()) const
inlineinherited

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ for_each_arc() [3/3]

void GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::for_each_arc ( __Graph_Node *  p,
Operation &  op 
) const
inlinenoexceptinherited

Unconditionally traverse all the arcs adjacnt to a node and on each one perform an operation.

for_each_ars(p) unconditionally traverse all the nodes of node p on each one performs operation, which must have the following signature: 

void operation(Arc * p)

The operation could be a function pointer matching that signature, a functor or a lambda. Note that the operation does not require return anything.

This probably is the most common primitive for algorithms on graphs.

The complexity for this primitive always is $O(V)$ worst case, but on sparsed graphs a fraction of $V$ or better $O(1)$ for special buy common graphs such as "small word" networks.

Your algorithm should not assume any particular order of visit.

Remarks
This primitive only has sense for non directed graph. Note that each seen arc does not distinguish to p. If you want to know the node connected to p then invoke to g.get_connected_node(a,p).
For directed graphs use for_each_in_arc() or for_each_out_arc()-
Parameters

◆ for_each_node() [1/2]

void GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::for_each_node ( Operation &  operation) const
inlinenoexceptinherited

Unconditionally traverse all the nodes of graph and on each one perform an operation.

for_each_node() unconditionally traverse all the nodes of a graph and on each one performs operation, whicsh must have the following signature: 

void operation(Node * p)

The operation could be a function pointer matching that signature, a functor or a lambda. Note that the operation does not require return anything.

Your algorithm should not assume any particular order of visit.

If your goal is to initialize control state of the nodes, then don't use this method. Instead, use reset_nodes() or their derivatives according your situation.

The complexity for this primitive always is $O(V)$.

Parameters
[in]operationto be performed on each node.
Exceptions
anythingthat can throw operation.

◆ for_each_node() [2/2]

void GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::for_each_node ( Operation &&  operation = Operation()) const
inlineinherited

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ for_each_out_arc()

void GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::for_each_out_arc ( __Graph_Node *  p,
Op &&  op = Op() 
) const
inlinenoexceptinherited

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ get_arc() [1/2]

__Graph_Node * GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::get_arc ( ) const
inlineinherited

Return any arc in the graph.

This method serves as an depart arc in the graph. Some algorithms only need an initial arc which could be anyone. In these cases, this method is indicated.

Returns
A pointer to a arc in the graph

◆ get_arc() [2/2]

__Graph_Node * GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::get_arc ( __Graph_Node *  p)
inlineinherited

Return any arc adjacent to a node.

This method serves as an arc of depart given a node. Some algorithms only need any arc adjacent to a node in order to start their computations. In these cases, this method is indicated.

Returns
A pointer to an arc adjacent to p

◆ get_arc_it() [1/2]

auto GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::get_arc_it ( ) const
inlinenoexceptinherited

Obtains an iterator to the arc of graph.

This method is useful for shorting the iterator initialization. A traditional way for writing an iterator is as follows: 

for (typename GT::Arc_Iterator it(g); it.has_curr(); it.next())
  operation on current arc

With get_arc_it() The previous snippet could be more shortly written thus: 

for (auto it = g.get_arc_it(); it.has_curr(); it.next())
  operation on current arc
Returns
an instantiated iterator on the arcs positioned at the first arc.

◆ get_arc_it() [2/2]

auto GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::get_arc_it ( __Graph_Node *  p) const
inlinenoexceptinherited

Obtains an iterator to the adjacent arcs of a node.

This method is useful for shorting the iterator initialization. A traditional way for writing an iterator on the arcs of a node is as follows: 

for (typename GT::Node_Arc_Iterator it(g); it.has_curr(); it.next())
  operation on current arc

With get_arc_it(p) The previous snippet could be more shortly written thus: 

for (auto it = g.get_arc_it(p); it.has_curr(); it.next())
  operation on current arc
Returns
an instantiated iterator on the arcs positioned at the first arc.

◆ get_connected_node()

__Graph_Node * GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::get_connected_node ( __Graph_Arc *  arc,
__Graph_Node *  node 
) const
inlinenoexceptinherited

Return the adjacent node to node through arc.

This method only has sense for non-directed graphs. In fact, for non directed graphs, this is the proper way for accessing to a target node from a specific arc.

This is the expected way for accesing the adjacent nodes to a specific node. From a node p, we can see its arcs through a iterator of a funcrional for_each().

As example, consider the following code snippet which examinates the adjacent nodes from a node p: 

for (auto it = g.get_arc_it(p); it.has_curr(); it.next())
  {
    auto arc = it.get_curr(); // obtain the current arc
    auto tgt = g.get_connected_node(arc, p); // the adjacent node

... }

Parameters
[in]arcthe arc
[in]nodethe node from you must be seeing the arc
Returns
an adjacent node tgt with form p ---arc--- tgt
Warning
This method has not any sense, and very probably gives incorrect results, on directed graphs. The subtle detail is that sometimes, unfortunately but incorrectly, can work. So be very careful and be sure of understand its use in the context of non directed graphs

◆ get_in_degree()

template<class NodeT = Net_Node<Empty_Class>, class ArcT = Net_Arc<Empty_Class, double>>
size_t Aleph::Net_Graph< NodeT, ArcT >::get_in_degree ( Node *  p) const
inlinenoexceptinherited

Retorna el grado de entrada del nodo (cantidad de arcos que inciden sobre él.

+ Here is the call graph for this function:

◆ get_in_it()

In_Iterator GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::get_in_it ( __Graph_Node *  p) const
inlinenoexceptinherited

Return an input iterator on the incoming arcs to p

This method is useful for shorting an input iterator initialization. A traditional way for writing an input iterator on the arcs of a node is as follows: 

for (typename GT::In_Iterator it(g); it.has_curr(); it.next())
  operation on current arc

With get_in_it(p) The previous snippet could be more shortly written thus: 

for (auto it = g.get_in_it(p); it.has_curr(); it.next())
  operation on current arc
Returns
an instantiated input iterator on the arcs positioned at the first arc.

◆ get_node()

__Graph_Node * GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::get_node ( ) const
inlineinherited

Return any node in the graph.

This method serves as an entry point to the graph. Some algorithms only need an initial node which could be anyone. In these cases, this method is indicated.

Returns
A pointer to a node in the graph

◆ get_node_it()

auto GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::get_node_it ( ) const
inlinenoexceptinherited

Obtains an iterator to the nodes of graph.

This method is useful for shorting the iterator initialization. A traditional way for writing an iterator is as follows: 

for (typename GT::Node_Iterator it(g); it.has_curr(); it.next())
  operation on current node

With get_node_it() The previous snippet could be more shortly written thus: 

for (auto it = g.get_node_it(); it.has_curr(); it.next())
  operation on current node
Returns
an instantiated iterator on the nodes positioned at the first node.

◆ get_num_arcs() [1/2]

size_t GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::get_num_arcs ( ) const
inlinenoexceptinherited

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ get_num_arcs() [2/2]

size_t GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::get_num_arcs ( __Graph_Node *  node) const
inlinenoexceptinherited

Return the total of arcs of a node. Only has sense for non directed graphs

◆ get_out_degree()

template<class NodeT = Net_Node<Empty_Class>, class ArcT = Net_Arc<Empty_Class, double>>
size_t Aleph::Net_Graph< NodeT, ArcT >::get_out_degree ( Node *  p) const
inlinenoexceptinherited

Retorna el grado de salida del nodo (cantidad de arcos que salen él.

+ Here is the call graph for this function:

◆ get_out_it()

Out_Iterator GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::get_out_it ( __Graph_Node *  p) const
inlinenoexceptinherited

Return an output iterator on the incoming nodes to p

This method is useful for shorting an output iterator initialization. A traditional way for writing an output iterator on the arcs of a node is as follows: 

for (typename GT::Out_Iterator it(g); it.has_curr(); it.next())
  operation on current arc

With get_out_it(p) The previous snippet could be more shortly written thus: 

for (auto it = g.get_out_it(p); it.has_curr(); it.next())
  operation on current arc
Returns
an instantiated output iterator on the arcs positioned at the first arc.

◆ in_arcs_map()

auto GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::in_arcs_map ( __Graph_Node *  p,
std::function< T(__Graph_Arc *)>  op 
) const
inlinenoexceptinherited

Return a list of incoming arcs of a node mapped to items of type given by transformation op.

This method is analogous to arcs_map() but only operates on the incoming arcs.

See also
arcs_map(Node * p, std::function<T(Arc *)> operation)

◆ in_degree()

size_t GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::in_degree ( __Graph_Node *  p) const
inlinenoexceptinherited

Compute the input degree of a node.

The method computes, not retrieves, the number of incoming arcs to node p. Be careful with the fact that this is a computation and to perform very often could degrade the performance.

Note that this method does not only serve too for explicit digraphs, but that would be necessary, since the in degree is neves stored.

Parameters
[in]ppoinger to the node
Returns
number of incoming arcs to p

◆ in_pairs()

auto GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::in_pairs ( __Graph_Node *  p) const
inlineinherited

Return a list of pair incoming arcs and nodes.

Sometimes is useful to directly have the incoming arcs and their nodes. This method perform that task in only a pass.

The pair are implemented with tuples. First item has the arc and the second the node.

Parameters
[in]ppointer to node
Returns
a list of incoming pairs arc, node
Exceptions
bad_allocif there is no enough memory

◆ insert_arc() [1/5]

template<class NodeT = Net_Node<Empty_Class>, class ArcT = Net_Arc<Empty_Class, double>>
Arc* Aleph::Net_Graph< NodeT, ArcT >::insert_arc ( Node *  src_node,
Node *  tgt_node,
const Flow_Type &  cap,
const Flow_Type &  flow,
const typename Arc::Arc_Type &  arc_info = Arc_Type() 
)
inlineinherited

Inserta un arco en una red de flujo.

insert_arc() crea un nuevo arco con valor de atributo arc_info, con valor de capacidad cap y flujo flow, desde el nodo src_node hacia el nodo tgt_node.

Parameters
[in]src_nodepuntero hacia el nodo origen.
[in]tgt_nodepuntero hacia el nodo destino.
[in]capvalor de capacidad del arco.
[in]flowvalor de flujo del arco.
[in]arc_infovalor de atributo a guardar en el nuevo arco.
Returns
puntero hacia el nuevo arco insertado
Exceptions
std::bad_allocsi no hay suficiente memoria para crear el arco.
std::overflow_errorsi el valor de flujo es mayor que el de la capacidad.
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ insert_arc() [2/5]

template<class NodeT = Net_Node<Empty_Class>, class ArcT = Net_Arc<Empty_Class, double>>
Arc* Aleph::Net_Graph< NodeT, ArcT >::insert_arc ( Node *  src_node,
Node *  tgt_node,
const Flow_Type &  cap 
)
inlineinherited

Inserta un arco en una red de flujo.

insert_arc() crea un nuevo arco con valor de atributo arc_info, con valor de capacidad cap desde el nodo src_node hacia el nodo tgt_node.

El valor de flujo es cero.

Parameters
[in]src_nodepuntero hacia el nodo origen.
[in]tgt_nodepuntero hacia el nodo destino.
[in]capvalor de capacidad del arco.
Returns
puntero hacia el nuevo arco insertado
Exceptions
std::bad_allocsi no hay suficiente memoria para crear el arco.
std::overflow_errorsi el valor de flujo es mayor que el de la capacidad.

◆ insert_arc() [3/5]

template<class NodeT = Net_Node<Empty_Class>, class ArcT = Net_Arc<Empty_Class, double>>
Arc* Aleph::Net_Graph< NodeT, ArcT >::insert_arc ( Node *  src_node,
Node *  tgt_node,
const typename Arc::Arc_Type &  arc_info = Arc_Type() 
)
inlineinherited

Inserta un arco en una red de flujo.

insert_arc() crea un nuevo arco con valor de atributo arc_info desde el nodo src_node hacia el nodo tgt_node.

El arco se crea con valores de capacidad y flujo de cero.

Parameters
[in]src_nodepuntero hacia el nodo origen.
[in]tgt_nodepuntero hacia el nodo destino.
[in]arc_infovalor de atributo a guardar en el nuevo arco.
Returns
puntero hacia el nuevo arco insertado
Exceptions
std::bad_allocsi no hay suficiente memoria para crear el arco.
std::overflow_errorsi el valor de flujo es mayor que el de la capacidad.

◆ insert_arc() [4/5]

__Graph_Arc * GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::insert_arc ( __Graph_Node *  src,
__Graph_Node *  tgt,
const Arc_Type &  arc_info 
)
inlineinherited

Create and insert a new arc linking two nodes and copying data.

insert_arc() allocates a new arc linking the nodes pointed by src and tgt. If this is a directed graph, then src is considered the source node and tgt the target one. When the arc has been effectively allocated, the data contained in arc_info is copied to the node. Finally, the arc is inserted into the graph.

The pointers srcand tgt must be valid; that is, of course, they must correspond to real nodes already inserted in the graph. At this regard, no validation is done.

Remarks
If this method does not throw exception, then this always returns a valid pointer,
Parameters
[in]srcpointer to the source node.
[in]tgtpointer to the target node.
[in]arc_infothe data to be copied to the node.
Returns
a pointer to the arc already inserted into the graph
Exceptions
bad_allocif there is no enough memory.

◆ insert_arc() [5/5]

__Graph_Arc * GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::insert_arc ( __Graph_Node *  src,
__Graph_Node *  tgt,
Arc_Type &&  arc_info = Arc_Type() 
)
inlineinherited

Create and insert a new arc linking two nodes and moving the received data.

Thi method firstallocates a new arc linking the nodes pointed by srcandtgt. Ifthisis a directed graph, thensrcis considered the source node andtgt` the target one. Once the arc has been effectively allocated, if possible, the data contained in arc_info is moved to the node avoiding copy. Finally, the arc is inserted into the graph.

The pointers srcand tgt must be valid; that is, of course, they must correspond to real nodes already inserted in the graph. At this regard, no validation is done.

Remarks
If this method does not throw exception, then this always returns a valid pointer,
Parameters
[in]srcpointer to the source node.
[in]tgtpointer to the target node.
[in]arc_infothe data to be moved to the node.
Returns
a pointer to the arc already inserted into the graph
Exceptions
bad_allocif there is no enough memory.

◆ insert_node() [1/7]

template<class NodeT = Net_Sup_Dem_Node<Empty_Class, double>, class ArcT = Net_Arc<Empty_Class, double>>
Node* Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::insert_node ( const Node_Type &  node_info,
const Flow_Type &  supply = 0 
)
inline

Crea un nodo con provisión y lo inserta en una red.

Parameters
[in]node_infovalor de atributo del nodo.
[in]supplyvalor de provisión de flujo. Si el valor es positivo, entonces el nodo es proveedor de flujo por el valor dado; de lo contrario, el nodo demanda la cantidad dada. Por omisión, este parámetro es cero.
Returns
puntero a nodo creado e insertado.
Exceptions
bad_allocsi no hay suficiente memoria.

◆ insert_node() [2/7]

template<class NodeT = Net_Sup_Dem_Node<Empty_Class, double>, class ArcT = Net_Arc<Empty_Class, double>>
Node* Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::insert_node ( const Flow_Type &  supply = 0)
inline

Crea un nodo con provisión y lo inserta en una red.

Parameters
[in]supplyvalor de provisión de flujo. Si el valor es positivo, entonces el nodo es proveedor de flujo por el valor dado; de lo contrario, el nodo demanda la cantidad dada. Por omisión, este parámetro es cero.
Returns
puntero a nodo creado e insertado.
Exceptions
bad_allocsi no hay suficiente memoria.

◆ insert_node() [3/7]

template<class NodeT = Net_Node<Empty_Class>, class ArcT = Net_Arc<Empty_Class, double>>
Node* Aleph::Net_Graph< NodeT, ArcT >::insert_node ( const Node_Type &  node_info)
inlineinherited

Inserta un nuevo nodo en la red.

insert_node(node_info) aparta memoria para un nodo de red, le copia la información asociada node_info e inserta el nodo en la red this.

Parameters
[in]node_infola información a copiar en el nodo.
Returns
puntero al nuevo nodo insertado en la red.
Exceptions
bad_allocsi no hay suficiente memoria.
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ insert_node() [4/7]

template<class NodeT = Net_Node<Empty_Class>, class ArcT = Net_Arc<Empty_Class, double>>
Node* Aleph::Net_Graph< NodeT, ArcT >::insert_node ( Node_Type &&  info = Node_Type())
inlineinherited

Inserta un nuevo nodo en la red. El valor de información es indeterminado. Dispara bad_alloc si no hay suficiente memoria.

◆ insert_node() [5/7]

template<class NodeT = Net_Node<Empty_Class>, class ArcT = Net_Arc<Empty_Class, double>>
Node* Aleph::Net_Graph< NodeT, ArcT >::insert_node ( Node *  p)
inlineinherited

Inserta un nuevo nodo en la red copia de otro nodo p.

insert_node(p) aparta memoria para un nodo de red, le copia la información contenida en p e inserta el nuevo nodo en la red this.

Parameters
[in]potro nodo de la misma o de otra red del cual se copiará la información asociada al nodo.
Returns
puntero al nuevo nodo insertado en la red.
Exceptions
bad_allocsi no hay suficiente memoria.
+ Here is the call graph for this function:

◆ insert_node() [6/7]

__Graph_Node * GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::insert_node ( const Node_Type &  node_info)
inlineinherited

Allocate a new node, set by copy its data content and insert it into the graph.

This method perform several actions. First, it allocates memory for a graph node. Then the data node_info is copied to the data associated to the node. This copy is done via the copy constructor and assign operator. So, these functionalities must be present for the class Node_Type. Finally, the node is topologically inserted into the graph.

Remarks
If this method does not throw exception, then this always returns a valid pointer,
Parameters
[in]node_infoinfopr to copy to the new node. The copy constructor and the assign operator must be defined for the class Node_Type.
Returns
a pointer to the new inserted node.
Exceptions
bad_allodif there is no enough memory

◆ insert_node() [7/7]

__Graph_Node * GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::insert_node ( Node_Type &&  node_info = Node_Type())
inlineinherited

Allocate a new node, set by moving its data content and insert it into the graph.

This method perform several actions. First, it allocates memory for a graph node. Then the data node_info is moved to the data associated to the node. This movement is done via the move constructor and move assign operator. So, these functionalities must be present for the class Node_Type. Finally, the node is topologically inserted into the graph.

Remarks
If this method does not throw exception, then this always returns a valid pointer,
Parameters
[in]node_infoinfo to move to the new node. The move constructor and the move assign operator must be defined for the class Node_Type.
Returns
a pointer to the new inserted node.
Exceptions
bad_allodif there is no enough memory.

◆ is_connected()

template<class NodeT = Net_Node<Empty_Class>, class ArcT = Net_Arc<Empty_Class, double>>
bool Aleph::Net_Graph< NodeT, ArcT >::is_connected ( Node *  p) const
inlinenoexceptinherited

Retorna true si el nodo node está conectado. El propósito de este método es de validación, como parte de la verificación de que una red sea conexa.

◆ is_feasible()

template<class NodeT = Net_Sup_Dem_Node<Empty_Class, double>, class ArcT = Net_Arc<Empty_Class, double>>
bool Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::is_feasible ( ) const
inline

Recorre la red de provisiones y determina si el flujo es factible.

Returns
true si el flujo es factible; false de lo contrario.
Exceptions
domain_errorsi la red capacitada equivalente no ha sido previamente calculada.

◆ make_super_nodes()

template<class NodeT = Net_Node<Empty_Class>, class ArcT = Net_Arc<Empty_Class, double>>
void Aleph::Net_Graph< NodeT, ArcT >::make_super_nodes ( )
inlineinherited

Convierte una red con varios nodos fuente y sumideros a una red con un solo nodo supra-fuente y uno supra-sumidero.

◆ make_super_sink()

template<class NodeT = Net_Node<Empty_Class>, class ArcT = Net_Arc<Empty_Class, double>>
void Aleph::Net_Graph< NodeT, ArcT >::make_super_sink ( )
inlineinherited

Convierte una red con varios sumideros a una red con un sólo nodo supra-sumidero. Dispara excepción si la red no contiene un nodo sumidero o si no hay suficiente memoria.

+ Here is the call graph for this function:

◆ make_super_source()

template<class NodeT = Net_Node<Empty_Class>, class ArcT = Net_Arc<Empty_Class, double>>
void Aleph::Net_Graph< NodeT, ArcT >::make_super_source ( )
inlineinherited

Convierte una red con varios fuentes a una red con un sólo nodo supra-fuente. Dispara excepción si la red no contiene un nodo fuente o si no hay suficiente memoria.

+ Here is the call graph for this function:

◆ map_arcs()

static void GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::map_arcs ( A1 *  p,
A2 *  q 
)
inlinestaticnoexceptinherited

Map the arcs through their cookies.

map_arcs(p, q) is intended to biyectively to map the arc p towards the arc q through their cookies. Basically, after calling the cookie of p points to q and the cookie of q points to p.

See map_nodes() for a better explanation.

Parameters
[in]psource arc of mapping
[in]qtarget arc of mapping
See also
mapped_arc()

◆ map_nodes()

static void GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::map_nodes ( N1 *  p,
N2 *  q 
)
inlinestaticnoexceptinherited

Map the nodes through their cookies.

map_nodes(p, q) is intended to biyectively to map the node p towards the node q through their cookies. Basically, after calling the cookie of p points to q and the cookie of q points to p.

If the cookie value of p is not nullptr, then map_nodes(p, q) assumes that there already is a mapping and then perform the composition. This could be very useful for having several mapping.

Supposse that we have three nodes p, q and r belonging to three different, but from certain way isomorphic, graphs g1 and g2 of type GT, and g3 of type GTT. Note that the types of graph could variate. Thus, this call: 

g1.map_nodes(p, q);

Instruments a biyective mapping $p \longleftrightarrow q$. Note that since p and q are of the same type (although belong to different graphs), it is not necessary to specify as template parameters the graph types. Another way for invoking exactly the same function is: 

GT::map_nodes(p, q);

This is because map_nodes() is a static member.

Now, suppose that you wish to map the node r to p and q- Ypu could do as follows: 

g1.map_nodes<GT, GTT>(p, r);

Now the mapping is $p \longleftrightarrow q \longleftrightarrow r$. Note that in this case, since the graph types are not the same, you must specify them as template parameters. Of course, in this case, for retrieving r you must do two cookie's inspections, one first on p for retrieving q, and a second on q for retrieving r.

In our experiences, this is the fastest way for implementing mappings. Apart from the fact that the retrieval is $O(1)$, this is also deterministic. Compare this fact with other approaches requiring bookkeeping throug hash tables or trees. In addiction, if many (or all) nodes are required to map, then this approach is also the less space consuming. More still, correctly used, this approach could be simpler than hash tables or trees, since you do not require additional declarations, inicializations, etc.

Of course, this approach has the big con that it is not very typed neither validated. If you do a mistake all probably will crash. However, the big gain in speed rewards and deserves the presence of this feature.

Parameters
[in]psource node of mapping
[in]qtarget node of mapping
See also
mapped_node()

◆ nodes()

Container<__Graph_Node *> GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::nodes ( ) const
inlineinherited

Return a container with all the nodes of the graph.

nodes() recollects all the nodes of the graph and builds a container with all them inserted. The container type is a template parameter, which by default is DynList.

Returns
a container, according the template parameter, with all the nodes into it.
Exceptions
bad_allocif there is no enough memory

◆ nodes_map()

auto GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::nodes_map ( std::function< T(__Graph_Node *)>  op) const
inlineinherited

Map the nodes of a graph to a specific range.

nodes_map(operation) produces a mapping list of the graph's nodes. The transformation is done by operation whose signature must imperatively be: 

T operation(Node * p)

operation instruments a map from the node to the range type T. By default, T is Node_Type (the type associated to the node's data). In this case, you do not require to specify the range type as template parameter. Otherwise, in order to the compiler can know the range type, you must specify it as template parameter.

Suppose by example that the nodes have integers and that you want to produce a mapping int –> double corresponding to the division of the data node between a specific divisor. Then you can do this as follows: 

auto l = g.map_nodes<double>([divisor] (auto p) 
{
  return 1.0*p->get_info()/divisor;
});
Remarks
The name of this method (nodes_map() instead of map_nodes()) is due to the ambiguity that would cause with the map_nodes() intended for mapping the nodes through their cookies.
Note
In metaprogramming you will probably need add the template keyword before the name nodes_map<your-target-type>. 
g.template nodes_map<ulong>([] (auto p) { return p->get_info(); });
Parameters
[in]operationtransformation from Node* to T to be performed on each node.
Returns
a DynList<T> containing the mapping.
Exceptions
bad_allocif there is no enough memory for fuilding the dynamic list or anything else that can throw operation

◆ non_feasible_nodes()

template<class NodeT = Net_Sup_Dem_Node<Empty_Class, double>, class ArcT = Net_Arc<Empty_Class, double>>
void Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::non_feasible_nodes ( DynDlist< Node *> &  supply_list,
DynDlist< Node *> &  demand_list 
)
inline

Calcula los nodos cuyo flujo no es factible.

non_feasible_nodes() recorre los nodos de la red. Por cada nodo, según su valor de provisión, se verifica si ésta se satisface. Si no es posible satisfacer la provisión, entonces la dirección del nodo se guarda en una lista según que el nodo se de demanda o de provisión.

Parameters
[out]supply_listlista de nodos cuyo flujo de salida es menor que lo que pueden proveer.
[out]demand_listlista de nodos cuyo flujo de entrada es menor que lo que reciben.
Exceptions
bad_allocsi no hay suficiente memoria para insertar en alguna de las listas parámetros.
+ Here is the call graph for this function:

◆ out_arcs_map()

auto GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::out_arcs_map ( __Graph_Node *  p,
std::function< T(__Graph_Arc *)>  op 
) const
inlineinherited

Return a list of outcoming arcs of a node mapped to items of type given by transformation op.

This method is analogous to arcs_map() but only operates on the outcoming arcs.

See also
arcs_map(Node * p, std::function<T(Arc *)> operation)

◆ out_degree()

size_t GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::out_degree ( __Graph_Node *  p) const
inlinenoexceptinherited

Compute the output degree of a node.

The method computes, not retrieves, the number of outcoming arcs to node p. Be careful with the fact that this is a computation and to perform very often could degrade the performance.

Note that if you are using a digraph, then it is not use to have this method, since the digraph stores the outcoming degree. In this case, you could use get_num_arcs(p) in order to obtain the same result wihout any computation

Parameters
[in]ppoinger to the node
Returns
number of incoming arcs to p
See also
get_num_arcs(Node*)

◆ out_pairs()

auto GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::out_pairs ( __Graph_Node *  p) const
inlineinherited

Return a list of pair outcoming arcs and nodes.

Sometimes is useful to directly have the outcoming arcs and their nodes. This method perform that task in only a pass.

The pair are implemented with tuples. First item has the arc and the second the node.

Parameters
[in]ppointer to node
Returns
a list of outcoming pairs arc, node
Exceptions
bad_allocif there is no enough memory

◆ reset_arc()

void GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::reset_arc ( __Graph_Arc *  arc) const
inlinenoexceptinherited

Reset all the control attributes of arc. That is: all control bits, the state and the counter are set to zero. The cookie is set to nullptr value

◆ reset_arcs()

void GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::reset_arcs ( ) const
inlineinherited

Reset all the arcs of graph (the control bits, the state, the counter and the cookie)

◆ reset_cookie_arcs()

void GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::reset_cookie_arcs ( ) const
inlinenoexceptinherited

Reset all the cookies to `nullptr for all the arcs of graph.

Warning
Be sure to verify that the cookie is not being used, otherwise most likely will lose memory or worse, your algorithm will not work properly

◆ reset_cookie_nodes()

void GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::reset_cookie_nodes ( ) const
inlinenoexceptinherited

Reset all the cookies to `nullptr for all the nodes of graph.

Warning
Be sure to verify that the cookie is not being used, otherwise most likely will lose memory or worse, your algorithm will not work properly

◆ reset_node()

void GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::reset_node ( __Graph_Node *  p) const
inlinenoexceptinherited

Reset all the control attributes of node p. That is: all control bits, the state and the counter are set to zero. The cookie is set to nullptr value

◆ reset_nodes()

void GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::reset_nodes ( ) const
inlineinherited

Reset all the nodes of graph (the control bits, the state, the counter and the cookie)

◆ search_arc() [1/5]

__Graph_Arc * GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::search_arc ( Op &  op) const
inlinenoexceptinherited

Linear search of an arc.

Search linearly an arc satisfying the condition op.

This method is some similar to exists_arc(); the difference is that it returns a pointer and its value indicates the success of search.

The complexity is $O(E)$ for the worst case.

Parameters
[in]opthe criteria.
Returns
a valid pointer to found arc if an arc satisfies the criteria or nullptr otherwise
See also
exists_arc()

◆ search_arc() [2/5]

__Graph_Arc * GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::search_arc ( Op &&  op) const
inlinenoexceptinherited

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ search_arc() [3/5]

__Graph_Arc * GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::search_arc ( __Graph_Node *  p,
Operation &  op 
) const
inlinenoexceptinherited

Linear search of an arc.

Search linearly an arc satisfying the condition op.

This method is some similar to exists_arc(); the difference is that it returns a pointer and its value indicates the success of search.

The complexity is $O(V)$ for the worst case.

Parameters
[in]ppointer to the node from which the adjacent arcs want to be searched.
[in]opthe criteria.
Returns
a valid pointer to found node if a node satisfies the criteria or nullptr otherwise
See also
exists_arc(Node * p, Operation & op)

◆ search_arc() [4/5]

__Graph_Arc * GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::search_arc ( __Graph_Node *  p,
Operation &&  op = Operation() 
) const
inlinenoexceptinherited

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ search_arc() [5/5]

__Graph_Arc * GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::search_arc ( __Graph_Node *  src,
__Graph_Node *  tgt 
) const
inlinenoexceptinherited

Search an arc linking two nodes.

search_arc(src, tgt) searches an arc linking src with tgt. The method inspect the ars adjacent to src verifying whether a target is or not tgt.

This method is conceived for both directed and non directed graphs. But in the not directed case, the notion of source and target node has not much sense. The result of search_node(src, tgt) is the same than search_node(tgt, src).

Note
If you require search arcs in directed graphs, the use search_directed()

The complexity is $ $O(V)$ worst case.

Parameters
[in]srcsource node [in] tgt target node
Returns
a valid pointer to an arc if this was found or nullptr otherwise.
See also
search_directed_arc()

◆ search_directed_arc()

__Graph_Arc * GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::search_directed_arc ( __Graph_Node *  src,
__Graph_Node *  tgt 
) const
inlinenoexceptinherited

Search a directed arc linking two nodes.

search_directed_arc(src, tgt) searches an arc of form src --> tgt, on bot directed and non directed graphs.

Parameters
[in]srcpinter to source node
[in]tgtpinter to target node
Returns
a valid pointer to an arc if this is found or nullptr otherwise.

◆ search_in_arc() [1/2]

auto GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::search_in_arc ( __Graph_Node *  p,
Op &  op 
) const
inlinenoexceptinherited

Search an incoming arc to a node satisfaying a condition.

search_in_arc(p, op) traveses the incoming arcs of p and search one for which op return true.

Parameters
[in]ppointer to the node.
[in]opoperation to be executed on each arc in order to match certain search criteria. op must return true when the arc satisfies the search criteria.
Returns
a valid pointer to arc satisfaying the search criteria it this exists; nullptr otherwise
Exceptions
anythingthat op could throw

◆ search_in_arc() [2/2]

auto GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::search_in_arc ( __Graph_Node *  p,
Op &&  op = Op() 
) const
inlinenoexceptinherited

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ search_node() [1/2]

__Graph_Node * GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::search_node ( Op &  op) const
inlinenoexceptinherited

Linear search of a node.

Search linearly a node satisfying the condition op.

This method is some similar to exists_node(); the difference is that it returns a pointer and its value indicates the success of search.

The complexity is $O(V)$ for the worst case.

Parameters
[in]opthe criteria.
Returns
a valid pointer to found node if a node satisfies the criteria or nullptr otherwise
See also
exists_node()

◆ search_node() [2/2]

__Graph_Node * GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::search_node ( Op &&  op) const
inlinenoexceptinherited

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ search_out_arc() [1/2]

auto GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::search_out_arc ( __Graph_Node *  p,
Op &  op 
) const
inlinenoexceptinherited

Search an outcoming arc to a node satisfaying a condition.

search_out_arc(p, op) traveses the outcoming arcs of p and search one for which op return true.

Parameters
[in]ppointer to the node.
[in]opoperation to be executed on each arc in order to match certain search criteria. op must return true when the arc satisfies the search criteria.
Returns
a valid pointer to arc satisfaying the search criteria it this exists; nullptr otherwise
Exceptions
anythingthat op could throw

◆ search_out_arc() [2/2]

auto GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::search_out_arc ( __Graph_Node *  p,
Op &&  op = Op() 
) const
inlinenoexceptinherited

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ set_digraph()

void GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::set_digraph ( bool  val)
inlineinherited

Temporal indication for preventing to other algorithms that an graph must be treated as a directed graph.

Sometimes (in Aleph-w ( $\aleph_\omega$) many times) is desirable to deal with a non-directed graph as if this was a directed one. Such is the case, for example, of functor Random_Digraph, which is used for generating random digraphs. Of course, since Random_Digraph is designed for generating digraphs, it manages its internal state thinking that a digraph is generated.

Now, in a few circunstances, very often for practical purpuses (performace, easiness of coding, etc), a non-directed graph is wanted to be dealt as a directed one. In this case some algorithms need to know that the graph is in reality directed. In order to solve this ambiguity, the internal state that indicates that the graph is directed could be changed. In this way, foin order to instruct to Random_Digraph that deals a non-directed as a directed one, the flag "directed" is changed to true.

Of course, this technique is very very risky. Take into account that topological changing operations variate according to the directness of graph. Thus, to change the directed flag and then to insert and/or to remove nodes and/or arcs will mess everything and the chances of disater will be very high. For this reason, the use of this method is not recommended and its presence must be considered temporal while we find a more proper approach, concretely while Random_Digraph remains without to be refactored, which is, in fact, the unique part of Aleph-w ( $\aleph_\omega$) that temporally uses this method.

Warning
Our advice is: don't use!

◆ set_flow()

template<class NodeT = Net_Node<Empty_Class>, class ArcT = Net_Arc<Empty_Class, double>>
void Aleph::Net_Graph< NodeT, ArcT >::set_flow ( Arc *  arc,
const Flow_Type &  flow 
)
inlineinherited

Coloca valor de flujo a un arco. Dispara excepción si el valor es mayor que la capacidad.

◆ set_supply_flow()

template<class NodeT = Net_Sup_Dem_Node<Empty_Class, double>, class ArcT = Net_Arc<Empty_Class, double>>
void Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::set_supply_flow ( Node *  p,
const Flow_Type &  supply 
)
inline

Ajusta el valor de provisión de un nodo.

set_supply_flow(p, supply) coloca el valor de provisión supply sobre el nodo apuntado por el puntero p.

Parameters
[in]ppuntero al nodo.
[in]supplyvalor de provisión a colocar sobre el nodo.
Note
una vez realizado cualquier ajuste sobre la provisión, es necesario recalcular el flujo máximo si se desea conocer la factibilidad del flujo.
Exceptions
range_errorsi el valor de provisión no es factible a la capacidad entrante o saliente del nodo.

◆ sort_arcs() [1/2]

template<class __Graph_Node = Graph_Anode<unsigned long>, class __Graph_Arc = Graph_Aarc<unsigned long>>
template<class Compare >
void Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::sort_arcs ( Compare &  cmp)
inlineinherited

Sort all the arcs of the graph according to a specific criteria.

The method takes an comparison operation between two arcs and sorts the arcs.

The comparison criteria should match the following signature: 

bool cmp(Arc * a1, Arc * a2);

So, inside cmp you would access to the data arcs and would perform the comparison.

After execution of this method, provided that no new arcs are inserted or others sorts are not performed with a different criteria, it is guaranted that order of apparition of the arc by the Arc_Iterator will be sorted.

Parameters
[in,out]cmpoperation of comparison that defines the sorting criteria

◆ sort_arcs() [2/2]

template<class __Graph_Node = Graph_Anode<unsigned long>, class __Graph_Arc = Graph_Aarc<unsigned long>>
template<class Compare >
void Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::sort_arcs ( Compare &&  cmp)
inlineinherited

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ sort_nodes() [1/2]

template<class __Graph_Node = Graph_Anode<unsigned long>, class __Graph_Arc = Graph_Aarc<unsigned long>>
template<class Compare >
void Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::sort_nodes ( Compare &  cmp)
inlinenoexceptinherited

Sort all the nodes of the graph according to a specific criteria.

The method takes an comparison operation between two nodes and sorts the nodes.

The comparison criteria should match the following signature:

bool cmp(Node * a1, Node * a2);

So, inside cmp you would access to the data arcs and would perform the comparison.

After execution of this method, provided that no new nodes are inserted or others sorts are not performed with a different criteria, it is guaranted that order of apparition of the nodes by the Node_Iterator will be sorted.

Parameters
[in,out]cmpoperation of comparison that defines the sorting criteria

◆ sort_nodes() [2/2]

template<class __Graph_Node = Graph_Anode<unsigned long>, class __Graph_Arc = Graph_Aarc<unsigned long>>
template<class Compare >
void Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::sort_nodes ( Compare &&  cmp = Compare())
inlinenoexceptinherited

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ traverse_arcs() [1/5]

bool GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::traverse_arcs ( Operation &  op) const
inlinenoexceptinherited

Conditioned traversal of all the arcs of a graph.

traverse_arc(operation) condionally traverses all the arcs of a graph and on each arc a executes operation(a). The operation must have the following functor structure: 

bool operation(Arc * a)

This signature can be accomplished through a function pointer, a functor or a lambda (via the overloaded rvalue version). Note that there is a return value. If operation(p) returns true, then the next node is traversed. Otherwise the traversal stops and the remainder nodes are not visited.

if the graph type was GT then the arc type would be GT::Arc. In this primitive as well for the majority of functional primitives, you could declare the parameter types as auto and to leave to compiler to infer them. This could be more practical and easier for writing but it also could hide the true type and in some cases to do incomprehensible the the type.

The operation is $O(E)$ for the worst and average case.

For example, supposse that we wish print out the arcs content for all the arcs. Then we could do it as follows: 

g.traverse_arcs([] (auto a) 
  { 
    cout << a->get_info() << endl; 
    return true; // for instructing to visit the next node
  });
Remarks
According to the compiler, invalid or uncompliant signatures for operation, by example, to not return anything, not only they probably will not compile, but the diagnostic errors could be hard to undertand. Perhaps, on some compilers, bad signatures could compile. So, be sure to match the correct operation signature.
Parameters
[in]operationoperation to be performed on each arc. The operation must imperatively return a bool indicating whether or not the next arc must be visited.
Returns
a bool with the last operationresult. If true then all the arcs were visited and on each one operation executed. Otherwise, the traversal was stopped.
Exceptions
anyexception that could throw operation
See also
traverse_arcs() all_arcs()

◆ traverse_arcs() [2/5]

bool GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::traverse_arcs ( Operation &&  op = Operation()) const
inlinenoexceptinherited

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ traverse_arcs() [3/5]

bool GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::traverse_arcs ( __Graph_Node *  p,
Operation &  op 
) const
inlinenoexceptinherited

Conditioned traversal of all the adjacent arcs of a node.

traverse_arc(p, operation) condionally traverses all the arcs of the node p and on each arc a executes operation(a). The operation must have the following functor structure: 

bool operation(Arc * a)

This signature can be accomplished through a function pointer, a functor or a lambda (via the overloaded rvalue version). Note that there is a bool return value. If operation(p) returns true, then the next node is traversed. Otherwise the traversal stops and the remainder nodes are not visited.

if the graph type was GT then the arc type would be GT::Arc. In this primitive as well for the majority of functional primitives, you could declare the parameter types as auto and to leave to compiler to infer them. This could be more practical and easier for writing but it also could hide the true type and in some cases to do incomprehensible the the type.

The operation is $O(V)$ for the worst case, but it could be much less for sparsed graphs.

For example, supposse that we wish print out the arcs content for the nodes adjacent to the node p. Then we could do it as follows: 

g.traverse_arcs(p, [] (auto a) 
{ 
  cout << a->get_info() << endl; 
  return true; // for instructing to visit the next node
});
Remarks
According to the compiler, invalid or uncompliant signatures for operation, by example, to not return anything, not only they probably will not compile, but the diagnostic errors could be hard to undertand. Perhaps, on some compilers, bad signatures could compile. So, be sure to match the correct operation signature.
Parameters
[in]pnode from you want to access its adjacent arcs.
[in]operationoperation to be performed on each arc. The operation must imperatively return a bool indicating whether or not the next arc must be visited.
Returns
a bool with the last operationresult. If true then all the arcs were visited and on each one operation executed. Otherwise, the traversal was stopped.
Exceptions
anyexception that could throw operation
See also
traverse_arcs() all_arcs()

◆ traverse_arcs() [4/5]

bool GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::traverse_arcs ( __Graph_Node *  p,
Operation &&  op = Operation() 
) const
inlinenoexceptinherited

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ traverse_arcs() [5/5]

bool GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::traverse_arcs ( __Graph_Node *  p,
Operation &  op 
) const
inlinenoexceptinherited

Traverse of arcs of a node according to specific arcs iterator.

traverse_arcs<Itor, Operation>(p, operation) is very similar a traverse_arcs(), except that this version receives the arc iterator as template parameter. Its use is intended to serve as implementation base for functional primitives on incoming and outcoming arcs.

Parameters
[in]pnode to traverse its arcs
[in]operationto perform on each arc given by the iterator. The convention is the the same than for traverse methods. If operationreturn true, then the next arc is revised; otherwise the traversal stops.
Returns
true if all the arcs were traversed; false otherwise.
Exceptions
whatevercould throw operation
See also
traverse(Node * p, Operation & operation)

◆ traverse_in_arcs() [1/2]

bool GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::traverse_in_arcs ( __Graph_Node *  p,
Op &  op 
) const
inlinenoexceptinherited

Traverse the incoming arcs of node p executing the conditioned operation

◆ traverse_in_arcs() [2/2]

bool GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::traverse_in_arcs ( __Graph_Node *  p,
Op &&  op = Op() 
) const
inlinenoexceptinherited

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ traverse_nodes() [1/2]

bool GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::traverse_nodes ( Operation &  op) const
inlinenoexceptinherited

Conditioned traversal of all the nodes of a graph.

traverse_nodes(operation) condionally traverses all the nodes of a graph and on each node p executes operation(p). The operation must have the following functor structure: 

bool operation(Node * p)

This signature can be accomplished through a function pointer, a functor or a lambda (via the overloaded rvalue version). Note that there is a return value. If operation(p) returns true, then the next node is traversed. Otherwise the traversal stops and the remainder nodes are not visited.

For example, supposse that we wish print out the nodes content for all the nodes. Then we could do it as follows: 

g.traverse_nodes([] (auto p) 
  { 
    cout << p->get_info() << endl; 
    return true; // for instructing to visit the next node
  });

traverse_nodes() is the heart of functional primitives on nodes of a graph. All other functional primitives depend on it. In general, ait is as fast as to directly iterate on the nodes.

The operation is $O(V)$ for the worst and average case.

Remarks
According to the compiler, invalid or uncompliant signatures for operation, by example, to not return anything, not only they probably will not compile, but the diagnostic errors could be hard to undertand. Perhaps, on some compilers, bad signatures could compile. So, be sure to match the correct operation signature.
Parameters
[in]operationoperation to be performed on each node. The operation must imperatively return a bool indicating whether or not the next node must be visited.
Returns
a bool with the last operationresult. If true then all the mode were visited and on each one operation executed. Otherwise, the traversal was stopped.
Exceptions
anyexception that could throw operation
See also
traverse_arcs() all_nodes()

◆ traverse_nodes() [2/2]

bool GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::traverse_nodes ( Operation &&  op = Operation()) const
inlinenoexceptinherited

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ traverse_out_arcs() [1/2]

bool GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::traverse_out_arcs ( __Graph_Node *  p,
Op &  op 
) const
inlinenoexceptinherited

Traverse the outcoming arcs of node p executing the conditioned operation

◆ traverse_out_arcs() [2/2]

bool GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc > , __Graph_Node , __Graph_Arc >::traverse_out_arcs ( __Graph_Node *  p,
Op &&  op = Op() 
) const
inlinenoexceptinherited

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ unmake_super_nodes()

template<class NodeT = Net_Node<Empty_Class>, class ArcT = Net_Arc<Empty_Class, double>>
void Aleph::Net_Graph< NodeT, ArcT >::unmake_super_nodes ( )
inlineinherited

Restaura una red con un nodo supra-fuente y uno solo supra-sumidero a la red original con varios nodos fuentes y sumideros.

◆ unmake_super_sink()

template<class NodeT = Net_Node<Empty_Class>, class ArcT = Net_Arc<Empty_Class, double>>
void Aleph::Net_Graph< NodeT, ArcT >::unmake_super_sink ( )
inlinenoexceptinherited

Restaura una red con un nodo supra-sumidero a la red original con varios nodos sumidero.

+ Here is the call graph for this function:

◆ unmake_super_source()

template<class NodeT = Net_Node<Empty_Class>, class ArcT = Net_Arc<Empty_Class, double>>
void Aleph::Net_Graph< NodeT, ArcT >::unmake_super_source ( )
inlinenoexceptinherited

Restaura una red con un nodo supra-fuente a la red original con varios nodos fuente.

+ Here is the call graph for this function:
The documentation for this class was generated from the following file:
Leandro Rabindranath León