Network graph with supply and demand nodes. More...

#include <tpl_net_sup_dem.H>

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

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

Public Types
using	Net_Class = Net_Graph< NodeT, ArcT >
	The 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_Sup_Dem_Graph
	Auxiliary network type (same as this class)

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 (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`.

Node *	insert_node (Node *p)
	Insert a node by copying another node.

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.

Constructors and Destructor
	Net_Sup_Dem_Graph ()=default
	Default constructor.

	~Net_Sup_Dem_Graph ()
	Destructor. Frees auxiliary network if it exists.

Node Insertion
Node *	insert_node (const Node_Type &node_info, const Flow_Type &supply=0)
	Insert a node with info and supply/demand value.

Node *	insert_node (const Flow_Type &supply)
	Insert a node with supply/demand value only.

Auxiliary Network Management
bool	exist_aux_net () const noexcept
	Check if the auxiliary network has been computed.

Net_Sup_Dem_Graph *	compute_aux_net ()
	Compute the auxiliary capacitated network.

Net_Sup_Dem_Graph *	get_aux_net () noexcept
	Get the auxiliary network if it exists.

Node *	get_super_source () const noexcept
	Get the super-source node.

Node *	get_super_sink () const noexcept
	Get the super-sink node.

void	free_aux_net ()
	Free the auxiliary network structures.

Feasibility Analysis
bool	is_feasible () const
	Check if the current flow is feasible.

void	non_feasible_nodes (DynDlist< Node * > &supply_list, DynDlist< Node * > &demand_list)
	Get lists of nodes with unsatisfied supply/demand.

Supply/Demand Modification
void	set_supply_flow (Node *p, const Flow_Type &supply)
	Set the supply/demand value for a node.

Flow_Type	get_supply_flow (Node *p) const noexcept
	Get the supply/demand value for a node.

Query Methods
size_t	count_supply_nodes () const noexcept
	Count the number of supply nodes.

size_t	count_demand_nodes () const noexcept
	Count the number of demand nodes.

Flow_Type	total_supply () const noexcept
	Calculate total supply in the network.

Flow_Type	total_demand () const noexcept
	Calculate total demand in the network.

bool	is_balanced () const noexcept
	Check if the network is balanced.

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

Private Attributes
Node *	super_source = nullptr
	Super-source for auxiliary network.

Node *	super_sink = nullptr
	Super-sink for auxiliary network.

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.

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

Network graph with supply and demand nodes.

A supply-demand network is a flow network where some nodes have supply values (sources) and others have demand values (sinks). The goal is typically to determine if all demands can be satisfied from available supplies (feasibility check).

How it works

Create nodes with supply/demand values using insert_node()
Connect nodes with arcs having capacities
Call compute_aux_net() to create the auxiliary capacitated network
Run a max-flow algorithm on the network
Call is_feasible() to check if all demands are satisfied
Call free_aux_net() to release auxiliary structures

Implementation Details

The auxiliary network is constructed by:

Creating a super-source connected to all supply nodes
Creating a super-sink connected from all demand nodes
Arc capacities from super-source equal supply values
Arc capacities to super-sink equal demand values (absolute)

Template Parameters

NodeT	Node type (default: Net_Sup_Dem_Node with double flow)
ArcT	Arc type (default: Net_Arc with double flow)

Definition at line 223 of file tpl_net_sup_dem.H.

Member Typedef Documentation

◆ Arc

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

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

Arc type.

Definition at line 229 of file tpl_net_sup_dem.H.

◆ Arc_Type

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

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

Type of information stored in arcs.

Definition at line 237 of file tpl_net_sup_dem.H.

◆ Aux_Net

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

using Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::Aux_Net = Net_Sup_Dem_Graph

Auxiliary network type (same as this class)

Definition at line 239 of file tpl_net_sup_dem.H.

◆ Flow_Type

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

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

Type representing capacity and flow values.

Definition at line 233 of file tpl_net_sup_dem.H.

◆ Net_Class

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

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

The base network class type.

Definition at line 227 of file tpl_net_sup_dem.H.

◆ Node

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

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

Node type.

Definition at line 231 of file tpl_net_sup_dem.H.

◆ Node_Type

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

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

Type of information stored in nodes.

Definition at line 235 of file tpl_net_sup_dem.H.

Constructor & Destructor Documentation

◆ Net_Sup_Dem_Graph()

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

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

default

Default constructor.

◆ ~Net_Sup_Dem_Graph()

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

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

inline

Destructor. Frees auxiliary network if it exists.

Definition at line 253 of file tpl_net_sup_dem.H.

References Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::exist_aux_net(), and Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::free_aux_net().

Member Function Documentation

◆ compute_aux_net()

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

Net_Sup_Dem_Graph * Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::compute_aux_net ( )

inline

Compute the auxiliary capacitated network.

Constructs the auxiliary network needed for max-flow computation. This creates:

A super-source connected to all supply nodes (supply_flow > 0)
A super-sink connected from all demand nodes (supply_flow < 0)

The auxiliary network is built in-place on this graph.

Returns: Pointer to this network (with auxiliary structures added)

Exceptions

std::domain_error	if auxiliary network already exists
std::range_error	if any supply exceeds node capacity
std::bad_alloc	if memory allocation fails

Definition at line 329 of file tpl_net_sup_dem.H.

References ah_domain_error_if, ah_range_error_if, Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::exist_aux_net(), Aleph::Net_Graph< NodeT, ArcT >::get_in_degree(), Aleph::Net_Graph< NodeT, ArcT >::get_out_degree(), Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::insert_node(), Aleph::Net_Graph< NodeT, ArcT >::remove_node(), Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::super_sink, and Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::super_source.

◆ count_demand_nodes()

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

size_t Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::count_demand_nodes ( ) const

inlinenoexcept

Count the number of demand nodes.

Returns: Number of nodes with negative supply_flow

Definition at line 551 of file tpl_net_sup_dem.H.

References Aleph::count().

◆ count_supply_nodes()

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

size_t Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::count_supply_nodes ( ) const

inlinenoexcept

Count the number of supply nodes.

Returns: Number of nodes with positive supply_flow

Definition at line 538 of file tpl_net_sup_dem.H.

References Aleph::count().

◆ exist_aux_net()

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

bool Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::exist_aux_net ( ) const

inlinenoexcept

Check if the auxiliary network has been computed.

Returns: true if auxiliary network exists

Definition at line 309 of file tpl_net_sup_dem.H.

References Aleph::maps(), Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::super_sink, and Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::super_source.

Referenced by Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::~Net_Sup_Dem_Graph(), Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::compute_aux_net(), Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::free_aux_net(), Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::get_aux_net(), and Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::is_feasible().

◆ free_aux_net()

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

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

inline

Free the auxiliary network structures.

Removes the super-source and super-sink nodes and their arcs. Also clears the residual network if it exists.

Exceptions

std::domain_error if auxiliary network doesn't exist

Definition at line 403 of file tpl_net_sup_dem.H.

References ah_domain_error_if, Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::exist_aux_net(), Aleph::maps(), Aleph::Net_Graph< NodeT, ArcT >::remove_node(), Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::super_sink, and Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::super_source.

Referenced by Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::~Net_Sup_Dem_Graph().

◆ get_aux_net()

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

Net_Sup_Dem_Graph * Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::get_aux_net ( )

inlinenoexcept

Get the auxiliary network if it exists.

Returns: Pointer to this network if auxiliary exists, nullptr otherwise

Definition at line 378 of file tpl_net_sup_dem.H.

References Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::exist_aux_net(), and Aleph::maps().

◆ get_super_sink()

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

Node * Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::get_super_sink ( ) const

inlinenoexcept

Get the super-sink node.

Returns: Pointer to super-sink, or nullptr if not computed

Definition at line 393 of file tpl_net_sup_dem.H.

References Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::super_sink.

◆ get_super_source()

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

Node * Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::get_super_source ( ) const

inlinenoexcept

Get the super-source node.

Returns: Pointer to super-source, or nullptr if not computed

Definition at line 387 of file tpl_net_sup_dem.H.

References Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::super_source.

◆ get_supply_flow()

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

Flow_Type Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::get_supply_flow ( Node * p ) const

inlinenoexcept

Get the supply/demand value for a node.

Parameters

p	Pointer to the node

Returns: The supply_flow value of the node

Definition at line 524 of file tpl_net_sup_dem.H.

◆ insert_node() [1/9]

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

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

inline

Insert a new node with default info.

Definition at line 565 of file tpl_net.H.

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

◆ insert_node() [2/9]

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

Node * Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::insert_node ( const Flow_Type & supply )

inline

Insert a node with supply/demand value only.

Creates and inserts a new node with default info and the given supply/demand value.

Parameters

supply Supply value (positive = supply, negative = demand)

Returns: Pointer to the newly created node

Exceptions

std::bad_alloc if memory allocation fails

Definition at line 295 of file tpl_net_sup_dem.H.

References Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::insert_node(), and Aleph::maps().

◆ insert_node() [3/9]

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

Node * Aleph::Net_Graph< NodeT, ArcT >::insert_node ( const Node_Type & node_info )

inline

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.

◆ insert_node() [4/9]

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

Node * GraphCommon< GT, Node, Arc >::insert_node ( const Node_Type & node_info )

inline

Allocate a new node, set by copy its data content and insert it into the graph.

This method perform several actions. First, it allocates memory for a graph node. Then the data node_info is copied to the data associated to the node. This copy is done via the copy constructor and assign operator. So, these functionalities must be present for the class Node_Type. Finally, the node is topologically inserted into the graph.

Remarks: If this method does not throw exception, then this always returns a valid pointer,

Parameters

[in] node_info info to copy to the new node. The copy constructor and the assign operator must be defined for the class Node_Type.

Returns: a pointer to the new inserted node.

Exceptions

bad_allod if there is no enough memory

Definition at line 267 of file graph-dry.H.

◆ insert_node() [5/9]

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

Node * Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::insert_node	(	const Node_Type &	node_info,
		const Flow_Type &	supply = `0`
	)

inline

Insert a node with info and supply/demand value.

Creates and inserts a new node with the given information and supply/demand value.

Parameters

node_info	Information to store in the node
supply	Supply value (positive = supply, negative = demand)

Returns: Pointer to the newly created node

Exceptions

std::bad_alloc if memory allocation fails

Definition at line 278 of file tpl_net_sup_dem.H.

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

Referenced by AuxNetTest::SetUp(), TEST_F(), and TEST_F().

◆ insert_node() [6/9]

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

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

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.

◆ insert_node() [7/9]

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

virtual Node * Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::insert_node ( Node * p )

inline

Definition at line 267 of file tpl_agraph.H.

◆ insert_node() [8/9]

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

Node * Aleph::Net_Graph< NodeT, ArcT >::insert_node ( Node_Type && info )

inline

Insert a new node by moving info.

Definition at line 571 of file tpl_net.H.

◆ insert_node() [9/9]

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

Node * GraphCommon< GT, Node, Arc >::insert_node ( Node_Type && node_info = Node_Type() )

inline

Allocate a new node, set by moving its data content and insert it into the graph.

This method perform several actions. First, it allocates memory for a graph node. Then the data node_info is moved to the data associated to the node. This movement is done via the move constructor and move assign operator. So, these functionalities must be present for the class Node_Type. Finally, the node is topologically inserted into the graph.

Remarks: If this method does not throw exception, then this always returns a valid pointer,

Parameters

[in] node_info info to move to the new node. The move constructor and the move assign operator must be defined for the class Node_Type.

Returns: a pointer to the new inserted node.

Exceptions

bad_allod if there is no enough memory.

Definition at line 267 of file graph-dry.H.

◆ is_balanced()

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

bool Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::is_balanced ( ) const

inlinenoexcept

Check if the network is balanced.

A network is balanced if total supply equals total demand.

Returns: true if total_supply() == total_demand()

Definition at line 599 of file tpl_net_sup_dem.H.

References Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::total_demand(), and Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::total_supply().

◆ is_feasible()

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

bool Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::is_feasible ( ) const

inline

Check if the current flow is feasible.

A flow is feasible if:

All supply nodes have out_flow >= supply_flow
All demand nodes have in_flow >= |supply_flow|

Returns: true if flow is feasible, false otherwise

Exceptions

std::domain_error if auxiliary network hasn't been computed

Note: You must run a max-flow algorithm before calling this method

Definition at line 438 of file tpl_net_sup_dem.H.

References ah_domain_error_if, Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::exist_aux_net(), and Aleph::maps().

◆ non_feasible_nodes()

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

void Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::non_feasible_nodes	(	DynDlist< Node * > &	supply_list,
		DynDlist< Node * > &	demand_list
	)

inline

Get lists of nodes with unsatisfied supply/demand.

Traverses all nodes and identifies those where the flow doesn't satisfy the supply or demand requirements.

Parameters

[out]	supply_list	Nodes with out_flow < supply_flow
[out]	demand_list	Nodes with in_flow < \|supply_flow\|

Exceptions

std::bad_alloc if memory allocation fails for the lists

Definition at line 471 of file tpl_net_sup_dem.H.

References Aleph::DynList< T >::append(), and Aleph::maps().

◆ set_supply_flow()

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

void Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::set_supply_flow	(	Node *	p,
		const Flow_Type &	supply
	)

inline

Set the supply/demand value for a node.

Changes the supply_flow attribute of the given node. Note that after modifying supply values, you must recompute the max-flow to check feasibility.

Parameters

p	Pointer to the node
supply	New supply value (positive = supply, negative = demand)

Exceptions

std::range_error	if supply exceeds node's out capacity
std::range_error	if demand exceeds node's in capacity

Definition at line 506 of file tpl_net_sup_dem.H.

References ah_range_error_if, and Aleph::maps().

◆ total_demand()

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

Flow_Type Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::total_demand ( ) const

inlinenoexcept

Calculate total demand in the network.

Returns: Sum of absolute values of all negative supply_flow values

Definition at line 580 of file tpl_net_sup_dem.H.

References Aleph::maps().

Referenced by Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::is_balanced().

◆ total_supply()

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

Flow_Type Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::total_supply ( ) const

inlinenoexcept

Calculate total supply in the network.

Returns: Sum of all positive supply_flow values

Definition at line 564 of file tpl_net_sup_dem.H.

References Aleph::maps().

Referenced by Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::is_balanced().

Member Data Documentation

◆ super_sink

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

Node* Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::super_sink = nullptr

private

Super-sink for auxiliary network.

Definition at line 243 of file tpl_net_sup_dem.H.

Referenced by Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::compute_aux_net(), Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::exist_aux_net(), Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::free_aux_net(), and Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::get_super_sink().

◆ super_source

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

Node* Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::super_source = nullptr

private

Super-source for auxiliary network.

Definition at line 242 of file tpl_net_sup_dem.H.

Referenced by Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::compute_aux_net(), Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::exist_aux_net(), Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::free_aux_net(), and Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >::get_super_source().

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

tpl_net_sup_dem.H

Public Types

Public Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

How it works

Implementation Details

Member Typedef Documentation

◆ Arc

◆ Arc_Type

◆ Aux_Net

◆ Flow_Type

◆ Net_Class

◆ Node

◆ Node_Type

Constructor & Destructor Documentation

◆ Net_Sup_Dem_Graph()

◆ ~Net_Sup_Dem_Graph()

Member Function Documentation

◆ compute_aux_net()

◆ count_demand_nodes()

◆ count_supply_nodes()

◆ exist_aux_net()

◆ free_aux_net()

◆ get_aux_net()

◆ get_super_sink()

◆ get_super_source()

◆ get_supply_flow()

◆ insert_node() [1/9]

◆ insert_node() [2/9]

◆ insert_node() [3/9]

◆ insert_node() [4/9]

◆ insert_node() [5/9]

◆ insert_node() [6/9]

◆ insert_node() [7/9]

◆ insert_node() [8/9]

◆ insert_node() [9/9]

◆ is_balanced()

◆ is_feasible()

◆ non_feasible_nodes()

◆ set_supply_flow()

◆ total_demand()

◆ total_supply()

Member Data Documentation

◆ super_sink

◆ super_source