Multi-commodity flow network (directed graph). More...

#include <tpl_multicommodity.H>

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

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

Public Types
using	Base = Array_Digraph< NodeT, ArcT >

using	Node = NodeT

using	Arc = ArcT

using	Flow_Type = typename Arc::Flow_Type

using	CommodityType = Commodity< Node, Flow_Type >

Public Types inherited from Aleph::Digraph< BaseGraph >
using	GT = BaseGraph

using	Node = typename BaseGraph::Node

using	Arc = typename BaseGraph::Arc

Public Member Functions
	MCF_Graph ()=default
	Default constructor.

size_t	num_commodities () const
	Get number of commodities.

const CommodityType &	get_commodity (size_t k) const
	Get commodity by index.

const std::vector< CommodityType > &	get_commodities () const
	Get all commodities.

size_t	add_commodity (Node source, Node sink, Flow_Type demand, const std::string &name="")
	Add a commodity to the network.

Arc *	insert_arc (Node src, Node tgt, Flow_Type capacity, Flow_Type cost=0)
	Insert arc with capacity and cost.

void	build_node_index ()
	Build node index mapping (call after all nodes inserted)

size_t	get_node_index (Node *p) const
	Get node index.

Flow_Type	total_cost () const
	Total flow cost across all commodities.

bool	demands_satisfied () const
	Check if all demands are satisfied.

bool	capacities_respected () const
	Check capacity constraints.

void	print_summary () const
	Print network summary.

Public Member Functions inherited from Aleph::Digraph< BaseGraph >
	Digraph () noexcept
	Default constructor.

	Digraph (const Digraph &dg)
	Copy constructor.

	Digraph (Digraph &&dg) noexcept
	Move constructor.

Digraph &	operator= (const Digraph &g)
	Copy assignment operator.

Digraph &	operator= (Digraph &&g) noexcept
	Move assignment operator.

Private Attributes
std::vector< CommodityType >	commodities

DynMapTree< Node *, size_t >	node_to_idx

Detailed Description

template<class NodeT = Graph_Anode<Empty_Class>, class ArcT = MCF_Arc<Empty_Class, double>>
class Aleph::MCF_Graph< NodeT, ArcT >

Multi-commodity flow network (directed graph).

A directed network that supports multiple commodities sharing arc capacities. Each commodity has its own source-sink pair and demand.

This class inherits from Array_Digraph to ensure proper directed graph behavior, which is essential for flow conservation constraints.

Template Parameters

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

Definition at line 247 of file tpl_multicommodity.H.

Member Typedef Documentation

◆ Arc

template<class NodeT = Graph_Anode<Empty_Class>, class ArcT = MCF_Arc<Empty_Class, double>>

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

Definition at line 252 of file tpl_multicommodity.H.

◆ Base

template<class NodeT = Graph_Anode<Empty_Class>, class ArcT = MCF_Arc<Empty_Class, double>>

using Aleph::MCF_Graph< NodeT, ArcT >::Base = Array_Digraph<NodeT, ArcT>

Definition at line 250 of file tpl_multicommodity.H.

◆ CommodityType

template<class NodeT = Graph_Anode<Empty_Class>, class ArcT = MCF_Arc<Empty_Class, double>>

using Aleph::MCF_Graph< NodeT, ArcT >::CommodityType = Commodity<Node, Flow_Type>

Definition at line 254 of file tpl_multicommodity.H.

◆ Flow_Type

template<class NodeT = Graph_Anode<Empty_Class>, class ArcT = MCF_Arc<Empty_Class, double>>

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

Definition at line 253 of file tpl_multicommodity.H.

◆ Node

template<class NodeT = Graph_Anode<Empty_Class>, class ArcT = MCF_Arc<Empty_Class, double>>

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

Definition at line 251 of file tpl_multicommodity.H.

Constructor & Destructor Documentation

◆ MCF_Graph()

template<class NodeT = Graph_Anode<Empty_Class>, class ArcT = MCF_Arc<Empty_Class, double>>

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

default

Default constructor.

Member Function Documentation

◆ add_commodity()

template<class NodeT = Graph_Anode<Empty_Class>, class ArcT = MCF_Arc<Empty_Class, double>>

size_t Aleph::MCF_Graph< NodeT, ArcT >::add_commodity	(	Node *	source,
		Node *	sink,
		Flow_Type	demand,
		const std::string &	name = `""`
	)

inline

Add a commodity to the network.

Parameters

[in]	source	Source node.
[in]	sink	Sink node.
[in]	demand	Required flow amount.
[in]	name	Optional name.

Returns: Commodity index.

Definition at line 289 of file tpl_multicommodity.H.

References Aleph::MCF_Graph< NodeT, ArcT >::commodities.

◆ build_node_index()

template<class NodeT = Graph_Anode<Empty_Class>, class ArcT = MCF_Arc<Empty_Class, double>>

void Aleph::MCF_Graph< NodeT, ArcT >::build_node_index ( )

inline

Build node index mapping (call after all nodes inserted)

Definition at line 322 of file tpl_multicommodity.H.

References Aleph::DynSetTree< Key, Tree, Compare >::empty(), Aleph::DynMapTree< Key, Data, Tree, Compare >::insert(), and Aleph::MCF_Graph< NodeT, ArcT >::node_to_idx.

◆ capacities_respected()

template<class NodeT = Graph_Anode<Empty_Class>, class ArcT = MCF_Arc<Empty_Class, double>>

bool Aleph::MCF_Graph< NodeT, ArcT >::capacities_respected ( ) const

inline

Check capacity constraints.

Definition at line 369 of file tpl_multicommodity.H.

◆ demands_satisfied()

template<class NodeT = Graph_Anode<Empty_Class>, class ArcT = MCF_Arc<Empty_Class, double>>

bool Aleph::MCF_Graph< NodeT, ArcT >::demands_satisfied ( ) const

inline

Check if all demands are satisfied.

Definition at line 350 of file tpl_multicommodity.H.

References Aleph::MCF_Graph< NodeT, ArcT >::commodities, Aleph::Digraph_Iterator< GT, Filter >::has_curr(), and Aleph::maps().

◆ get_commodities()

template<class NodeT = Graph_Anode<Empty_Class>, class ArcT = MCF_Arc<Empty_Class, double>>

const std::vector< CommodityType > & Aleph::MCF_Graph< NodeT, ArcT >::get_commodities ( ) const

inline

Get all commodities.

Definition at line 276 of file tpl_multicommodity.H.

References Aleph::MCF_Graph< NodeT, ArcT >::commodities.

◆ get_commodity()

template<class NodeT = Graph_Anode<Empty_Class>, class ArcT = MCF_Arc<Empty_Class, double>>

const CommodityType & Aleph::MCF_Graph< NodeT, ArcT >::get_commodity ( size_t k ) const

inline

Get commodity by index.

Definition at line 268 of file tpl_multicommodity.H.

References ah_out_of_range_error_if, Aleph::MCF_Graph< NodeT, ArcT >::commodities, Aleph::maps(), and Aleph::HTList::size().

◆ get_node_index()

template<class NodeT = Graph_Anode<Empty_Class>, class ArcT = MCF_Arc<Empty_Class, double>>

size_t Aleph::MCF_Graph< NodeT, ArcT >::get_node_index ( Node * p ) const

inline

Get node index.

Definition at line 331 of file tpl_multicommodity.H.

References Aleph::DynMapTree< Key, Data, Tree, Compare >::find(), and Aleph::MCF_Graph< NodeT, ArcT >::node_to_idx.

◆ insert_arc()

template<class NodeT = Graph_Anode<Empty_Class>, class ArcT = MCF_Arc<Empty_Class, double>>

Arc * Aleph::MCF_Graph< NodeT, ArcT >::insert_arc	(	Node *	src,
		Node *	tgt,
		Flow_Type	capacity,
		Flow_Type	cost = `0`
	)

inline

Insert arc with capacity and cost.

Overload of insert_arc that sets capacity and cost for flow networks.

Parameters

[in]	src	Source node.
[in]	tgt	Target node.
[in]	capacity	Arc capacity.
[in]	cost	Cost per unit flow.

Returns: Pointer to created arc.

Definition at line 312 of file tpl_multicommodity.H.

References Aleph::MCF_Graph< NodeT, ArcT >::commodities.

Referenced by MultiCommodityTest::build_diamond_network(), MultiCommodityTest::build_parallel_paths(), and MultiCommodityTest::build_single_arc_network().

◆ num_commodities()

template<class NodeT = Graph_Anode<Empty_Class>, class ArcT = MCF_Arc<Empty_Class, double>>

size_t Aleph::MCF_Graph< NodeT, ArcT >::num_commodities ( ) const

inline

Get number of commodities.

Definition at line 265 of file tpl_multicommodity.H.

References Aleph::MCF_Graph< NodeT, ArcT >::commodities.

◆ print_summary()

template<class NodeT = Graph_Anode<Empty_Class>, class ArcT = MCF_Arc<Empty_Class, double>>

void Aleph::MCF_Graph< NodeT, ArcT >::print_summary ( ) const

inline

Print network summary.

Definition at line 381 of file tpl_multicommodity.H.

References Aleph::MCF_Graph< NodeT, ArcT >::commodities, and Aleph::MCF_Graph< NodeT, ArcT >::total_cost().

◆ total_cost()

template<class NodeT = Graph_Anode<Empty_Class>, class ArcT = MCF_Arc<Empty_Class, double>>

Flow_Type Aleph::MCF_Graph< NodeT, ArcT >::total_cost ( ) const

inline

Total flow cost across all commodities.

Definition at line 337 of file tpl_multicommodity.H.

References Aleph::MCF_Graph< NodeT, ArcT >::commodities, Aleph::maps(), Aleph::HTList::size(), and Aleph::sum().

Referenced by Aleph::MCF_Graph< NodeT, ArcT >::print_summary().

Member Data Documentation

◆ commodities

template<class NodeT = Graph_Anode<Empty_Class>, class ArcT = MCF_Arc<Empty_Class, double>>

std::vector<CommodityType> Aleph::MCF_Graph< NodeT, ArcT >::commodities

private

Definition at line 257 of file tpl_multicommodity.H.

Referenced by Aleph::MCF_Graph< NodeT, ArcT >::add_commodity(), Aleph::MCF_Graph< NodeT, ArcT >::demands_satisfied(), Aleph::MCF_Graph< NodeT, ArcT >::get_commodities(), Aleph::MCF_Graph< NodeT, ArcT >::get_commodity(), Aleph::MCF_Graph< NodeT, ArcT >::insert_arc(), Aleph::MCF_Graph< NodeT, ArcT >::num_commodities(), Aleph::MCF_Graph< NodeT, ArcT >::print_summary(), and Aleph::MCF_Graph< NodeT, ArcT >::total_cost().

◆ node_to_idx

template<class NodeT = Graph_Anode<Empty_Class>, class ArcT = MCF_Arc<Empty_Class, double>>

DynMapTree<Node*, size_t> Aleph::MCF_Graph< NodeT, ArcT >::node_to_idx

private

Definition at line 258 of file tpl_multicommodity.H.

Referenced by Aleph::MCF_Graph< NodeT, ArcT >::build_node_index(), and Aleph::MCF_Graph< NodeT, ArcT >::get_node_index().

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

tpl_multicommodity.H

Public Types

Public Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ Arc

◆ Base

◆ CommodityType

◆ Flow_Type

◆ Node

Constructor & Destructor Documentation

◆ MCF_Graph()

Member Function Documentation

◆ add_commodity()

◆ build_node_index()

◆ capacities_respected()

◆ demands_satisfied()

◆ get_commodities()

◆ get_commodity()

◆ get_node_index()

◆ insert_arc()

◆ num_commodities()

◆ print_summary()

◆ total_cost()

Member Data Documentation

◆ commodities

◆ node_to_idx