Capacitated flow network with costs associated to arcs. More...

#include <tpl_netcost.H>

Inheritance diagram for Aleph::Net_Cost_Graph< NodeT, ArcT >:

Collaboration diagram for Aleph::Net_Cost_Graph< NodeT, ArcT >:

Public Types
using	Base = Net_Graph< NodeT, ArcT >

using	Net = Net_Graph< NodeT, ArcT >
	The underlying flow network type.

using	Net_MFMC = Net_Cost_Graph< NodeT, ArcT >
	Self type alias.

using	Arc = ArcT
	Arc type.

using	Node = NodeT
	Node type.

using	Flow_Type = typename Arc::Flow_Type
	Type representing capacity, flow, and cost values.

using	Node_Type = typename Node::Node_Type
	Type of attribute stored in a node.

using	Arc_Type = typename Arc::Arc_Type
	Type of attribute stored in an arc.

Public Types inherited from Aleph::Net_Graph< NodeT, ArcT >
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
	Net_Cost_Graph ()=default
	Default constructor.

	Net_Cost_Graph (const Net_Cost_Graph &net)
	Copy constructor.

	Net_Cost_Graph (Net_Cost_Graph &&)=default
	Move constructor.

Net_Cost_Graph &	operator= (const Net_Cost_Graph &net)
	Copy assignment operator (uses copy-and-swap idiom).

Net_Cost_Graph &	operator= (Net_Cost_Graph &&)=default
	Move assignment operator.

Flow_Type &	get_cost (Arc *a) noexcept
	Return a modifiable reference to the cost of an arc.

Flow_Type	get_cost (Arc *a) const noexcept
	Return the cost of an arc (const version).

virtual Arc *	insert_arc (Node src_node, Node tgt_node, const Flow_Type &cap, const Flow_Type &__cost)
	Create and insert an arc in a flow network with costs.

template<typename... Args>
Arc *	emplace_arc (Node src_node, Node tgt_node, const Flow_Type &cap, const Flow_Type &__cost, Args &&... args)
	Create and insert an arc with arc info using perfect forwarding.

virtual Arc *	insert_arc (Node src_node, Node tgt_node)
	Insert arc (internal use only).

Flow_Type	flow_cost () const
	Compute the total cost of flow circulating through the network.

auto	out_pars (Node *p)
	Compute outgoing flow parameters for a node.

auto	in_pars (Node *p)
	Compute incoming flow parameters for a node.

Public Member Functions inherited from Aleph::Net_Graph< NodeT, ArcT >
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

Static Public Member Functions
static Flow_Type	arc_flow_cost (Arc *a) noexcept
	Compute the cost of the flow through an arc.

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.

Additional Inherited Members
Public Attributes inherited from Aleph::Net_Graph< NodeT, ArcT >
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.

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

template<class NodeT = Net_Cost_Node<Empty_Class>, class ArcT = Net_Cost_Arc<Empty_Class, double>>
struct Aleph::Net_Cost_Graph< NodeT, ArcT >

Capacitated flow network with costs associated to arcs.

This type, derived from Net_Graph, models a capacitated network where each arc has an associated cost per unit of flow. This model, extending the capacitated network concept, considerably expands the range of combinatorial optimization problems by posing a max-min optimization. In this case, maximum flow at minimum cost.

Being a derivation of Net_Graph, its interface is very similar, with the addition of parameters and methods to handle the cost of each arc.

Template Parameters

NodeT	Node type (should be Net_Cost_Node or compatible).
ArcT	Arc type (should be Net_Cost_Arc or compatible).

See also: max_flow_min_cost_by_cycle_canceling Max_Flow_Min_Cost_By_Cycle_Canceling

Definition at line 146 of file tpl_netcost.H.

Member Typedef Documentation

◆ Arc

template<class NodeT = Net_Cost_Node<Empty_Class>, class ArcT = Net_Cost_Arc<Empty_Class, double>>

using Aleph::Net_Cost_Graph< NodeT, ArcT >::Arc = ArcT

Arc type.

Definition at line 157 of file tpl_netcost.H.

◆ Arc_Type

template<class NodeT = Net_Cost_Node<Empty_Class>, class ArcT = Net_Cost_Arc<Empty_Class, double>>

using Aleph::Net_Cost_Graph< NodeT, ArcT >::Arc_Type = typename Arc::Arc_Type

Type of attribute stored in an arc.

Definition at line 169 of file tpl_netcost.H.

◆ Base

template<class NodeT = Net_Cost_Node<Empty_Class>, class ArcT = Net_Cost_Arc<Empty_Class, double>>

using Aleph::Net_Cost_Graph< NodeT, ArcT >::Base = Net_Graph<NodeT, ArcT>

Definition at line 148 of file tpl_netcost.H.

◆ Flow_Type

template<class NodeT = Net_Cost_Node<Empty_Class>, class ArcT = Net_Cost_Arc<Empty_Class, double>>

using Aleph::Net_Cost_Graph< NodeT, ArcT >::Flow_Type = typename Arc::Flow_Type

Type representing capacity, flow, and cost values.

Definition at line 163 of file tpl_netcost.H.

◆ Net

template<class NodeT = Net_Cost_Node<Empty_Class>, class ArcT = Net_Cost_Arc<Empty_Class, double>>

using Aleph::Net_Cost_Graph< NodeT, ArcT >::Net = Net_Graph<NodeT, ArcT>

The underlying flow network type.

Definition at line 151 of file tpl_netcost.H.

◆ Net_MFMC

template<class NodeT = Net_Cost_Node<Empty_Class>, class ArcT = Net_Cost_Arc<Empty_Class, double>>

using Aleph::Net_Cost_Graph< NodeT, ArcT >::Net_MFMC = Net_Cost_Graph<NodeT, ArcT>

Self type alias.

Definition at line 154 of file tpl_netcost.H.

◆ Node

template<class NodeT = Net_Cost_Node<Empty_Class>, class ArcT = Net_Cost_Arc<Empty_Class, double>>

using Aleph::Net_Cost_Graph< NodeT, ArcT >::Node = NodeT

Node type.

Definition at line 160 of file tpl_netcost.H.

◆ Node_Type

template<class NodeT = Net_Cost_Node<Empty_Class>, class ArcT = Net_Cost_Arc<Empty_Class, double>>

using Aleph::Net_Cost_Graph< NodeT, ArcT >::Node_Type = typename Node::Node_Type

Type of attribute stored in a node.

Definition at line 166 of file tpl_netcost.H.

Constructor & Destructor Documentation

◆ Net_Cost_Graph() [1/3]

template<class NodeT = Net_Cost_Node<Empty_Class>, class ArcT = Net_Cost_Arc<Empty_Class, double>>

Aleph::Net_Cost_Graph< NodeT, ArcT >::Net_Cost_Graph ( )

default

Default constructor.

◆ Net_Cost_Graph() [2/3]

template<class NodeT = Net_Cost_Node<Empty_Class>, class ArcT = Net_Cost_Arc<Empty_Class, double>>

Aleph::Net_Cost_Graph< NodeT, ArcT >::Net_Cost_Graph ( const Net_Cost_Graph< NodeT, ArcT > & net )

inline

Copy constructor.

Creates a deep copy of the network, including all nodes, arcs, and their cost values.

Parameters

[in] net Network to copy.

Definition at line 181 of file tpl_netcost.H.

References GraphCommon< GT, Node, Arc >::arcs(), Aleph::maps(), and Aleph::zip().

◆ Net_Cost_Graph() [3/3]

template<class NodeT = Net_Cost_Node<Empty_Class>, class ArcT = Net_Cost_Arc<Empty_Class, double>>

Aleph::Net_Cost_Graph< NodeT, ArcT >::Net_Cost_Graph ( Net_Cost_Graph< NodeT, ArcT > && )

default

Move constructor.

Member Function Documentation

◆ arc_flow_cost()

template<class NodeT = Net_Cost_Node<Empty_Class>, class ArcT = Net_Cost_Arc<Empty_Class, double>>

static Flow_Type Aleph::Net_Cost_Graph< NodeT, ArcT >::arc_flow_cost ( Arc * a )

inlinestaticnoexcept

Compute the cost of the flow through an arc.

Parameters

[in] a Pointer to the arc.

Returns: The product of flow and cost for this arc.

Definition at line 226 of file tpl_netcost.H.

◆ emplace_arc()

template<class NodeT = Net_Cost_Node<Empty_Class>, class ArcT = Net_Cost_Arc<Empty_Class, double>>

template<typename... Args>

Arc * Aleph::Net_Cost_Graph< NodeT, ArcT >::emplace_arc	(	Node *	src_node,
		Node *	tgt_node,
		const Flow_Type &	cap,
		const Flow_Type &	__cost,
		Args &&...	args
	)

inline

Create and insert an arc with arc info using perfect forwarding.

Template Parameters

Args	Types of arguments to forward to Arc_Type constructor.

Parameters

[in]	src_node	Source node.
[in]	tgt_node	Target node.
[in]	cap	Capacity value.
[in]	__cost	Cost per unit of flow.
[in]	args	Arguments to forward to Arc_Type constructor.

Returns: Pointer to the new arc.

Definition at line 258 of file tpl_netcost.H.

References Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), and Aleph::maps().

◆ flow_cost()

template<class NodeT = Net_Cost_Node<Empty_Class>, class ArcT = Net_Cost_Arc<Empty_Class, double>>

Flow_Type Aleph::Net_Cost_Graph< NodeT, ArcT >::flow_cost ( ) const

inline

Compute the total cost of flow circulating through the network.

Sums up the flow cost (flow * cost) for all arcs in the network.

Returns: Total flow cost.

Definition at line 290 of file tpl_netcost.H.

References Aleph::maps().

Referenced by demo_compare_algorithms_on_logistics(), and demo_mincost_maxflow().

◆ get_cost() [1/2]

template<class NodeT = Net_Cost_Node<Empty_Class>, class ArcT = Net_Cost_Arc<Empty_Class, double>>

Flow_Type Aleph::Net_Cost_Graph< NodeT, ArcT >::get_cost ( Arc * a ) const

inlinenoexcept

Return the cost of an arc (const version).

Parameters

[in] a Pointer to the arc.

Returns: The arc's cost value.

Definition at line 219 of file tpl_netcost.H.

◆ get_cost() [2/2]

template<class NodeT = Net_Cost_Node<Empty_Class>, class ArcT = Net_Cost_Arc<Empty_Class, double>>

Flow_Type & Aleph::Net_Cost_Graph< NodeT, ArcT >::get_cost ( Arc * a )

inlinenoexcept

Return a modifiable reference to the cost of an arc.

Parameters

[in] a Pointer to the arc.

Returns: Reference to the arc's cost field.

Definition at line 212 of file tpl_netcost.H.

◆ in_pars()

template<class NodeT = Net_Cost_Node<Empty_Class>, class ArcT = Net_Cost_Arc<Empty_Class, double>>

auto Aleph::Net_Cost_Graph< NodeT, ArcT >::in_pars ( Node * p )

inline

Compute incoming flow parameters for a node.

Parameters

[in] p Node to analyze.

Returns: Tuple of (total capacity, total flow, total cost) for all incoming arcs.

Definition at line 326 of file tpl_netcost.H.

References Aleph::Digraph_Iterator< GT, Filter >::has_curr(), and Aleph::maps().

◆ insert_arc() [1/2]

template<class NodeT = Net_Cost_Node<Empty_Class>, class ArcT = Net_Cost_Arc<Empty_Class, double>>

virtual Arc * Aleph::Net_Cost_Graph< NodeT, ArcT >::insert_arc	(	Node *	src_node,
		Node *	tgt_node
	)

inlinevirtual

Insert arc (internal use only).

Used by internal algorithms. Creates an arc with zero cost.

Parameters

[in]	src_node	Source node.
[in]	tgt_node	Target node.

Returns: Pointer to the new arc.

Warning: For internal use only. Do not call directly.

Definition at line 277 of file tpl_netcost.H.

References Aleph::Net_Graph< NodeT, ArcT >::insert_arc().

◆ insert_arc() [2/2]

template<class NodeT = Net_Cost_Node<Empty_Class>, class ArcT = Net_Cost_Arc<Empty_Class, double>>

virtual Arc * Aleph::Net_Cost_Graph< NodeT, ArcT >::insert_arc	(	Node *	src_node,
		Node *	tgt_node,
		const Flow_Type &	cap,
		const Flow_Type &	__cost
	)

inlinevirtual

Create and insert an arc in a flow network with costs.

The created arc has zero initial flow.

Parameters

[in]	src_node	Source node.
[in]	tgt_node	Target node.
[in]	cap	Capacity value of the arc.
[in]	__cost	Cost per unit of flow.

Returns: Pointer to the new arc.

Exceptions

bad_alloc If there is not enough memory.

Definition at line 239 of file tpl_netcost.H.

References Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), and Aleph::maps().

Referenced by build_simple_network().

◆ operator=() [1/2]

template<class NodeT = Net_Cost_Node<Empty_Class>, class ArcT = Net_Cost_Arc<Empty_Class, double>>

Net_Cost_Graph & Aleph::Net_Cost_Graph< NodeT, ArcT >::operator= ( const Net_Cost_Graph< NodeT, ArcT > & net )

inline

Copy assignment operator (uses copy-and-swap idiom).

Definition at line 195 of file tpl_netcost.H.

References Aleph::maps(), and Aleph::Net_Graph< NodeT, ArcT >::swap().

◆ operator=() [2/2]

template<class NodeT = Net_Cost_Node<Empty_Class>, class ArcT = Net_Cost_Arc<Empty_Class, double>>

Net_Cost_Graph & Aleph::Net_Cost_Graph< NodeT, ArcT >::operator= ( Net_Cost_Graph< NodeT, ArcT > && )

default

Move assignment operator.

◆ out_pars()

template<class NodeT = Net_Cost_Node<Empty_Class>, class ArcT = Net_Cost_Arc<Empty_Class, double>>

auto Aleph::Net_Cost_Graph< NodeT, ArcT >::out_pars ( Node * p )

inline

Compute outgoing flow parameters for a node.

Parameters

[in] p Node to analyze.

Returns: Tuple of (total capacity, total flow, total cost) for all outgoing arcs.

Definition at line 307 of file tpl_netcost.H.

References Aleph::Digraph_Iterator< GT, Filter >::has_curr(), and Aleph::maps().

The documentation for this struct was generated from the following file:

tpl_netcost.H

Public Types

Public Member Functions

Static Public Member Functions

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ Arc

◆ Arc_Type

◆ Base

◆ Flow_Type

◆ Net

◆ Net_MFMC

◆ Node

◆ Node_Type

Constructor & Destructor Documentation

◆ Net_Cost_Graph() [1/3]

◆ Net_Cost_Graph() [2/3]

◆ Net_Cost_Graph() [3/3]

Member Function Documentation

◆ arc_flow_cost()

◆ emplace_arc()

◆ flow_cost()

◆ get_cost() [1/2]

◆ get_cost() [2/2]

◆ in_pars()

◆ insert_arc() [1/2]

◆ insert_arc() [2/2]

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ out_pars()