Graph implemented with double-linked adjacency lists. More...
#include <tpl_graph.H>
Classes | |
| struct | Arc_Iterator |
| Iterator on all arcs of a graph. More... | |
| class | Node_Arc_Iterator |
| Iterator on the arcs of a graph. More... | |
| struct | Node_Iterator |
| Node iterator. More... | |
Public Types | |
| using | GT = List_Graph |
| using | Node = _Graph_Node |
| The graph type. | |
| using | Arc = _Graph_Arc |
| The node class type. | |
| using | Node_Type = typename Node::Node_Type |
| The arc class type. | |
| using | Arc_Type = typename Arc::Arc_Type |
| The type of data stored in the arc. | |
| using | CommonBase = GraphCommon< List_Graph< _Graph_Node, _Graph_Arc >, _Graph_Node, _Graph_Arc > |
 Public Types inherited from GraphCommon< GT, Node, Arc > | |
| using | Node_Type = typename Node::Node_Type |
| using | Arc_Type = typename Arc::Arc_Type |
| using | ArcPair = std::tuple< Arc *, Node * > |
| Pair of arc and node (topologically related) | |
Public Member Functions | |
| Dlink & | get_node_dlink () noexcept |
| Return a reference to the internal node Dlink for sorting. | |
| Dlink & | get_arc_dlink () noexcept |
| Return a reference to the internal arc Dlink for sorting. | |
| virtual Node * | insert_node (Node *node) noexcept |
| Insertion of a node already allocated. | |
| virtual void | remove_node (Node *node) noexcept |
| Remove a node from the graph and free its memory. | |
| Node * | get_first_node () const |
| Return any node in the graph. | |
| Arc * | get_first_arc (Node *node) const |
| Return any arc adjacent to a node. | |
| virtual void | remove_arc (Arc *arc) noexcept |
| Remove an arc from the graph and free it. | |
| virtual void | disconnect_arc (Arc *arc) noexcept |
| Disconnect an arc from graph. | |
| virtual Arc * | connect_arc (Arc *arc) noexcept |
| Connect a previously disconnected arc to the graph. | |
| Arc * | get_first_arc () const |
| Return any arc in the graph. | |
| List_Graph (const List_Graph &g) | |
| Copy constructor. | |
| List_Graph (List_Graph &&g) noexcept | |
| Move constructor. | |
| List_Graph & | operator= (const List_Graph &g) |
| Copy assignment. | |
| List_Graph & | operator= (List_Graph &&g) noexcept |
| Move assignment. | |
| virtual | ~List_Graph () |
| Destructor: all the nodes and arcs and removed and freed. | |
| List_Graph ()=default | |
| Construct an empty graph. | |
| void | swap (List_Graph &g) noexcept |
Swap in constant time this with g | |
| Node * | insert_node (const Node_Type &node_info) |
| Allocate a new node, set by copy its data content and insert it into the graph. | |
| Node * | insert_node (Node_Type &&node_info=Node_Type()) |
| Allocate a new node, set by moving its data content and insert it into the graph. | |
| Arc * | insert_arc (Node *src, Node *tgt, const Arc_Type &arc_info) |
| Create and insert a new arc linking two nodes and copying data. | |
| Arc * | insert_arc (Node *src, Node *tgt, Arc_Type &&arc_info=Arc_Type()) |
| Create and insert a new arc linking two nodes and moving the received data. | |
| Public Member Functions inherited from GraphCommon< GT, Node, Arc > | |
| 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. | |
| bool | is_digraph () const noexcept |
Return true if the graph this is directed. | |
| void | set_digraph (bool val) |
| Temporal indication for preventing to other algorithms that an graph must be treated as a directed graph. | |
| constexpr size_t | get_num_nodes () const noexcept |
| Return the total of nodes of graph. | |
| constexpr size_t | vsize () const noexcept |
| Node * | get_node () const |
| Return any node in the graph. | |
| Node * | get_arc () const |
| Return any arc in the graph. | |
| Node * | get_arc (Node *p) |
| Return any arc adjacent to a node. | |
| Node * | get_src_node (Arc *arc) const noexcept |
Return the source node of arc (only for directed graphs) | |
| Node * | get_tgt_node (Arc *arc) const noexcept |
Return the target node of arc (only for directed graphs) | |
| Node * | get_connected_node (Arc *arc, Node *node) const noexcept |
Return the adjacent node to node through arc. | |
| constexpr size_t | get_num_arcs () const noexcept |
| size_t | get_num_arcs (Node *node) const noexcept |
| Return the total of arcs of a node. | |
| size_t | degree (Node *p) const noexcept |
| Return the total of arcs (or degree) of a node. | |
| size_t | esize () const noexcept |
| Return the total of arcs of graph. | |
| Bit_Fields & | get_control_bits (Node *node) const noexcept |
Return a reference to control fields of node | |
| void | reset_bit (Node *node, int bit) const noexcept |
Reset the bit of node (to zero) | |
| void | reset_bits (Node *node) const noexcept |
Reset all the control bits of node | |
| int | get_bit (Node *node, int bit) const noexcept |
Get the control bit of node | |
| void | set_bit (Node *node, int bit, int value) const noexcept |
Set the control bit of node to value | |
| Bit_Fields & | get_control_bits (Arc *arc) const noexcept |
Return a reference to the control bits of arc | |
| void | reset_bit (Arc *arc, int bit) const noexcept |
Reset the bit of arc to zero. | |
| void | reset_bits (Arc *arc) const noexcept |
Reset all the control bits of arc | |
| int | get_bit (Arc *arc, int bit) const noexcept |
Get the control bit of arc | |
| void | set_bit (Arc *arc, int bit, int value) const noexcept |
Set the control bit of arc to value | |
| void *& | get_cookie (Node *node) const noexcept |
Get a modifiable reference to the cookie pointer of node | |
| void *& | get_cookie (Arc *arc) const noexcept |
Get a modifiable reference to the cookie pointer of arc | |
| long & | get_counter (Node *node) const noexcept |
Get a modifiable reference to the counter of node | |
| void | reset_counter (Node *node) const noexcept |
Reset the node counter to zero. | |
| void | reset_node_counters () const noexcept |
| Reset all the node counters of graph to zero. | |
| void | reset_node (Node *p) const noexcept |
Reset all the control attributes of node p. | |
| long & | get_counter (Arc *arc) const noexcept |
Get a modifiable reference to the counter of arc | |
| void | reset_counter (Arc *arc) const noexcept |
Reset the acr counter to zero. | |
| void | reset_arc_counters () const noexcept |
| Reset all the arc counters of graph to zero. | |
| void | reset_arc (Arc *arc) const noexcept |
Reset all the control attributes of arc. | |
| void | reset_nodes () const |
| Reset all the nodes of graph (the control bits, the state, the counter and the cookie) | |
| void | reset_arcs () const |
| Reset all the arcs of graph (the control bits, the state, the counter and the cookie) | |
| void | reset_bit_nodes (int bit) const noexcept |
Reset bit to zero 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_nodes () const noexcept |
| Reset all the bits for all the nodes 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 |
| Reset all the cookies to `nullptr for all the nodes of graph. | |
| void | reset_cookie_arcs () const noexcept |
| Reset all the cookies to `nullptr for all the arcs of graph. | |
| Node * | insert_node (const Node_Type &node_info) |
| Allocate a new node, set by copy its data content and insert it into the graph. | |
| Node * | insert_node (Node_Type &&node_info=Node_Type()) |
| Allocate a new node, set by moving its data content and insert it into the graph. | |
| template<typename... Args> | |
| Node * | emplace_node (Args &&... args) |
| Insert a new node in the graph by constructing it in-place with the given args. | |
| Arc * | insert_arc (Node *src, Node *tgt, const Arc_Type &arc_info) |
| Create and insert a new arc linking two nodes and copying data. | |
| Arc * | insert_arc (Node *src, Node *tgt, Arc_Type &&arc_info=Arc_Type()) |
| Create and insert a new arc linking two nodes and moving the received data. | |
| template<typename... Args> | |
| Arc * | emplace_arc (Node *src, Node *tgt, Args &&... args) |
| Insert a new arc in the graph by constructing its associated data in-place with the given args. | |
| template<class Operation > | |
| bool | traverse_nodes (Operation &op) const |
| Conditioned traversal of all the nodes of a graph. | |
| template<class Operation > | |
| bool | traverse_nodes (Operation &&op=Operation()) const |
Overload of traverse_nodes(Operation&) that accepts rvalues. | |
| template<class Operation > | |
| bool | traverse_arcs (Operation &op) const |
| Conditioned traversal of all the arcs of a graph. | |
| template<class Operation > | |
| bool | traverse_arcs (Operation &&op=Operation()) const |
Overload of traverse_arcs(Operation&) that accepts rvalues. | |
| template<class Operation > | |
| bool | traverse_arcs (Node *p, Operation &op) const |
| Conditioned traversal of all the adjacent arcs of a node. | |
| template<class Operation > | |
| bool | traverse_arcs (Node *p, Operation &&op=Operation()) const |
Overload of traverse_arcs(Node*, Operation&) that accepts rvalues. | |
| template<class Operation > | |
| void | for_each_node (Operation &operation) const |
| Unconditionally traverse all the nodes of graph and on each one perform an operation. | |
| template<class Operation > | |
| void | for_each_node (Operation &&operation=Operation()) const |
Overload of for_each_node(Operation&) that accepts rvalues. | |
| template<class Operation > | |
| void | for_each_arc (Operation &op) const |
| Unconditionally traverse all the arcs of graph and on each one perform an operation. | |
| template<class Operation > | |
| void | for_each_arc (Operation &&operation=Operation()) const |
Overload of for_each_arc(Operation&) that accepts rvalues. | |
| template<class Operation > | |
| void | for_each_arc (Node *p, Operation &op) const |
| Unconditionally traverse all the arcs adjacnt to a node and on each one perform an operation. | |
| template<class Operation > | |
| void | for_each_arc (Node *p, Operation &&op=Operation()) const |
Overload of for_each_arc(Node*, Operation&) that accepts rvalues. | |
| template<class Operation > | |
| bool | all_nodes (Operation &op) const |
| Check if all the nodes of graph satisfy an boolean condition. | |
| template<class Operation > | |
| bool | all_nodes (Operation &&op=Operation()) const |
Overload of all_nodes(Operation&) that accepts rvalues. | |
| template<class Operation > | |
| bool | all_arcs (Operation &op) const |
| Check if all the arcs of graph satisfy a boolean condition. | |
| template<class Operation > | |
| bool | all_arcs (Operation &&op=Operation()) const |
Overload of all_arcs(Operation&) that accepts rvalues. | |
| template<class Operation > | |
| bool | all_arcs (Node *p, Operation &op) const |
| Check if all the arcs adjacent to a node satisfy an boolean condition. | |
| template<class Operation > | |
| bool | all_arcs (Node *p, Operation &&op=Operation()) const |
Overload of all_arcs(Node*, Operation&) that accepts rvalues. | |
| template<typename T = Node_Type> | |
| auto | nodes_map (std::function< T(Node *)> op) const |
| Map the nodes of a graph to a specific range. | |
| template<typename T = Arc_Type> | |
| auto | arcs_map (std::function< T(Arc *)> operation) const |
| Map the arcs of a graph to a specific range. | |
| template<typename T = Arc_Type> | |
| auto | arcs_map (Node *p, std::function< T(Arc *)> operation) const |
| Map the adjacent arcs of a node to a specific range. | |
| template<typename T = Node_Type> | |
| T | foldl_nodes (const T &init, std::function< T(const T &, Node *)> op) const |
| Folding of nodes on a graph. | |
| template<typename T = Arc_Type> | |
| T | foldl_arcs (const T &init, std::function< T(const T &, Arc *)> op) const |
| Folding of arcs on a graph. | |
| template<typename T = Arc_Type> | |
| T | foldl_arcs (Node *p, const T &init, std::function< T(const T &, Arc *)> op) const |
| Folding of arcs of a node. | |
| template<class Op > | |
| auto | filter_nodes (Op &op) const |
| Filter the nodes satisfying a condition. | |
| template<class Op > | |
| auto | filter_nodes (Op &&op) const |
Overload of filter_nodes(Op&) that accepts rvalues. | |
| template<class Op > | |
| auto | filter_arcs (Op &op) const |
| Filter the arcs of graph satisfying a condition. | |
| template<class Op > | |
| auto | filter_arcs (Op &&op) const |
Overload of filter_arcs(Op&) that accepts rvalues. | |
| template<class Op > | |
| auto | filter_arcs (Node *p, Op &op) const |
| Filter the arcs adjacent to a node satisfying a condition. | |
| template<class Op > | |
| auto | filter_arcs (Node *p, Op &&op) const |
Overload of filter_arcs(Node*, Op&) that accepts rvalues. | |
| template<class Operation > | |
| bool | exists_node (Operation &op) const |
| Determine if exists at least a node satisfying a condition. | |
| template<class Operation > | |
| bool | exists_node (Operation &&op=Operation()) const |
Overload of exists_node(Operation&) that accepts rvalues. | |
| template<class Operation > | |
| bool | exists_arc (Operation &op) const |
| Determine if exists at least a arc satisfying a condition. | |
| template<class Operation > | |
| bool | exists_arc (Operation &&op=Operation()) const |
Overload of exists_arc(Operation&) that accepts rvalues. | |
| template<class Operation > | |
| bool | exists_arc (Node *p, Operation &op) const |
| Determine if exists at least a arc adjacent to a node satisfying a condition. | |
| template<class Operation > | |
| bool | exists_arc (Node *p, Operation &&op=Operation()) const |
Overload of exists_arc(Node*, Operation&) that accepts rvalues. | |
| template<class Operation > | |
| bool | none_node (Operation &op) const |
| Determine if no node satisfies a condition. | |
| template<class Operation > | |
| bool | none_node (Operation &&op) const |
Overload of none_node(Operation&) that accepts rvalues. | |
| template<class Operation > | |
| bool | none_arc (Operation &op) const |
| Determine if no arc satisfies a condition. | |
| template<class Operation > | |
| bool | none_arc (Operation &&op) const |
Overload of none_arc(Operation&) that accepts rvalues. | |
| template<class Operation > | |
| bool | none_arc (Node *p, Operation &op) const |
| Determine if no arc adjacent to a node satisfies a condition. | |
| template<class Operation > | |
| bool | none_arc (Node *p, Operation &&op) const |
Overload of none_arc(Node*, Operation&) that accepts rvalues. | |
| template<class Operation = std::function<bool(Node*)>> | |
| size_t | count_nodes (Operation op=[](Node *) { return true;}) const |
| Count the nodes satisfying a condition. | |
| template<class Operation = std::function<bool(Arc*)>> | |
| size_t | count_arcs (Operation op=[](Arc *) { return true;}) const |
| Count the arcs satisfying a condition. | |
| template<class Operation = std::function<bool(Arc*)>> | |
| size_t | count_arcs (Node *p, Operation op=[](Arc *) { return true;}) const |
| Count arcs adjacent to a node satisfying a condition. | |
| template<typename T = double, class Extract > | |
| T | sum_arcs (Node *p, Extract extract) const |
| Sum values derived from arcs adjacent to a node. | |
| template<typename T = double> | |
| T | sum_arcs (Node *p) const |
Overload of sum_arcs(Node*, Extract) using the arc info as extractor. | |
| template<class Compare = std::function<bool(Arc*, Arc*)>> | |
| Arc * | min_arc (Node *p, Compare cmp=[](Arc *a, Arc *b) { return a->get_info()< b->get_info();}) const |
| Find the minimum arc adjacent to a node. | |
| template<class Compare = std::function<bool(Arc*, Arc*)>> | |
| Arc * | max_arc (Node *p, Compare cmp=[](Arc *a, Arc *b) { return a->get_info()< b->get_info();}) const |
| Find the maximum arc adjacent to a node. | |
| template<class Compare = std::function<bool(Arc*, Arc*)>> | |
| Arc * | min_arc (Compare cmp=[](Arc *a, Arc *b) { return a->get_info()< b->get_info();}) const |
| Find the minimum arc in the entire graph. | |
| template<class Compare = std::function<bool(Arc*, Arc*)>> | |
| Arc * | max_arc (Compare cmp=[](Arc *a, Arc *b) { return a->get_info()< b->get_info();}) const |
| Find the maximum arc in the entire graph. | |
| template<class Operation > | |
| std::pair< DynList< Node * >, DynList< Node * > > | partition_nodes (Operation op) const |
| Partition nodes into two groups based on a predicate. | |
| template<class Operation > | |
| std::pair< DynList< Arc * >, DynList< Arc * > > | partition_arcs (Operation op) const |
| Partition arcs into two groups based on a predicate. | |
| DynList< Node * > | adjacent_nodes (Node *p) const |
| Get all adjacent nodes (neighbors) of a node. | |
| template<class Op > | |
| Node * | search_node (Op &op) const |
| Linear search of a node. | |
| template<class Op > | |
| Node * | search_node (Op &&op) const |
Overload of search_node(Op&) that accepts rvalues. | |
| Node * | find_node (const Node_Type &info) const noexcept |
| Find a node mathing a content. | |
| template<class Op > | |
| Arc * | search_arc (Op &op) const |
| Linear search of an arc. | |
| template<class Op > | |
| Arc * | search_arc (Op &&op) const |
Overload of search_arc(Op&) that accepts rvalues. | |
| Arc * | find_arc (const Arc_Type &info) const noexcept |
| Find an arc mathing a content. | |
| template<class Operation > | |
| Arc * | search_arc (Node *p, Operation &op) const |
| Linear search of an arc. | |
| template<class Operation > | |
| Arc * | search_arc (Node *p, Operation &&op=Operation()) const |
Overload of search_arc(Node*, Operation&) that accepts rvalues. | |
| Arc * | search_arc (Node *src, Node *tgt) const noexcept |
| Search an arc linking two nodes. | |
| template<template< typename > class Container = Aleph::DynList> | |
| Container< Node * > | nodes () const |
| Return a container with all the nodes of the graph. | |
| template<template< typename > class Container = Aleph::DynList> | |
| Container< Arc * > | arcs () const |
| Return a container with all the arcs of the graph. | |
| template<template< typename > class Container = Aleph::DynList> | |
| Container< Arc * > | arcs (Node *p) const |
| Return a container with all the arcs adjacent to a node. | |
| auto | get_node_it () const noexcept |
| Obtains an iterator to the nodes of graph. | |
| auto | get_arc_it () const noexcept |
| Obtains an iterator to the arc of graph. | |
| auto | get_arc_it (Node *p) const noexcept |
| Obtains an iterator to the adjacent arcs of a node. | |
| In_Iterator | get_in_it (Node *p) const noexcept |
Return an input iterator on the incoming arcs to p | |
| Out_Iterator | get_out_it (Node *p) const noexcept |
Return an output iterator on the incoming nodes to p | |
| Arc * | search_directed_arc (Node *src, Node *tgt) const noexcept |
| Search a directed arc linking two nodes. | |
| DynList< Node * > | in_nodes (Node *p) const |
Return a list with the incoming nodes to p | |
| DynList< Node * > | out_nodes (Node *p) const |
Return a list with the outcoming nodes to p | |
| DynList< Arc * > | out_arcs (Node *p) const |
| Return a list with the outcoming arcs to p`. | |
| DynList< Arc * > | in_arcs (Node *p) const |
| Return a list with the incoming arcs to p`. | |
| auto | in_pairs (Node *p) const |
| Return a list of pair incoming arcs and nodes. | |
| auto | out_pairs (Node *p) const |
| Return a list of pair outcoming arcs and nodes. | |
| size_t | in_degree (Node *p) const noexcept |
| Compute the input degree of a node. | |
| size_t | out_degree (Node *p) const noexcept |
| Compute the output degree of a node. | |
| template<class Itor , class Operation > | |
| bool | traverse_arcs (Node *p, Operation &op) const |
| Traverse of arcs of a node according to specific arcs iterator. | |
| template<class Itor , class Operation > | |
| void | for_each_arc (Node *p, Operation &op) const |
Perform op on each arc of node p | |
| template<class Op > | |
| bool | traverse_in_arcs (Node *p, Op &op) const |
Traverse the incoming arcs of node p executing the conditioned operation | |
| template<class Op > | |
| bool | traverse_in_arcs (Node *p, Op &&op=Op()) const |
Overload of traverse_in_arcs(Node*, Op&) that accepts rvalues. | |
| template<class Op > | |
| void | for_each_in_arc (Node *p, Op &op) const |
Perform op on each incoming arc of node p | |
| template<class Op > | |
| void | for_each_in_arc (Node *p, Op &&op=Op()) const |
Overload of for_each_in_arc(Node*, Op&) that accepts rvalues. | |
| template<class Op > | |
| bool | all_in_arcs (Node *p, Op &op) const |
Return true if op is true for all the incoming arcs to node p | |
| template<class Op > | |
| bool | all_in_arcs (Node *p, Op &&op=Op()) const |
Overload of all_in_arcs(Node*, Op&) that accepts rvalues. | |
| template<class Op > | |
| bool | exists_in_arc (Node *p, Op &op) const |
Return true if it exists a incoming arc to p returning true for op | |
| template<class Op > | |
| bool | exists_in_arc (Node *p, Op &&op=Op()) const |
Overload of exists_in_arc(Node*, Op&) that accepts rvalues. | |
| template<class Op > | |
| auto | search_in_arc (Node *p, Op &op) const |
| Search an incoming arc to a node satisfaying a condition. | |
| template<class Op > | |
| auto | search_in_arc (Node *p, Op &&op=Op()) const |
Overload of search_in_arc(Node*, Op&) that accepts rvalues. | |
| template<typename T > | |
| auto | in_arcs_map (Node *p, std::function< T(Arc *)> op) const |
Return a list of incoming arcs of a node mapped to items of type given by transformation op. | |
| template<typename T = Arc_Type> | |
| T | foldl_in_arcs (Node *p, const T &init, std::function< T(const T &, Arc *)> op) const |
| Fold the incoming arcs of a node. | |
| template<class Op > | |
| DynList< Arc * > | filter_in_arcs (Node *p, Op &op) const |
| Filter the incoming arcs of a node. | |
| template<class Op > | |
| auto | filter_in_arcs (Node *p, Op &&op=Op()) const |
Overload of filter_in_arcs(Node*, Op&) that accepts rvalues. | |
| template<class Op > | |
| bool | traverse_out_arcs (Node *p, Op &op) const |
Traverse the outcoming arcs of node p executing the conditioned operation | |
| template<class Op > | |
| bool | traverse_out_arcs (Node *p, Op &&op=Op()) const |
Overload of traverse_out_arcs(Node*, Op&) that accepts rvalues. | |
| template<class Op > | |
| void | for_each_out_arc (Node *p, Op &op) const |
Perform op on each outcoming arc of node p | |
| template<class Op > | |
| void | for_each_out_arc (Node *p, Op &&op=Op()) const |
Overload of for_each_out_arc(Node*, Op&) that accepts rvalues. | |
| template<class Op > | |
| bool | all_out_arcs (Node *p, Op &op) const |
Return true if op is true for all the outcoming arcs to node p | |
| template<class Op > | |
| bool | all_out_arcs (Node *p, Op &&op=Op()) const |
Overload of all_out_arcs(Node*, Op&) that accepts rvalues. | |
| template<class Op > | |
| bool | exists_out_arc (Node *p, Op &op) const |
Return true if it exists a outcoming arc to p returning true for op | |
| template<class Op > | |
| bool | exists_out_arc (Node *p, Op &&op=Op()) const |
Overload of exists_out_arc(Node*, Op&) that accepts rvalues. | |
| template<class Op > | |
| auto | search_out_arc (Node *p, Op &op) const |
| Search an outcoming arc to a node satisfaying a condition. | |
| template<class Op > | |
| auto | search_out_arc (Node *p, Op &&op=Op()) const |
Overload of search_out_arc(Node*, Op&) that accepts rvalues. | |
| template<typename T = Arc_Type> | |
| auto | out_arcs_map (Node *p, std::function< T(Arc *)> op) const |
Return a list of outcoming arcs of a node mapped to items of type given by transformation op. | |
| template<typename T = Arc_Type> | |
| T | foldl_out_arcs (Node *p, const T &init, std::function< T(const T &, Arc *)> op) const |
| Fold-left over outcoming arcs of a node. | |
| template<class Op > | |
| DynList< Arc * > | filter_out_arcs (Node *p, Op &op) const |
| Filter the outcoming arcs of a node. | |
| template<class Op > | |
| auto | filter_out_arcs (Node *p, Op &&op=Op()) const |
Overload of filter_out_arcs(Node*, Op&) that accepts rvalues. | |
| template<class Compare > requires (has_node_dlink_v<GT>) | |
| void | sort_nodes (Compare &cmp) noexcept |
| template<class Compare > requires (has_node_dlink_v<GT>) | |
| void | sort_nodes (Compare &&cmp=Compare()) noexcept |
| template<class Compare > requires (has_arc_dlink_v<GT>) | |
| void | sort_arcs (Compare &cmp) noexcept |
| Sort all the arcs of the graph according to a specific criteria. | |
| template<class Compare > requires (has_arc_dlink_v<GT>) | |
| void | sort_arcs (Compare &&cmp=Compare()) noexcept |
Private Member Functions | |
| Arc * | insert_arc (Node *src_node, Node *tgt_node, void *a) |
Static Private Member Functions | |
| static Node * | dlink_to_node (Dlink *p) noexcept |
| static Arc * | dlink_to_arc (Dlink *p) noexcept |
| static Arc_Node * | dlink_to_arc_node (Dlink *p) noexcept |
| static Arc * | void_to_arc (Arc_Node *arc_node) noexcept |
Private Attributes | |
| Dlink | node_list |
| Dlink | arc_list |
Friends | |
| class | GraphCommon< List_Graph< _Graph_Node, _Graph_Arc >, _Graph_Node, _Graph_Arc > |
Additional Inherited Members | |
| Static Public Member Functions inherited from GraphCommon< GT, Node, Arc > | |
| template<class N1 , class N2 = N1> | |
| static void | map_nodes (N1 *p, N2 *q) noexcept |
| Map the nodes through their cookies. | |
| template<class A1 , class A2 = A1> | |
| static void | map_arcs (A1 *p, A2 *q) noexcept |
| Map the arcs through their cookies. | |
| Static Public Attributes inherited from GraphCommon< GT, Node, Arc > | |
| template<class U > | |
| static constexpr bool | has_node_dlink_v |
| Sort all the nodes of the graph according to a specific criteria. | |
| template<class U > | |
| static constexpr bool | has_arc_dlink_v |
| Protected Member Functions inherited from GraphCommon< GT, Node, Arc > | |
| void | init () noexcept |
| void | common_swap (GT &g) noexcept |
| template<class Predicate > | |
| DynList< Arc * > | collect_arcs_if (Predicate pred) const |
| Collect all arcs matching a predicate. | |
| template<class Predicate > | |
| void | remove_arcs_if (Predicate pred) |
| Remove all arcs matching a predicate. | |
| Protected Attributes inherited from GraphCommon< GT, Node, Arc > | |
| void * | cookie = nullptr |
| size_t | num_nodes = 0 |
| size_t | num_arcs = 0 |
| bool | digraph = false |
Detailed Description
class Aleph::List_Graph< _Graph_Node, _Graph_Arc >
Graph implemented with double-linked adjacency lists.
This class manages two template parameters
_Graph_Node: the type of node, which previously must have been defined through of Graph_Node class._Graph_Arc: the type of arc, which previously must have been defined through ofGraph_Arcclass.
It is highly recommendable to use an alias for the final graph type. Some such as
using My_Graph = List_Graph<Graph_Node<My_Node_Type>, Graph_Arc<My_Arc_Type>>;
Once instantiated a List_Graph object, its nodes and arcs must be accessed through the following subclasses:
List_Graph<Node, Arc>::NodeList_Graph<Node, Arc>::Arc
Directed or non-directed? (how and when using them)
Using of alias is very "natural". For the previously shown alias example, you could type:
My_Graph::Node * node_ptr = .... My_Graph::Arc * arc_ptr = ....
This graph can be directed or non-directed. From a functional perspective, what gives the difference between a directed graph and a non-directed one is the way for accessing to arcs given a node. Perhaps an example could help to understand better. Suppose that you have a graph g and two node pointers p and q respectively. Now, to specify an arc, you execute some such as
auto arc = g.insert_arc(p, q);
If you execute
auto my_node = g.get_connected_arc(arc, p);
Then you will get q, which is the node connected to p through arc. Now, if you execute
auto my_node = g.get_connected_arc(arc, q);
Then you will get p, which is the node connected to q through arc. In this situation you are trying g as a non-directed graph.
However, when you inserted the arc, you specified a source node and a target one. This knowledge, which is embedded in the internal data structure, can be profited by the user for treating g as a directed graph. In that case, instead of using the get_connected_node() method, you use other methods expressing the arc sense. For instance, in the previous example you could do:
auto src = g.get_src_node(arc); // source node of arc auto tgt = g.get_tgt_node(arc); // target node of arc
The class <tt>List_Digraph</tt>
Aleph-w ( \(\aleph_\omega\)) exports a derived named List_Digraph. At the functional level, there is no almost any difference with List_Graph. The only functional difference is that get_connected_node() has no any sense on List_Digraph objects. Be very careful with the fact that Aleph-w ( \(\aleph_\omega\)) does not perform any check of this. To use get_connected_node() for List_Digraph objects is an programming error.
So that, if there is no practically much difference, then, why to use List_Digraph?
Memory consumption
Probably List_Graph is the more versatile graph class of Aleph-w ( \(\aleph_\omega\)). However, its versatility is at the expense of highest memory consumption. First, the internal lists are double, not single. Second, for each arc, there is a double linked list of arc references. This implicates that the same arc information is duplicated in each involved node, the source and the target one.
At the contrary, in List_Digraph the arc references are not stored in the target node. This fact could considerably save memory.
Performance
For List_Graph all (yes, all!) operations are \(O(1)\), but, as said, this performance is achieved at the expense of memory.
For List_Digraph all operations are \(O(1)\), except node removal. In this case, since with this representation there is no direct way to know the incoming arcs, the node removal requires traversing all the arcs for checking for those incoming to the removed one. So, the node removal is \(O(E)\).
Versatility (<tt>List_Graph</tt> vs <tt>List_Digraph</tt>)
So that a guideline for choosing List_Graph vs List_Digraph is to ask if the node removal will be used. If yes, then how often? If you know that the node removal will be used several times, then prefer List_Graph; otherwise, that is, you know there are no node removals, then use List_Digraph, since it uses less memory.
Note on validations
Almost all the methods of this class do not perform any validation. This is especially delicate for those methods involved topologic changes (insertions and removals of nodes or arcs).
When a removal operation is called, this assumes that it is performed on a valid object. For example, remove_node(p) assumes that p is a valid node pointer. For valid we understand that the pointer was returned for another method of graph class and on the same graph. At this regard, is very important to be careful because no method validates if the involved object was or not created either this belongs to the graph.
Definition at line 425 of file tpl_graph.H.
Member Typedef Documentation
◆ Arc
| using Aleph::List_Graph< _Graph_Node, _Graph_Arc >::Arc = _Graph_Arc |
The node class type.
Definition at line 433 of file tpl_graph.H.
◆ Arc_Type
| using Aleph::List_Graph< _Graph_Node, _Graph_Arc >::Arc_Type = typename Arc::Arc_Type |
The type of data stored in the arc.
Definition at line 439 of file tpl_graph.H.
◆ CommonBase
| using Aleph::List_Graph< _Graph_Node, _Graph_Arc >::CommonBase = GraphCommon<List_Graph<_Graph_Node, _Graph_Arc>, _Graph_Node, _Graph_Arc> |
Definition at line 444 of file tpl_graph.H.
◆ GT
| using Aleph::List_Graph< _Graph_Node, _Graph_Arc >::GT = List_Graph |
Definition at line 430 of file tpl_graph.H.
◆ Node
| using Aleph::List_Graph< _Graph_Node, _Graph_Arc >::Node = _Graph_Node |
The graph type.
Definition at line 432 of file tpl_graph.H.
◆ Node_Type
| using Aleph::List_Graph< _Graph_Node, _Graph_Arc >::Node_Type = typename Node::Node_Type |
Constructor & Destructor Documentation
◆ List_Graph() [1/3]
|
inline |
Copy constructor.
Definition at line 780 of file tpl_graph.H.
◆ List_Graph() [2/3]
|
inlinenoexcept |
◆ ~List_Graph()
|
inlinevirtual |
Destructor: all the nodes and arcs and removed and freed.
Definition at line 783 of file tpl_graph.H.
References Aleph::clear_graph().
◆ List_Graph() [3/3]
|
default |
Construct an empty graph.
Member Function Documentation
◆ connect_arc()
|
inlinevirtualnoexcept |
Connect a previously disconnected arc to the graph.
This method serves for connecting an arc that has been disconnected with disconnect_arc() method. Once connected, the arc is again part of the graph and can be removed and freed by remove_arc() or by the destructor.
- Parameters
-
[in] arc pointer to the arc to connect
- Returns
- a pointer to the connected arc
Definition at line 733 of file tpl_graph.H.
References Aleph::Dlink::append(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::arc_list, GraphCommon< GT, Node, Arc >::digraph, GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::maps(), and GraphCommon< GT, Node, Arc >::num_arcs.
Referenced by TEST().
◆ disconnect_arc()
|
inlinevirtualnoexcept |
Disconnect an arc from graph.
This method removes an arc from the graph; that is, it does no longer belong to the graph. However, the memory is not freed.
Although the use of this method is occasional, it is not exceptional. For example, some situations require to temporarily disconnect the arc and afterward connect it again.
The disconnected arc is already for being reinserted in the graph with the connect_arc() method.
- Warning
- The arc remains out of graph. So, from the graph perspective, a disconnected arc does not exist longer, and it will not be freed by the graph destructor neither by
remove_arc(). In fact, to callremove_arc()on a disconnected arc is an error. It is your responsibility to free a disconnected arc.
- Parameters
-
[in] arc pointer to the arc to disconnect
- See also
- connect_arc(Arc * arc)
Definition at line 699 of file tpl_graph.H.
References Aleph::Dlink::del(), GraphCommon< GT, Node, Arc >::digraph, GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::maps(), and GraphCommon< GT, Node, Arc >::num_arcs.
Referenced by TEST().
◆ dlink_to_arc()
|
inlinestaticprivatenoexcept |
◆ dlink_to_arc_node()
|
inlinestaticprivatenoexcept |
Definition at line 464 of file tpl_graph.H.
Referenced by Aleph::List_Graph< _Graph_Node, _Graph_Arc >::Node_Arc_Iterator::get_current_arc_node(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::Node_Arc_Iterator::get_current_arc_node_ne(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::get_first_arc(), and Aleph::List_Graph< _Graph_Node, _Graph_Arc >::remove_node().
◆ dlink_to_node()
|
inlinestaticprivatenoexcept |
Definition at line 454 of file tpl_graph.H.
Referenced by Aleph::List_Graph< _Graph_Node, _Graph_Arc >::get_first_node().
◆ get_arc_dlink()
|
inlinenoexcept |
Return a reference to the internal arc Dlink for sorting.
This accessor, get_arc_dlink(), exposes the internal arc_list used by sort operations (e.g., sort_arcs()).
- Returns
- Dlink& reference to
arc_list.
- Exceptions
-
none
- Note
- Complexity: O(1)
- Exception safety: noexcept
- Intended for sorting operations; mutating the list directly can violate graph invariants if used outside that context.
Definition at line 501 of file tpl_graph.H.
References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::arc_list.
◆ get_first_arc() [1/2]
|
inline |
Return any arc in the graph.
This method serves as an arc of depart in the graph. Some algorithms only need an initial arc which could be anyone. In these cases, this method is indicated.
- Note
- The idea of "first arc" does not obey any order; the method simply returns a arc.
- Returns
- A pointer to an arc in the graph
Definition at line 769 of file tpl_graph.H.
References ah_range_error_if, Aleph::List_Graph< _Graph_Node, _Graph_Arc >::arc_list, Aleph::List_Graph< _Graph_Node, _Graph_Arc >::dlink_to_arc(), and GraphCommon< GT, Node, Arc >::get_num_arcs().
◆ get_first_arc() [2/2]
|
inline |
Return any arc adjacent to a node.
This method serves as an arc of departure 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.
- Note
- The idea of "first arc" does not obey any order; the method simply returns an arc. The majority of algorithms should be independent of the processing order of arcs
- Returns
- A pointer to an arc adjacent to
node
Definition at line 595 of file tpl_graph.H.
References ah_range_error_if, Aleph::Arc_Node::arc, Aleph::List_Graph< _Graph_Node, _Graph_Arc >::dlink_to_arc_node(), and GraphCommon< GT, Node, Arc >::get_num_arcs().
Referenced by Aleph::Tarjan_Connected_Components< GT, Itor, SA >::build_path(), GraphCommon< GT, Node, Arc >::get_arc(), GraphCommon< GT, Node, Arc >::get_arc(), TEST(), TEST(), and TEST().
◆ get_first_node()
|
inline |
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.
- Note
- The idea of "first node" does not obey any order; the method simply returns a node.
- Returns
- A pointer to a node in the graph
Definition at line 576 of file tpl_graph.H.
References ah_range_error_if, Aleph::List_Graph< _Graph_Node, _Graph_Arc >::dlink_to_node(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::node_list, and GraphCommon< GT, Node, Arc >::num_nodes.
Referenced by Aleph::breadth_first_traversal(), Aleph::compute_bipartite(), demo_biconnected_components(), demo_cut_nodes(), demo_fixing_vulnerabilities(), demo_network_vulnerability(), Aleph::depth_first_traversal(), GraphCommon< GT, Node, Arc >::get_node(), Aleph::Prim_Min_Spanning_Tree< GT, Distance, SA >::operator()(), Aleph::Prim_Min_Spanning_Tree< GT, Distance, SA >::operator()(), Aleph::Breadth_First_Traversal< GT, Operation, SA >::operator()(), Aleph::Depth_First_Traversal< GT, Operation, SA >::operator()(), Aleph::Compute_Cut_Nodes< GT, SA >::operator()(), Aleph::Find_Depth_First_Spanning_Tree< GT, SA >::operator()(), Aleph::Find_Breadth_First_Spanning_Tree< GT, SA >::operator()(), TEST(), and TEST().
◆ get_node_dlink()
|
inlinenoexcept |
Return a reference to the internal node Dlink for sorting.
This accessor, get_node_dlink(), exposes the internal node_list used by sort operations (e.g., sort_nodes()).
- Returns
- Dlink& reference to
node_list.
- Exceptions
-
none
- Note
- Complexity: O(1)
- Exception safety: noexcept
- Intended for sorting operations; mutating the list directly can violate graph invariants if used outside that context.
Definition at line 487 of file tpl_graph.H.
References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::node_list.
◆ insert_arc() [1/3]
|
inline |
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 andtgtthe 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] src pointer to the source node. [in] tgt pointer to the target node. [in] arc_info the data to be moved to the node.
- Returns
- a pointer to the arc already inserted into the graph
- Exceptions
-
bad_alloc if there is no enough memory.
Definition at line 1223 of file graph-dry.H.
◆ insert_arc() [2/3]
|
inline |
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] src pointer to the source node. [in] tgt pointer to the target node. [in] arc_info the data to be copied to the node.
- Returns
- a pointer to the arc already inserted into the graph
- Exceptions
-
bad_alloc if there is no enough memory.
Definition at line 1193 of file graph-dry.H.
◆ insert_arc() [3/3]
|
inlineprivate |
Definition at line 604 of file tpl_graph.H.
References Aleph::Dlink::append(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::arc_list, GraphCommon< GT, Node, Arc >::digraph, Aleph::maps(), and GraphCommon< GT, Node, Arc >::num_arcs.
Referenced by Aleph::__find_depth_first_spanning_tree(), Aleph::__map_subgraph(), add_edge(), EulerianUndirectedTest::add_edge(), HamiltonianUndirectedTest::add_edge(), build_barbell_graph(), build_campus_network(), build_complete_graph(), build_complete_graph(), build_computer_network(), Aleph::GraphCopyWithMapping< GT, Tree >::build_copy(), build_cycle_graph(), build_cyclic_graph(), build_network_graph(), build_path_graph(), build_social_network(), Aleph::build_subgraph(), Aleph::Build_Subgraph< GT, SA >::build_subgraph(), Aleph::Find_Breadth_First_Spanning_Tree< GT, SA >::build_tree(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::build_tree(), Aleph::Find_Depth_First_Spanning_Tree< GT, SA >::build_tree(), build_tree_graph(), build_two_clusters(), build_weighted_chain(), Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::compute_min_paths_tree(), Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::compute_min_paths_tree(), Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::compute_partial_min_paths_tree(), Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::compute_partial_min_paths_tree(), Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::compute_partial_path(), create_chain(), create_complete_bipartite(), FindPathTest::create_complete_graph(), create_cycle(), create_cycle_graph(), create_disconnected_bipartite(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::create_dummy_node(), create_grid_graph(), FindPathTest::create_linear_graph(), create_path_graph(), create_star_graph(), create_triangle(), demo_comparison(), demo_connected_components(), demo_definition(), demo_density(), demo_eulerian_cycle(), demo_fixing_vulnerabilities(), demo_hierholzer(), demo_testing(), GraphCommon< GT, Node, Arc >::emplace_arc(), example_algorithm_comparison(), example_api_patterns(), example_basic_sccs(), example_comparison_tarjan(), example_dag(), example_lightweight_version(), example_strongly_connected(), Aleph::find_breadth_first_spanning_tree(), generate_random_graph(), Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::insert_arc(), GraphCommon< GT, Node, Arc >::insert_arc(), GraphCommon< GT, Node, Arc >::insert_arc(), Aleph::GraphCopyWithMapping< GT, Tree >::insert_arc(), Aleph::Arcs_Index< GT, Compare, Tree, SA >::insert_in_graph(), Aleph::IndexArc< GT, Tree, SA >::insert_in_graph(), Aleph::IndexArc< GT, Tree, SA >::insert_in_graph(), Aleph::IO_Graph< GT, Load_Node, Store_Node, Load_Arc, Store_Arc, NF, AF >::load(), Aleph::IO_Graph< GT, Load_Node, Store_Node, Load_Arc, Store_Arc, NF, AF >::load_in_text_mode(), main(), Aleph::Compute_Cut_Nodes< GT, SA >::map_subgraph(), Aleph::Prim_Min_Spanning_Tree< GT, Distance, SA >::min_spanning_tree(), Aleph::Build_Grid< GT, Operation_On_Node, Operation_On_Arc >::operator()(), Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::paint_min_spanning_tree(), parse_arc_definition(), Aleph::Xml_Graph< GT, Node_Reader, Arc_Reader, Node_Writer, Arc_Writer >::read_graph(), AStarBasicTest::SetUp(), AStarGridTest::SetUp(), AStarDijkstraModeTest::SetUp(), AStarHeapTest< HeapTag >::SetUp(), CookieGuardTest::SetUp(), GraphFunctionalTest::SetUp(), GraphTraverseTest::SetUp(), DisconnectedGraphTest::SetUp(), TreeGraphTest::SetUp(), CyclicGraphTest::SetUp(), SimpleGraphTest::SetUp(), IOGraphTest::SetUp(), GraphArcRemovalTest::SetUp(), GraphIteratorTest::SetUp(), GraphMoveTest::SetUp(), PathTest::SetUp(), MatGraphTestBase::SetUp(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), test_cross_comparison(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), test_ks_single_edge(), test_ks_triangle(), test_performance_ks(), test_performance_sw(), test_sw_complete_k4(), test_sw_single_edge(), test_sw_triangle_weighted(), test_sw_two_heavy_clusters(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), and TYPED_TEST().
◆ insert_node() [1/3]
|
inline |
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_info info 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_allod if there is no enough memory
Definition at line 1116 of file graph-dry.H.
◆ insert_node() [2/3]
|
inlinevirtualnoexcept |
Insertion of a node already allocated.
This method takes a pointer to a node already allocated and inserts it in the graph.
The node allocation and its life in memory are the user's responsibility. At this regard, take into account that the graph destructor and remove_method() will assume that the nodes were allocated with new operator, and consequently it will call to delete for deallocating. So, it is very dangerous to use nodes whose memory does not come from new.
- Note
- Since that it is programmer responsibility to allocate memory for the node, and in addition, the graph destructor and the
remove_noe()will calldeleteoperator, it is preferable and highly recommended to use any other overloaded version ofinsert_node()which automatically allocates the node's memory. In fact, those overloaded methods invoke this version.
- Parameters
-
[in] node a pointer to an already allocated node.
- Returns
- the node pointer
Reimplemented in Aleph::Euclidian_Graph< __Euclidian_Node, __Euclidian_Arc >.
Definition at line 524 of file tpl_graph.H.
References Aleph::Dlink::append(), and GraphCommon< GT, Node, Arc >::num_nodes.
Referenced by Aleph::__find_depth_first_spanning_tree(), Aleph::__map_subgraph(), EulerianUndirectedTest::add_node(), HamiltonianUndirectedTest::add_node(), build_barbell_graph(), build_campus_network(), build_complete_graph(), build_complete_graph(), build_computer_network(), Aleph::GraphCopyWithMapping< GT, Tree >::build_copy(), build_cycle_graph(), build_cyclic_graph(), build_network_graph(), build_path_graph(), build_social_network(), Aleph::build_subgraph(), Aleph::Build_Subgraph< GT, SA >::build_subgraph(), Aleph::Find_Depth_First_Spanning_Tree< GT, SA >::build_tree(), Aleph::Find_Breadth_First_Spanning_Tree< GT, SA >::build_tree(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::build_tree(), Aleph::Find_Depth_First_Spanning_Tree< GT, SA >::build_tree(), build_tree_graph(), build_two_clusters(), build_weighted_chain(), Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::compute_min_paths_tree(), Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::compute_min_paths_tree(), Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::compute_partial_min_paths_tree(), Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::compute_partial_min_paths_tree(), Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::compute_partial_path(), Aleph::Compute_Cut_Nodes< GT, SA >::create_and_map_node(), create_chain(), create_complete_bipartite(), FindPathTest::create_complete_graph(), create_cycle(), create_cycle_graph(), create_disconnected_bipartite(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::create_dummy_node(), create_grid_graph(), FindPathTest::create_linear_graph(), Aleph::Random_Graph< GT, Init_Node, Init_Arc >::create_nodes_and_initialize_arc_index(), Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::create_nodes_and_initialize_arc_index(), create_path_graph(), create_star_graph(), create_triangle(), demo_comparison(), demo_connected_components(), demo_definition(), demo_density(), demo_eulerian_cycle(), demo_hierholzer(), demo_testing(), GraphCommon< GT, Node, Arc >::emplace_node(), example_algorithm_comparison(), example_api_patterns(), example_basic_sccs(), example_comparison_tarjan(), example_dag(), example_lightweight_version(), example_strongly_connected(), Aleph::find_breadth_first_spanning_tree(), Aleph::find_depth_first_spanning_tree(), find_or_create(), generate_random_graph(), Aleph::Nodes_Index< GT, Compare, Tree, SN >::insert_in_graph(), Aleph::IndexNode< GT, Compare, Tree, SN >::insert_in_graph(), Aleph::Nodes_Index< GT, Compare, Tree, SN >::insert_in_graph(), Aleph::IndexNode< GT, Compare, Tree, SN >::insert_in_graph(), GraphCommon< GT, Node, Arc >::insert_node(), GraphCommon< GT, Node, Arc >::insert_node(), Aleph::GraphCopyWithMapping< GT, Tree >::insert_unmapped_node(), Aleph::GraphCopyWithMapping< GT, Tree >::insert_unmapped_node(), Aleph::IO_Graph< GT, Load_Node, Store_Node, Load_Arc, Store_Arc, NF, AF >::load(), Aleph::IO_Graph< GT, Load_Node, Store_Node, Load_Arc, Store_Arc, NF, AF >::load_in_text_mode(), main(), Aleph::map_subgraph(), Aleph::Init_Prim_Info< GT >::operator()(), Aleph::Build_Grid< GT, Operation_On_Node, Operation_On_Arc >::operator()(), Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::paint_min_spanning_tree(), parse_graph_definition(), Aleph::Xml_Graph< GT, Node_Reader, Arc_Reader, Node_Writer, Arc_Writer >::read_graph(), Aleph::Nodes_Index< GT, Compare, Tree, SN >::search_or_insert_in_graph(), Aleph::Nodes_Index< GT, Compare, Tree, SN >::search_or_insert_in_graph(), AStarBasicTest::SetUp(), AStarGridTest::SetUp(), AStarDijkstraModeTest::SetUp(), AStarHeapTest< HeapTag >::SetUp(), CookieGuardTest::SetUp(), GraphFunctionalTest::SetUp(), GraphTraverseTest::SetUp(), DisconnectedGraphTest::SetUp(), TreeGraphTest::SetUp(), CyclicGraphTest::SetUp(), SimpleGraphTest::SetUp(), IOGraphTest::SetUp(), GraphNodeRemovalTest::SetUp(), GraphArcRemovalTest::SetUp(), GraphIteratorTest::SetUp(), GraphMoveTest::SetUp(), PathTest::SetUp(), MatGraphTestBase::SetUp(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), test_cross_comparison(), TEST_F(), TEST_F(), TEST_F(), test_ks_single_edge(), test_ks_triangle(), test_performance_ks(), test_performance_sw(), test_sw_complete_k4(), test_sw_empty_graph(), test_sw_single_edge(), test_sw_triangle_weighted(), test_sw_two_heavy_clusters(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), and TYPED_TEST().
◆ insert_node() [3/3]
|
inline |
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_info info 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_allod if there is no enough memory.
Definition at line 1140 of file graph-dry.H.
◆ operator=() [1/2]
|
inline |
Copy assignment.
Replaces contents with a deep copy of g.
Definition at line 780 of file tpl_graph.H.
◆ operator=() [2/2]
|
inlinenoexcept |
◆ remove_arc()
|
inlinevirtualnoexcept |
Remove an arc from the graph and free it.
- Parameters
-
[in] arc pointer to the arc to be removed from graph and free it
- See also
- disconnect_arc(Arc * arc)
Definition at line 649 of file tpl_graph.H.
References Aleph::Dlink::del(), GraphCommon< GT, Node, Arc >::digraph, GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::maps(), and GraphCommon< GT, Node, Arc >::num_arcs.
Referenced by Aleph::clear_graph(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::create_dummy_node(), Aleph::Arcs_Index< GT, Compare, Tree, SA >::insert_in_graph(), Aleph::GraphCopyWithMapping< GT, Tree >::remove_arc(), GraphCommon< GT, Node, Arc >::remove_arcs_if(), Aleph::Arcs_Index< GT, Compare, Tree, SA >::remove_from_graph(), Aleph::IndexArc< GT, Tree, SA >::remove_from_graph(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::remove_node(), TEST(), TEST(), TEST(), and TEST().
◆ remove_node()
|
inlinevirtualnoexcept |
Remove a node from the graph and free its memory.
This method removes all the incoming and outcoming arcs referred to the node and frees the memory. Then removes the node from the graph and frees its memory. All the memory occupied by the arcs related to the node and the node itself is freed.
The method takes \(O(1)\) on List_Graph objects and \(O(E)\) on List_Digraph objects**.
- Parameters
-
[in] node to be removed and freed
Definition at line 543 of file tpl_graph.H.
References GraphCommon< GT, Node, Arc >::digraph, Aleph::List_Graph< _Graph_Node, _Graph_Arc >::dlink_to_arc_node(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::HTList::is_empty(), Aleph::maps(), GraphCommon< GT, Node, Arc >::num_nodes, Aleph::List_Graph< _Graph_Node, _Graph_Arc >::remove_arc(), GraphCommon< GT, Node, Arc >::remove_arcs_if(), and Aleph::List_Graph< _Graph_Node, _Graph_Arc >::void_to_arc().
Referenced by Aleph::clear_graph(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::create_dummy_node(), Aleph::Nodes_Index< GT, Compare, Tree, SN >::insert_in_graph(), Aleph::IndexNode< GT, Compare, Tree, SN >::insert_in_graph(), Aleph::Nodes_Index< GT, Compare, Tree, SN >::insert_in_graph(), Aleph::IndexNode< GT, Compare, Tree, SN >::insert_in_graph(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::remove_dummy_node(), Aleph::Nodes_Index< GT, Compare, Tree, SN >::remove_from_graph(), Aleph::IndexNode< GT, Compare, Tree, SN >::remove_from_graph(), Aleph::GraphCopyWithMapping< GT, Tree >::remove_node(), Aleph::Nodes_Index< GT, Compare, Tree, SN >::search_or_insert_in_graph(), Aleph::Nodes_Index< GT, Compare, Tree, SN >::search_or_insert_in_graph(), TEST(), TEST(), TEST(), and TEST().
◆ swap()
|
inlinenoexcept |
Swap in constant time this with g
Definition at line 983 of file tpl_graph.H.
References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::arc_list, GraphCommon< GT, Node, Arc >::common_swap(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::node_list, and Aleph::Dlink::swap().
Referenced by Aleph::Tarjan_Connected_Components< GT, Itor, SA >::operator()().
◆ void_to_arc()
|
inlinestaticprivatenoexcept |
Definition at line 469 of file tpl_graph.H.
References Aleph::maps().
Referenced by Aleph::List_Graph< _Graph_Node, _Graph_Arc >::remove_node().
Friends And Related Symbol Documentation
◆ GraphCommon< List_Graph< _Graph_Node, _Graph_Arc >, _Graph_Node, _Graph_Arc >
|
friend |
Definition at line 284 of file tpl_graph.H.
Member Data Documentation
◆ arc_list
|
private |
Definition at line 452 of file tpl_graph.H.
Referenced by Aleph::List_Graph< _Graph_Node, _Graph_Arc >::connect_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::get_arc_dlink(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::get_first_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), and Aleph::List_Graph< _Graph_Node, _Graph_Arc >::swap().
◆ node_list
|
private |
Definition at line 451 of file tpl_graph.H.
Referenced by Aleph::List_Graph< _Graph_Node, _Graph_Arc >::get_first_node(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::get_node_dlink(), and Aleph::List_Graph< _Graph_Node, _Graph_Arc >::swap().
The documentation for this class was generated from the following file:
