Arc information for multi-commodity flow. More...

#include <tpl_multicommodity.H>

Inheritance diagram for Aleph::MCF_Arc< Arc_Info, FT >:

Collaboration diagram for Aleph::MCF_Arc< Arc_Info, FT >:

Public Types
using	Base = Graph_Aarc< Arc_Info >

using	Flow_Type = FT
	Type for flow values.

Public Types inherited from GTArcCommon< ArcInfo >
using	Item_Type = ArcInfo

using	Arc_Type = ArcInfo

Public Member Functions
	MCF_Arc ()=default
	Default constructor.

	MCF_Arc (const Arc_Info &)
	Constructor from Arc_Info (required by graph framework)

	MCF_Arc (Arc_Info &&)
	Constructor from Arc_Info rvalue (required by graph framework)

	MCF_Arc (Flow_Type cap, Flow_Type cost=0)
	Constructor with capacity and cost.

Flow_Type	total_flow () const
	Total flow on this arc (sum of all commodities)

Flow_Type	residual () const
	Residual capacity.

Flow_Type	flow (size_t k) const
	Get flow for commodity k.

Flow_Type	cost (size_t k) const
	Get cost for commodity k.

void	set_flow (size_t k, Flow_Type f)
	Set flow for commodity k.

void	set_cost (size_t k, Flow_Type c)
	Set cost for commodity k.

void	init_commodities (size_t K)
	Initialize for K commodities.

Public Member Functions inherited from Aleph::Graph_Aarc< Arc_Info >
	Graph_Aarc (const Arc_Info &info)

	Graph_Aarc (Arc_Info &&info=Arc_Info())

	Graph_Aarc (const Graph_Aarc &arc)

Graph_Aarc &	operator= (const Graph_Aarc &arc)

	Graph_Aarc (void src, void tgt, const Arc_Info &data)

	Graph_Aarc (void src, void tgt, Arc_Info &&data=Arc_Info())

Public Member Functions inherited from Aleph::Dlink
template<typename T >
Dnode< T > *	to_dnode () noexcept

template<typename T >
const Dnode< T > *	to_dnode () const noexcept

template<typename T >
T &	to_data () noexcept

template<typename T >
const T &	to_data () const noexcept

	Dlink () noexcept
	Initialize a node or an empty list.

	Dlink (const Dlink &l) noexcept
	Copy constructor.

void	swap (Dlink *link) noexcept
	Swap `this` with list whose header is `link`.

void	swap (Dlink &l) noexcept
	Swap `this` with list whose header is `l`.

	Dlink (Dlink &&l) noexcept
	Construct a new list with the items of l moved.

Dlink &	operator= (const Dlink &l) noexcept
	Copy assignation.

Dlink &	operator= (Dlink &&l) noexcept
	Move assignation.

void	reset () noexcept
	Reset `this`

void	init () noexcept

constexpr bool	is_empty () const noexcept
	Return `true` if `this` (as header node) is empty.

constexpr bool	is_unitarian () const noexcept
	Return `true` if `this` (as header node) has exactly one element.

constexpr bool	is_unitarian_or_empty () const noexcept
	Return `true` if `this` (as header node) has zero or one element.

void	insert (Dlink *node) noexcept
	Insert `node` after `this`.

void	push (Dlink *node) noexcept

void	append (Dlink *node) noexcept
	Insert `node` before `this`.

Dlink *&	get_next () const noexcept
	Return the link that is after `this`

Dlink *&	get_prev () const noexcept
	Return the link that is before `this`

constexpr Dlink *&	get_first_ne () const noexcept
	If `this` is a header node, it return the first node of `this`

constexpr Dlink *&	get_last_ne () const noexcept
	If `this` is a header node, it return the last node of `this`

constexpr Dlink *&	get_first () const noexcept
	If `this` is a header node, it return the first node of `this`

constexpr Dlink *&	get_last () const noexcept
	If `this` is a header node, it return the last node of `this`

void	wrap_header (Dlink *l) noexcept
	Wrap a header to a list (without header).

void	insert_list (Dlink *head) noexcept
	Insert the list `head` before `this`

void	append_list (Dlink *head) noexcept
	Insert the list `head` after `this`

void	splice (Dlink *l) noexcept
	Insert a list `l` without header node after the node `this`.

void	concat_list (Dlink *head) noexcept
	Concatenate list `head` to list `this`

void	concat_list (Dlink &head) noexcept

Dlink *	del () noexcept
	Remove `this` from the list. `this` must not be a header node.

void	erase () noexcept

Dlink *	remove_prev () noexcept
	Remove the item that is before `this`

Dlink *	remove_next () noexcept
	Remove the item that is after `this`

Dlink *	remove_last_ne () noexcept

Dlink *	remove_first_ne () noexcept

Dlink *	remove_last () noexcept

Dlink *	remove_first () noexcept

Dlink *	top () const

Dlink *	pop ()

size_t	reverse_list () noexcept
	Reverse the list.

size_t	reverse () noexcept

size_t	split_list_ne (Dlink &l, Dlink &r) noexcept
	Split `this` in the middle in two lists.

size_t	split_list (Dlink &l, Dlink &r) noexcept

Dlink	cut_list (Dlink *link) noexcept
	Cut `this` from `link`.

void	remove_all_and_delete () noexcept
	Remove and free memory for all the items of list.

void	rotate_left (size_t n)
	Rotate to left the list n positions.

void	rotate_right (size_t n)
	Analogous to rotate_left() but to right.

bool	check ()
	Return `true` if the list is consistent.

Public Member Functions inherited from GTArcCommon< ArcInfo >
	GTArcCommon () noexcept=default
	data contained in arc

	GTArcCommon (const ArcInfo &info)
	Construct from info value (copy)

	GTArcCommon (ArcInfo &&info)
	Construct from info value (move)

	GTArcCommon (void src, void tgt, const ArcInfo &data)
	Construct with endpoints and info (copy)

	GTArcCommon (void src, void tgt, ArcInfo &&data=ArcInfo())
	Construct with endpoints and info (move)

	GTArcCommon (const GTArcCommon &other)
	Copy constructor.

	GTArcCommon (GTArcCommon &&other) noexcept
	Move constructor.

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

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

unsigned int	state () const noexcept
	Return the state of arc.

void	set_state (unsigned int s) noexcept
	Set the state of arc to value `s`

ArcInfo &	get_info () noexcept
	Return a modifiable reference to the arc data.

const ArcInfo &	get_info () const noexcept
	Return a constant reference to the arc data.

void *	get_connected_node (void *node) noexcept

void *	get_img_node (void *node) noexcept

Public Attributes
Flow_Type	capacity = 0
	Arc capacity (shared)

Flow_Type	base_cost = 0
	Default cost per unit flow.

std::vector< Flow_Type >	commodity_flow
	Flow per commodity.

std::vector< Flow_Type >	commodity_cost
	Cost per commodity (optional)

Public Attributes inherited from GTArcCommon< ArcInfo >
void *	src_node = nullptr

void *	tgt_node = nullptr
	Please don't use.

Graph_Attr	attrs
	Please don't use.

ArcInfo	arc_info

Additional Inherited Members
Protected Attributes inherited from Aleph::Dlink
Dlink *	prev

Dlink *	next

Detailed Description

template<typename Arc_Info = Empty_Class, typename FT = double>
struct Aleph::MCF_Arc< Arc_Info, FT >

Arc information for multi-commodity flow.

Extends basic arc with per-commodity flow tracking and costs.

Template Parameters

Arc_Info	Base arc information type.
Flow_Type	Numeric type for flow values.

Definition at line 158 of file tpl_multicommodity.H.

Member Typedef Documentation

◆ Base

template<typename Arc_Info = Empty_Class, typename FT = double>

using Aleph::MCF_Arc< Arc_Info, FT >::Base = Graph_Aarc<Arc_Info>

Definition at line 160 of file tpl_multicommodity.H.

◆ Flow_Type

template<typename Arc_Info = Empty_Class, typename FT = double>

using Aleph::MCF_Arc< Arc_Info, FT >::Flow_Type = FT

Type for flow values.

Definition at line 161 of file tpl_multicommodity.H.

Constructor & Destructor Documentation

◆ MCF_Arc() [1/4]

template<typename Arc_Info = Empty_Class, typename FT = double>

Aleph::MCF_Arc< Arc_Info, FT >::MCF_Arc ( )

default

Default constructor.

◆ MCF_Arc() [2/4]

template<typename Arc_Info = Empty_Class, typename FT = double>

Aleph::MCF_Arc< Arc_Info, FT >::MCF_Arc ( const Arc_Info & )

inline

Constructor from Arc_Info (required by graph framework)

Definition at line 172 of file tpl_multicommodity.H.

◆ MCF_Arc() [3/4]

template<typename Arc_Info = Empty_Class, typename FT = double>

Aleph::MCF_Arc< Arc_Info, FT >::MCF_Arc ( Arc_Info && )

inline

Constructor from Arc_Info rvalue (required by graph framework)

Definition at line 175 of file tpl_multicommodity.H.

◆ MCF_Arc() [4/4]

template<typename Arc_Info = Empty_Class, typename FT = double>

Aleph::MCF_Arc< Arc_Info, FT >::MCF_Arc	(	Flow_Type	cap,
		Flow_Type	cost = `0`
	)

inline

Constructor with capacity and cost.

Definition at line 178 of file tpl_multicommodity.H.

Member Function Documentation

◆ cost()

template<typename Arc_Info = Empty_Class, typename FT = double>

Flow_Type Aleph::MCF_Arc< Arc_Info, FT >::cost ( size_t k ) const

inline

Get cost for commodity k.

Definition at line 200 of file tpl_multicommodity.H.

References Aleph::MCF_Arc< Arc_Info, FT >::base_cost, Aleph::MCF_Arc< Arc_Info, FT >::commodity_cost, Aleph::maps(), and Aleph::HTList::size().

◆ flow()

template<typename Arc_Info = Empty_Class, typename FT = double>

Flow_Type Aleph::MCF_Arc< Arc_Info, FT >::flow ( size_t k ) const

inline

Get flow for commodity k.

Definition at line 194 of file tpl_multicommodity.H.

References Aleph::MCF_Arc< Arc_Info, FT >::commodity_flow, Aleph::maps(), and Aleph::HTList::size().

◆ init_commodities()

template<typename Arc_Info = Empty_Class, typename FT = double>

void Aleph::MCF_Arc< Arc_Info, FT >::init_commodities ( size_t K )

inline

Initialize for K commodities.

Definition at line 224 of file tpl_multicommodity.H.

References Aleph::MCF_Arc< Arc_Info, FT >::commodity_cost, and Aleph::MCF_Arc< Arc_Info, FT >::commodity_flow.

◆ residual()

template<typename Arc_Info = Empty_Class, typename FT = double>

Flow_Type Aleph::MCF_Arc< Arc_Info, FT >::residual ( ) const

inline

Residual capacity.

Definition at line 191 of file tpl_multicommodity.H.

References Aleph::MCF_Arc< Arc_Info, FT >::capacity, and Aleph::MCF_Arc< Arc_Info, FT >::total_flow().

◆ set_cost()

template<typename Arc_Info = Empty_Class, typename FT = double>

void Aleph::MCF_Arc< Arc_Info, FT >::set_cost	(	size_t	k,
		Flow_Type	c
	)

inline

Set cost for commodity k.

Definition at line 216 of file tpl_multicommodity.H.

References Aleph::MCF_Arc< Arc_Info, FT >::commodity_cost, Aleph::maps(), and Aleph::HTList::size().

◆ set_flow()

template<typename Arc_Info = Empty_Class, typename FT = double>

void Aleph::MCF_Arc< Arc_Info, FT >::set_flow	(	size_t	k,
		Flow_Type	f
	)

inline

Set flow for commodity k.

Definition at line 208 of file tpl_multicommodity.H.

References Aleph::MCF_Arc< Arc_Info, FT >::commodity_flow, Aleph::maps(), and Aleph::HTList::size().

◆ total_flow()

template<typename Arc_Info = Empty_Class, typename FT = double>

Flow_Type Aleph::MCF_Arc< Arc_Info, FT >::total_flow ( ) const

inline

Total flow on this arc (sum of all commodities)

Definition at line 182 of file tpl_multicommodity.H.

References Aleph::MCF_Arc< Arc_Info, FT >::commodity_flow, and Aleph::sum().

Referenced by Aleph::MCF_Arc< Arc_Info, FT >::residual().

Member Data Documentation

◆ base_cost

template<typename Arc_Info = Empty_Class, typename FT = double>

Flow_Type Aleph::MCF_Arc< Arc_Info, FT >::base_cost = 0

Default cost per unit flow.

Definition at line 164 of file tpl_multicommodity.H.

Referenced by Aleph::MCF_Arc< Arc_Info, FT >::cost().

◆ capacity

template<typename Arc_Info = Empty_Class, typename FT = double>

Flow_Type Aleph::MCF_Arc< Arc_Info, FT >::capacity = 0

Arc capacity (shared)

Definition at line 163 of file tpl_multicommodity.H.

Referenced by Aleph::MCF_Arc< Arc_Info, FT >::residual().

◆ commodity_cost

template<typename Arc_Info = Empty_Class, typename FT = double>

std::vector<Flow_Type> Aleph::MCF_Arc< Arc_Info, FT >::commodity_cost

Cost per commodity (optional)

Definition at line 166 of file tpl_multicommodity.H.

Referenced by Aleph::MCF_Arc< Arc_Info, FT >::cost(), Aleph::MCF_Arc< Arc_Info, FT >::init_commodities(), and Aleph::MCF_Arc< Arc_Info, FT >::set_cost().

◆ commodity_flow

template<typename Arc_Info = Empty_Class, typename FT = double>

std::vector<Flow_Type> Aleph::MCF_Arc< Arc_Info, FT >::commodity_flow

Flow per commodity.

Definition at line 165 of file tpl_multicommodity.H.

Referenced by Aleph::MCF_Arc< Arc_Info, FT >::flow(), Aleph::MCF_Arc< Arc_Info, FT >::init_commodities(), Aleph::MCF_Arc< Arc_Info, FT >::set_flow(), and Aleph::MCF_Arc< Arc_Info, FT >::total_flow().

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

tpl_multicommodity.H

Public Types

Public Member Functions

Public Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ Base

◆ Flow_Type

Constructor & Destructor Documentation

◆ MCF_Arc() [1/4]

◆ MCF_Arc() [2/4]

◆ MCF_Arc() [3/4]

◆ MCF_Arc() [4/4]

Member Function Documentation

◆ cost()

◆ flow()

◆ init_commodities()

◆ residual()

◆ set_cost()

◆ set_flow()

◆ total_flow()

Member Data Documentation

◆ base_cost

◆ capacity

◆ commodity_cost

◆ commodity_flow