Augmenting-path search over a directed network. More...

#include <tpl_net.H>

Collaboration diagram for Aleph::Find_Aumenting_Path< Net, Q >:

Public Member Functions
SemiPath< Net >	find_aum_path (typename Net::Flow_Type min_slack=0.0)
	Find an augmenting semi-path with at least `min_slack`.

SemiPath< Net >	find_dec_path (typename Net::Flow_Type min_slack=0.0)
	Find a decrementing semi-path with at least `min_slack`.

	Find_Aumenting_Path (const Net &__g)
	Construct a finder for `net`.

Path< Net >	operator() (typename Net::Node start, typename Net::Node end, typename Net::Flow_Type min_slack=0)
	Find a concrete Path with at least `min_slack`.

SemiPath< Net >	operator() (typename Net::Flow_Type min_slack=0)
	Find an augmenting semi-path from the network source to sink.

Net::Flow_Type	semi_path (typename Net::Node start, typename Net::Node end, DynList< Parc< Net > > &semi_path, const typename Net::Flow_Type &min_slack=0)
	Fill `semi_path` and return the slack value.

Private Member Functions
Net::Node *	search (typename Net::Node start, typename Net::Node end, typename Net::Flow_Type min_slack)

Path< Net >	find (typename Net::Node start, typename Net::Node end, const typename Net::Flow_Type &min_slack=typename Net::Flow_Type{0})
	Build a Path from `start` to `end` with minimum slack.

SemiPath< Net >	find_path (typename Net::Node start, typename Net::Node end, typename Net::Flow_Type min_slack=typename Net::Flow_Type{0})
	Build a SemiPath from `start` to `end` with minimum slack.

Private Attributes
const Net &	net

Detailed Description

template<class Net, template< typename T > class Q>
class Aleph::Find_Aumenting_Path< Net, Q >

Augmenting-path search over a directed network.

The network is modeled with a graph class (not a digraph class).

Definition at line 1024 of file tpl_net.H.

Constructor & Destructor Documentation

◆ Find_Aumenting_Path()

template<class Net , template< typename T > class Q>

Aleph::Find_Aumenting_Path< Net, Q >::Find_Aumenting_Path ( const Net & __g )

inline

Construct a finder for net.

Definition at line 1183 of file tpl_net.H.

Member Function Documentation

◆ find()

template<class Net , template< typename T > class Q>

Path< Net > Aleph::Find_Aumenting_Path< Net, Q >::find	(	typename Net::Node *	start,
		typename Net::Node *	end,
		const typename Net::Flow_Type &	min_slack = `typename Net::Flow_Type{0}`
	)

inlineprivate

Build a Path from start to end with minimum slack.

Definition at line 1099 of file tpl_net.H.

Referenced by Aleph::Find_Aumenting_Path< Net, Q >::operator()().

◆ find_aum_path()

template<class Net , template< typename T > class Q>

SemiPath< Net > Aleph::Find_Aumenting_Path< Net, Q >::find_aum_path ( typename Net::Flow_Type min_slack = 0.0 )

inline

Find an augmenting semi-path with at least min_slack.

Definition at line 1171 of file tpl_net.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Find_Aumenting_Path< Net, Q >::find_path(), Aleph::Net_Graph< NodeT, ArcT >::get_sink(), Aleph::Net_Graph< NodeT, ArcT >::get_source(), and Aleph::Find_Aumenting_Path< Net, Q >::net.

Referenced by Aleph::Find_Aumenting_Path< Net, Q >::operator()().

◆ find_dec_path()

template<class Net , template< typename T > class Q>

SemiPath< Net > Aleph::Find_Aumenting_Path< Net, Q >::find_dec_path ( typename Net::Flow_Type min_slack = 0.0 )

inline

Find a decrementing semi-path with at least min_slack.

Definition at line 1177 of file tpl_net.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Find_Aumenting_Path< Net, Q >::find_path(), Aleph::Net_Graph< NodeT, ArcT >::get_sink(), Aleph::Net_Graph< NodeT, ArcT >::get_source(), and Aleph::Find_Aumenting_Path< Net, Q >::net.

◆ find_path()

template<class Net , template< typename T > class Q>

SemiPath< Net > Aleph::Find_Aumenting_Path< Net, Q >::find_path	(	typename Net::Node *	start,
		typename Net::Node *	end,
		typename Net::Flow_Type	min_slack = `typename Net::Flow_Type{0}`
	)

inlineprivate

Build a SemiPath from start to end with minimum slack.

Definition at line 1121 of file tpl_net.H.

Referenced by Aleph::Find_Aumenting_Path< Net, Q >::find_aum_path(), Aleph::Find_Aumenting_Path< Net, Q >::find_dec_path(), and Aleph::Find_Aumenting_Path< Net, Q >::semi_path().

◆ operator()() [1/2]

template<class Net , template< typename T > class Q>

SemiPath< Net > Aleph::Find_Aumenting_Path< Net, Q >::operator() ( typename Net::Flow_Type min_slack = 0 )

inline

Find an augmenting semi-path from the network source to sink.

Definition at line 1197 of file tpl_net.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Find_Aumenting_Path< Net, Q >::find_aum_path().

◆ operator()() [2/2]

template<class Net , template< typename T > class Q>

Path< Net > Aleph::Find_Aumenting_Path< Net, Q >::operator()	(	typename Net::Node *	start,
		typename Net::Node *	end,
		typename Net::Flow_Type	min_slack = `0`
	)

inline

Find a concrete Path with at least min_slack.

Definition at line 1189 of file tpl_net.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Find_Aumenting_Path< Net, Q >::find().

◆ search()

template<class Net , template< typename T > class Q>

Net::Node * Aleph::Find_Aumenting_Path< Net, Q >::search	(	typename Net::Node *	start,
		typename Net::Node *	end,
		typename Net::Flow_Type	min_slack
	)

inlineprivate

Definition at line 1029 of file tpl_net.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), GraphCommon< GT, Node, Arc >::get_connected_node(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::Find_Aumenting_Path< Net, Q >::net, NODE_COOKIE, Aleph::Processed, Aleph::Processing, GraphCommon< GT, Node, Arc >::reset_arcs(), GraphCommon< GT, Node, Arc >::reset_nodes(), and Aleph::Unprocessed.

◆ semi_path()

template<class Net , template< typename T > class Q>

Net::Flow_Type Aleph::Find_Aumenting_Path< Net, Q >::semi_path	(	typename Net::Node *	start,
		typename Net::Node *	end,
		DynList< Parc< Net > > &	semi_path,
		const typename Net::Flow_Type &	min_slack = `0`
	)