Capacitated network with node capacity constraints. More...

#include <tpl_netcapgraph.H>

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

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

Public Types
using	Net_Class = Net_Graph< NodeT, ArcT >
	Base network class type.

using	Arc = ArcT
	Arc type.

using	Node = NodeT
	Node type.

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

using	Node_Type = typename Node::Node_Type
	Type of information stored in nodes.

using	Arc_Type = typename Arc::Arc_Type
	Type of information stored in arcs.

using	Aux_Net = Net_Graph< Net_Node< Empty_Class >, Net_Arc< bool, Flow_Type > >
	Auxiliary network type for solving node-capacitated networks.

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
Node *	insert_node (Node *p) override

Node *	insert_node (const Node_Type &node_info, const Flow_Type &cap=std::numeric_limits< Flow_Type >::max())
	Insert a new capacitated node into the network.

Node *	insert_node (const Flow_Type &cap)
	Insert a new node with default info and specified capacity.

Node *	insert_node ()
	Insert a new node with default info and unlimited capacity.

	Net_Cap_Graph () noexcept
	Default constructor.

	Net_Cap_Graph (const Net_Cap_Graph &other)
	Copy constructor.

	Net_Cap_Graph (Net_Cap_Graph &&other) noexcept
	Move constructor.

Net_Cap_Graph &	operator= (const Net_Cap_Graph &other)
	Copy assignment operator.

Net_Cap_Graph &	operator= (Net_Cap_Graph &&other) noexcept
	Move assignment operator.

	~Net_Cap_Graph ()
	Destructor.

Aux_Net *	get_aux_net () noexcept
	Get pointer to the auxiliary network.

const Aux_Net *	get_aux_net () const noexcept
	Get const pointer to the auxiliary network.

bool	has_aux_net () const noexcept
	Check if auxiliary network has been computed.

Aux_Net *	compute_aux_net ()
	Compute the equivalent arc-capacitated auxiliary network.

void	update ()
	Update flow values from auxiliary network to this network.

void	free_aux_net ()
	Free the auxiliary network.

Flow_Type	get_total_flow () const
	Get the total flow value of the network.

bool	check_node_capacities () const noexcept
	Check if all node capacity constraints are satisfied.

void	reset_flows () noexcept
	Reset all flow values to zero.

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	get_node_cap (const Node *node) noexcept
	Get the capacity of a node.

static void	set_node_cap (Node *node, const Flow_Type &cap)
	Set the capacity of a node.

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.

Private Attributes
Aux_Net *	aux_net = nullptr

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_Cap_Node<Empty_Class, double>, class ArcT = Net_Arc<Empty_Class, double>>
class Aleph::Net_Cap_Graph< NodeT, ArcT >

Capacitated network with node capacity constraints.

Net_Cap_Graph models a flow network where nodes have maximum throughput limits in addition to arc capacities. This extends the standard maximum flow model to handle vertex-capacitated networks.

Network Transformation

A node-capacitated network cannot be directly solved by standard maximum flow algorithms. Instead, it must be transformed into an equivalent arc-capacitated network (called the auxiliary network).

The transformation works as follows:

Each node v with capacity c(v) is split into two nodes: v_in and v_out
An arc (v_in, v_out) with capacity c(v) is added
All incoming arcs to v now go to v_in
All outgoing arcs from v now come from v_out

Usage Pattern

Net_Cap_Graph<MyNode, MyArc> net;
 
// Build the network
auto n1 = net.insert_node("A", 10);  // Node with capacity 10
auto n2 = net.insert_node("B", 5);   // Node with capacity 5
net.insert_arc(n1, n2, 15, 0);       // Arc with capacity 15
 
// Compute auxiliary network
auto aux = net.compute_aux_net();
 
// Run max flow on auxiliary network
ford_fulkerson_maximum_flow(*aux);
 
// Transfer flow values back
net.update();
 
// Clean up
net.free_aux_net();

Template Parameters

NodeT	Node type (must derive from Net_Cap_Node).
ArcT	Arc type (must derive from Net_Arc).

See also: Net_Graph compute_aux_net() Net_Cap_Node

Definition at line 267 of file tpl_netcapgraph.H.

Member Typedef Documentation

◆ Arc

template<class NodeT = Net_Cap_Node<Empty_Class, double>, class ArcT = Net_Arc<Empty_Class, double>>

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

Arc type.

Definition at line 274 of file tpl_netcapgraph.H.

◆ Arc_Type

template<class NodeT = Net_Cap_Node<Empty_Class, double>, class ArcT = Net_Arc<Empty_Class, double>>

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

Type of information stored in arcs.

Definition at line 286 of file tpl_netcapgraph.H.

◆ Aux_Net

template<class NodeT = Net_Cap_Node<Empty_Class, double>, class ArcT = Net_Arc<Empty_Class, double>>

using Aleph::Net_Cap_Graph< NodeT, ArcT >::Aux_Net = Net_Graph<Net_Node<Empty_Class>, Net_Arc<bool, Flow_Type> >

Auxiliary network type for solving node-capacitated networks.

Aux_Net is the equivalent arc-capacitated network that can be processed by standard maximum flow algorithms.

The auxiliary network is created by compute_aux_net(). Each node in Net_Cap_Graph maps to an arc in Aux_Net. The arc's boolean info indicates whether it represents a node (true) or an original arc (false).

Mapping between networks:

For a node p in Net_Cap_Graph: NODE_COOKIE(p) points to the corresponding arc in Aux_Net
For an arc in Aux_Net: ARC_COOKIE(arc) points to either the original node (if arc->get_info() == true) or the original arc (if arc->get_info() == false)

Definition at line 355 of file tpl_netcapgraph.H.

◆ Flow_Type

template<class NodeT = Net_Cap_Node<Empty_Class, double>, class ArcT = Net_Arc<Empty_Class, double>>

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

Type representing capacity and flow values.

Definition at line 280 of file tpl_netcapgraph.H.

◆ Net_Class

template<class NodeT = Net_Cap_Node<Empty_Class, double>, class ArcT = Net_Arc<Empty_Class, double>>

using Aleph::Net_Cap_Graph< NodeT, ArcT >::Net_Class = Net_Graph<NodeT, ArcT>

Base network class type.

Definition at line 271 of file tpl_netcapgraph.H.

◆ Node

template<class NodeT = Net_Cap_Node<Empty_Class, double>, class ArcT = Net_Arc<Empty_Class, double>>

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

Node type.

Definition at line 277 of file tpl_netcapgraph.H.

◆ Node_Type

template<class NodeT = Net_Cap_Node<Empty_Class, double>, class ArcT = Net_Arc<Empty_Class, double>>

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

Type of information stored in nodes.

Definition at line 283 of file tpl_netcapgraph.H.

Constructor & Destructor Documentation

◆ Net_Cap_Graph() [1/3]

template<class NodeT = Net_Cap_Node<Empty_Class, double>, class ArcT = Net_Arc<Empty_Class, double>>

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

inlinenoexcept

Default constructor.

Creates an empty node-capacitated network.

Definition at line 366 of file tpl_netcapgraph.H.

◆ Net_Cap_Graph() [2/3]

template<class NodeT = Net_Cap_Node<Empty_Class, double>, class ArcT = Net_Arc<Empty_Class, double>>

Aleph::Net_Cap_Graph< NodeT, ArcT >::Net_Cap_Graph ( const Net_Cap_Graph< NodeT, ArcT > & other )

inline

Copy constructor.

Parameters

other Network to copy from.

Note: The auxiliary network is NOT copied.

Definition at line 377 of file tpl_netcapgraph.H.

◆ Net_Cap_Graph() [3/3]

template<class NodeT = Net_Cap_Node<Empty_Class, double>, class ArcT = Net_Arc<Empty_Class, double>>

Aleph::Net_Cap_Graph< NodeT, ArcT >::Net_Cap_Graph ( Net_Cap_Graph< NodeT, ArcT > && other )

inlinenoexcept

Move constructor.

Parameters

other Network to move from.

Definition at line 387 of file tpl_netcapgraph.H.

References Aleph::maps().

◆ ~Net_Cap_Graph()

template<class NodeT = Net_Cap_Node<Empty_Class, double>, class ArcT = Net_Arc<Empty_Class, double>>

Aleph::Net_Cap_Graph< NodeT, ArcT >::~Net_Cap_Graph ( )

inline

Destructor.

Automatically frees the auxiliary network if it exists.

Definition at line 432 of file tpl_netcapgraph.H.

References Aleph::Net_Cap_Graph< NodeT, ArcT >::aux_net, and Aleph::clear_graph().

Member Function Documentation

◆ check_node_capacities()

template<class NodeT = Net_Cap_Node<Empty_Class, double>, class ArcT = Net_Arc<Empty_Class, double>>

bool Aleph::Net_Cap_Graph< NodeT, ArcT >::check_node_capacities ( ) const

inlinenoexcept

Check if all node capacity constraints are satisfied.

Verifies that for each node, the flow through it does not exceed its maximum capacity.

Returns: true if all node capacities are respected, false otherwise.

Definition at line 641 of file tpl_netcapgraph.H.

◆ compute_aux_net()

template<class NodeT = Net_Cap_Node<Empty_Class, double>, class ArcT = Net_Arc<Empty_Class, double>>

Aux_Net * Aleph::Net_Cap_Graph< NodeT, ArcT >::compute_aux_net ( )

inline

Compute the equivalent arc-capacitated auxiliary network.

Transforms this node-capacitated network into an equivalent arc-capacitated network that can be solved by standard maximum flow algorithms.

The transformation:

Each node v is split into v_in and v_out
Arc (v_in, v_out) with capacity = v.max_cap is added
Original arcs are remapped accordingly

Cookie mappings are established for update():

NODE_COOKIE(p) -> arc representing node p
ARC_COOKIE(node_arc) -> original node p
ARC_COOKIE(edge_arc) -> original arc

Returns: Pointer to the computed auxiliary network.

Exceptions

std::domain_error	if auxiliary network already exists.
std::bad_alloc	if memory allocation fails.

Note: Call update() after running max flow on the auxiliary network to transfer flow values back to this network.

Definition at line 492 of file tpl_netcapgraph.H.

References ah_domain_error_if, ARC_COOKIE, Aleph::Net_Cap_Graph< NodeT, ArcT >::aux_net, Aleph::clear_graph(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), Aleph::Net_Graph< NodeT, ArcT >::insert_node(), Aleph::maps(), and NODE_COOKIE.

Referenced by TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ free_aux_net()

template<class NodeT = Net_Cap_Node<Empty_Class, double>, class ArcT = Net_Arc<Empty_Class, double>>

void Aleph::Net_Cap_Graph< NodeT, ArcT >::free_aux_net ( )

inline

Free the auxiliary network.

Releases all memory used by the auxiliary network and clears the cookie mappings.

Exceptions

std::domain_error if auxiliary network has not been computed.

Definition at line 600 of file tpl_netcapgraph.H.

References ah_domain_error_if, Aleph::Net_Cap_Graph< NodeT, ArcT >::aux_net, and Aleph::clear_graph().

Referenced by Aleph::Net_Cap_Graph< NodeT, ArcT >::operator=(), Aleph::Net_Cap_Graph< NodeT, ArcT >::operator=(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ get_aux_net() [1/2]

template<class NodeT = Net_Cap_Node<Empty_Class, double>, class ArcT = Net_Arc<Empty_Class, double>>

const Aux_Net * Aleph::Net_Cap_Graph< NodeT, ArcT >::get_aux_net ( ) const

inlinenoexcept

Get const pointer to the auxiliary network.

Returns: Const pointer to the auxiliary network, or nullptr if not computed.

Definition at line 455 of file tpl_netcapgraph.H.

References Aleph::Net_Cap_Graph< NodeT, ArcT >::aux_net.

◆ get_aux_net() [2/2]

template<class NodeT = Net_Cap_Node<Empty_Class, double>, class ArcT = Net_Arc<Empty_Class, double>>

Aux_Net * Aleph::Net_Cap_Graph< NodeT, ArcT >::get_aux_net ( )

inlinenoexcept

Get pointer to the auxiliary network.

Returns: Pointer to the auxiliary network, or nullptr if not computed.

Definition at line 446 of file tpl_netcapgraph.H.

References Aleph::Net_Cap_Graph< NodeT, ArcT >::aux_net.

◆ get_node_cap()

template<class NodeT = Net_Cap_Node<Empty_Class, double>, class ArcT = Net_Arc<Empty_Class, double>>

static Flow_Type Aleph::Net_Cap_Graph< NodeT, ArcT >::get_node_cap ( const Node * node )

inlinestaticnoexcept

Get the capacity of a node.

Parameters

node	Pointer to the node.

Returns: The maximum capacity of the node.

Definition at line 676 of file tpl_netcapgraph.H.

◆ get_total_flow()

template<class NodeT = Net_Cap_Node<Empty_Class, double>, class ArcT = Net_Arc<Empty_Class, double>>

Flow_Type Aleph::Net_Cap_Graph< NodeT, ArcT >::get_total_flow ( ) const

inline

Get the total flow value of the network.

Returns the total flow passing through the network, computed as the sum of flows through all nodes (using their in_flow).

Returns: Total network flow value.

Exceptions

std::domain_error if auxiliary network has not been computed.

Note: update() must be called first to transfer flow values.

Definition at line 620 of file tpl_netcapgraph.H.

References ah_domain_error_if, Aleph::Net_Cap_Graph< NodeT, ArcT >::aux_net, and Aleph::maps().

◆ has_aux_net()

template<class NodeT = Net_Cap_Node<Empty_Class, double>, class ArcT = Net_Arc<Empty_Class, double>>

bool Aleph::Net_Cap_Graph< NodeT, ArcT >::has_aux_net ( ) const

inlinenoexcept

Check if auxiliary network has been computed.

Returns: true if auxiliary network exists, false otherwise.

Definition at line 464 of file tpl_netcapgraph.H.

References Aleph::Net_Cap_Graph< NodeT, ArcT >::aux_net.

Referenced by TEST_F().

◆ insert_node() [1/4]

template<class NodeT = Net_Cap_Node<Empty_Class, double>, class ArcT = Net_Arc<Empty_Class, double>>

Node * Aleph::Net_Cap_Graph< NodeT, ArcT >::insert_node ( )

inline

Insert a new node with default info and unlimited capacity.

Returns: Pointer to the newly created and inserted node.

Exceptions

std::bad_alloc if memory allocation fails.

Definition at line 333 of file tpl_netcapgraph.H.

References Aleph::Net_Cap_Graph< NodeT, ArcT >::insert_node().

Referenced by Aleph::Net_Cap_Graph< NodeT, ArcT >::insert_node(), and Aleph::Net_Cap_Graph< NodeT, ArcT >::insert_node().

◆ insert_node() [2/4]

template<class NodeT = Net_Cap_Node<Empty_Class, double>, class ArcT = Net_Arc<Empty_Class, double>>

Node * Aleph::Net_Cap_Graph< NodeT, ArcT >::insert_node ( const Flow_Type & cap )

inline

Insert a new node with default info and specified capacity.

Parameters

cap	Maximum flow capacity for this node.

Returns: Pointer to the newly created and inserted node.

Exceptions

std::bad_alloc	if memory allocation fails.
std::domain_error	if cap is negative.

Definition at line 323 of file tpl_netcapgraph.H.

References Aleph::Net_Cap_Graph< NodeT, ArcT >::insert_node().

◆ insert_node() [3/4]

template<class NodeT = Net_Cap_Node<Empty_Class, double>, class ArcT = Net_Arc<Empty_Class, double>>

Node * Aleph::Net_Cap_Graph< NodeT, ArcT >::insert_node	(	const Node_Type &	node_info,
		const Flow_Type &	cap = `std::numeric_limits<Flow_Type>::max()`
	)

inline

Insert a new capacitated node into the network.

Creates a new node with the given information and capacity, and inserts it into the network.

Parameters

node_info	Information to store in the node.
cap	Maximum flow capacity for this node. Defaults to the maximum representable value (unlimited).

Returns: Pointer to the newly created and inserted node.

Exceptions

std::bad_alloc	if memory allocation fails.
std::domain_error	if cap is negative.

Definition at line 305 of file tpl_netcapgraph.H.

References ah_domain_error_if, and Aleph::Net_Graph< NodeT, ArcT >::insert_node().

◆ insert_node() [4/4]

template<class NodeT = Net_Cap_Node<Empty_Class, double>, class ArcT = Net_Arc<Empty_Class, double>>

Node * Aleph::Net_Cap_Graph< NodeT, ArcT >::insert_node ( Node * p )

inlineoverride

Definition at line 288 of file tpl_netcapgraph.H.

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

Referenced by 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 TEST_F().

◆ operator=() [1/2]

template<class NodeT = Net_Cap_Node<Empty_Class, double>, class ArcT = Net_Arc<Empty_Class, double>>

Net_Cap_Graph & Aleph::Net_Cap_Graph< NodeT, ArcT >::operator= ( const Net_Cap_Graph< NodeT, ArcT > & other )

inline

Copy assignment operator.

Parameters

other Network to copy from.

Returns: Reference to this network.

Note: Frees existing auxiliary network before copying.

Definition at line 399 of file tpl_netcapgraph.H.

References Aleph::Net_Cap_Graph< NodeT, ArcT >::aux_net, Aleph::Net_Cap_Graph< NodeT, ArcT >::free_aux_net(), Aleph::maps(), and Aleph::Net_Graph< NodeT, ArcT >::operator=().

◆ operator=() [2/2]

template<class NodeT = Net_Cap_Node<Empty_Class, double>, class ArcT = Net_Arc<Empty_Class, double>>

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

inlinenoexcept

Move assignment operator.

Parameters

other Network to move from.

Returns: Reference to this network.

Definition at line 415 of file tpl_netcapgraph.H.

References Aleph::Net_Cap_Graph< NodeT, ArcT >::aux_net, Aleph::Net_Cap_Graph< NodeT, ArcT >::free_aux_net(), Aleph::maps(), and Aleph::Net_Graph< NodeT, ArcT >::operator=().

◆ reset_flows()

template<class NodeT = Net_Cap_Node<Empty_Class, double>, class ArcT = Net_Arc<Empty_Class, double>>

void Aleph::Net_Cap_Graph< NodeT, ArcT >::reset_flows ( )

inlinenoexcept

Reset all flow values to zero.

Resets flows in both arcs and nodes.

Definition at line 656 of file tpl_netcapgraph.H.

◆ set_node_cap()

template<class NodeT = Net_Cap_Node<Empty_Class, double>, class ArcT = Net_Arc<Empty_Class, double>>

static void Aleph::Net_Cap_Graph< NodeT, ArcT >::set_node_cap	(	Node *	node,
		const Flow_Type &	cap
	)

inlinestatic

Set the capacity of a node.

Parameters

node	Pointer to the node.
cap	New capacity value.

Exceptions

std::domain_error	if cap is negative.
std::overflow_error	if current flow exceeds new capacity.

Definition at line 688 of file tpl_netcapgraph.H.

References ah_domain_error_if, and ah_overflow_error_if.

◆ update()

template<class NodeT = Net_Cap_Node<Empty_Class, double>, class ArcT = Net_Arc<Empty_Class, double>>

void Aleph::Net_Cap_Graph< NodeT, ArcT >::update ( )

inline

Update flow values from auxiliary network to this network.

After running a maximum flow algorithm on the auxiliary network, call this method to transfer the computed flow values back to the original node-capacitated network.

Updates:

Node in_flow and out_flow from node-representing arcs
Arc flow values from edge-representing arcs

Exceptions

std::domain_error if auxiliary network has not been computed.

Definition at line 570 of file tpl_netcapgraph.H.

References ah_domain_error_if, ARC_COOKIE, and Aleph::Net_Cap_Graph< NodeT, ArcT >::aux_net.

Referenced by TEST_F(), TEST_F(), and TEST_F().

Member Data Documentation

◆ aux_net

template<class NodeT = Net_Cap_Node<Empty_Class, double>, class ArcT = Net_Arc<Empty_Class, double>>

Aux_Net* Aleph::Net_Cap_Graph< NodeT, ArcT >::aux_net = nullptr

private

Definition at line 359 of file tpl_netcapgraph.H.

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

tpl_netcapgraph.H

Public Types

Public Member Functions

Static Public Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Network Transformation

Usage Pattern

Member Typedef Documentation

◆ Arc

◆ Arc_Type

◆ Aux_Net

◆ Flow_Type

◆ Net_Class

◆ Node

◆ Node_Type

Constructor & Destructor Documentation

◆ Net_Cap_Graph() [1/3]

◆ Net_Cap_Graph() [2/3]

◆ Net_Cap_Graph() [3/3]

◆ ~Net_Cap_Graph()

Member Function Documentation

◆ check_node_capacities()

◆ compute_aux_net()

◆ free_aux_net()

◆ get_aux_net() [1/2]

◆ get_aux_net() [2/2]

◆ get_node_cap()

◆ get_total_flow()

◆ has_aux_net()

◆ insert_node() [1/4]

◆ insert_node() [2/4]

◆ insert_node() [3/4]

◆ insert_node() [4/4]

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ reset_flows()

◆ set_node_cap()

◆ update()

Member Data Documentation

◆ aux_net