#include <project.h>

Collaboration diagram for spams::MaxFlow< T >:

Detailed Description

template<typename T>
class spams::MaxFlow< T >

Definition at line 463 of file project.h.

Public Member Functions
void	add_edge (const int u, const int v, const T cu, const T cv)

bool	check_flow ()

void	component_gap (const list_int &component)

void	component_relabelling (const list_int &component, const int max_label, const bool force)

T	compute_thrs_project_l1 (T *X, const int n, const T lambda)

void	deactivate ()

void	deactivate (const list_int &component)

void	discharge (const list_int &component, const int u, const int max_label)

void	extractConnexComponents (std::list< list_int * > &connex_components)

T	flow_component (const list_int &component, const int Ng)

void	gap_relabelling (const list_int &component, const int gap, const int max_label)

T	getMaxFlow () const

void	global_relabelling ()

void	init_split_variables (SpMatrix< T > &splitted_w, const int Ng, const int Nv)

void	init_split_variables_aux (const int node, int &current_counter, Vector< int > &counter_node, list_int **splitted_w, const int Ng, const int Nv)

	MaxFlow (const int N, const int *num_edges, const int s, const int t)

T	norm (const T variables, T work, const T *weights, const int Ng, const bool linf=true)

int	nzmax () const

void	perform_maxflow ()

void	perform_maxflow_component (const list_int &component)

void	print_component (const list_int &component)

void	print_component2 (const list_int &component)

void	print_excess ()

void	print_graph ()

void	print_graph_aux (const int node)

void	print_labels ()

void	print_sink ()

T	project (const list_int &component, const T variables_in, T variables_out, T *work, const int Ng)

T	project_box (const list_int &component, const T variables_in, T variables_out, T *work, bool &fusion, const int Ng)

T	project_weighted (const list_int &component, const T variables_in, T variables_out, T work, const T weights, const int Ng)

void	reset_component (const list_int &component)

void	reset_flow ()

void	restore_capacities (const list_int &component)

void	restore_capacities ()

void	restore_flow ()

void	save_capacities ()

void	save_flow ()

void	scale_flow (const T scal)

void	set_capacities_groups (const list_int &component, const Vector< T > &weights, const T lambda, const int Ng)

void	set_capacities_variables (const T *cap, const int Nv, const int Ng)

void	set_weights (const T lambda)

void	set_weights (const T *weights, const T lambda)

bool	splitComponent (const list_int &component, std::list< list_int * > &connex_components, const int Ng, bool *positive, const bool addpos=true)

void	sub_gradient (const Vector< T > &input, Vector< T > &output, const Vector< T > &weights, const int Ng)

void	sub_gradient_aux (const Vector< T > &input, Vector< T > &output, const Vector< T > &weights, const int node, list_int &list, const int Ng)

void	update_capacities (const list_int &component, T *work)

void	update_capacities_aux (const int node, T *work)

	~MaxFlow ()

Private Attributes
bool *	_active

list_int **	_active_nodes

int *	_all_nodes

T *	_capacity

int *	_children

T *	_copycapacity

T *	_copyexcess

T *	_copyflow

int *	_current_edges

int	_current_max_label

T *	_excess

T *	_flow

int *	_labels

int *	_max_num_edges

int	_N

int *	_num_edges

int	_nzmax

int *	_pr_node

int *	_reverse_address

int	_s

bool *	_seen

int	_t

Constructor & Destructor Documentation

template<typename T >

spams::MaxFlow< T >::MaxFlow	(	const int	N,
		const int *	num_edges,
		const int	s,
		const int	t
	)

Definition at line 565 of file project.h.

References INFINITY.

template<typename T >

spams::MaxFlow< T >::~MaxFlow ( )

Definition at line 600 of file project.h.

Member Function Documentation

template<typename T >

void spams::MaxFlow< T >::add_edge	(	const int	u,
		const int	v,
		const T	cu,
		const T	cv
	)

inline

Definition at line 620 of file project.h.

Referenced by spams::Graph< T >::create_graph().

Here is the caller graph for this function:

template<typename T >

bool spams::MaxFlow< T >::check_flow ( )

inline

Definition at line 835 of file project.h.

References spams::abs(), spams::List< T >::empty(), EPSILON_MAXFLOW, spams::List< T >::front(), spams::List< T >::pop_front(), and spams::List< T >::push_back().

Here is the call graph for this function:

template<typename T>

void spams::MaxFlow< T >::component_gap ( const list_int & component )

inline

template<typename T >

void spams::MaxFlow< T >::component_relabelling	(	const list_int &	component,
		const int	max_label,
		const bool	force
	)

inline

relabel component, with warm restart

discharge source

Definition at line 1657 of file project.h.

References spams::List< T >::begin(), spams::List< T >::empty(), spams::List< T >::end(), EPSILON_MAXFLOW, spams::List< T >::front(), spams::Timer::getElapsed(), spams::List< T >::pop_front(), spams::List< T >::push_back(), spams::List< T >::size(), spams::Timer::start(), and spams::Timer::stop().

Here is the call graph for this function:

template<typename T >

T spams::MaxFlow< T >::compute_thrs_project_l1	(	T *	X,
		const int	n,
		const T	lambda
	)

inline

Definition at line 1842 of file project.h.

References INFINITY, and MAX.

template<typename T >

void spams::MaxFlow< T >::deactivate ( )

inline

Definition at line 742 of file project.h.

template<typename T >

void spams::MaxFlow< T >::deactivate ( const list_int & component )

inline

Definition at line 751 of file project.h.

References spams::List< T >::begin(), and spams::List< T >::end().

Here is the call graph for this function:

template<typename T >

void spams::MaxFlow< T >::discharge	(	const list_int &	component,
		const int	u,
		const int	max_label
	)

inline

add v to the list of active nodes

relabel:

Definition at line 638 of file project.h.

References EPSILON_MAXFLOW, and MIN.

template<typename T >

void spams::MaxFlow< T >::extractConnexComponents ( std::list< list_int * > & connex_components )

inline

extract all the connex components for the initialization

Definition at line 1185 of file project.h.

References spams::List< T >::empty(), spams::List< T >::front(), spams::List< T >::pop_front(), and spams::List< T >::push_back().

Here is the call graph for this function:

template<typename T >

T spams::MaxFlow< T >::flow_component	(	const list_int &	component,
		const int	Ng
	)

inline

do relabelling and update list of active nodes

return the amount of flow

Definition at line 1417 of file project.h.

References spams::List< T >::begin(), and spams::List< T >::end().

Here is the call graph for this function:

template<typename T >

void spams::MaxFlow< T >::gap_relabelling	(	const list_int &	component,
		const int	gap,
		const int	max_label
	)

inline

Definition at line 1638 of file project.h.

References spams::List< T >::begin(), spams::List< T >::end(), spams::Timer::getElapsed(), spams::Timer::start(), and spams::Timer::stop().

Here is the call graph for this function:

template<typename T>

T spams::MaxFlow< T >::getMaxFlow ( ) const

inline

Definition at line 483 of file project.h.

template<typename T >

void spams::MaxFlow< T >::global_relabelling ( )

inline

Definition at line 1152 of file project.h.

References spams::List< T >::empty(), EPSILON_MAXFLOW, spams::List< T >::front(), spams::List< T >::pop_front(), and spams::List< T >::push_back().

Here is the call graph for this function:

template<typename T >

void spams::MaxFlow< T >::init_split_variables	(	SpMatrix< T > &	splitted_w,
		const int	Ng,
		const int	Nv
	)

inline

assumes memory is not an issue

Definition at line 780 of file project.h.

References spams::List< T >::end(), spams::SpMatrix< T >::pB(), spams::SpMatrix< T >::r(), spams::SpMatrix< T >::resize(), spams::List< T >::size(), and spams::SpMatrix< T >::v().

Here is the call graph for this function:

template<typename T >

void spams::MaxFlow< T >::init_split_variables_aux	(	const int	node,
		int &	current_counter,
		Vector< int > &	counter_node,
		list_int **	splitted_w,
		const int	Ng,
		const int	Nv
	)

inline

rempli colonne current de splitted_w avec les enfants + propres variables

Definition at line 1114 of file project.h.

References spams::List< T >::end(), spams::Vector< T >::n(), spams::List< T >::push_back(), and spams::Vector< T >::setZeros().

Here is the call graph for this function:

template<typename T >

T spams::MaxFlow< T >::norm	(	const T *	variables,
		T *	work,
		const T *	weights,
		const int	Ng,
		const bool	linf = `true`
	)

inline

Definition at line 997 of file project.h.

References spams::abs(), spams::List< T >::empty(), spams::List< T >::front(), MAX, spams::List< T >::pop_front(), spams::List< T >::push_back(), and spams::List< T >::push_front().

Here is the call graph for this function:

template<typename T>

int spams::MaxFlow< T >::nzmax ( ) const

inline

Definition at line 530 of file project.h.

template<typename T >

void spams::MaxFlow< T >::perform_maxflow ( )

inline

Definition at line 704 of file project.h.

References EPSILON_MAXFLOW.

template<typename T >

void spams::MaxFlow< T >::perform_maxflow_component ( const list_int & component )

inline

discharge the source and relabel

perform max flow

Definition at line 1579 of file project.h.

References EPSILON_MAXFLOW, PRINT_I, spams::List< T >::size(), spams::Timer::start(), spams::stop(), and spams::Timer::stop().

Here is the call graph for this function:

template<typename T >

void spams::MaxFlow< T >::print_component ( const list_int & component )

inline

Definition at line 918 of file project.h.

References spams::List< T >::begin(), and spams::List< T >::end().

Here is the call graph for this function:

template<typename T >

void spams::MaxFlow< T >::print_component2 ( const list_int & component )

inline

Definition at line 1054 of file project.h.

References spams::List< T >::begin(), and spams::List< T >::end().

Here is the call graph for this function:

template<typename T >

void spams::MaxFlow< T >::print_excess ( )

inline

Definition at line 731 of file project.h.

template<typename T >

void spams::MaxFlow< T >::print_graph ( )

inline

Definition at line 771 of file project.h.

template<typename T >

void spams::MaxFlow< T >::print_graph_aux ( const int node )

inline

Definition at line 1081 of file project.h.

template<typename T >

void spams::MaxFlow< T >::print_labels ( )

inline

Definition at line 762 of file project.h.

template<typename T >

void spams::MaxFlow< T >::print_sink ( )

inline

Definition at line 904 of file project.h.

template<typename T >

T spams::MaxFlow< T >::project	(	const list_int &	component,
		const T *	variables_in,
		T *	variables_out,
		T *	work,
		const int	Ng
	)

inline

project on the component, project, update the capacity, update the preflow, update variables_out, update labels return the maximum value of the potential flow

Definition at line 1260 of file project.h.

References spams::List< T >::begin(), spams::List< T >::end(), and MIN.

Here is the call graph for this function:

template<typename T >

T spams::MaxFlow< T >::project_box	(	const list_int &	component,
		const T *	variables_in,
		T *	variables_out,
		T *	work,
		bool &	fusion,
		const int	Ng
	)

inline

Definition at line 1301 of file project.h.

References spams::List< T >::begin(), spams::List< T >::empty(), spams::List< T >::end(), spams::List< T >::front(), INFINITY, MAX, MIN, spams::List< T >::pop_front(), spams::List< T >::push_back(), and spams::List< T >::push_front().

Here is the call graph for this function:

template<typename T >

T spams::MaxFlow< T >::project_weighted	(	const list_int &	component,
		const T *	variables_in,
		T *	variables_out,
		T *	work,
		const T *	weights,
		const int	Ng
	)

inline

Definition at line 1217 of file project.h.

References spams::List< T >::begin(), spams::List< T >::end(), spams::Vector< T >::l1project_weighted(), spams::Vector< T >::setn(), and spams::List< T >::size().

Here is the call graph for this function:

template<typename T >

void spams::MaxFlow< T >::reset_component ( const list_int & component )

inline

Definition at line 1566 of file project.h.

References spams::List< T >::begin(), and spams::List< T >::end().

Here is the call graph for this function:

template<typename T >

void spams::MaxFlow< T >::reset_flow ( )

inline

Definition at line 875 of file project.h.

References INFINITY.

template<typename T >

void spams::MaxFlow< T >::restore_capacities ( const list_int & component )

inline

relabel component, with warm restart

Definition at line 1817 of file project.h.

References spams::List< T >::begin(), spams::List< T >::end(), and INFINITY.

Here is the call graph for this function:

template<typename T >

void spams::MaxFlow< T >::restore_capacities ( )

inline

Definition at line 830 of file project.h.

template<typename T >

void spams::MaxFlow< T >::restore_flow ( )

inline

Definition at line 821 of file project.h.

template<typename T >

void spams::MaxFlow< T >::save_capacities ( )

inline

Definition at line 810 of file project.h.

template<typename T >

void spams::MaxFlow< T >::save_flow ( )

inline

Definition at line 814 of file project.h.

template<typename T >

void spams::MaxFlow< T >::scale_flow ( const T scal )

inline

Definition at line 882 of file project.h.

References INFINITY.

template<typename T >

void spams::MaxFlow< T >::set_capacities_groups	(	const list_int &	component,
		const Vector< T > &	weights,
		const T	lambda,
		const int	Ng
	)

inline

Definition at line 1805 of file project.h.

References spams::List< T >::begin(), and spams::List< T >::end().

Here is the call graph for this function:

template<typename T >

void spams::MaxFlow< T >::set_capacities_variables	(	const T *	cap,
		const int	Nv,
		const int	Ng
	)

inline

Definition at line 1796 of file project.h.

References spams::abs().

Here is the call graph for this function:

template<typename T >

void spams::MaxFlow< T >::set_weights ( const T lambda )

inline

Definition at line 889 of file project.h.

template<typename T >

void spams::MaxFlow< T >::set_weights	(	const T *	weights,
		const T	lambda
	)

inline

Definition at line 896 of file project.h.

template<typename T >

bool spams::MaxFlow< T >::splitComponent	(	const list_int &	component,
		std::list< list_int * > &	connex_components,
		const int	Ng,
		bool *	positive,
		const bool	addpos = `true`
	)

inline

cut the component into connex components, and add them to connex_components

make the "positive part of the graph"

start new component, track from where the excess can come

update from the source

extract the connex components of the positive part

start new component, track from where the excess can come

extract the connex components of the negative part

start new component, track from where the excess can come

Definition at line 1437 of file project.h.

References spams::List< T >::begin(), spams::List< T >::empty(), spams::List< T >::end(), EPSILON_MAXFLOW, spams::List< T >::front(), spams::List< T >::pop_front(), and spams::List< T >::push_back().

Here is the call graph for this function:

template<typename T >

void spams::MaxFlow< T >::sub_gradient	(	const Vector< T > &	input,
		Vector< T > &	output,
		const Vector< T > &	weights,
		const int	Ng
	)

inline

Definition at line 979 of file project.h.

References spams::List< T >::empty(), spams::List< T >::front(), spams::List< T >::pop_front(), spams::List< T >::push_back(), and spams::Vector< T >::setZeros().

Here is the call graph for this function:

template<typename T >

void spams::MaxFlow< T >::sub_gradient_aux	(	const Vector< T > &	input,
		Vector< T > &	output,
		const Vector< T > &	weights,
		const int	node,
		list_int &	list,
		const int	Ng
	)

inline

Definition at line 941 of file project.h.

References spams::List< T >::begin(), spams::List< T >::end(), spams::List< T >::fusion(), spams::List< T >::push_back(), and spams::List< T >::size().

Here is the call graph for this function:

template<typename T >

void spams::MaxFlow< T >::update_capacities	(	const list_int &	component,
		T *	work
	)

inline

Definition at line 1742 of file project.h.

References spams::List< T >::begin(), spams::List< T >::empty(), spams::List< T >::end(), spams::List< T >::front(), MAX, spams::List< T >::pop_front(), spams::List< T >::push_back(), and spams::List< T >::push_front().

Here is the call graph for this function:

template<typename T>

void spams::MaxFlow< T >::update_capacities_aux	(	const int	node,
		T *	work
	)

inline

Member Data Documentation

template<typename T>

bool* spams::MaxFlow< T >::_active

private

Definition at line 544 of file project.h.

template<typename T>

list_int** spams::MaxFlow< T >::_active_nodes

private

Definition at line 560 of file project.h.

template<typename T>

int* spams::MaxFlow< T >::_all_nodes

private

Definition at line 561 of file project.h.

template<typename T>

T* spams::MaxFlow< T >::_capacity

private

Definition at line 554 of file project.h.

template<typename T>

int* spams::MaxFlow< T >::_children

private

Definition at line 552 of file project.h.

template<typename T>

T* spams::MaxFlow< T >::_copycapacity

private

Definition at line 555 of file project.h.

template<typename T>

T* spams::MaxFlow< T >::_copyexcess

private

Definition at line 542 of file project.h.

template<typename T>

T* spams::MaxFlow< T >::_copyflow

private

Definition at line 557 of file project.h.

template<typename T>

int* spams::MaxFlow< T >::_current_edges

private

Definition at line 547 of file project.h.

template<typename T>

int spams::MaxFlow< T >::_current_max_label

private

Definition at line 559 of file project.h.

template<typename T>

T* spams::MaxFlow< T >::_excess

private

Definition at line 541 of file project.h.

template<typename T>

T* spams::MaxFlow< T >::_flow

private

Definition at line 556 of file project.h.

template<typename T>

int* spams::MaxFlow< T >::_labels

private

Definition at line 540 of file project.h.

template<typename T>

int* spams::MaxFlow< T >::_max_num_edges

private

Definition at line 546 of file project.h.

template<typename T>

int spams::MaxFlow< T >::_N

private

Definition at line 536 of file project.h.

template<typename T>

int* spams::MaxFlow< T >::_num_edges

private

Definition at line 548 of file project.h.

template<typename T>

int spams::MaxFlow< T >::_nzmax

private

Definition at line 550 of file project.h.

template<typename T>

int* spams::MaxFlow< T >::_pr_node

private

Definition at line 549 of file project.h.

template<typename T>

int* spams::MaxFlow< T >::_reverse_address

private

Definition at line 553 of file project.h.

template<typename T>

int spams::MaxFlow< T >::_s

private

Definition at line 537 of file project.h.

template<typename T>

bool* spams::MaxFlow< T >::_seen

private

Definition at line 543 of file project.h.

template<typename T>

int spams::MaxFlow< T >::_t

private

Definition at line 538 of file project.h.

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

ThirdParty/Spams/include/project.h

Detailed Description

template<typename T> class spams::MaxFlow< T >

Public Member Functions

Private Attributes

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<typename T>
class spams::MaxFlow< T >