- Generated by
1.9.8
|
Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
|
Common methods to the Aleph-w ( \(\aleph_\omega\)) graph classes.
More...
#include <graph-dry.H>
Classes | |
| class | Digraph_Iterator |
| Special iterator for distinguishing input arcs of output ones. More... | |
| struct | In_Filt |
| Filter for input arcs of a node. More... | |
| struct | In_Iterator |
Alias for Digraph_Iterator More... | |
| struct | Out_Filt |
| Filter for output arcs of a node. More... | |
| struct | Out_Iterator |
Public Types | |
| 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 | |
| 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 |
Static Public Member Functions | |
| 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 | |
| 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 | |
| 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 | |
| void * | cookie = nullptr |
| size_t | num_nodes = 0 |
| size_t | num_arcs = 0 |
| bool | digraph = false |
Private Member Functions | |
| GT * | me () |
| const GT * | const_me () const |
Common methods to the Aleph-w ( \(\aleph_\omega\)) graph classes.
Definition at line 617 of file graph-dry.H.
| using GraphCommon< GT, Node, Arc >::Arc_Type = typename Arc::Arc_Type |
Definition at line 631 of file graph-dry.H.
Pair of arc and node (topologically related)
Definition at line 3189 of file graph-dry.H.
| using GraphCommon< GT, Node, Arc >::Node_Type = typename Node::Node_Type |
Definition at line 630 of file graph-dry.H.
Get all adjacent nodes (neighbors) of a node.
For undirected graphs, returns all connected nodes. For directed graphs, returns the union of in-nodes and out-nodes.
| p | node from which to get neighbors |
Definition at line 2530 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_arc(), and GraphCommon< GT, Node, Arc >::get_connected_node().
|
inline |
Overload of all_arcs(Node*, Operation&) that accepts rvalues.
Definition at line 1698 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::all_arcs().
|
inline |
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; });
all_arcs(p) is semantically equivalent to traverse_arcs().The complexity for this primitive always is \(O(V)\) worst case for dense graphs.
| [in] | p | node pointer |
| [in] | op | condition to test on each arc. |
true if all the arcs satisfy the condition; false otherwise.Definition at line 1691 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::traverse_arcs().
|
inline |
Overload of all_arcs(Operation&) that accepts rvalues.
Definition at line 1653 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::all_arcs().
|
inline |
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; });
all_arcs() is semantically equivalent to traverse_arcs().The complexity for this primitive always is \(O(E)\) worst case.
| [in] | op | condition to test on each arc. |
true if all the arcs satisfy the condition; false otherwise.Definition at line 1646 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::traverse_arcs().
Referenced by GraphCommon< GT, Node, Arc >::all_arcs(), and GraphCommon< GT, Node, Arc >::all_arcs().
|
inline |
Overload of all_in_arcs(Node*, Op&) that accepts rvalues.
Definition at line 3354 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::all_in_arcs().
|
inline |
Return true if op is true for all the incoming arcs to node p
Definition at line 3347 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::traverse_in_arcs().
Referenced by GraphCommon< GT, Node, Arc >::all_in_arcs().
|
inline |
Overload of all_nodes(Operation&) that accepts rvalues.
Definition at line 1611 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::all_nodes().
|
inline |
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; });
all_nodes() is semantically equivalent to traverse_nodes().The complexity for this primitive always is \(O(V)\) worst case.
| [in] | op | condition to test on each node. |
true if all the nodes satisfy the condition; false otherwise.Definition at line 1604 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::traverse_nodes().
Referenced by GraphCommon< GT, Node, Arc >::all_nodes().
|
inline |
Overload of all_out_arcs(Node*, Op&) that accepts rvalues.
Definition at line 3506 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::all_out_arcs().
|
inline |
Return true if op is true for all the outcoming arcs to node p
Definition at line 3499 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::traverse_out_arcs().
Referenced by GraphCommon< GT, Node, Arc >::all_out_arcs().
|
inline |
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.
| bad_alloc | if there is no enough memory |
Definition at line 2738 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_arc().
Referenced by Aleph::Net_Cost_Graph< NodeT, ArcT >::Net_Cost_Graph(), Aleph::Net_Graph< NodeT, ArcT >::Net_Graph(), Aleph::Net_Graph< NodeT, ArcT >::check_network(), and Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::remove_node().
|
inline |
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.
| bad_alloc | if there is no enough memory |
Definition at line 2756 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_arc().
|
inline |
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.
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.template keyword before the name arcs_map<your-target-type>. g.template arcs_map<ulong>([] (auto p) { return p->get_info(); });
| [in] | p | node from which you want to traverse adjacent arcs. |
| [in] | operation | transformation from Arc* to T to be performed on each arc. |
DynList<T> containing the mapping. | bad_alloc | if there is no enough memory for building the dynamic list or anything else that can throw operation. |
Definition at line 1841 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_arc().
|
inline |
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()); });
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.template keyword before the name arcs_map<your-target-type>. g.template arcs_map<ulong>([] (auto p) { return p->get_info(); });
| [in] | operation | transformation from ARc* to T to be performed on each arc. |
DynList<T> containing the mapping. | bad_alloc | if there is no enough memory for fuilding the dynamic list or anything else that can throw operation |
Definition at line 1790 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_arc().
|
inlineprotected |
Collect all arcs matching a predicate.
This method traverses all arcs in the graph and collects those for which the predicate returns true. The collection is done without modifying the graph, making it safe for subsequent batch removal.
| pred | Predicate with signature bool pred(Arc*) |
Definition at line 3634 of file graph-dry.H.
References Aleph::DynList< T >::append(), GraphCommon< GT, Node, Arc >::const_me(), and pred.
Referenced by GraphCommon< GT, Node, Arc >::remove_arcs_if().
|
inlineprotectednoexcept |
Definition at line 641 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::cookie, GraphCommon< GT, Node, Arc >::digraph, GraphCommon< GT, Node, Arc >::num_arcs, and GraphCommon< GT, Node, Arc >::num_nodes.
Referenced by Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::swap(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::swap(), Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::swap(), and Aleph::Net_Graph< NodeT, ArcT >::swap().
|
inlineprivate |
Definition at line 621 of file graph-dry.H.
Referenced by GraphCommon< GT, Node, Arc >::collect_arcs_if(), GraphCommon< GT, Node, Arc >::for_each_arc(), GraphCommon< GT, Node, Arc >::for_each_node(), GraphCommon< GT, Node, Arc >::get_arc(), GraphCommon< GT, Node, Arc >::get_arc(), GraphCommon< GT, Node, Arc >::get_arc_it(), GraphCommon< GT, Node, Arc >::get_node(), GraphCommon< GT, Node, Arc >::get_node_it(), GraphCommon< GT, Node, Arc >::search_arc(), GraphCommon< GT, Node, Arc >::search_node(), GraphCommon< GT, Node, Arc >::traverse_arcs(), and GraphCommon< GT, Node, Arc >::traverse_nodes().
|
inline |
Count arcs adjacent to a node satisfying a condition.
| p | node from which to count adjacent arcs |
| op | predicate to test (default: count all adjacent arcs) |
Definition at line 2334 of file graph-dry.H.
|
inline |
Count the arcs satisfying a condition.
count_arcs(op) traverses all arcs and counts how many satisfy the predicate op.
The operation has \(O(E)\) complexity.
| op | predicate to test (default: count all arcs) |
Definition at line 2320 of file graph-dry.H.
Referenced by TEST_F().
|
inline |
Count the nodes satisfying a condition.
count_nodes(op) traverses all nodes and counts how many satisfy the predicate op.
The operation has \(O(V)\) complexity.
| op | predicate to test (default: count all nodes) |
Definition at line 2296 of file graph-dry.H.
Referenced by TEST_F().
|
inlinenoexcept |
Return the total of arcs (or degree) of a node.
Only has sense for non-directed graphs
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
Definition at line 789 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::get_num_arcs().
|
inline |
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 unnecessary 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.
| [in] | src | pointer to the source node. |
| [in] | tgt | pointer to the target node. |
| [in] | args | variadic argument list for the construction of data associated to the arc. |
| bad_allod | if there is no enough memory. |
Definition at line 1252 of file graph-dry.H.
References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), and GraphCommon< GT, Node, Arc >::me().
|
inline |
Insert a new node in the graph by constructing it in-place with the given args.
This method is an effective way for inserting a new node in the graph and bypassing unnecessary copies. emplace_node() allocates a new node, takes the parameters received and calls to the constructor of data associated to the node. Then the data is forwarded to the node data constructor avoiding, if possible, innecessary copy. Once the node is completely built, this is inserted, at this moment without any logic possibility of failure, into the graph.
| [in] | args | variadic argument list for the construction of data associated to the node. |
| bad_allod | if there is no enough memory. |
Definition at line 1166 of file graph-dry.H.
References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and GraphCommon< GT, Node, Arc >::me().
|
inlinenoexcept |
Return the total of arcs of graph.
Definition at line 792 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::get_num_arcs().
Referenced by Aleph::export_network_to_dimacs(), Aleph::export_network_to_json(), Aleph::network_to_json_string(), Aleph::Network_Simplex< Net >::print_diagnostics(), Aleph::MCF_LP_Solver< Net >::print_formulation(), Aleph::Network_Simplex< Net >::run(), Aleph::MCF_LP_Solver< Net >::solve(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and Aleph::MCF_LP_Solver< Net >::var_index().
|
inline |
Overload of exists_arc(Node*, Operation&) that accepts rvalues.
Definition at line 2200 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::exists_arc().
|
inline |
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.
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); });
| [in] | p | node from which you want to access its arcs |
| [in] | op | operation for testing existing condition |
true if at least a node satisfaying the condition is found; false otherwise. Definition at line 2193 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::traverse_arcs().
|
inline |
Overload of exists_arc(Operation&) that accepts rvalues.
Definition at line 2165 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::exists_arc().
|
inline |
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.
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); });
| [in] | op | operation for testing existing condition |
true if at least a node satisfaying the condition is found; false otherwise. Definition at line 2158 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::traverse_arcs().
Referenced by GraphCommon< GT, Node, Arc >::exists_arc(), GraphCommon< GT, Node, Arc >::exists_arc(), GraphCommon< GT, Node, Arc >::none_arc(), and GraphCommon< GT, Node, Arc >::none_arc().
|
inline |
Overload of exists_in_arc(Node*, Op&) that accepts rvalues.
Definition at line 3369 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::exists_in_arc().
|
inline |
Return true if it exists a incoming arc to p returning true for op
Definition at line 3362 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::traverse_in_arcs().
Referenced by GraphCommon< GT, Node, Arc >::exists_in_arc().
|
inline |
Overload of exists_node(Operation&) that accepts rvalues.
Definition at line 2134 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::exists_node().
|
inline |
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.
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); });
| [in] | op | operation for testing existing condition |
true if at least a node satisfaying the condition is found; false otherwise. Definition at line 2127 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::traverse_nodes().
Referenced by GraphCommon< GT, Node, Arc >::exists_node(), and GraphCommon< GT, Node, Arc >::none_node().
|
inline |
Overload of exists_out_arc(Node*, Op&) that accepts rvalues.
Definition at line 3521 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::exists_out_arc().
|
inline |
Return true if it exists a outcoming arc to p returning true for op
Definition at line 3514 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::traverse_out_arcs().
Referenced by GraphCommon< GT, Node, Arc >::exists_out_arc().
|
inline |
Overload of filter_arcs(Node*, Op&) that accepts rvalues.
Definition at line 2103 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::filter_arcs().
|
inline |
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.
| [in] | p | pointer to node wanted to explore and to filter its adjacent arcs. |
| [in] | op | operation implementing the filtering condition. |
| bad_alloc | if there is no enough memory for building the full returning list. |
Definition at line 2090 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_arc().
|
inline |
Overload of filter_arcs(Op&) that accepts rvalues.
Definition at line 2054 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::filter_arcs().
|
inline |
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; });
| [in] | op | operation implementing the filtering condition. |
| bad_alloc | if there is no enough memory for building the full returning list. |
Definition at line 2041 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_arc().
Referenced by GraphCommon< GT, Node, Arc >::filter_arcs(), and GraphCommon< GT, Node, Arc >::filter_arcs().
|
inline |
Overload of filter_in_arcs(Node*, Op&) that accepts rvalues.
Definition at line 3463 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::filter_in_arcs().
|
inline |
Filter the incoming arcs of a node.
This method is analogous to filter_arcs() but only operates on the incoming arcs.
Definition at line 3450 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_in_arc().
Referenced by GraphCommon< GT, Node, Arc >::filter_in_arcs().
|
inline |
Overload of filter_nodes(Op&) that accepts rvalues.
Definition at line 2014 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::filter_nodes().
|
inline |
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; });
| [in] | op | operation implementing the filtering condition. |
| bad_alloc | if there is no enough memory for building the full returning list. |
Definition at line 2001 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_node().
Referenced by GraphCommon< GT, Node, Arc >::filter_nodes().
|
inline |
Overload of filter_out_arcs(Node*, Op&) that accepts rvalues.
Definition at line 3609 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::filter_out_arcs().
|
inline |
Filter the outcoming arcs of a node.
This method is analogous to filter_arcs() but only operates on the outcoming arcs.
Definition at line 3596 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_out_arc().
Referenced by GraphCommon< GT, Node, Arc >::filter_out_arcs().
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.
| [in] | info | to be compared with arcs content |
info or nullptr otherwise. Definition at line 2636 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::search_arc().
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.
| [in] | info | to be compared with nodes content |
info or nullptr otherwise. Definition at line 2585 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::search_node().
|
inline |
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(); });
| [in] | init | initial value of accumulator |
| [in] | op | to be performed, which must match the signature previously explained. |
Definition at line 1928 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_arc(), and GraphCommon< GT, Node, Arc >::init().
|
inline |
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(); });
| [in] | p | node from where to access its adjacent arcs |
| [in] | init | initial value of accumulator |
| [in] | op | to be performed, which must match the signature previously explained. |
Definition at line 1971 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_arc(), and GraphCommon< GT, Node, Arc >::init().
|
inline |
Fold the incoming arcs of a node.
This method is analogous to foldl_arcs() but only operates on the incoming arcs.
Definition at line 3434 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_in_arc(), and GraphCommon< GT, Node, Arc >::init().
|
inline |
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(); });
| [in] | init | initial value of accumulator |
| [in] | op | to be performed, which must match the signature previously explained. |
Definition at line 1886 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_node(), and GraphCommon< GT, Node, Arc >::init().
|
inline |
Fold-left over outcoming arcs of a node.
Definition at line 3580 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_out_arc(), and GraphCommon< GT, Node, Arc >::init().
|
inline |
Overload of for_each_arc(Node*, Operation&) that accepts rvalues.
Definition at line 1569 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_arc().
|
inline |
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.
p. If you want to know the node connected to p then invoke to g.get_connected_node(a,p).for_each_in_arc() or for_each_out_arc()-| [in] | p | pointer to the node from which you want to traverse adjacent arcs. |
| [in] | op | operation to be performed on each arc. |
| anything | that can throw op. |
Definition at line 1561 of file graph-dry.H.
|
inline |
Perform op on each arc of node p
Definition at line 3310 of file graph-dry.H.
|
inline |
Overload of for_each_arc(Operation&) that accepts rvalues.
Definition at line 1522 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_arc().
|
inline |
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)\).
| [in] | op | to be performed on each arc. |
| anything | that can throw op. |
Definition at line 1514 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::const_me().
Referenced by GraphCommon< GT, Node, Arc >::adjacent_nodes(), GraphCommon< GT, Node, Arc >::arcs(), GraphCommon< GT, Node, Arc >::arcs(), GraphCommon< GT, Node, Arc >::arcs_map(), GraphCommon< GT, Node, Arc >::arcs_map(), GraphCommon< GT, Node, Arc >::filter_arcs(), GraphCommon< GT, Node, Arc >::filter_arcs(), GraphCommon< GT, Node, Arc >::foldl_arcs(), GraphCommon< GT, Node, Arc >::foldl_arcs(), GraphCommon< GT, Node, Arc >::for_each_arc(), GraphCommon< GT, Node, Arc >::for_each_arc(), GraphCommon< GT, Node, Arc >::partition_arcs(), GraphCommon< GT, Node, Arc >::reset_arc_counters(), GraphCommon< GT, Node, Arc >::reset_arcs(), GraphCommon< GT, Node, Arc >::reset_bit_arcs(), GraphCommon< GT, Node, Arc >::reset_bit_arcs(), GraphCommon< GT, Node, Arc >::reset_cookie_arcs(), GraphCommon< GT, Node, Arc >::reset_counter_arcs(), GraphCommon< GT, Node, Arc >::sum_arcs(), and GraphCommon< GT, Node, Arc >::sum_arcs().
|
inline |
Overload of for_each_in_arc(Node*, Op&) that accepts rvalues.
Definition at line 3340 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_in_arc().
|
inline |
Perform op on each incoming arc of node p
Definition at line 3333 of file graph-dry.H.
Referenced by GraphCommon< GT, Node, Arc >::filter_in_arcs(), GraphCommon< GT, Node, Arc >::foldl_in_arcs(), GraphCommon< GT, Node, Arc >::for_each_in_arc(), and GraphCommon< GT, Node, Arc >::in_arcs_map().
|
inline |
Overload of for_each_node(Operation&) that accepts rvalues.
Definition at line 1484 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_node().
|
inline |
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)\).
| [in] | operation | to be performed on each node. |
| anything | that can throw operation. |
Definition at line 1476 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::const_me().
Referenced by Aleph::Compute_Cut_Nodes< GT, SA >::cut_nodes(), GraphCommon< GT, Node, Arc >::filter_nodes(), GraphCommon< GT, Node, Arc >::foldl_nodes(), GraphCommon< GT, Node, Arc >::for_each_node(), GraphCommon< GT, Node, Arc >::nodes(), GraphCommon< GT, Node, Arc >::nodes_map(), GraphCommon< GT, Node, Arc >::partition_nodes(), GraphCommon< GT, Node, Arc >::reset_bit_nodes(), GraphCommon< GT, Node, Arc >::reset_bit_nodes(), GraphCommon< GT, Node, Arc >::reset_cookie_nodes(), GraphCommon< GT, Node, Arc >::reset_counter_nodes(), GraphCommon< GT, Node, Arc >::reset_node_counters(), and GraphCommon< GT, Node, Arc >::reset_nodes().
|
inline |
Overload of for_each_out_arc(Node*, Op&) that accepts rvalues.
Definition at line 3492 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_out_arc().
|
inline |
Perform op on each outcoming arc of node p
Definition at line 3485 of file graph-dry.H.
Referenced by GraphCommon< GT, Node, Arc >::filter_out_arcs(), GraphCommon< GT, Node, Arc >::foldl_out_arcs(), GraphCommon< GT, Node, Arc >::for_each_out_arc(), and GraphCommon< GT, Node, Arc >::out_arcs_map().
|
inline |
Return any arc in the graph.
This method serves as a departure arc in the graph. Some algorithms only need an initial arc which could be anyone. In these cases, this method is indicated.
Definition at line 718 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::const_me(), and Aleph::List_Graph< _Graph_Node, _Graph_Arc >::get_first_arc().
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.
p Definition at line 728 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::const_me(), and Aleph::List_Graph< _Graph_Node, _Graph_Arc >::get_first_arc().
|
inlinenoexcept |
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
Definition at line 2802 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::const_me().
Referenced by Aleph::__compute_cut_nodes(), Aleph::__depth_first_traversal(), Aleph::__find_depth_first_spanning_tree(), Aleph::__find_path_depth_first(), Aleph::__is_graph_acyclique(), Aleph::__map_subgraph(), Aleph::__paint_from_cut_node(), Aleph::__paint_subgraph(), Aleph::__test_cycle(), Aleph::__test_for_path(), add_super_source_and_sink(), CookieGuardTest::all_arc_cookies_null(), Aleph::breadth_first_traversal(), Aleph::build_subgraph(), Aleph::Cookie_Guard< GT >::clear_now(), Aleph::compute_cut_nodes(), demo_spanning_tree(), demonstrate_bipartite_matching(), demonstrate_min_cut(), demonstrate_min_cut(), Aleph::find_breadth_first_spanning_tree(), Aleph::find_depth_first_spanning_tree(), Aleph::find_path_breadth_first(), Aleph::find_path_depth_first(), Aleph::invert_digraph(), is_simple_graph(), Aleph::kosaraju_connected_components(), Aleph::map_cut_graph(), mst_total_weight(), print_cost_network(), print_flow_stats(), print_graph(), print_mst(), print_network(), print_network_stats(), Aleph::Cookie_Saver< GT >::restore_now(), satisfies_ore_condition(), Aleph::Cookie_Saver< GT >::save_cookies(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), Aleph::test_for_cycle(), Aleph::test_for_path(), and time_algorithm().
|
inlinenoexcept |
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
Definition at line 2825 of file graph-dry.H.
|
inlinenoexcept |
|
inlinenoexcept |
|
inlinenoexcept |
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 ... }
| [in] | arc | the arc |
| [in] | node | the node from you must be seeing the arc |
p ---arc--- tgtDefinition at line 772 of file graph-dry.H.
Referenced by GraphCommon< GT, Node, Arc >::adjacent_nodes(), Aleph::Path< GT >::append(), Aleph::build_level_graph(), Aleph::Network_Simplex< Net >::build_spanning_tree(), Aleph::capacity_scaling_maximum_flow(), Aleph::Path< GT >::check(), Aleph::check_baseball_elimination(), Aleph::compute_min_cut(), compute_min_cut_capacity(), Aleph::Map_Matrix_Graph< GT, SA >::copy_list_graph(), Aleph::dinic_blocking_flow(), Graph_Traverse< GT, Itor, Q, Show_Arc >::exec(), Aleph::Find_Path_Depth_First< GT, Itor, SA >::find(), Aleph::Find_Eulerian_Path< GT, SN, SA >::find_node_sequence(), Aleph::Find_Path_Depth_First< GT, Itor, SA >::find_path(), Aleph::generic_preflow_vertex_push_maximum_flow(), Aleph::Find_Eulerian_Path< GT, SN, SA >::hierholzer_undirected(), Aleph::hlpp_maximum_flow(), Aleph::hopcroft_karp_dfs(), Aleph::hopcroft_karp_matching(), Aleph::Path< GT >::insert(), Graph_Traverse< GT, Itor, Q, Show_Arc >::operator()(), Graph_Traverse< GT, Itor, Q, Show_Arc >::operator()(), print_graph(), satisfies_ore_condition(), Aleph::Find_Aumenting_Path< Net, Q >::search(), Aleph::segment_image(), Aleph::solve_project_selection(), Aleph::ssp_shortest_path(), and TEST().
|
inlinenoexcept |
Return a reference to the control bits of arc
Definition at line 825 of file graph-dry.H.
References ARC_BITS.
|
inlinenoexcept |
Return a reference to control fields of node
Definition at line 795 of file graph-dry.H.
References NODE_BITS.
|
inlinenoexcept |
Return a constant reference to graph's cookie.
Definition at line 654 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::cookie.
|
inlinenoexcept |
Return a modifiable reference to graph's cookie.
Definition at line 651 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::cookie.
|
inlinenoexcept |
Get a modifiable reference to the cookie pointer of arc
Definition at line 861 of file graph-dry.H.
References ARC_COOKIE.
|
inlinenoexcept |
Get a modifiable reference to the cookie pointer of node
Definition at line 855 of file graph-dry.H.
References NODE_COOKIE.
|
inlinenoexcept |
Get a modifiable reference to the counter of arc
Definition at line 893 of file graph-dry.H.
References ARC_COUNTER.
|
inlinenoexcept |
Get a modifiable reference to the counter of node
Definition at line 867 of file graph-dry.H.
References NODE_COUNTER.
Referenced by demo_biconnected_components().
|
inlinenoexcept |
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
Definition at line 3079 of file graph-dry.H.
|
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.
Definition at line 708 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::const_me(), and Aleph::List_Graph< _Graph_Node, _Graph_Arc >::get_first_node().
Referenced by Aleph::compute_cut_nodes(), and Aleph::find_depth_first_spanning_tree().
|
inlinenoexcept |
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
Definition at line 2780 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::const_me().
Referenced by add_super_source_and_sink(), CookieGuardTest::all_node_cookies_null(), all_nodes_have_even_degree(), Aleph::Cookie_Guard< GT >::clear_now(), Aleph::compute_cut_nodes(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::compute_nodes_weights(), demo_biconnected_components(), demo_eulerian(), find_node(), find_or_create(), Aleph::inconnected_components(), Aleph::invert_digraph(), Aleph::is_graph_acyclique(), Aleph::kosaraju_connected_components(), Aleph::kosaraju_connected_components(), Aleph::map_subgraph(), Aleph::Invert_Digraph< GT, SA >::operator()(), Aleph::Topological_Sort< GT, Itor, SA >::perform(), Aleph::Q_Topological_Sort< GT, Itor, SA >::perform(), print_degrees(), print_graph(), print_graph(), print_graph(), Aleph::Cookie_Saver< GT >::restore_now(), satisfies_ore_condition(), Aleph::Cookie_Saver< GT >::save_cookies(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().
|
inlineconstexprnoexcept |
Definition at line 778 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::num_arcs.
Referenced by Aleph::__find_depth_first_spanning_tree(), all_nodes_have_even_degree(), Aleph::Test_Eulerian< GT, SN, SA >::analyze_digraph(), Aleph::Test_Eulerian< GT, SN, SA >::analyze_graph(), Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::balance_digraph_node(), Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::balance_digraph_nodes_degree(), Aleph::Random_Graph< GT, Init_Node, Init_Arc >::balance_graph_nodes_degree(), Aleph::Find_Depth_First_Spanning_Tree< GT, SA >::build_tree(), compare_algorithms(), GraphCommon< GT, Node, Arc >::degree(), demo_benchmarking(), demo_spanning_tree(), GraphCommon< GT, Node, Arc >::esize(), example_algorithm_comparison(), Aleph::Test_Dirac_Condition< GT, SN, SA >::find_min_degree_vertex(), Aleph::Find_Eulerian_Path< GT, SN, SA >::find_start_vertex(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::get_first_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::get_first_arc(), Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::get_first_arc(), Aleph::invert_digraph(), Aleph::Test_Eulerian< GT, SN, SA >::is_connected(), Aleph::is_graph_acyclique(), Aleph::is_graph_acyclique(), Aleph::Test_Eulerian< GT, SN, SA >::is_strongly_connected(), main(), main(), Aleph::Prim_Min_Spanning_Tree< GT, Distance, SA >::min_spanning_tree(), Aleph::GraphCopyWithMapping< GT, Tree >::num_arcs(), Aleph::Is_Graph_Acyclique< GT, SA >::operator()(), Test_Connectivity< GT, SA >::operator()(), Test_Connectivity< GT, SA >::operator()(), print_cost_network(), print_graph(), print_graph(), print_mst(), print_network(), print_network_stats(), satisfies_ore_condition(), Aleph::IO_Graph< GT, Load_Node, Store_Node, Load_Arc, Store_Arc, NF, AF >::save(), Aleph::Cookie_Saver< GT >::save_cookies(), Aleph::IO_Graph< GT, Load_Node, Store_Node, Load_Arc, Store_Arc, NF, AF >::save_in_text_mode(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), Aleph::test_connectivity(), Aleph::Test_Eulerian< GT, SN, SA >::test_degree_only(), Aleph::Test_Hamiltonian_Sufficiency< GT, SN, SA >::test_digraph(), Aleph::Test_Dirac_Condition< GT, SN, SA >::test_digraph(), 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_F(), TEST_F(), TEST_F(), Aleph::Test_Hamiltonian_Sufficiency< GT, SN, SA >::test_graph(), Aleph::Test_Dirac_Condition< GT, SN, SA >::test_graph(), Aleph::Test_For_Path< GT, SA >::test_path(), 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(), Aleph::Random_Graph< GT, Init_Node, Init_Arc >::update_parity_after_arc_insertion(), Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::update_parity_after_arc_insertion(), Aleph::Karger_Min_Cut< GT, SA >::validate_graph(), and Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::verify_tables().
|
inlinenoexcept |
Return the total of arcs of a node.
Only has sense for non- directed graphs
Definition at line 782 of file graph-dry.H.
|
inlineconstexprnoexcept |
Return the total of nodes of graph.
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
Definition at line 695 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::num_nodes.
Referenced by Aleph::__depth_first_traversal(), Aleph::Depth_First_Traversal< GT, Operation, SA >::__dft(), Aleph::__find_depth_first_spanning_tree(), Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::balance_digraph_node(), Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::balance_digraph_nodes_degree(), Aleph::Random_Graph< GT, Init_Node, Init_Arc >::balance_graph_nodes_degree(), Aleph::Breadth_First_Traversal< GT, Operation, SA >::bft(), Aleph::breadth_first_traversal(), build_cross_net_graph(), build_net_graph(), 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::Find_Depth_First_Spanning_Tree< GT, SA >::build_tree(), compare_algorithms(), Aleph::Unconnected_Components< GT, SA >::compute_blocks(), Aleph::compute_cut_nodes(), Aleph::Unconnected_Components< GT, SA >::compute_lists(), Aleph::compute_min_cut(), Aleph::Karger_Min_Cut< GT, SA >::compute_min_cut_size(), 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::Bellman_Ford< GT, Distance, Ait, NAit, SA >::compute_nodes_weights(), 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::Random_Digraph< GT, Init_Node, Init_Arc >::connect(), Aleph::Matrix_Graph< GT, SA >::copy(), Aleph::Map_Matrix_Graph< GT, SA >::copy_list_graph(), Aleph::Bit_Mat_Graph< GT, SA >::copy_list_graph(), Aleph::Ady_Mat< GT, __Entry_Type, SA >::copy_nodes(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::create_dummy_node(), demo_benchmarking(), demo_spanning_tree(), Aleph::edge_connectivity(), example_algorithm_comparison(), example_dag(), Aleph::Karger_Min_Cut< GT, SA >::fast(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::faster_paint_spanning_tree(), Aleph::find_breadth_first_spanning_tree(), Aleph::floyd_all_shortest_paths(), Aleph::floyd_all_shortest_paths_latex(), Aleph::generate_cross_graph(), Aleph::generate_net_graph(), Aleph::hopcroft_karp_matching(), Aleph::inconnected_components(), Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::init_from_graph(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::init_tarjan(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::init_with_indexes(), Aleph::invert_digraph(), Aleph::Is_Graph_Acyclique< GT, SA >::is_acyclique(), Aleph::Unconnected_Components< GT, SA >::is_connected(), Aleph::Test_Eulerian< GT, SN, SA >::is_connected(), Aleph::Karger_Min_Cut< GT, SA >::is_connected_filtered(), Aleph::is_graph_acyclique(), Aleph::is_graph_acyclique(), Aleph::is_strongly_connected(), Aleph::Test_Eulerian< GT, SN, SA >::is_strongly_connected(), Aleph::Karger_Min_Cut< GT, SA >::karger_min_cut(), main(), main(), Aleph::Random_Graph< GT, Init_Node, Init_Arc >::make_hamiltonian(), Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::make_hamiltonian(), Aleph::min_cut(), Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::min_cut_weight(), Aleph::Test_Dirac_Condition< GT, SN, SA >::min_required_degree(), Aleph::Prim_Min_Spanning_Tree< GT, Distance, SA >::min_spanning_tree(), Aleph::Invert_Digraph< GT, SA >::operator()(), Aleph::Build_Grid< GT, Operation_On_Node, Operation_On_Arc >::operator()(), Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::operator()(), Aleph::Karger_Min_Cut< GT, SA >::operator()(), Aleph::Find_Depth_First_Spanning_Tree< GT, SA >::operator()(), Aleph::Find_Breadth_First_Spanning_Tree< GT, SA >::operator()(), Test_Connectivity< GT, SA >::operator()(), Test_Connectivity< GT, SA >::operator()(), Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::paint_min_paths_tree(), Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::paint_min_paths_tree(), Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::paint_min_spanning_tree(), Aleph::Prim_Min_Spanning_Tree< GT, Distance, SA >::paint_min_spanning_tree(), Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::paint_partial_min_paths_tree(), Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::paint_partial_min_paths_tree(), Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::paint_partial_path(), Aleph::Topological_Sort< GT, Itor, SA >::perform(), print_cost_network(), print_graph(), print_graph(), print_network(), print_network_stats(), satisfies_ore_condition(), Aleph::IO_Graph< GT, Load_Node, Store_Node, Load_Arc, Store_Arc, NF, AF >::save(), Aleph::Cookie_Saver< GT >::save_cookies(), Aleph::IO_Graph< GT, Load_Node, Store_Node, Load_Arc, Store_Arc, NF, AF >::save_in_text_mode(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::search_negative_cycle(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::search_negative_cycle(), Aleph::Bit_Mat_Graph< GT, SA >::set_list_graph(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), Aleph::test_connectivity(), Aleph::Test_Hamiltonian_Sufficiency< GT, SN, SA >::test_digraph(), Aleph::Test_Dirac_Condition< GT, SN, SA >::test_digraph(), 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_F(), 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_F(), TEST_F(), TEST_F(), TEST_F(), Aleph::Test_Hamiltonian_Sufficiency< GT, SN, SA >::test_graph(), Aleph::Test_Dirac_Condition< GT, SN, SA >::test_graph(), Aleph::Test_For_Path< GT, SA >::test_path(), Aleph::Topological_Sort< GT, Itor, SA >::topological_sort(), 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(), Aleph::Karger_Min_Cut< GT, SA >::validate_graph(), Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::verify_tables(), Aleph::vertex_connectivity(), and GraphCommon< GT, Node, Arc >::vsize().
|
inlinenoexcept |
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
Definition at line 3099 of file graph-dry.H.
Referenced by Aleph::__dfp_phase1(), Aleph::__dfp_phase2_list(), Aleph::__dfp_phase2_subgraph(), and print_graph().
Return the source node of arc (only for directed graphs)
Definition at line 731 of file graph-dry.H.
Referenced by Aleph::Breadth_First_Traversal< GT, Operation, SA >::bft(), Aleph::breadth_first_traversal(), Aleph::GraphCopyWithMapping< GT, Tree >::build_copy(), Aleph::Karger_Min_Cut< GT, SA >::build_kgraph(), Aleph::build_level_graph(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::build_path(), Aleph::Find_Breadth_First_Spanning_Tree< GT, SA >::build_tree(), Aleph::capacity_scaling_maximum_flow(), Aleph::check_baseball_elimination(), Aleph::Path< GT >::check_directed(), Aleph::Net_Cap_Graph< NodeT, ArcT >::compute_aux_net(), Aleph::compute_min_cut(), compute_min_cut_capacity(), 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::Array_Graph< __Graph_Node, __Graph_Arc >::connect_arc(), Aleph::Net_Graph< NodeT, ArcT >::connect_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::connect_arc(), Aleph::create_residual_arc(), Aleph::decompose_flow(), demo_spanning_tree(), demonstrate_bipartite_matching(), demonstrate_min_cut(), demonstrate_min_cut(), Aleph::digraph_graphviz(), Aleph::dinic_blocking_flow(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::disconnect_arc(), Aleph::Net_Graph< NodeT, ArcT >::disconnect_arc(), Aleph::edge_connectivity(), example_basic_sccs(), Aleph::export_network_to_dimacs(), Aleph::export_network_to_dot(), Aleph::export_network_to_json(), Aleph::Directed_Find_Path< GT, Itor, SA >::find(), Aleph::find_breadth_first_spanning_tree(), Aleph::Find_Eulerian_Path< GT, SN, SA >::find_node_sequence(), Aleph::Find_Path_Breadth_First< GT, Itor, SA >::find_path(), Aleph::find_path_breadth_first(), Aleph::generate_graphpic(), Aleph::generate_graphviz(), Aleph::generate_graphviz(), Aleph::Euclidian_Graph< __Euclidian_Node, __Euclidian_Arc >::get_distance(), Aleph::Karger_Min_Cut< GT, SA >::has_self_loop(), Aleph::hlpp_maximum_flow(), Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::init_from_graph(), Aleph::invert_digraph(), is_simple_graph(), RandomNetworkTest::is_valid_network(), Aleph::kosaraju_connected_components(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::last_relax_and_prepare_check_negative_cycle(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::last_relax_and_test_negative_cycle(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::link_cookies_and_free(), Aleph::map_cut_graph(), Aleph::Compute_Cut_Nodes< GT, SA >::map_cut_graph(), Aleph::min_cut(), Aleph::Prim_Min_Spanning_Tree< GT, Distance, SA >::min_spanning_tree(), Aleph::network_to_dot_string(), Aleph::network_to_json_string(), Aleph::Invert_Digraph< GT, SA >::operator()(), Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::operator()(), Aleph::Init_Arc< GT >::operator()(), Graph_Traverse< GT, Itor, Q, Show_Arc >::operator()(), Graph_Traverse< GT, Itor, Q, Show_Arc >::operator()(), Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::paint_min_paths_tree(), Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::paint_min_paths_tree(), Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::paint_min_spanning_tree(), Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::paint_min_spanning_tree(), Aleph::Prim_Min_Spanning_Tree< GT, Distance, SA >::paint_min_spanning_tree(), Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::paint_partial_min_paths_tree(), Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::paint_partial_min_paths_tree(), Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::paint_partial_path(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::paint_tree(), print_cost_network(), print_cut_edges(), print_graph(), print_matching(), print_mst(), print_network(), process_arc(), Aleph::rank_graphviz(), Aleph::reduced_cost(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::relax_arcs(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::relax_arcs(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::remove_arc(), Aleph::Net_Graph< NodeT, ArcT >::remove_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::remove_node(), Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::remove_node(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::reweight_arcs(), Aleph::IO_Graph< GT, Load_Node, Store_Node, Load_Arc, Store_Arc, NF, AF >::save(), Aleph::IO_Graph< GT, Load_Node, Store_Node, Load_Arc, Store_Arc, NF, AF >::save_in_text_mode(), Aleph::Find_Aumenting_Path< Net, Q >::search(), Aleph::segment_image(), Aleph::solve_circulation(), Aleph::solve_project_selection(), Aleph::ssp_init_potentials(), Aleph::ssp_shortest_path(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST_F(), TEST_F(), verify_bipartition(), verify_flow_conservation(), verify_matching(), Aleph::vertex_connectivity(), and Aleph::Xml_Graph< GT, Node_Reader, Arc_Reader, Node_Writer, Arc_Writer >::write_graph().
Return the target node of arc (only for directed graphs)
Definition at line 737 of file graph-dry.H.
Referenced by Aleph::__dfp_phase1(), Aleph::__dfp_phase2_list(), Aleph::__dfp_phase2_subgraph(), Aleph::Breadth_First_Traversal< GT, Operation, SA >::bft(), Aleph::breadth_first_traversal(), Aleph::GraphCopyWithMapping< GT, Tree >::build_copy(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::build_cycle(), Aleph::Karger_Min_Cut< GT, SA >::build_kgraph(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::build_path(), Aleph::Find_Breadth_First_Spanning_Tree< GT, SA >::build_tree(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::build_tree(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::check_painted_arcs(), Aleph::Net_Cap_Graph< NodeT, ArcT >::compute_aux_net(), Aleph::compute_maximum_cardinality_bipartite_matching(), Aleph::compute_min_cut(), compute_min_cut_capacity(), 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::Array_Graph< __Graph_Node, __Graph_Arc >::connect_arc(), Aleph::Net_Graph< NodeT, ArcT >::connect_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::connect_arc(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components(), Aleph::create_residual_arc(), Aleph::decompose_flow(), demo_spanning_tree(), demonstrate_bipartite_matching(), demonstrate_flow_decomposition(), demonstrate_min_cut(), demonstrate_min_cut(), Aleph::design_survey(), Aleph::digraph_graphviz(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::disconnect_arc(), Aleph::Net_Graph< NodeT, ArcT >::disconnect_arc(), Aleph::edge_connectivity(), example_basic_sccs(), Aleph::export_network_to_dimacs(), Aleph::export_network_to_dot(), Aleph::export_network_to_json(), Aleph::Directed_Find_Path< GT, Itor, SA >::find(), Aleph::find_breadth_first_spanning_tree(), Aleph::Find_Eulerian_Path< GT, SN, SA >::find_node_sequence(), Aleph::Find_Path_Breadth_First< GT, Itor, SA >::find_path(), Aleph::find_path_breadth_first(), Aleph::Testing::LayeredNetworkGenerator< Net >::generate(), Aleph::generate_graphpic(), Aleph::generate_graphviz(), Aleph::generate_graphviz(), Aleph::generic_preflow_vertex_push_maximum_flow(), Aleph::Euclidian_Graph< __Euclidian_Node, __Euclidian_Arc >::get_distance(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::get_distance(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::has_cycle(), Aleph::Karger_Min_Cut< GT, SA >::has_self_loop(), Aleph::Find_Eulerian_Path< GT, SN, SA >::hierholzer_directed(), Aleph::hlpp_maximum_flow(), Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::init_from_graph(), Aleph::init_height_in_nodes(), Aleph::invert_digraph(), Aleph::Testing::RandomNetworkGenerator< Net >::is_connected(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::is_connected(), is_simple_graph(), RandomNetworkTest::is_valid_network(), Aleph::kosaraju_connected_components(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::last_relax_and_prepare_check_negative_cycle(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::last_relax_and_test_negative_cycle(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::link_cookies_and_free(), Aleph::map_cut_graph(), Aleph::Compute_Cut_Nodes< GT, SA >::map_cut_graph(), Aleph::min_cut(), Aleph::Prim_Min_Spanning_Tree< GT, Distance, SA >::min_spanning_tree(), Aleph::network_to_dot_string(), Aleph::network_to_json_string(), Aleph::Ady_Mat< GT, __Entry_Type, SA >::operate_all_arcs_list_graph(), Aleph::Invert_Digraph< GT, SA >::operator()(), Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::operator()(), Aleph::Init_Arc< GT >::operator()(), Graph_Traverse< GT, Itor, Q, Show_Arc >::operator()(), Graph_Traverse< GT, Itor, Q, Show_Arc >::operator()(), Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::paint_min_paths_tree(), Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::paint_min_paths_tree(), Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::paint_min_spanning_tree(), Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::paint_min_spanning_tree(), Aleph::Prim_Min_Spanning_Tree< GT, Distance, SA >::paint_min_spanning_tree(), Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::paint_partial_min_paths_tree(), Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::paint_partial_min_paths_tree(), Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::paint_partial_path(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::paint_tree(), print_cost_network(), print_cut_edges(), print_graph(), print_graph(), print_matching(), print_mst(), print_network(), process_arc(), Aleph::rank_graphviz(), Aleph::reduced_cost(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::relax_arcs(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::remove_arc(), Aleph::Net_Graph< NodeT, ArcT >::remove_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::remove_node(), Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::remove_node(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::reweight_arcs(), Aleph::IO_Graph< GT, Load_Node, Store_Node, Load_Arc, Store_Arc, NF, AF >::save(), Aleph::IO_Graph< GT, Load_Node, Store_Node, Load_Arc, Store_Arc, NF, AF >::save_in_text_mode(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::scc_by_blocks(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::scc_by_len(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::scc_by_lists(), Aleph::Find_Aumenting_Path< Net, Q >::search(), Aleph::solve_assignment(), Aleph::solve_circulation(), Aleph::ssp_init_potentials(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST_F(), TEST_F(), verify_bipartition(), verify_flow_conservation(), verify_matching(), Aleph::vertex_connectivity(), and Aleph::Xml_Graph< GT, Node_Reader, Arc_Reader, Node_Writer, Arc_Writer >::write_graph().
Return a list with the incoming arcs to p`.
The method returns all the incoming arcs s --> p.
| bad_alloc | if there is no enough memory |
Definition at line 3180 of file graph-dry.H.
References Aleph::DynList< T >::append(), and GraphCommon< GT, Node, Arc >::Digraph_Iterator< Filter >::has_curr().
|
inline |
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.
Definition at line 3419 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_in_arc().
|
inlinenoexcept |
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.
| [in] | p | poinger to the node |
p Definition at line 3250 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::Digraph_Iterator< Filter >::has_curr().
Referenced by Aleph::Net_Graph< NodeT, ArcT >::get_in_degree().
Return a list with the incoming nodes to p
The method filters all the incoming arcs s --> p and return their nodes.
| [in] | p | pointer to node |
| bad_alloc | if there is no enough memory |
Definition at line 3129 of file graph-dry.H.
References Aleph::DynList< T >::append(), and GraphCommon< GT, Node, Arc >::Digraph_Iterator< Filter >::has_curr().
|
inline |
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.
| [in] | p | pointer to node |
| bad_alloc | if there is no enough memory |
Definition at line 3203 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::Digraph_Iterator< Filter >::has_curr().
|
inlineprotectednoexcept |
Definition at line 634 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::cookie, GraphCommon< GT, Node, Arc >::digraph, GraphCommon< GT, Node, Arc >::num_arcs, and GraphCommon< GT, Node, Arc >::num_nodes.
Referenced by GraphCommon< GT, Node, Arc >::foldl_arcs(), GraphCommon< GT, Node, Arc >::foldl_arcs(), GraphCommon< GT, Node, Arc >::foldl_in_arcs(), GraphCommon< GT, Node, Arc >::foldl_nodes(), and GraphCommon< GT, Node, Arc >::foldl_out_arcs().
|
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.
| [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. |
| bad_alloc | if there is no enough memory. |
Definition at line 1223 of file graph-dry.H.
References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), and GraphCommon< GT, Node, Arc >::me().
|
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.
| [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. |
| bad_alloc | if there is no enough memory. |
Definition at line 1193 of file graph-dry.H.
References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), and GraphCommon< GT, Node, Arc >::me().
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.
| [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. |
| bad_allod | if there is no enough memory |
Definition at line 1116 of file graph-dry.H.
References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and GraphCommon< GT, Node, Arc >::me().
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.
| [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. |
| bad_allod | if there is no enough memory. |
Definition at line 1140 of file graph-dry.H.
References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and GraphCommon< GT, Node, Arc >::me().
|
inlinenoexcept |
Return true if the graph this is directed.
Definition at line 657 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::digraph.
Referenced by Aleph::Random_Graph< GT, Init_Node, Init_Arc >::Random_Graph(), Aleph::Random_Graph< GT, Init_Node, Init_Arc >::Random_Graph(), Aleph::Test_Eulerian< GT, SN, SA >::analyze_digraph(), Aleph::Test_Eulerian< GT, SN, SA >::analyze_graph(), Aleph::Test_Eulerian< GT, SN, SA >::compute(), Aleph::compute_cut_nodes(), Aleph::compute_min_cut(), Aleph::edge_connectivity(), Aleph::Find_Eulerian_Path< GT, SN, SA >::find_node_sequence(), Aleph::Find_Eulerian_Path< GT, SN, SA >::find_start_vertex(), Aleph::generate_cross_graph(), Aleph::generate_graphviz(), Aleph::generate_graphviz(), Aleph::generate_net_graph(), Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::initialize_and_create_nodes(), Aleph::invert_digraph(), Aleph::Is_Graph_Acyclique< GT, SA >::is_acyclique(), Aleph::is_graph_acyclique(), Aleph::is_graph_acyclique(), Aleph::Prim_Min_Spanning_Tree< GT, Distance, SA >::min_spanning_tree(), Aleph::Invert_Digraph< GT, SA >::operator()(), Aleph::Find_Eulerian_Path< GT, SN, SA >::operator()(), Aleph::Test_Hamiltonian_Sufficiency< GT, SN, SA >::operator()(), Aleph::Test_Dirac_Condition< GT, SN, SA >::operator()(), Test_Connectivity< GT, SA >::operator()(), Test_Connectivity< GT, SA >::operator()(), Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::paint_min_spanning_tree(), Aleph::Prim_Min_Spanning_Tree< GT, Distance, SA >::paint_min_spanning_tree(), process_arc(), Aleph::Arcs_Index< GT, Compare, Tree, SA >::search(), Aleph::search_arc(), Aleph::search_spanning_tree_arc(), TEST(), TEST(), Aleph::test_connectivity(), Aleph::Test_Eulerian< GT, SN, SA >::test_degree_only(), Aleph::Test_Hamiltonian_Sufficiency< GT, SN, SA >::test_digraph(), Aleph::Test_Dirac_Condition< GT, SN, SA >::test_digraph(), TEST_F(), TEST_F(), Aleph::Test_Hamiltonian_Sufficiency< GT, SN, SA >::test_graph(), Aleph::Test_Dirac_Condition< GT, SN, SA >::test_graph(), Aleph::Test_For_Path< GT, SA >::test_path(), and Aleph::vertex_connectivity().
|
inlinestaticnoexcept |
Map the arcs through their cookies.
map_arcs(p, q) is intended to bijectively 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.
| [in] | p | source arc of mapping |
| [in] | q | target arc of mapping |
Definition at line 1026 of file graph-dry.H.
References ARC_COOKIE.
Referenced by Aleph::__find_depth_first_spanning_tree(), Aleph::__map_subgraph(), 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(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components(), Aleph::Copy_Graph< GT, SN, SA >::copy(), Aleph::copy_graph(), Aleph::find_breadth_first_spanning_tree(), Aleph::invert_digraph(), Aleph::kosaraju_connected_components(), Aleph::map_cut_graph(), Aleph::Compute_Cut_Nodes< GT, SA >::map_cut_graph(), Aleph::Compute_Cut_Nodes< GT, SA >::map_subgraph(), Aleph::Prim_Min_Spanning_Tree< GT, Distance, SA >::min_spanning_tree(), Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::Destroy_Tree_Arc::operator()(), Aleph::Invert_Digraph< GT, SA >::operator()(), and Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::paint_min_spanning_tree().
|
inlinestaticnoexcept |
Map the nodes through their cookies.
map_nodes(p, q) is intended to bijectively 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.
Suppose 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 bijective 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 through 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, initialization, 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.
| [in] | p | source node of mapping |
| [in] | q | target node of mapping |
Definition at line 995 of file graph-dry.H.
References NODE_COOKIE.
Referenced by Aleph::__dfp_phase2_subgraph(), Aleph::__find_depth_first_spanning_tree(), Aleph::__map_subgraph(), Aleph::Karger_Min_Cut< GT, SA >::build_kgraph(), 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(), Aleph::compute_min_cut(), Aleph::Copy_Graph< GT, SN, SA >::copy(), Aleph::copy_graph(), Aleph::Compute_Cut_Nodes< GT, SA >::create_and_map_node(), Aleph::find_breadth_first_spanning_tree(), Aleph::find_depth_first_spanning_tree(), Aleph::invert_digraph(), Aleph::map_cut_graph(), Aleph::Compute_Cut_Nodes< GT, SA >::map_cut_graph(), Aleph::map_subgraph(), Aleph::Uninit_Prim_Info< GT >::operator()(), Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::Destroy_Tree_Node::operator()(), Aleph::Invert_Digraph< GT, SA >::operator()(), Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::paint_min_spanning_tree(), and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::scc_by_blocks().
|
inline |
Find the maximum arc in the entire graph.
| cmp | comparator (default: compare arc info with <) |
Definition at line 2454 of file graph-dry.H.
|
inline |
Find the maximum arc adjacent to a node.
max_arc(p, cmp) returns the arc adjacent to p with the maximum value according to the comparator cmp.
| p | node from which to find maximum adjacent arc |
| cmp | comparator (default: compare arc info with <) |
Definition at line 2418 of file graph-dry.H.
|
inlineprivate |
Definition at line 619 of file graph-dry.H.
Referenced by GraphCommon< GT, Node, Arc >::emplace_arc(), GraphCommon< GT, Node, Arc >::emplace_node(), GraphCommon< GT, Node, Arc >::insert_arc(), GraphCommon< GT, Node, Arc >::insert_arc(), GraphCommon< GT, Node, Arc >::insert_node(), GraphCommon< GT, Node, Arc >::insert_node(), GraphCommon< GT, Node, Arc >::remove_arcs_if(), GraphCommon< GT, Node, Arc >::sort_arcs(), and GraphCommon< GT, Node, Arc >::sort_nodes().
|
inline |
Find the minimum arc in the entire graph.
| cmp | comparator (default: compare arc info with <) |
Definition at line 2436 of file graph-dry.H.
|
inline |
Find the minimum arc adjacent to a node.
min_arc(p, cmp) returns the arc adjacent to p with the minimum value according to the comparator cmp.
| p | node from which to find minimum adjacent arc |
| cmp | comparator (default: compare arc info with <) |
Definition at line 2390 of file graph-dry.H.
Referenced by TEST_F().
|
inline |
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.
| bad_alloc | if there is no enough memory |
Definition at line 2720 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_node().
Referenced by Aleph::Net_Graph< NodeT, ArcT >::check_network(), Aleph::print_net_cost(), and Aleph::print_residual_net().
|
inline |
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; });
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.template keyword before the name nodes_map<your-target-type>. g.template nodes_map<ulong>([] (auto p) { return p->get_info(); });
| [in] | op | transformation from Node* to T to be performed on each node. |
DynList<T> containing the mapping. | bad_alloc | if there is no enough memory for fuilding the dynamic list or anything else that can throw op |
Definition at line 1743 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_node().
|
inline |
Overload of none_arc(Node*, Operation&) that accepts rvalues.
Definition at line 2274 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::none_arc().
|
inline |
Determine if no arc adjacent to a node satisfies a condition.
| p | node from which to check adjacent arcs |
| op | predicate to test |
true if no adjacent arc satisfies the condition Definition at line 2267 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::exists_arc().
|
inline |
Overload of none_arc(Operation&) that accepts rvalues.
Definition at line 2254 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::none_arc().
|
inline |
Determine if no arc satisfies a condition.
none_arc(op) returns true if no arc of graph satisfies the condition expressed by op. It is the logical complement of exists_arc().
Equivalent to: not exists_arc(op)
The operation has \(O(E)\) complexity for the worst case.
| op | predicate to test |
true if no arc satisfies the condition; false otherwise Definition at line 2247 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::exists_arc().
Referenced by GraphCommon< GT, Node, Arc >::none_arc(), and GraphCommon< GT, Node, Arc >::none_arc().
|
inline |
Overload of none_node(Operation&) that accepts rvalues.
Definition at line 2227 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::none_node().
|
inline |
Determine if no node satisfies a condition.
none_node(op) returns true if no node of graph satisfies the condition expressed by op. It is the logical complement of exists_node().
Equivalent to: not exists_node(op)
The operation has \(O(V)\) complexity for the worst case.
| op | predicate to test |
true if no node satisfies the condition; false otherwise Definition at line 2220 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::exists_node().
Referenced by GraphCommon< GT, Node, Arc >::none_node(), and TEST_F().
Return a list with the outcoming arcs to p`.
The method returns all the outcoming arcs p --> t.
| [in] | p | pointer to node |
| bad_alloc | if there is no enough memory |
Definition at line 3164 of file graph-dry.H.
References Aleph::DynList< T >::append(), and GraphCommon< GT, Node, Arc >::Digraph_Iterator< Filter >::has_curr().
|
inline |
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.
Definition at line 3571 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_out_arc().
|
inlinenoexcept |
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
| [in] | p | poinger to the node |
p Definition at line 3273 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::Digraph_Iterator< Filter >::has_curr().
Referenced by Aleph::Net_Graph< NodeT, ArcT >::get_out_degree().
Return a list with the outcoming nodes to p
The method filters all the outcoming arcs p --> t and return their nodes.
| [in] | p | pointer to node |
| bad_alloc | if there is no enough memory |
Definition at line 3147 of file graph-dry.H.
References Aleph::DynList< T >::append(), and GraphCommon< GT, Node, Arc >::Digraph_Iterator< Filter >::has_curr().
|
inline |
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.
| [in] | p | pointer to node |
| bad_alloc | if there is no enough memory |
Definition at line 3226 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::Digraph_Iterator< Filter >::has_curr().
|
inline |
Partition arcs into two groups based on a predicate.
partition_arcs(op) divides all arcs into two lists: those that satisfy op and those that don't.
The operation has \(O(E)\) complexity.
| op | predicate to partition by |
Definition at line 2505 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_arc().
|
inline |
Partition nodes into two groups based on a predicate.
partition_nodes(op) divides all nodes into two lists: those that satisfy op and those that don't.
The operation has \(O(V)\) complexity.
| op | predicate to partition by |
Definition at line 2482 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_node().
Referenced by TEST_F().
|
inlineprotected |
Remove all arcs matching a predicate.
This method removes all arcs for which the predicate returns true. It uses a safe two-phase approach:
| pred | Predicate with signature bool pred(Arc*) |
Example usage in remove_node:
Definition at line 3665 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::collect_arcs_if(), FunctionalMethods< Container, T >::for_each(), GraphCommon< GT, Node, Arc >::me(), pred, and Aleph::List_Graph< _Graph_Node, _Graph_Arc >::remove_arc().
Referenced by Aleph::List_Graph< _Graph_Node, _Graph_Arc >::remove_node(), and Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::remove_node().
|
inlinenoexcept |
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
Definition at line 913 of file graph-dry.H.
|
inlinenoexcept |
Reset all the arc counters of graph to zero.
Definition at line 905 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_arc(), and GraphCommon< GT, Node, Arc >::reset_counter().
|
inline |
Reset all the arcs of graph (the control bits, the state, the counter and the cookie)
Definition at line 927 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_arc().
Referenced by Aleph::Karger_Min_Cut< GT, SA >::build_kgraph(), Aleph::Find_Depth_First_Spanning_Tree< GT, SA >::build_tree(), Aleph::compute_bipartite(), Aleph::compute_bipartite_all_components(), Aleph::Unconnected_Components< GT, SA >::compute_blocks(), Aleph::compute_cut_nodes(), Aleph::Unconnected_Components< GT, SA >::compute_lists(), Aleph::Compute_Cut_Nodes< GT, SA >::cut_nodes(), Graph_Traverse< GT, Itor, Q, Show_Arc >::exec(), Aleph::Directed_Find_Path< GT, Itor, SA >::find(), Aleph::find_depth_first_spanning_tree(), Aleph::Find_Path_Breadth_First< GT, Itor, SA >::find_path(), Aleph::find_path_breadth_first(), Aleph::Find_Eulerian_Path< GT, SN, SA >::hierholzer_directed(), Aleph::Find_Eulerian_Path< GT, SN, SA >::hierholzer_undirected(), Aleph::inconnected_components(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::init_simple(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::init_with_indexes(), Aleph::invert_digraph(), Aleph::kosaraju_connected_components(), Aleph::kosaraju_connected_components(), Aleph::Prim_Min_Spanning_Tree< GT, Distance, SA >::min_spanning_tree(), Aleph::Invert_Digraph< GT, SA >::operator()(), Graph_Traverse< GT, Itor, Q, Show_Arc >::operator()(), Graph_Traverse< GT, Itor, Q, Show_Arc >::operator()(), Aleph::Prim_Min_Spanning_Tree< GT, Distance, SA >::paint_min_spanning_tree(), Aleph::Find_Aumenting_Path< Net, Q >::search(), TEST(), TEST(), TEST(), TYPED_TEST(), and TYPED_TEST().
|
inlinenoexcept |
|
inlinenoexcept |
Reset the bit of node (to zero)
Definition at line 801 of file graph-dry.H.
References NODE_BITS.
Referenced by Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::init_simple(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::init_with_indexes(), Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::Initialize_Arc::operator()(), Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::Initialize_Tree_Arc::operator()(), Aleph::Init_Prim_Info< GT >::operator()(), Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::Initialize_Node::operator()(), Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::Initialize_Tree_Node::operator()(), GraphCommon< GT, Node, Arc >::reset_bit_arcs(), and GraphCommon< GT, Node, Arc >::reset_bit_nodes().
|
inlinenoexcept |
Reset all the bits for all the arcs of graph.
Definition at line 1058 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_arc(), and GraphCommon< GT, Node, Arc >::reset_bits().
|
inlinenoexcept |
Reset bit to zero for all the arcs of graph.
Definition at line 1046 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_arc(), and GraphCommon< GT, Node, Arc >::reset_bit().
Referenced by Aleph::Breadth_First_Traversal< GT, Operation, SA >::bft(), Aleph::breadth_first_traversal(), Aleph::Find_Breadth_First_Spanning_Tree< GT, SA >::build_tree(), Aleph::depth_first_traversal(), Aleph::Depth_First_Traversal< GT, Operation, SA >::dft(), Aleph::Find_Path_Depth_First< GT, Itor, SA >::find(), Aleph::find_breadth_first_spanning_tree(), Aleph::find_path_depth_first(), Aleph::Is_Graph_Acyclique< GT, SA >::is_acyclique(), Aleph::is_graph_acyclique(), Aleph::is_graph_acyclique(), Aleph::map_subgraph(), Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::paint_min_spanning_tree(), Aleph::Test_For_Cycle< GT, SA >::test_cycle(), Aleph::test_for_cycle(), Aleph::test_for_path(), and Aleph::Test_For_Path< GT, SA >::test_path().
|
inlinenoexcept |
Reset all the bits for all the nodes of graph.
Definition at line 1052 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_node(), and GraphCommon< GT, Node, Arc >::reset_bits().
|
inlinenoexcept |
Reset bit to zero for all the nodes of graph.
Definition at line 1040 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_node(), and GraphCommon< GT, Node, Arc >::reset_bit().
Referenced by Aleph::Breadth_First_Traversal< GT, Operation, SA >::bft(), Aleph::breadth_first_traversal(), Aleph::Find_Breadth_First_Spanning_Tree< GT, SA >::build_tree(), Aleph::depth_first_traversal(), Aleph::Depth_First_Traversal< GT, Operation, SA >::dft(), Aleph::Find_Path_Depth_First< GT, Itor, SA >::find(), Aleph::find_breadth_first_spanning_tree(), Aleph::find_path_depth_first(), Aleph::Is_Graph_Acyclique< GT, SA >::is_acyclique(), Aleph::is_graph_acyclique(), Aleph::is_graph_acyclique(), Aleph::map_subgraph(), Aleph::Topological_Sort< GT, Itor, SA >::perform(), Aleph::Test_For_Cycle< GT, SA >::test_cycle(), Aleph::test_for_cycle(), Aleph::test_for_path(), and Aleph::Test_For_Path< GT, SA >::test_path().
|
inlinenoexcept |
|
inlinenoexcept |
Reset all the control bits of node
Definition at line 807 of file graph-dry.H.
References NODE_BITS.
Referenced by GraphCommon< GT, Node, Arc >::reset_bit_arcs(), and GraphCommon< GT, Node, Arc >::reset_bit_nodes().
|
inlinenoexcept |
Reset all the cookies to `nullptr for all the arcs of graph.
Definition at line 1092 of file graph-dry.H.
References ARC_COOKIE, and GraphCommon< GT, Node, Arc >::for_each_arc().
|
inlinenoexcept |
Reset all the cookies to `nullptr for all the nodes of graph.
Definition at line 1081 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_node(), and NODE_COOKIE.
|
inlinenoexcept |
|
inlinenoexcept |
Reset the node counter to zero.
Definition at line 873 of file graph-dry.H.
References NODE_COUNTER.
Referenced by GraphCommon< GT, Node, Arc >::reset_arc_counters(), GraphCommon< GT, Node, Arc >::reset_counter_arcs(), GraphCommon< GT, Node, Arc >::reset_counter_nodes(), and GraphCommon< GT, Node, Arc >::reset_node_counters().
|
inlinenoexcept |
Reset all the counters to zero for all the arcs of graph.
Definition at line 1070 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_arc(), and GraphCommon< GT, Node, Arc >::reset_counter().
Referenced by Aleph::Compute_Cut_Nodes< GT, SA >::paint_subgraphs(), and Aleph::paint_subgraphs().
|
inlinenoexcept |
Reset all the counters to zero for all the nodes of graph.
Definition at line 1064 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_node(), and GraphCommon< GT, Node, Arc >::reset_counter().
Referenced by Aleph::Test_Eulerian< GT, SN, SA >::analyze_digraph(), Aleph::Find_Eulerian_Path< GT, SN, SA >::find_start_vertex(), Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::make_hamiltonian(), Aleph::Compute_Cut_Nodes< GT, SA >::paint_subgraphs(), Aleph::paint_subgraphs(), Aleph::Q_Topological_Sort< GT, Itor, SA >::perform(), Aleph::Q_Topological_Sort< GT, Itor, SA >::ranks(), Aleph::Test_Eulerian< GT, SN, SA >::test_degree_only(), Aleph::Test_Hamiltonian_Sufficiency< GT, SN, SA >::test_digraph(), and Aleph::Test_Dirac_Condition< GT, SN, SA >::test_digraph().
|
inlinenoexcept |
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
Definition at line 887 of file graph-dry.H.
|
inlinenoexcept |
Reset all the node counters of graph to zero.
Definition at line 879 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_node(), and GraphCommon< GT, Node, Arc >::reset_counter().
|
inline |
Reset all the nodes of graph (the control bits, the state, the counter and the cookie)
Definition at line 920 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_node().
Referenced by Aleph::Karger_Min_Cut< GT, SA >::build_kgraph(), Aleph::Find_Depth_First_Spanning_Tree< GT, SA >::build_tree(), Aleph::compute_bipartite(), Aleph::compute_bipartite_all_components(), Aleph::Unconnected_Components< GT, SA >::compute_blocks(), Aleph::Unconnected_Components< GT, SA >::compute_lists(), Graph_Traverse< GT, Itor, Q, Show_Arc >::exec(), Aleph::Directed_Find_Path< GT, Itor, SA >::find(), Aleph::find_depth_first_spanning_tree(), Aleph::Find_Path_Breadth_First< GT, Itor, SA >::find_path(), Aleph::find_path_breadth_first(), Aleph::generic_preflow_vertex_push_maximum_flow(), Aleph::inconnected_components(), Aleph::invert_digraph(), Aleph::Test_Eulerian< GT, SN, SA >::is_connected(), Aleph::Test_Eulerian< GT, SN, SA >::is_strongly_connected(), Aleph::kosaraju_connected_components(), Aleph::kosaraju_connected_components(), Aleph::Invert_Digraph< GT, SA >::operator()(), Graph_Traverse< GT, Itor, Q, Show_Arc >::operator()(), Graph_Traverse< GT, Itor, Q, Show_Arc >::operator()(), Aleph::Prim_Min_Spanning_Tree< GT, Distance, SA >::paint_min_spanning_tree(), Aleph::preflow_create_residual_net(), Aleph::Find_Aumenting_Path< Net, Q >::search(), TEST(), TEST(), TEST(), TYPED_TEST(), and TYPED_TEST().
|
inline |
Overload of search_arc(Node*, Operation&) that accepts rvalues.
Definition at line 2673 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::search_arc().
|
inline |
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.
| [in] | p | pointer to the node from which the adjacent arcs want to be searched. |
| [in] | op | the criteria. |
nullptr otherwiseDefinition at line 2660 of file graph-dry.H.
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).
search_directed()The complexity is $ \(O(V)\) worst case.
| [in] | src | source node |
| [in] | tgt | target node |
nullptr otherwise.Definition at line 2701 of file graph-dry.H.
|
inline |
Overload of search_arc(Op&) that accepts rvalues.
Definition at line 2620 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::search_arc().
|
inline |
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.
| [in] | op | the criteria. |
nullptr otherwiseDefinition at line 2607 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::const_me().
Referenced by GraphCommon< GT, Node, Arc >::find_arc(), GraphCommon< GT, Node, Arc >::search_arc(), and GraphCommon< GT, Node, Arc >::search_arc().
|
inlinenoexcept |
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.
| [in] | src | pinter to source node |
| [in] | tgt | pinter to target node |
nullptr otherwise. Definition at line 3111 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::Digraph_Iterator< Filter >::has_curr().
|
inline |
Overload of search_in_arc(Node*, Op&) that accepts rvalues.
Definition at line 3405 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::search_in_arc().
|
inline |
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.
| [in] | p | pointer to the node. |
| [in] | op | operation to be executed on each arc in order to match certain search criteria. op must return true when the arc satisfies the search criteria. |
nullptr otherwise | anything | that op could throw |
Definition at line 3388 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::traverse_in_arcs().
Referenced by GraphCommon< GT, Node, Arc >::search_in_arc().
|
inline |
Overload of search_node(Op&) that accepts rvalues.
Definition at line 2569 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::search_node().
|
inline |
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.
| [in] | op | the criteria. |
nullptr otherwiseDefinition at line 2556 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::const_me().
Referenced by GraphCommon< GT, Node, Arc >::find_node(), and GraphCommon< GT, Node, Arc >::search_node().
|
inline |
Overload of search_out_arc(Node*, Op&) that accepts rvalues.
Definition at line 3557 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::search_out_arc().
|
inline |
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.
| [in] | p | pointer to the node. |
| [in] | op | operation to be executed on each arc in order to match certain search criteria. op must return true when the arc satisfies the search criteria. |
nullptr otherwise | anything | that op could throw |
Definition at line 3540 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::traverse_out_arcs().
Referenced by GraphCommon< GT, Node, Arc >::search_out_arc().
|
inlinenoexcept |
Set the control bit of arc to value
Definition at line 849 of file graph-dry.H.
References ARC_BITS.
|
inlinenoexcept |
Set the control bit of node to value
Definition at line 819 of file graph-dry.H.
References NODE_BITS.
Referenced by Aleph::find_depth_first_spanning_tree().
|
inline |
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 circumstances, very often for practical purposes (performance, 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 disaster 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.
Definition at line 692 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::digraph.
Referenced by Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::Random_Digraph(), and Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::~Random_Digraph().
|
inlinenoexcept |
Definition at line 3745 of file graph-dry.H.
References cmp(), and GraphCommon< GT, Node, Arc >::sort_arcs().
|
inlinenoexcept |
Sort all the arcs of the graph according to a specific criteria.
This method is available only for graph implementations that use Dlink-based storage (List_Graph, Array_Graph). It sorts the internal arc list using mergesort.
The comparison criteria should match the following signature:
bool cmp(Arc * a1, Arc * a2);
After execution of this method, provided that no new arcs are inserted or other sorts are not performed with a different criteria, it is guaranteed that order of apparition of the arcs by the Arc_Iterator will be sorted.
| cmp | comparison operation that defines the sorting criteria |
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
Definition at line 3736 of file graph-dry.H.
References cmp(), and GraphCommon< GT, Node, Arc >::me().
Referenced by GraphCommon< GT, Node, Arc >::sort_arcs(), and TEST().
|
inlinenoexcept |
Definition at line 3711 of file graph-dry.H.
References cmp(), and GraphCommon< GT, Node, Arc >::sort_nodes().
|
inlinenoexcept |
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
Definition at line 3702 of file graph-dry.H.
References cmp(), and GraphCommon< GT, Node, Arc >::me().
Referenced by GraphCommon< GT, Node, Arc >::sort_nodes(), and TEST().
|
inline |
Overload of sum_arcs(Node*, Extract) using the arc info as extractor.
Definition at line 2367 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_arc().
|
inline |
Sum values derived from arcs adjacent to a node.
sum_arcs(p, extract) sums the values extracted from each arc adjacent to node p using the extract function.
| T | the numeric type to sum (default: double) |
| p | node from which to sum adjacent arc values |
| extract | function Arc* -> T (default: arc info) |
Definition at line 2358 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::for_each_arc().
|
inline |
Overload of traverse_arcs(Node*, Operation&) that accepts rvalues.
Definition at line 1446 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::traverse_arcs().
|
inline |
Conditioned traversal of all the adjacent arcs of a node.
traverse_arc(p, operation) conditionally 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 type.
The operation is \(O(V)\) for the worst case, but it could be much less for sparce graphs.
For example, suppose 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)
{ std::cout << a->get_info() << '
'; return true; // for instructing to visit the next node });
operation, by example, to not return anything, not only they probably will not compile, but the diagnostic errors could be hard to understand. Perhaps, on some compilers, bad signatures could compile. So, be sure to match the correct operation signature.| [in] | p | node from you want to access its adjacent arcs. |
| [in] | op | operation to be performed on each arc. The operation must imperatively return a bool indicating whether or not the next arc must be visited. |
bool with the last operationresult. If true then all the arcs were visited and on each one operation executed. Otherwise, the traversal was stopped. | any | exception that could throw operation |
Definition at line 1436 of file graph-dry.H.
|
inline |
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.
| [in] | p | node to traverse its arcs |
| [in] | op | to perform on each arc given by the iterator. The convention is the the same than for traverse methods. If op return true, then the next arc is revised; otherwise the traversal stops. |
true if all the arcs were traversed; false otherwise. | whatever | could throw op |
Definition at line 3300 of file graph-dry.H.
|
inline |
Overload of traverse_arcs(Operation&) that accepts rvalues.
Definition at line 1379 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::traverse_arcs().
|
inline |
Conditioned traversal of all the arcs of a graph.
traverse_arc(operation) conditionally 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 type.
The operation is \(O(E)\) for the worst and average case.
For example, suppose that we wish print out the arcs content for all the arcs. Then we could do it as follows:
g.traverse_arcs([] (auto a)
{ std::cout << a->get_info() << '
'; return true; // for instructing to visit the next node });
operation, by example, to not return anything, not only they probably will not compile, but the diagnostic errors could be hard to understand. Perhaps, on some compilers, bad signatures could compile. So, be sure to match the correct operation signature.| [in] | op | operation to be performed on each arc. The operation must imperatively return a bool indicating whether the next arc must be visited. |
bool with the last operationresult. If true then all the arcs were visited and on each one operation executed. Otherwise, the traversal was stopped. | any | exception that could throw operation |
Definition at line 1369 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::const_me().
Referenced by GraphCommon< GT, Node, Arc >::all_arcs(), GraphCommon< GT, Node, Arc >::all_arcs(), GraphCommon< GT, Node, Arc >::exists_arc(), GraphCommon< GT, Node, Arc >::exists_arc(), GraphCommon< GT, Node, Arc >::traverse_arcs(), and GraphCommon< GT, Node, Arc >::traverse_arcs().
|
inline |
Overload of traverse_in_arcs(Node*, Op&) that accepts rvalues.
Definition at line 3326 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::traverse_in_arcs().
|
inline |
Traverse the incoming arcs of node p executing the conditioned operation
Definition at line 3319 of file graph-dry.H.
Referenced by GraphCommon< GT, Node, Arc >::all_in_arcs(), GraphCommon< GT, Node, Arc >::exists_in_arc(), GraphCommon< GT, Node, Arc >::search_in_arc(), and GraphCommon< GT, Node, Arc >::traverse_in_arcs().
|
inline |
Overload of traverse_nodes(Operation&) that accepts rvalues.
Definition at line 1314 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::traverse_nodes().
|
inline |
Conditioned traversal of all the nodes of a graph.
traverse_nodes(operation) conditionally 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, suppose that we wish print out the nodes content for all the nodes. Then we could do it as follows:
g.traverse_nodes([] (auto p)
{ std::cout << p->get_info() << '
'; 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.
operation, by example, to not return anything, not only they probably will not compile, but the diagnostic errors could be hard to understand. Perhaps, on some compilers, bad signatures could compile. So, be sure to match the correct operation signature.| [in] | op | operation to be performed on each node. The operation must imperatively return a bool indicating whether or not the next node must be visited. |
bool with the last operationresult. If true then all the mode were visited and on each one operation executed. Otherwise, the traversal was stopped. | any | exception that could throw operation |
Definition at line 1304 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::const_me().
Referenced by GraphCommon< GT, Node, Arc >::all_nodes(), GraphCommon< GT, Node, Arc >::exists_node(), and GraphCommon< GT, Node, Arc >::traverse_nodes().
|
inline |
Overload of traverse_out_arcs(Node*, Op&) that accepts rvalues.
Definition at line 3478 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::traverse_out_arcs().
|
inline |
Traverse the outcoming arcs of node p executing the conditioned operation
Definition at line 3471 of file graph-dry.H.
Referenced by GraphCommon< GT, Node, Arc >::all_out_arcs(), GraphCommon< GT, Node, Arc >::exists_out_arc(), GraphCommon< GT, Node, Arc >::search_out_arc(), and GraphCommon< GT, Node, Arc >::traverse_out_arcs().
|
inlineconstexprnoexcept |
Definition at line 698 of file graph-dry.H.
References GraphCommon< GT, Node, Arc >::get_num_nodes().
Referenced by Aleph::Network_Simplex< Net >::build_spanning_tree(), Aleph::dinic_blocking_flow(), Aleph::dinic_maximum_flow(), Graph_Traverse< GT, Itor, Q, Show_Arc >::exec(), Aleph::export_network_to_dimacs(), Aleph::export_network_to_json(), Aleph::generic_preflow_vertex_push_maximum_flow(), Aleph::hlpp_maximum_flow(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::link_cookies_and_free(), Aleph::max_flow_min_cost_by_cycle_canceling(), Aleph::network_to_json_string(), Graph_Traverse< GT, Itor, Q, Show_Arc >::operator()(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::paint_tree(), Aleph::Network_Simplex< Net >::print_diagnostics(), Aleph::MCF_LP_Solver< Net >::print_formulation(), Aleph::Network_Simplex< Net >::print_stats(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::relax_arcs(), Aleph::Network_Simplex< Net >::run(), Aleph::ssp_init_potentials(), Aleph::successive_shortest_paths(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().
|
protected |
Definition at line 624 of file graph-dry.H.
Referenced by GraphCommon< GT, Node, Arc >::common_swap(), GraphCommon< GT, Node, Arc >::get_cookie(), GraphCommon< GT, Node, Arc >::get_cookie(), and GraphCommon< GT, Node, Arc >::init().
|
protected |
Definition at line 627 of file graph-dry.H.
Referenced by GraphCommon< GT, Node, Arc >::common_swap(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::connect_arc(), Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::disconnect_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::disconnect_arc(), GraphCommon< GT, Node, Arc >::init(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), GraphCommon< GT, Node, Arc >::is_digraph(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::remove_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::remove_node(), Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::remove_node(), GraphCommon< GT, Node, Arc >::set_digraph(), and Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::try_insert_arc().
|
staticconstexpr |
Definition at line 3698 of file graph-dry.H.
|
staticconstexpr |
Sort all the nodes of the graph according to a specific criteria.
This method is available only for graph implementations that use Dlink-based storage (List_Graph, Array_Graph). It sorts the internal node list using mergesort.
The comparison criteria should match the following signature:
bool cmp(Node * n1, Node * n2);
After execution of this method, provided that no new nodes are inserted or other sorts are not performed with a different criteria, it is guaranteed that order of apparition of the nodes by the Node_Iterator will be sorted.
| cmp | comparison operation that defines the sorting criteria |
Definition at line 3694 of file graph-dry.H.
|
protected |
Definition at line 626 of file graph-dry.H.
Referenced by Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::Array_Graph(), Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::clear(), GraphCommon< GT, Node, Arc >::common_swap(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::connect_arc(), Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::disconnect_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::disconnect_arc(), GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::init(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::remove_arc(), and Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::try_insert_arc().
|
protected |
Definition at line 625 of file graph-dry.H.
Referenced by Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::Array_Graph(), Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::clear(), GraphCommon< GT, Node, Arc >::common_swap(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::get_first_node(), GraphCommon< GT, Node, Arc >::get_num_nodes(), GraphCommon< GT, Node, Arc >::init(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::insert_node(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::remove_node(), and Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::remove_node().
1.9.8