Flow network implemented with adjacency lists. More...
#include <tpl_net.H>
Public Types | |
| using | Net = Net_Graph< NodeT, ArcT > |
| using | Base = Array_Graph< NodeT, ArcT > |
| using | Graph = Base |
| using | Arc = ArcT |
| Arc type. | |
| using | Node = NodeT |
| Node type. | |
| using | Flow_Type = typename Arc::Flow_Type |
| Capacity/flow numeric type. | |
| using | Node_Type = typename Node::Node_Type |
| Node info type. | |
| using | Arc_Type = typename Arc::Arc_Type |
| Arc info type. | |
 Public Types inherited from Aleph::Array_Graph< __Graph_Node, __Graph_Arc > | |
| using | Node = __Graph_Node |
| using | Arc = __Graph_Arc |
| using | Node_Type = typename Node::Node_Type |
| using | Arc_Type = typename Arc::Arc_Type |
| using | CommonBase = GraphCommon< Array_Graph< __Graph_Node, __Graph_Arc >, __Graph_Node, __Graph_Arc > |
| Public Types inherited from GraphCommon< GT, Node, Arc > | |
| using | Node_Type = typename Node::Node_Type |
| using | Arc_Type = typename Arc::Arc_Type |
| using | ArcPair = std::tuple< Arc *, Node * > |
| Pair of arc and node (topologically related) | |
Public Member Functions | |
| DynList< Arc * > | out_arcs (Node *p) const noexcept |
Return arcs outgoing from p (as a DynList). | |
| DynList< Node * > | out_nodes (Node *p) const noexcept |
Return nodes reachable from p through outgoing arcs. | |
| DynList< Arc * > | in_arcs (Node *p) const noexcept |
Return arcs incoming to p (as a DynList). | |
| DynList< Node * > | in_nodes (Node *p) const noexcept |
Return nodes that can reach p through incoming arcs. | |
| Flow_Type | get_in_cap (Node *node) const noexcept |
Return total incoming capacity of node. | |
| Flow_Type | get_out_cap (Node *node) const noexcept |
Return total outgoing capacity of node. | |
| size_t | get_in_degree (Node *p) const noexcept |
Return the in-degree of p (number of incoming arcs). | |
| size_t | get_out_degree (Node *p) const noexcept |
Return the out-degree of p (number of outgoing arcs). | |
| Flow_Type | get_out_flow (Node *node) const noexcept |
Return total outgoing flow of node. | |
| Flow_Type | get_in_flow (Node *node) const noexcept |
Return total incoming flow of node. | |
| bool | is_source (Node *node) const noexcept |
Return true if node is a source. | |
| bool | is_sink (Node *node) const noexcept |
Return true if node is a sink. | |
| constexpr bool | is_single_source () const noexcept |
| Return true if the network has a single source. | |
| constexpr bool | is_single_sink () const noexcept |
| Return true if the network has a single sink. | |
| bool | is_connected (Node *p) const noexcept |
Return true if p is connected (used for validation). | |
| bool | check_node (Node *node) const noexcept |
Return true if node satisfies flow conservation constraints. | |
| const DynSetTree< Node * > & | get_src_nodes () const noexcept |
| Return the set of source nodes. | |
| const DynSetTree< Node * > & | get_sink_nodes () const noexcept |
| Return the set of sink nodes. | |
| void | make_super_source () |
| Convert a multi-source network into a single super-source network. | |
| void | unmake_super_source () noexcept |
| Restore a super-source network to its original multi-source form. | |
| void | make_super_sink () |
| Convert a multi-sink network into a single super-sink network. | |
| void | unmake_super_sink () noexcept |
| Restore a super-sink network to its original multi-sink form. | |
| void | make_super_nodes () |
| Convert a multi-source/multi-sink network into super-source/super-sink. | |
| void | unmake_super_nodes () |
| Restore a super-source/super-sink network to its original form. | |
| Node * | get_source () const |
| Return an arbitrary source node. | |
| Node * | get_sink () const |
| Return an arbitrary sink node. | |
| Node * | insert_node (const Node_Type &node_info) |
Insert a new node by copying node_info. | |
| Node * | insert_node () |
| Insert a new node with default info. | |
| Node * | insert_node (Node_Type &&info) |
Insert a new node by moving info. | |
| template<typename... Args> | |
| Node * | emplace_node (Args &&... args) |
| Construct a node in-place and insert it into the network. | |
| Node * | insert_node (Node *p) |
| Insert a node by copying another node. | |
| Arc * | insert_arc (Node *src_node, Node *tgt_node, const Flow_Type &cap, const Flow_Type &flow, const typename Arc::Arc_Type &arc_info=Arc_Type()) |
| Insert a capacitated arc with an initial flow. | |
| template<typename... Args> | |
| Arc * | emplace_arc (Node *src_node, Node *tgt_node, const Flow_Type &cap, const Flow_Type &flow, Args &&... args) |
| Construct arc info in-place and insert the arc. | |
| Arc * | connect_arc (Arc *arc) |
| Connect a previously disconnected arc. | |
| Arc * | insert_arc (Node *src_node, Node *tgt_node, const Flow_Type &cap) |
Insert an arc with capacity cap and zero flow. | |
| template<typename T = Arc_Type, typename = std::enable_if_t<!std::is_same<T, Flow_Type>::value && !std::is_arithmetic_v<T>>> | |
| Arc * | insert_arc (Node *src_node, Node *tgt_node, const T &arc_info=Arc_Type()) |
| Insert an arc with zero capacity and flow. | |
| void | remove_arc (Arc *arc) override |
Remove arc arc from the network. | |
| void | disconnect_arc (Arc *arc) noexcept |
Disconnect arc arc from the graph without deleting it. | |
| void | remove_node (Node *p) noexcept override |
Remove node p and all its arcs from the network. | |
| Net_Graph (const Net_Graph &net) | |
| Copy-construct a network. Throws bad_alloc on allocation failure. | |
| void | swap (Net_Graph &other) noexcept |
| Swap contents with another network. O(1) operation. | |
| Net_Graph (Net_Graph &&other) noexcept | |
| Move-construct a network. O(1) operation. | |
| Net_Graph & | operator= (Net_Graph &&other) noexcept |
| Move-assign a network. O(1) operation. | |
| Net_Graph & | operator= (const Net_Graph &net) |
| Copy-assign a network. Throws bad_alloc on allocation failure. | |
| void | set_cap (Arc *arc, const Flow_Type &cap) |
| Set the capacity of an arc. | |
| void | set_flow (Arc *arc, const Flow_Type &flow) |
Set the flow of an arc. Throws if flow exceeds capacity. | |
| const Flow_Type & | get_flow (Arc *arc) const noexcept |
| Return the flow value of an arc. | |
| const Flow_Type & | get_cap (Arc *arc) const noexcept |
| Return the capacity value of an arc. | |
| void | reset () |
| Reset all arc flows to zero. | |
| bool | check_network () const |
| Validate flow-conservation and capacity constraints. | |
| Flow_Type | flow_value () const |
| Return the total flow value of the network. | |
| Net_Graph () | |
| Default constructor. | |
| virtual Node * | insert_node (Node *p) |
| 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. | |
| Public Member Functions inherited from Aleph::Array_Graph< __Graph_Node, __Graph_Arc > | |
| Dlink & | get_node_dlink () noexcept |
| Returns reference to internal node Dlink for sorting operations. | |
| Dlink & | get_arc_dlink () noexcept |
| Returns reference to internal arc Dlink for sorting operations. | |
| virtual Node * | insert_node (Node *p) |
| void | compress () |
| Arc * | connect_arc (Arc *arc) |
| Arc * | disconnect_arc (Arc *arc) |
| virtual void | remove_arc (Arc *a) |
| virtual void | remove_node (Node *p) |
| Node * | get_first_node () const |
| Arc * | get_first_arc () const |
| Arc * | get_first_arc (Node *p) const |
| Array_Graph () | |
| virtual | ~Array_Graph () noexcept |
| void | swap (Array_Graph &g) noexcept |
| Array_Graph (const Array_Graph &g) | |
| Copy constructor. | |
| Array_Graph (Array_Graph &&g) noexcept | |
| Move constructor. | |
| Array_Graph & | operator= (const Array_Graph &g) |
| Copy assignment. | |
| Array_Graph & | operator= (Array_Graph &&g) noexcept |
| Move assignment. | |
| Node * | insert_node (const Node_Type &node_info) |
| Allocate a new node, set by copy its data content and insert it into the graph. | |
| Node * | insert_node (Node_Type &&node_info=Node_Type()) |
| Allocate a new node, set by moving its data content and insert it into the graph. | |
| Arc * | insert_arc (Node *src, Node *tgt, const Arc_Type &arc_info) |
| Create and insert a new arc linking two nodes and copying data. | |
| Arc * | insert_arc (Node *src, Node *tgt, Arc_Type &&arc_info=Arc_Type()) |
| Create and insert a new arc linking two nodes and moving the received data. | |
| Public Member Functions inherited from GraphCommon< GT, Node, Arc > | |
| void *& | get_cookie () noexcept |
| Return a modifiable reference to graph's cookie. | |
| void * | get_cookie () const noexcept |
| Return a constant reference to graph's cookie. | |
| bool | is_digraph () const noexcept |
Return true if the graph this is directed. | |
| void | set_digraph (bool val) |
| Temporal indication for preventing to other algorithms that an graph must be treated as a directed graph. | |
| constexpr size_t | get_num_nodes () const noexcept |
| Return the total of nodes of graph. | |
| constexpr size_t | vsize () const noexcept |
| Node * | get_node () const |
| Return any node in the graph. | |
| Node * | get_arc () const |
| Return any arc in the graph. | |
| Node * | get_arc (Node *p) |
| Return any arc adjacent to a node. | |
| Node * | get_src_node (Arc *arc) const noexcept |
Return the source node of arc (only for directed graphs) | |
| Node * | get_tgt_node (Arc *arc) const noexcept |
Return the target node of arc (only for directed graphs) | |
| Node * | get_connected_node (Arc *arc, Node *node) const noexcept |
Return the adjacent node to node through arc. | |
| constexpr size_t | get_num_arcs () const noexcept |
| size_t | get_num_arcs (Node *node) const noexcept |
| Return the total of arcs of a node. | |
| size_t | degree (Node *p) const noexcept |
| Return the total of arcs (or degree) of a node. | |
| size_t | esize () const noexcept |
| Return the total of arcs of graph. | |
| Bit_Fields & | get_control_bits (Node *node) const noexcept |
Return a reference to control fields of node | |
| void | reset_bit (Node *node, int bit) const noexcept |
Reset the bit of node (to zero) | |
| void | reset_bits (Node *node) const noexcept |
Reset all the control bits of node | |
| int | get_bit (Node *node, int bit) const noexcept |
Get the control bit of node | |
| void | set_bit (Node *node, int bit, int value) const noexcept |
Set the control bit of node to value | |
| Bit_Fields & | get_control_bits (Arc *arc) const noexcept |
Return a reference to the control bits of arc | |
| void | reset_bit (Arc *arc, int bit) const noexcept |
Reset the bit of arc to zero. | |
| void | reset_bits (Arc *arc) const noexcept |
Reset all the control bits of arc | |
| int | get_bit (Arc *arc, int bit) const noexcept |
Get the control bit of arc | |
| void | set_bit (Arc *arc, int bit, int value) const noexcept |
Set the control bit of arc to value | |
| void *& | get_cookie (Node *node) const noexcept |
Get a modifiable reference to the cookie pointer of node | |
| void *& | get_cookie (Arc *arc) const noexcept |
Get a modifiable reference to the cookie pointer of arc | |
| long & | get_counter (Node *node) const noexcept |
Get a modifiable reference to the counter of node | |
| void | reset_counter (Node *node) const noexcept |
Reset the node counter to zero. | |
| void | reset_node_counters () const noexcept |
| Reset all the node counters of graph to zero. | |
| void | reset_node (Node *p) const noexcept |
Reset all the control attributes of node p. | |
| long & | get_counter (Arc *arc) const noexcept |
Get a modifiable reference to the counter of arc | |
| void | reset_counter (Arc *arc) const noexcept |
Reset the acr counter to zero. | |
| void | reset_arc_counters () const noexcept |
| Reset all the arc counters of graph to zero. | |
| void | reset_arc (Arc *arc) const noexcept |
Reset all the control attributes of arc. | |
| void | reset_nodes () const |
| Reset all the nodes of graph (the control bits, the state, the counter and the cookie) | |
| void | reset_arcs () const |
| Reset all the arcs of graph (the control bits, the state, the counter and the cookie) | |
| void | reset_bit_nodes (int bit) const noexcept |
Reset bit to zero for all the nodes of graph. | |
| void | reset_bit_arcs (int bit) const noexcept |
Reset bit to zero for all the arcs of graph. | |
| void | reset_bit_nodes () const noexcept |
| Reset all the bits for all the nodes of graph. | |
| void | reset_bit_arcs () const noexcept |
| Reset all the bits for all the arcs of graph. | |
| void | reset_counter_nodes () const noexcept |
| Reset all the counters to zero for all the nodes of graph. | |
| void | reset_counter_arcs () const noexcept |
| Reset all the counters to zero for all the arcs of graph. | |
| void | reset_cookie_nodes () const noexcept |
| Reset all the cookies to `nullptr for all the nodes of graph. | |
| void | reset_cookie_arcs () const noexcept |
| Reset all the cookies to `nullptr for all the arcs of graph. | |
| Node * | insert_node (const Node_Type &node_info) |
| Allocate a new node, set by copy its data content and insert it into the graph. | |
| Node * | insert_node (Node_Type &&node_info=Node_Type()) |
| Allocate a new node, set by moving its data content and insert it into the graph. | |
| template<typename... Args> | |
| Node * | emplace_node (Args &&... args) |
| Insert a new node in the graph by constructing it in-place with the given args. | |
| Arc * | insert_arc (Node *src, Node *tgt, const Arc_Type &arc_info) |
| Create and insert a new arc linking two nodes and copying data. | |
| Arc * | insert_arc (Node *src, Node *tgt, Arc_Type &&arc_info=Arc_Type()) |
| Create and insert a new arc linking two nodes and moving the received data. | |
| template<typename... Args> | |
| Arc * | emplace_arc (Node *src, Node *tgt, Args &&... args) |
| Insert a new arc in the graph by constructing its associated data in-place with the given args. | |
| template<class Operation > | |
| bool | traverse_nodes (Operation &op) const |
| Conditioned traversal of all the nodes of a graph. | |
| template<class Operation > | |
| bool | traverse_nodes (Operation &&op=Operation()) const |
Overload of traverse_nodes(Operation&) that accepts rvalues. | |
| template<class Operation > | |
| bool | traverse_arcs (Operation &op) const |
| Conditioned traversal of all the arcs of a graph. | |
| template<class Operation > | |
| bool | traverse_arcs (Operation &&op=Operation()) const |
Overload of traverse_arcs(Operation&) that accepts rvalues. | |
| template<class Operation > | |
| bool | traverse_arcs (Node *p, Operation &op) const |
| Conditioned traversal of all the adjacent arcs of a node. | |
| template<class Operation > | |
| bool | traverse_arcs (Node *p, Operation &&op=Operation()) const |
Overload of traverse_arcs(Node*, Operation&) that accepts rvalues. | |
| template<class Operation > | |
| void | for_each_node (Operation &operation) const |
| Unconditionally traverse all the nodes of graph and on each one perform an operation. | |
| template<class Operation > | |
| void | for_each_node (Operation &&operation=Operation()) const |
Overload of for_each_node(Operation&) that accepts rvalues. | |
| template<class Operation > | |
| void | for_each_arc (Operation &op) const |
| Unconditionally traverse all the arcs of graph and on each one perform an operation. | |
| template<class Operation > | |
| void | for_each_arc (Operation &&operation=Operation()) const |
Overload of for_each_arc(Operation&) that accepts rvalues. | |
| template<class Operation > | |
| void | for_each_arc (Node *p, Operation &op) const |
| Unconditionally traverse all the arcs adjacnt to a node and on each one perform an operation. | |
| template<class Operation > | |
| void | for_each_arc (Node *p, Operation &&op=Operation()) const |
Overload of for_each_arc(Node*, Operation&) that accepts rvalues. | |
| template<class Operation > | |
| bool | all_nodes (Operation &op) const |
| Check if all the nodes of graph satisfy an boolean condition. | |
| template<class Operation > | |
| bool | all_nodes (Operation &&op=Operation()) const |
Overload of all_nodes(Operation&) that accepts rvalues. | |
| template<class Operation > | |
| bool | all_arcs (Operation &op) const |
| Check if all the arcs of graph satisfy a boolean condition. | |
| template<class Operation > | |
| bool | all_arcs (Operation &&op=Operation()) const |
Overload of all_arcs(Operation&) that accepts rvalues. | |
| template<class Operation > | |
| bool | all_arcs (Node *p, Operation &op) const |
| Check if all the arcs adjacent to a node satisfy an boolean condition. | |
| template<class Operation > | |
| bool | all_arcs (Node *p, Operation &&op=Operation()) const |
Overload of all_arcs(Node*, Operation&) that accepts rvalues. | |
| template<typename T = Node_Type> | |
| auto | nodes_map (std::function< T(Node *)> op) const |
| Map the nodes of a graph to a specific range. | |
| template<typename T = Arc_Type> | |
| auto | arcs_map (std::function< T(Arc *)> operation) const |
| Map the arcs of a graph to a specific range. | |
| template<typename T = Arc_Type> | |
| auto | arcs_map (Node *p, std::function< T(Arc *)> operation) const |
| Map the adjacent arcs of a node to a specific range. | |
| template<typename T = Node_Type> | |
| T | foldl_nodes (const T &init, std::function< T(const T &, Node *)> op) const |
| Folding of nodes on a graph. | |
| template<typename T = Arc_Type> | |
| T | foldl_arcs (const T &init, std::function< T(const T &, Arc *)> op) const |
| Folding of arcs on a graph. | |
| template<typename T = Arc_Type> | |
| T | foldl_arcs (Node *p, const T &init, std::function< T(const T &, Arc *)> op) const |
| Folding of arcs of a node. | |
| template<class Op > | |
| auto | filter_nodes (Op &op) const |
| Filter the nodes satisfying a condition. | |
| template<class Op > | |
| auto | filter_nodes (Op &&op) const |
Overload of filter_nodes(Op&) that accepts rvalues. | |
| template<class Op > | |
| auto | filter_arcs (Op &op) const |
| Filter the arcs of graph satisfying a condition. | |
| template<class Op > | |
| auto | filter_arcs (Op &&op) const |
Overload of filter_arcs(Op&) that accepts rvalues. | |
| template<class Op > | |
| auto | filter_arcs (Node *p, Op &op) const |
| Filter the arcs adjacent to a node satisfying a condition. | |
| template<class Op > | |
| auto | filter_arcs (Node *p, Op &&op) const |
Overload of filter_arcs(Node*, Op&) that accepts rvalues. | |
| template<class Operation > | |
| bool | exists_node (Operation &op) const |
| Determine if exists at least a node satisfying a condition. | |
| template<class Operation > | |
| bool | exists_node (Operation &&op=Operation()) const |
Overload of exists_node(Operation&) that accepts rvalues. | |
| template<class Operation > | |
| bool | exists_arc (Operation &op) const |
| Determine if exists at least a arc satisfying a condition. | |
| template<class Operation > | |
| bool | exists_arc (Operation &&op=Operation()) const |
Overload of exists_arc(Operation&) that accepts rvalues. | |
| template<class Operation > | |
| bool | exists_arc (Node *p, Operation &op) const |
| Determine if exists at least a arc adjacent to a node satisfying a condition. | |
| template<class Operation > | |
| bool | exists_arc (Node *p, Operation &&op=Operation()) const |
Overload of exists_arc(Node*, Operation&) that accepts rvalues. | |
| template<class Operation > | |
| bool | none_node (Operation &op) const |
| Determine if no node satisfies a condition. | |
| template<class Operation > | |
| bool | none_node (Operation &&op) const |
Overload of none_node(Operation&) that accepts rvalues. | |
| template<class Operation > | |
| bool | none_arc (Operation &op) const |
| Determine if no arc satisfies a condition. | |
| template<class Operation > | |
| bool | none_arc (Operation &&op) const |
Overload of none_arc(Operation&) that accepts rvalues. | |
| template<class Operation > | |
| bool | none_arc (Node *p, Operation &op) const |
| Determine if no arc adjacent to a node satisfies a condition. | |
| template<class Operation > | |
| bool | none_arc (Node *p, Operation &&op) const |
Overload of none_arc(Node*, Operation&) that accepts rvalues. | |
| template<class Operation = std::function<bool(Node*)>> | |
| size_t | count_nodes (Operation op=[](Node *) { return true;}) const |
| Count the nodes satisfying a condition. | |
| template<class Operation = std::function<bool(Arc*)>> | |
| size_t | count_arcs (Operation op=[](Arc *) { return true;}) const |
| Count the arcs satisfying a condition. | |
| template<class Operation = std::function<bool(Arc*)>> | |
| size_t | count_arcs (Node *p, Operation op=[](Arc *) { return true;}) const |
| Count arcs adjacent to a node satisfying a condition. | |
| template<typename T = double, class Extract > | |
| T | sum_arcs (Node *p, Extract extract) const |
| Sum values derived from arcs adjacent to a node. | |
| template<typename T = double> | |
| T | sum_arcs (Node *p) const |
Overload of sum_arcs(Node*, Extract) using the arc info as extractor. | |
| template<class Compare = std::function<bool(Arc*, Arc*)>> | |
| Arc * | min_arc (Node *p, Compare cmp=[](Arc *a, Arc *b) { return a->get_info()< b->get_info();}) const |
| Find the minimum arc adjacent to a node. | |
| template<class Compare = std::function<bool(Arc*, Arc*)>> | |
| Arc * | max_arc (Node *p, Compare cmp=[](Arc *a, Arc *b) { return a->get_info()< b->get_info();}) const |
| Find the maximum arc adjacent to a node. | |
| template<class Compare = std::function<bool(Arc*, Arc*)>> | |
| Arc * | min_arc (Compare cmp=[](Arc *a, Arc *b) { return a->get_info()< b->get_info();}) const |
| Find the minimum arc in the entire graph. | |
| template<class Compare = std::function<bool(Arc*, Arc*)>> | |
| Arc * | max_arc (Compare cmp=[](Arc *a, Arc *b) { return a->get_info()< b->get_info();}) const |
| Find the maximum arc in the entire graph. | |
| template<class Operation > | |
| std::pair< DynList< Node * >, DynList< Node * > > | partition_nodes (Operation op) const |
| Partition nodes into two groups based on a predicate. | |
| template<class Operation > | |
| std::pair< DynList< Arc * >, DynList< Arc * > > | partition_arcs (Operation op) const |
| Partition arcs into two groups based on a predicate. | |
| DynList< Node * > | adjacent_nodes (Node *p) const |
| Get all adjacent nodes (neighbors) of a node. | |
| template<class Op > | |
| Node * | search_node (Op &op) const |
| Linear search of a node. | |
| template<class Op > | |
| Node * | search_node (Op &&op) const |
Overload of search_node(Op&) that accepts rvalues. | |
| Node * | find_node (const Node_Type &info) const noexcept |
| Find a node mathing a content. | |
| template<class Op > | |
| Arc * | search_arc (Op &op) const |
| Linear search of an arc. | |
| template<class Op > | |
| Arc * | search_arc (Op &&op) const |
Overload of search_arc(Op&) that accepts rvalues. | |
| Arc * | find_arc (const Arc_Type &info) const noexcept |
| Find an arc mathing a content. | |
| template<class Operation > | |
| Arc * | search_arc (Node *p, Operation &op) const |
| Linear search of an arc. | |
| template<class Operation > | |
| Arc * | search_arc (Node *p, Operation &&op=Operation()) const |
Overload of search_arc(Node*, Operation&) that accepts rvalues. | |
| Arc * | search_arc (Node *src, Node *tgt) const noexcept |
| Search an arc linking two nodes. | |
| template<template< typename > class Container = Aleph::DynList> | |
| Container< Node * > | nodes () const |
| Return a container with all the nodes of the graph. | |
| template<template< typename > class Container = Aleph::DynList> | |
| Container< Arc * > | arcs () const |
| Return a container with all the arcs of the graph. | |
| template<template< typename > class Container = Aleph::DynList> | |
| Container< Arc * > | arcs (Node *p) const |
| Return a container with all the arcs adjacent to a node. | |
| auto | get_node_it () const noexcept |
| Obtains an iterator to the nodes of graph. | |
| auto | get_arc_it () const noexcept |
| Obtains an iterator to the arc of graph. | |
| auto | get_arc_it (Node *p) const noexcept |
| Obtains an iterator to the adjacent arcs of a node. | |
| In_Iterator | get_in_it (Node *p) const noexcept |
Return an input iterator on the incoming arcs to p | |
| Out_Iterator | get_out_it (Node *p) const noexcept |
Return an output iterator on the incoming nodes to p | |
| Arc * | search_directed_arc (Node *src, Node *tgt) const noexcept |
| Search a directed arc linking two nodes. | |
| DynList< Node * > | in_nodes (Node *p) const |
Return a list with the incoming nodes to p | |
| DynList< Node * > | out_nodes (Node *p) const |
Return a list with the outcoming nodes to p | |
| DynList< Arc * > | out_arcs (Node *p) const |
| Return a list with the outcoming arcs to p`. | |
| DynList< Arc * > | in_arcs (Node *p) const |
| Return a list with the incoming arcs to p`. | |
| auto | in_pairs (Node *p) const |
| Return a list of pair incoming arcs and nodes. | |
| auto | out_pairs (Node *p) const |
| Return a list of pair outcoming arcs and nodes. | |
| size_t | in_degree (Node *p) const noexcept |
| Compute the input degree of a node. | |
| size_t | out_degree (Node *p) const noexcept |
| Compute the output degree of a node. | |
| template<class Itor , class Operation > | |
| bool | traverse_arcs (Node *p, Operation &op) const |
| Traverse of arcs of a node according to specific arcs iterator. | |
| template<class Itor , class Operation > | |
| void | for_each_arc (Node *p, Operation &op) const |
Perform op on each arc of node p | |
| template<class Op > | |
| bool | traverse_in_arcs (Node *p, Op &op) const |
Traverse the incoming arcs of node p executing the conditioned operation | |
| template<class Op > | |
| bool | traverse_in_arcs (Node *p, Op &&op=Op()) const |
Overload of traverse_in_arcs(Node*, Op&) that accepts rvalues. | |
| template<class Op > | |
| void | for_each_in_arc (Node *p, Op &op) const |
Perform op on each incoming arc of node p | |
| template<class Op > | |
| void | for_each_in_arc (Node *p, Op &&op=Op()) const |
Overload of for_each_in_arc(Node*, Op&) that accepts rvalues. | |
| template<class Op > | |
| bool | all_in_arcs (Node *p, Op &op) const |
Return true if op is true for all the incoming arcs to node p | |
| template<class Op > | |
| bool | all_in_arcs (Node *p, Op &&op=Op()) const |
Overload of all_in_arcs(Node*, Op&) that accepts rvalues. | |
| template<class Op > | |
| bool | exists_in_arc (Node *p, Op &op) const |
Return true if it exists a incoming arc to p returning true for op | |
| template<class Op > | |
| bool | exists_in_arc (Node *p, Op &&op=Op()) const |
Overload of exists_in_arc(Node*, Op&) that accepts rvalues. | |
| template<class Op > | |
| auto | search_in_arc (Node *p, Op &op) const |
| Search an incoming arc to a node satisfaying a condition. | |
| template<class Op > | |
| auto | search_in_arc (Node *p, Op &&op=Op()) const |
Overload of search_in_arc(Node*, Op&) that accepts rvalues. | |
| template<typename T > | |
| auto | in_arcs_map (Node *p, std::function< T(Arc *)> op) const |
Return a list of incoming arcs of a node mapped to items of type given by transformation op. | |
| template<typename T = Arc_Type> | |
| T | foldl_in_arcs (Node *p, const T &init, std::function< T(const T &, Arc *)> op) const |
| Fold the incoming arcs of a node. | |
| template<class Op > | |
| DynList< Arc * > | filter_in_arcs (Node *p, Op &op) const |
| Filter the incoming arcs of a node. | |
| template<class Op > | |
| auto | filter_in_arcs (Node *p, Op &&op=Op()) const |
Overload of filter_in_arcs(Node*, Op&) that accepts rvalues. | |
| template<class Op > | |
| bool | traverse_out_arcs (Node *p, Op &op) const |
Traverse the outcoming arcs of node p executing the conditioned operation | |
| template<class Op > | |
| bool | traverse_out_arcs (Node *p, Op &&op=Op()) const |
Overload of traverse_out_arcs(Node*, Op&) that accepts rvalues. | |
| template<class Op > | |
| void | for_each_out_arc (Node *p, Op &op) const |
Perform op on each outcoming arc of node p | |
| template<class Op > | |
| void | for_each_out_arc (Node *p, Op &&op=Op()) const |
Overload of for_each_out_arc(Node*, Op&) that accepts rvalues. | |
| template<class Op > | |
| bool | all_out_arcs (Node *p, Op &op) const |
Return true if op is true for all the outcoming arcs to node p | |
| template<class Op > | |
| bool | all_out_arcs (Node *p, Op &&op=Op()) const |
Overload of all_out_arcs(Node*, Op&) that accepts rvalues. | |
| template<class Op > | |
| bool | exists_out_arc (Node *p, Op &op) const |
Return true if it exists a outcoming arc to p returning true for op | |
| template<class Op > | |
| bool | exists_out_arc (Node *p, Op &&op=Op()) const |
Overload of exists_out_arc(Node*, Op&) that accepts rvalues. | |
| template<class Op > | |
| auto | search_out_arc (Node *p, Op &op) const |
| Search an outcoming arc to a node satisfaying a condition. | |
| template<class Op > | |
| auto | search_out_arc (Node *p, Op &&op=Op()) const |
Overload of search_out_arc(Node*, Op&) that accepts rvalues. | |
| template<typename T = Arc_Type> | |
| auto | out_arcs_map (Node *p, std::function< T(Arc *)> op) const |
Return a list of outcoming arcs of a node mapped to items of type given by transformation op. | |
| template<typename T = Arc_Type> | |
| T | foldl_out_arcs (Node *p, const T &init, std::function< T(const T &, Arc *)> op) const |
| Fold-left over outcoming arcs of a node. | |
| template<class Op > | |
| DynList< Arc * > | filter_out_arcs (Node *p, Op &op) const |
| Filter the outcoming arcs of a node. | |
| template<class Op > | |
| auto | filter_out_arcs (Node *p, Op &&op=Op()) const |
Overload of filter_out_arcs(Node*, Op&) that accepts rvalues. | |
| template<class Compare > requires (has_node_dlink_v<GT>) | |
| void | sort_nodes (Compare &cmp) noexcept |
| template<class Compare > requires (has_node_dlink_v<GT>) | |
| void | sort_nodes (Compare &&cmp=Compare()) noexcept |
| template<class Compare > requires (has_arc_dlink_v<GT>) | |
| void | sort_arcs (Compare &cmp) noexcept |
| Sort all the arcs of the graph according to a specific criteria. | |
| template<class Compare > requires (has_arc_dlink_v<GT>) | |
| void | sort_arcs (Compare &&cmp=Compare()) noexcept |
Public Attributes | |
| Flow_Type | Infinity |
| bool | with_super_source |
| True if the network has a super-source. | |
| bool | with_super_sink |
| True if the network has a super-sink. | |
Private Member Functions | |
| Flow_Type | total_source_out_flow () const |
| Return total outgoing flow from all sources. | |
| Flow_Type | total_sink_in_flow () const |
| Return total incoming flow to all sinks. | |
| Node * | register_node (Node *p) |
Insert p into source/sink sets with rollback on failure. | |
Private Attributes | |
| DynSetTree< Node * > | src_nodes |
| DynSetTree< Node * > | sink_nodes |
Friends | |
| std::ostream & | operator<< (std::ostream &s, const Path< Net_Graph > &path) |
| Stream a path with arc (cap,flow) tuples. | |
Additional Inherited Members | |
| Static Public Member Functions inherited from GraphCommon< GT, Node, Arc > | |
| template<class N1 , class N2 = N1> | |
| static void | map_nodes (N1 *p, N2 *q) noexcept |
| Map the nodes through their cookies. | |
| template<class A1 , class A2 = A1> | |
| static void | map_arcs (A1 *p, A2 *q) noexcept |
| Map the arcs through their cookies. | |
| Static Public Attributes inherited from GraphCommon< GT, Node, Arc > | |
| template<class U > | |
| static constexpr bool | has_node_dlink_v |
| Sort all the nodes of the graph according to a specific criteria. | |
| template<class U > | |
| static constexpr bool | has_arc_dlink_v |
| Protected Member Functions inherited from GraphCommon< GT, Node, Arc > | |
| void | init () noexcept |
| void | common_swap (GT &g) noexcept |
| template<class Predicate > | |
| DynList< Arc * > | collect_arcs_if (Predicate pred) const |
| Collect all arcs matching a predicate. | |
| template<class Predicate > | |
| void | remove_arcs_if (Predicate pred) |
| Remove all arcs matching a predicate. | |
| Protected Attributes inherited from GraphCommon< GT, Node, Arc > | |
| void * | cookie = nullptr |
| size_t | num_nodes = 0 |
| size_t | num_arcs = 0 |
| bool | digraph = false |
Detailed Description
struct Aleph::Net_Graph< NodeT, ArcT >
Flow network implemented with adjacency lists.
Net_Graph models a capacitated network, the main data structure for maximum-flow algorithms and related graph routines.
Template parameters:
- NodeT: node type (must derive from Net_Node).
- ArcT: arc type (must derive from Net_Arc).
Member Typedef Documentation
◆ Arc
◆ Arc_Type
| using Aleph::Net_Graph< NodeT, ArcT >::Arc_Type = typename Arc::Arc_Type |
◆ Base
| using Aleph::Net_Graph< NodeT, ArcT >::Base = Array_Graph<NodeT, ArcT> |
◆ Flow_Type
| using Aleph::Net_Graph< NodeT, ArcT >::Flow_Type = typename Arc::Flow_Type |
◆ Graph
◆ Net
◆ Node
◆ Node_Type
| using Aleph::Net_Graph< NodeT, ArcT >::Node_Type = typename Node::Node_Type |
Constructor & Destructor Documentation
◆ Net_Graph() [1/3]
|
inline |
Copy-construct a network. Throws bad_alloc on allocation failure.
Definition at line 713 of file tpl_net.H.
References GraphCommon< GT, Node, Arc >::arcs(), Aleph::copy_graph(), Aleph::maps(), and Aleph::zip().
◆ Net_Graph() [2/3]
|
inlinenoexcept |
Move-construct a network. O(1) operation.
Definition at line 745 of file tpl_net.H.
References Aleph::maps(), and Aleph::Net_Graph< NodeT, ArcT >::swap().
◆ Net_Graph() [3/3]
|
inline |
Member Function Documentation
◆ check_network()
|
inline |
Validate flow-conservation and capacity constraints.
- Returns
- true if the network is valid; false otherwise.
Definition at line 804 of file tpl_net.H.
References FunctionalMethods< Container, T >::all(), GraphCommon< GT, Node, Arc >::arcs(), Aleph::Net_Graph< NodeT, ArcT >::check_node(), Aleph::DynSetTree< Key, Tree, Compare >::is_empty(), Aleph::maps(), GraphCommon< GT, Node, Arc >::nodes(), Aleph::Net_Graph< NodeT, ArcT >::sink_nodes, Aleph::Net_Graph< NodeT, ArcT >::src_nodes, Aleph::Net_Graph< NodeT, ArcT >::total_sink_in_flow(), and Aleph::Net_Graph< NodeT, ArcT >::total_source_out_flow().
Referenced by Aleph::generic_preflow_vertex_push_maximum_flow(), Aleph::increase_flow(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().
◆ check_node()
|
inlinenoexcept |
Return true if node satisfies flow conservation constraints.
Definition at line 381 of file tpl_net.H.
References Aleph::Net_Graph< NodeT, ArcT >::get_in_flow(), Aleph::Net_Graph< NodeT, ArcT >::get_out_flow(), Aleph::Net_Graph< NodeT, ArcT >::is_connected(), Aleph::Net_Graph< NodeT, ArcT >::is_sink(), Aleph::Net_Graph< NodeT, ArcT >::is_source(), and Aleph::maps().
Referenced by Aleph::Net_Graph< NodeT, ArcT >::check_network().
◆ connect_arc()
|
inline |
Connect a previously disconnected arc.
The arc must already belong to the graph; no verification is performed. Multigraphs are supported (no check for existing arcs).
- Parameters
-
[in] arc Arc to connect.
- Returns
- Pointer to the connected arc.
Definition at line 641 of file tpl_net.H.
References Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::connect_arc(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::DynSetTree< Key, Tree, Compare >::remove(), Aleph::Net_Graph< NodeT, ArcT >::sink_nodes, and Aleph::Net_Graph< NodeT, ArcT >::src_nodes.
Referenced by TEST(), and Aleph::vertex_connectivity().
◆ disconnect_arc()
|
inlinenoexcept |
Disconnect arc arc from the graph without deleting it.
Definition at line 691 of file tpl_net.H.
References Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::disconnect_arc(), Aleph::Net_Graph< NodeT, ArcT >::get_in_degree(), Aleph::Net_Graph< NodeT, ArcT >::get_out_degree(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::DynSetTree< Key, Tree, Compare >::insert(), Aleph::Net_Graph< NodeT, ArcT >::sink_nodes, and Aleph::Net_Graph< NodeT, ArcT >::src_nodes.
Referenced by TEST(), and Aleph::vertex_connectivity().
◆ emplace_arc()
|
inline |
Construct arc info in-place and insert the arc.
Definition at line 626 of file tpl_net.H.
References Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), and Aleph::maps().
◆ emplace_node()
|
inline |
Construct a node in-place and insert it into the network.
Definition at line 578 of file tpl_net.H.
References Aleph::Net_Graph< NodeT, ArcT >::insert_node(), and Aleph::maps().
◆ flow_value()
|
inline |
Return the total flow value of the network.
Definition at line 822 of file tpl_net.H.
References ah_domain_error_if, Aleph::DynSetTree< Key, Tree, Compare >::is_empty(), Aleph::maps(), Aleph::Net_Graph< NodeT, ArcT >::sink_nodes, Aleph::Net_Graph< NodeT, ArcT >::src_nodes, Aleph::Net_Graph< NodeT, ArcT >::total_sink_in_flow(), and Aleph::Net_Graph< NodeT, ArcT >::total_source_out_flow().
Referenced by Aleph::compute_flow_statistics(), Aleph::generic_preflow_vertex_push_maximum_flow(), Aleph::min_cut(), and print_flow_stats().
◆ get_cap()
◆ get_flow()
◆ get_in_cap()
|
inlinenoexcept |
Return total incoming capacity of node.
Definition at line 315 of file tpl_net.H.
References Aleph::Digraph_Iterator< GT, Filter >::has_curr(), and Aleph::sum().
Referenced by Aleph::Net_Graph< NodeT, ArcT >::make_super_sink().
◆ get_in_degree()
|
inlinenoexcept |
Return the in-degree of p (number of incoming arcs).
Definition at line 333 of file tpl_net.H.
References GraphCommon< GT, Node, Arc >::in_degree().
Referenced by Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::compute_aux_net(), Aleph::Net_Graph< NodeT, ArcT >::disconnect_arc(), Aleph::Net_Graph< NodeT, ArcT >::is_connected(), Aleph::Net_Graph< NodeT, ArcT >::remove_arc(), Aleph::solve_circulation(), and TEST().
◆ get_in_flow()
|
inlinenoexcept |
Return total incoming flow of node.
Definition at line 354 of file tpl_net.H.
References Aleph::Digraph_Iterator< GT, Filter >::has_curr(), and Aleph::sum().
Referenced by Aleph::Net_Graph< NodeT, ArcT >::check_node(), Aleph::generic_preflow_vertex_push_maximum_flow(), Aleph::is_node_active(), Aleph::preflow_create_residual_net(), and Aleph::Net_Graph< NodeT, ArcT >::total_sink_in_flow().
◆ get_out_cap()
|
inlinenoexcept |
Return total outgoing capacity of node.
Definition at line 324 of file tpl_net.H.
References Aleph::Digraph_Iterator< GT, Filter >::has_curr(), and Aleph::sum().
Referenced by Aleph::Net_Graph< NodeT, ArcT >::make_super_source().
◆ get_out_degree()
|
inlinenoexcept |
Return the out-degree of p (number of outgoing arcs).
Definition at line 339 of file tpl_net.H.
References GraphCommon< GT, Node, Arc >::out_degree().
Referenced by Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::compute_aux_net(), Aleph::Net_Graph< NodeT, ArcT >::disconnect_arc(), Aleph::Net_Graph< NodeT, ArcT >::is_connected(), Aleph::Net_Graph< NodeT, ArcT >::remove_arc(), Aleph::solve_circulation(), and TEST().
◆ get_out_flow()
|
inlinenoexcept |
Return total outgoing flow of node.
Definition at line 345 of file tpl_net.H.
References Aleph::Digraph_Iterator< GT, Filter >::has_curr(), and Aleph::sum().
Referenced by Aleph::aumenting_path_maximum_flow(), Aleph::Net_Graph< NodeT, ArcT >::check_node(), demo_compare_algorithms_on_logistics(), demo_mincost_maxflow(), Aleph::generic_preflow_vertex_push_maximum_flow(), Aleph::is_node_active(), Aleph::preflow_create_residual_net(), and Aleph::Net_Graph< NodeT, ArcT >::total_source_out_flow().
◆ get_sink()
|
inline |
Return an arbitrary sink node.
Definition at line 551 of file tpl_net.H.
References Aleph::DynSetTree< Key, Tree, Compare >::get_item(), and Aleph::Net_Graph< NodeT, ArcT >::sink_nodes.
Referenced by Aleph::capacity_scaling_maximum_flow(), compute_min_cut_capacity(), Aleph::decompose_flow(), Aleph::dinic_maximum_flow(), Aleph::export_network_to_dimacs(), Aleph::export_network_to_dot(), Aleph::export_network_to_json(), Aleph::Find_Aumenting_Path< Net, Q >::find_aum_path(), Aleph::find_aumenting_path(), Aleph::Find_Aumenting_Path< Net, Q >::find_dec_path(), Aleph::generic_preflow_vertex_push_maximum_flow(), Aleph::hlpp_maximum_flow(), Aleph::init_height_in_nodes(), Aleph::network_to_dot_string(), Aleph::network_to_json_string(), Aleph::preflow_create_residual_net(), print_network(), Aleph::successive_shortest_paths(), TEST(), and TEST().
◆ get_sink_nodes()
|
inlinenoexcept |
Return the set of sink nodes.
Definition at line 450 of file tpl_net.H.
References Aleph::Net_Graph< NodeT, ArcT >::sink_nodes.
◆ get_source()
|
inline |
Return an arbitrary source node.
Definition at line 548 of file tpl_net.H.
References Aleph::DynSetTree< Key, Tree, Compare >::get_item(), and Aleph::Net_Graph< NodeT, ArcT >::src_nodes.
Referenced by Aleph::aumenting_path_maximum_flow(), Aleph::build_residual_net(), Aleph::Network_Simplex< Net >::build_spanning_tree(), Aleph::capacity_scaling_maximum_flow(), compute_min_cut_capacity(), Aleph::decompose_flow(), demo_compare_algorithms_on_logistics(), demo_mincost_maxflow(), demonstrate_flow_decomposition(), Aleph::dinic_maximum_flow(), Aleph::export_network_to_dimacs(), Aleph::export_network_to_dot(), Aleph::export_network_to_json(), Aleph::Find_Aumenting_Path< Net, Q >::find_aum_path(), Aleph::find_aumenting_path(), Aleph::Find_Aumenting_Path< Net, Q >::find_dec_path(), Aleph::generic_preflow_vertex_push_maximum_flow(), Aleph::hlpp_maximum_flow(), Aleph::min_cut(), Aleph::network_to_dot_string(), Aleph::network_to_json_string(), Aleph::preflow_create_residual_net(), print_network(), Aleph::successive_shortest_paths(), TEST(), and TEST().
◆ get_src_nodes()
|
inlinenoexcept |
Return the set of source nodes.
Definition at line 447 of file tpl_net.H.
References Aleph::Net_Graph< NodeT, ArcT >::src_nodes.
Referenced by TEST().
◆ in_arcs()
Return arcs incoming to p (as a DynList).
Definition at line 302 of file tpl_net.H.
References Aleph::maps().
◆ in_nodes()
Return nodes that can reach p through incoming arcs.
Definition at line 308 of file tpl_net.H.
References Aleph::maps().
◆ insert_arc() [1/3]
|
inline |
Insert an arc with capacity cap and zero flow.
Definition at line 655 of file tpl_net.H.
References Aleph::Net_Graph< NodeT, ArcT >::insert_arc().
◆ insert_arc() [2/3]
|
inline |
Insert a capacitated arc with an initial flow.
- Parameters
-
[in] src_node Source node. [in] tgt_node Target node. [in] cap Capacity value. [in] flow Flow value. [in] arc_info Arc info to store.
- Returns
- Pointer to the inserted arc.
- Exceptions
-
bad_alloc If there is not enough memory. overflow_error If flowexceedscap.
Definition at line 607 of file tpl_net.H.
References ah_overflow_error_if, Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::insert_arc(), Aleph::maps(), Aleph::DynSetTree< Key, Tree, Compare >::remove(), Aleph::Net_Graph< NodeT, ArcT >::sink_nodes, and Aleph::Net_Graph< NodeT, ArcT >::src_nodes.
Referenced by add_super_source_and_sink(), build_antiparallel_network(), build_datacenter_network(), build_grid_network(), build_supply_chain(), build_water_network(), Aleph::check_baseball_elimination(), Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::compute_aux_net(), Aleph::Net_Cap_Graph< NodeT, ArcT >::compute_aux_net(), Aleph::compute_min_cut(), demo_dot_export(), demonstrate_bipartite_matching(), Aleph::design_survey(), Aleph::edge_connectivity(), Aleph::Net_Cost_Graph< NodeT, ArcT >::emplace_arc(), Aleph::Net_Graph< NodeT, ArcT >::emplace_arc(), Aleph::generate_bipartite_network(), Aleph::generate_grid_network(), Aleph::generate_layered_network(), Aleph::generate_random_network(), Aleph::import_network_from_dimacs(), Aleph::Testing::RandomNetworkGenerator< Net >::insert_arc(), Aleph::Net_Cost_Graph< NodeT, ArcT >::insert_arc(), Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), Aleph::Net_Cost_Graph< NodeT, ArcT >::insert_arc(), Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), Aleph::Net_Graph< NodeT, ArcT >::make_super_sink(), Aleph::Net_Graph< NodeT, ArcT >::make_super_source(), Aleph::segment_image(), AuxNetTest::SetUp(), Aleph::solve_assignment(), Aleph::solve_circulation(), Aleph::solve_project_selection(), Aleph::solve_transportation(), Aleph::solve_transshipment(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), 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(), 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(), and Aleph::vertex_connectivity().
◆ insert_arc() [3/3]
|
inline |
Insert an arc with zero capacity and flow.
This overload is disabled when Arc_Type equals Flow_Type to avoid a signature clash with the capacity-only overload. It is also disabled for arithmetic types to ensure that integer literals match the capacity overload instead.
Definition at line 670 of file tpl_net.H.
References Aleph::Net_Graph< NodeT, ArcT >::insert_arc().
◆ insert_node() [1/7]
|
inline |
Insert a new node with default info.
Definition at line 565 of file tpl_net.H.
References Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::insert_node(), and Aleph::Net_Graph< NodeT, ArcT >::register_node().
Referenced by Aleph::Net_Graph< NodeT, ArcT >::emplace_node(), Aleph::Net_Cap_Graph< NodeT, ArcT >::insert_node(), Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::insert_node(), Aleph::Net_Cap_Graph< NodeT, ArcT >::insert_node(), Aleph::Net_Graph< NodeT, ArcT >::make_super_sink(), and Aleph::Net_Graph< NodeT, ArcT >::make_super_source().
◆ insert_node() [2/7]
Allocate a new node, set by copy its data content and insert it into the graph.
This method perform several actions. First, it allocates memory for a graph node. Then the data node_info is copied to the data associated to the node. This copy is done via the copy constructor and assign operator. So, these functionalities must be present for the class Node_Type. Finally, the node is topologically inserted into the graph.
- Remarks
- If this method does not throw exception, then this always returns a valid pointer,
- Parameters
-
[in] node_info info to copy to the new node. The copy constructor and the assign operator must be defined for the class Node_Type.
- Returns
- a pointer to the new inserted node.
- Exceptions
-
bad_allod if there is no enough memory
Definition at line 288 of file graph-dry.H.
◆ insert_node() [3/7]
Insert a new node by copying node_info.
- Parameters
-
[in] node_info Info to copy into the node.
- Returns
- Pointer to the inserted node.
- Exceptions
-
bad_alloc If there is not enough memory.
Definition at line 559 of file tpl_net.H.
References Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::insert_node(), and Aleph::Net_Graph< NodeT, ArcT >::register_node().
Referenced by add_super_source_and_sink(), build_antiparallel_network(), build_datacenter_network(), build_grid_network(), build_simple_network(), build_supply_chain(), build_water_network(), Aleph::check_baseball_elimination(), Aleph::Net_Cap_Graph< NodeT, ArcT >::compute_aux_net(), Aleph::compute_min_cut(), demo_dot_export(), demonstrate_bipartite_matching(), Aleph::design_survey(), Aleph::edge_connectivity(), Aleph::Testing::ErdosRenyiGenerator< Net >::generate(), Aleph::Testing::LayeredNetworkGenerator< Net >::generate(), Aleph::Testing::GridNetworkGenerator< Net >::generate(), Aleph::Testing::BipartiteNetworkGenerator< Net >::generate(), Aleph::generate_bipartite_network(), Aleph::generate_grid_network(), Aleph::generate_layered_network(), Aleph::generate_random_network(), Aleph::import_network_from_dimacs(), Aleph::segment_image(), Aleph::solve_assignment(), Aleph::solve_circulation(), Aleph::solve_project_selection(), Aleph::solve_transportation(), Aleph::solve_transshipment(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), 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(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and Aleph::vertex_connectivity().
◆ insert_node() [4/7]
|
inline |
Definition at line 393 of file tpl_agraph.H.
◆ insert_node() [5/7]
|
inline |
Insert a node by copying another node.
- Parameters
-
[in] p Node to copy.
- Returns
- Pointer to the inserted node.
- Exceptions
-
bad_alloc If there is not enough memory.
Definition at line 590 of file tpl_net.H.
References Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::insert_node(), and Aleph::Net_Graph< NodeT, ArcT >::register_node().
◆ insert_node() [6/7]
|
inline |
Insert a new node by moving info.
Definition at line 571 of file tpl_net.H.
References Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::insert_node(), Aleph::maps(), and Aleph::Net_Graph< NodeT, ArcT >::register_node().
◆ insert_node() [7/7]
Allocate a new node, set by moving its data content and insert it into the graph.
This method perform several actions. First, it allocates memory for a graph node. Then the data node_info is moved to the data associated to the node. This movement is done via the move constructor and move assign operator. So, these functionalities must be present for the class Node_Type. Finally, the node is topologically inserted into the graph.
- Remarks
- If this method does not throw exception, then this always returns a valid pointer,
- Parameters
-
[in] node_info info to move to the new node. The move constructor and the move assign operator must be defined for the class Node_Type.
- Returns
- a pointer to the new inserted node.
- Exceptions
-
bad_allod if there is no enough memory.
Definition at line 288 of file graph-dry.H.
◆ is_connected()
|
inlinenoexcept |
Return true if p is connected (used for validation).
Definition at line 375 of file tpl_net.H.
References Aleph::Net_Graph< NodeT, ArcT >::get_in_degree(), Aleph::Net_Graph< NodeT, ArcT >::get_out_degree(), and Aleph::maps().
Referenced by Aleph::Net_Graph< NodeT, ArcT >::check_node().
◆ is_single_sink()
|
inlineconstexprnoexcept |
Return true if the network has a single sink.
Definition at line 372 of file tpl_net.H.
References Aleph::Net_Graph< NodeT, ArcT >::sink_nodes, and Aleph::DynSetTree< Key, Tree, Compare >::size().
Referenced by Aleph::aumenting_path_maximum_flow(), Aleph::build_residual_net(), Aleph::capacity_scaling_maximum_flow(), Aleph::decompose_flow(), Aleph::dinic_maximum_flow(), Aleph::export_network_to_dimacs(), Aleph::export_network_to_dot(), Aleph::export_network_to_json(), Aleph::generic_preflow_vertex_push_maximum_flow(), Aleph::hlpp_maximum_flow(), Aleph::network_to_dot_string(), Aleph::network_to_json_string(), Aleph::Network_Simplex< Net >::run(), Aleph::successive_shortest_paths(), TEST(), TEST(), TEST(), TEST(), and TEST().
◆ is_single_source()
|
inlineconstexprnoexcept |
Return true if the network has a single source.
Definition at line 369 of file tpl_net.H.
References Aleph::DynSetTree< Key, Tree, Compare >::size(), and Aleph::Net_Graph< NodeT, ArcT >::src_nodes.
Referenced by Aleph::aumenting_path_maximum_flow(), Aleph::build_residual_net(), Aleph::capacity_scaling_maximum_flow(), Aleph::compute_flow_statistics(), Aleph::decompose_flow(), Aleph::dinic_maximum_flow(), Aleph::export_network_to_dimacs(), Aleph::export_network_to_dot(), Aleph::export_network_to_json(), Aleph::generic_preflow_vertex_push_maximum_flow(), Aleph::hlpp_maximum_flow(), Aleph::network_to_dot_string(), Aleph::network_to_json_string(), Aleph::Network_Simplex< Net >::run(), Aleph::successive_shortest_paths(), TEST(), TEST(), TEST(), TEST(), and TEST().
◆ is_sink()
|
inlinenoexcept |
Return true if node is a sink.
Definition at line 366 of file tpl_net.H.
References Aleph::DynSetTree< Key, Tree, Compare >::contains(), and Aleph::Net_Graph< NodeT, ArcT >::sink_nodes.
Referenced by Aleph::Net_Graph< NodeT, ArcT >::check_node(), demonstrate_bipartite_matching(), print_network(), TEST(), TEST(), and verify_flow_conservation().
◆ is_source()
|
inlinenoexcept |
Return true if node is a source.
Definition at line 363 of file tpl_net.H.
References Aleph::DynSetTree< Key, Tree, Compare >::contains(), and Aleph::Net_Graph< NodeT, ArcT >::src_nodes.
Referenced by Aleph::Net_Graph< NodeT, ArcT >::check_node(), demonstrate_bipartite_matching(), print_cost_network(), print_network(), TEST(), TEST(), and verify_flow_conservation().
◆ make_super_nodes()
|
inline |
Convert a multi-source/multi-sink network into super-source/super-sink.
Definition at line 526 of file tpl_net.H.
References Aleph::Net_Graph< NodeT, ArcT >::make_super_sink(), Aleph::Net_Graph< NodeT, ArcT >::make_super_source(), and Aleph::Net_Graph< NodeT, ArcT >::unmake_super_source().
◆ make_super_sink()
|
inline |
Convert a multi-sink network into a single super-sink network.
Throws if there is no sink node or on allocation failure.
Definition at line 493 of file tpl_net.H.
References ah_domain_error_if, Aleph::DynList< T >::append(), Aleph::Net_Graph< NodeT, ArcT >::get_in_cap(), Aleph::HTList::Iterator::has_curr(), Aleph::BinNodeInfixIterator< Node >::has_curr(), Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), Aleph::Net_Graph< NodeT, ArcT >::insert_node(), Aleph::maps(), Aleph::Net_Graph< NodeT, ArcT >::sink_nodes, Aleph::DynSetTree< Key, Tree, Compare >::size(), and Aleph::Net_Graph< NodeT, ArcT >::with_super_sink.
Referenced by Aleph::check_baseball_elimination(), Aleph::design_survey(), Aleph::Net_Graph< NodeT, ArcT >::make_super_nodes(), Aleph::segment_image(), TEST(), TEST(), TEST(), TEST(), and TEST().
◆ make_super_source()
|
inline |
Convert a multi-source network into a single super-source network.
Throws if there is no source node or on allocation failure.
Definition at line 458 of file tpl_net.H.
References ah_domain_error_if, Aleph::DynList< T >::append(), Aleph::Net_Graph< NodeT, ArcT >::get_out_cap(), Aleph::HTList::Iterator::has_curr(), Aleph::BinNodeInfixIterator< Node >::has_curr(), Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), Aleph::Net_Graph< NodeT, ArcT >::insert_node(), Aleph::maps(), Aleph::DynSetTree< Key, Tree, Compare >::size(), Aleph::Net_Graph< NodeT, ArcT >::src_nodes, and Aleph::Net_Graph< NodeT, ArcT >::with_super_source.
Referenced by Aleph::check_baseball_elimination(), Aleph::design_survey(), Aleph::Net_Graph< NodeT, ArcT >::make_super_nodes(), Aleph::segment_image(), TEST(), TEST(), TEST(), TEST(), and TEST().
◆ operator=() [1/2]
|
inline |
Copy-assign a network. Throws bad_alloc on allocation failure.
Definition at line 761 of file tpl_net.H.
References Aleph::maps(), and Aleph::Net_Graph< NodeT, ArcT >::swap().
◆ operator=() [2/2]
|
inlinenoexcept |
Move-assign a network. O(1) operation.
Definition at line 753 of file tpl_net.H.
References Aleph::maps(), and Aleph::Net_Graph< NodeT, ArcT >::swap().
Referenced by Aleph::Net_Cap_Graph< NodeT, ArcT >::operator=(), and Aleph::Net_Cap_Graph< NodeT, ArcT >::operator=().
◆ out_arcs()
Return arcs outgoing from p (as a DynList).
Definition at line 289 of file tpl_net.H.
References Aleph::maps().
◆ out_nodes()
Return nodes reachable from p through outgoing arcs.
Definition at line 295 of file tpl_net.H.
References Aleph::maps().
◆ register_node()
|
inlineprivate |
Insert p into source/sink sets with rollback on failure.
Definition at line 428 of file tpl_net.H.
References Aleph::DynSetTree< Key, Tree, Compare >::insert(), Aleph::DynSetTree< Key, Tree, Compare >::remove(), Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::remove_node(), Aleph::Net_Graph< NodeT, ArcT >::sink_nodes, and Aleph::Net_Graph< NodeT, ArcT >::src_nodes.
Referenced by Aleph::Net_Graph< NodeT, ArcT >::insert_node(), Aleph::Net_Graph< NodeT, ArcT >::insert_node(), Aleph::Net_Graph< NodeT, ArcT >::insert_node(), and Aleph::Net_Graph< NodeT, ArcT >::insert_node().
◆ remove_arc()
|
inlineoverride |
Remove arc arc from the network.
Definition at line 677 of file tpl_net.H.
References Aleph::Net_Graph< NodeT, ArcT >::get_in_degree(), Aleph::Net_Graph< NodeT, ArcT >::get_out_degree(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::DynSetTree< Key, Tree, Compare >::insert(), Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::remove_arc(), Aleph::Net_Graph< NodeT, ArcT >::sink_nodes, and Aleph::Net_Graph< NodeT, ArcT >::src_nodes.
Referenced by Aleph::solve_circulation(), and TEST().
◆ remove_node()
|
inlineoverridenoexcept |
Remove node p and all its arcs from the network.
Definition at line 705 of file tpl_net.H.
References Aleph::DynSetTree< Key, Tree, Compare >::remove(), Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::remove_node(), Aleph::Net_Graph< NodeT, ArcT >::sink_nodes, and Aleph::Net_Graph< NodeT, ArcT >::src_nodes.
Referenced by Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::compute_aux_net(), Aleph::compute_min_cut(), Aleph::edge_connectivity(), Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::free_aux_net(), Aleph::solve_circulation(), Aleph::Net_Graph< NodeT, ArcT >::unmake_super_sink(), and Aleph::Net_Graph< NodeT, ArcT >::unmake_super_source().
◆ reset()
|
inline |
Reset all arc flows to zero.
Definition at line 794 of file tpl_net.H.
Referenced by Aleph::compute_min_cut(), Aleph::edge_connectivity(), Random_Network_Flow< Net >::operator()(), and Aleph::vertex_connectivity().
◆ set_cap()
Set the capacity of an arc.
Definition at line 772 of file tpl_net.H.
References ah_out_of_range_error_if, and Aleph::maps().
◆ set_flow()
Set the flow of an arc. Throws if flow exceeds capacity.
Definition at line 780 of file tpl_net.H.
References ah_out_of_range_error_if.
Referenced by TEST_F().
◆ swap()
Swap contents with another network. O(1) operation.
Definition at line 732 of file tpl_net.H.
References GraphCommon< GT, Node, Arc >::common_swap(), Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::get_arc_dlink(), Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::get_node_dlink(), Aleph::Net_Graph< NodeT, ArcT >::Infinity, Aleph::maps(), Aleph::Net_Graph< NodeT, ArcT >::sink_nodes, Aleph::Net_Graph< NodeT, ArcT >::src_nodes, Aleph::Dlink::swap(), Aleph::DynSetTree< Key, Tree, Compare >::swap(), Aleph::Net_Graph< NodeT, ArcT >::with_super_sink, and Aleph::Net_Graph< NodeT, ArcT >::with_super_source.
Referenced by Aleph::Net_Graph< NodeT, ArcT >::Net_Graph(), Aleph::Net_Cost_Graph< NodeT, ArcT >::operator=(), Aleph::Net_Graph< NodeT, ArcT >::operator=(), and Aleph::Net_Graph< NodeT, ArcT >::operator=().
◆ total_sink_in_flow()
|
inlineprivate |
Return total incoming flow to all sinks.
Definition at line 418 of file tpl_net.H.
References Aleph::Net_Graph< NodeT, ArcT >::get_in_flow(), Aleph::BinNodeInfixIterator< Node >::has_curr(), Aleph::Net_Graph< NodeT, ArcT >::sink_nodes, and Aleph::sum().
Referenced by Aleph::Net_Graph< NodeT, ArcT >::check_network(), and Aleph::Net_Graph< NodeT, ArcT >::flow_value().
◆ total_source_out_flow()
|
inlineprivate |
Return total outgoing flow from all sources.
Definition at line 408 of file tpl_net.H.
References Aleph::Net_Graph< NodeT, ArcT >::get_out_flow(), Aleph::BinNodeInfixIterator< Node >::has_curr(), Aleph::Net_Graph< NodeT, ArcT >::src_nodes, and Aleph::sum().
Referenced by Aleph::Net_Graph< NodeT, ArcT >::check_network(), and Aleph::Net_Graph< NodeT, ArcT >::flow_value().
◆ unmake_super_nodes()
|
inline |
Restore a super-source/super-sink network to its original form.
Definition at line 541 of file tpl_net.H.
References Aleph::Net_Graph< NodeT, ArcT >::unmake_super_sink(), and Aleph::Net_Graph< NodeT, ArcT >::unmake_super_source().
◆ unmake_super_sink()
|
inlinenoexcept |
Restore a super-sink network to its original multi-sink form.
Definition at line 514 of file tpl_net.H.
References Aleph::DynSetTree< Key, Tree, Compare >::get_item(), Aleph::maps(), Aleph::Net_Graph< NodeT, ArcT >::remove_node(), Aleph::Net_Graph< NodeT, ArcT >::sink_nodes, Aleph::DynSetTree< Key, Tree, Compare >::size(), and Aleph::Net_Graph< NodeT, ArcT >::with_super_sink.
Referenced by TEST(), and Aleph::Net_Graph< NodeT, ArcT >::unmake_super_nodes().
◆ unmake_super_source()
|
inlinenoexcept |
Restore a super-source network to its original multi-source form.
Definition at line 480 of file tpl_net.H.
References Aleph::DynSetTree< Key, Tree, Compare >::get_item(), Aleph::maps(), Aleph::Net_Graph< NodeT, ArcT >::remove_node(), Aleph::DynSetTree< Key, Tree, Compare >::size(), Aleph::Net_Graph< NodeT, ArcT >::src_nodes, and Aleph::Net_Graph< NodeT, ArcT >::with_super_source.
Referenced by Aleph::Net_Graph< NodeT, ArcT >::make_super_nodes(), TEST(), and Aleph::Net_Graph< NodeT, ArcT >::unmake_super_nodes().
Friends And Related Symbol Documentation
◆ operator<<
Member Data Documentation
◆ Infinity
|
mutable |
Definition at line 286 of file tpl_net.H.
Referenced by Aleph::increase_flow(), and Aleph::Net_Graph< NodeT, ArcT >::swap().
◆ sink_nodes
|
private |
Definition at line 405 of file tpl_net.H.
Referenced by Aleph::Net_Graph< NodeT, ArcT >::check_network(), Aleph::Net_Graph< NodeT, ArcT >::connect_arc(), Aleph::Net_Graph< NodeT, ArcT >::disconnect_arc(), Aleph::Net_Graph< NodeT, ArcT >::flow_value(), Aleph::Net_Graph< NodeT, ArcT >::get_sink(), Aleph::Net_Graph< NodeT, ArcT >::get_sink_nodes(), Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), Aleph::Net_Graph< NodeT, ArcT >::is_single_sink(), Aleph::Net_Graph< NodeT, ArcT >::is_sink(), Aleph::Net_Graph< NodeT, ArcT >::make_super_sink(), Aleph::Net_Graph< NodeT, ArcT >::register_node(), Aleph::Net_Graph< NodeT, ArcT >::remove_arc(), Aleph::Net_Graph< NodeT, ArcT >::remove_node(), Aleph::Net_Graph< NodeT, ArcT >::swap(), Aleph::Net_Graph< NodeT, ArcT >::total_sink_in_flow(), and Aleph::Net_Graph< NodeT, ArcT >::unmake_super_sink().
◆ src_nodes
|
private |
Definition at line 404 of file tpl_net.H.
Referenced by Aleph::Net_Graph< NodeT, ArcT >::check_network(), Aleph::Net_Graph< NodeT, ArcT >::connect_arc(), Aleph::Net_Graph< NodeT, ArcT >::disconnect_arc(), Aleph::Net_Graph< NodeT, ArcT >::flow_value(), Aleph::Net_Graph< NodeT, ArcT >::get_source(), Aleph::Net_Graph< NodeT, ArcT >::get_src_nodes(), Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), Aleph::Net_Graph< NodeT, ArcT >::is_single_source(), Aleph::Net_Graph< NodeT, ArcT >::is_source(), Aleph::Net_Graph< NodeT, ArcT >::make_super_source(), Aleph::Net_Graph< NodeT, ArcT >::register_node(), Aleph::Net_Graph< NodeT, ArcT >::remove_arc(), Aleph::Net_Graph< NodeT, ArcT >::remove_node(), Aleph::Net_Graph< NodeT, ArcT >::swap(), Aleph::Net_Graph< NodeT, ArcT >::total_source_out_flow(), and Aleph::Net_Graph< NodeT, ArcT >::unmake_super_source().
◆ with_super_sink
| bool Aleph::Net_Graph< NodeT, ArcT >::with_super_sink |
True if the network has a super-sink.
Definition at line 839 of file tpl_net.H.
Referenced by Aleph::Net_Graph< NodeT, ArcT >::make_super_sink(), Aleph::Net_Graph< NodeT, ArcT >::swap(), and Aleph::Net_Graph< NodeT, ArcT >::unmake_super_sink().
◆ with_super_source
| bool Aleph::Net_Graph< NodeT, ArcT >::with_super_source |
True if the network has a super-source.
Definition at line 836 of file tpl_net.H.
Referenced by Aleph::Net_Graph< NodeT, ArcT >::make_super_source(), Aleph::Net_Graph< NodeT, ArcT >::swap(), and Aleph::Net_Graph< NodeT, ArcT >::unmake_super_source().
The documentation for this struct was generated from the following file:
