spams::MinCostFlow< Int > Class Template Reference

#include <project.h>

Inheritance diagram for spams::MinCostFlow< Int >:

Collaboration diagram for spams::MinCostFlow< Int >:

Detailed Description

template<typename Int = long long>
class spams::MinCostFlow< Int >

Definition at line 2278 of file project.h.

Public Member Functions
void	add_edge (const int u, const int v, const Int cost, const double double_cost, const Int cap)
void	add_flow (const int node, const int num_arc, const Int flow)
Int	compute_cost () const
double	compute_cost_double () const
void	compute_min_cost (const bool scale_data=true, const bool verbose=false)
Int	compute_uncap_cost () const
Int	cost_shortest_path_in_dag (list_int &path)
void	discharge (const int node, const Int eps)
Int	get_flow (const int node, const int num_arc) const
	MinCostFlow (const int n, const int *max_num_arcs)
bool	price_refine (const Int eps)
void	price_update (const Int eps)
void	print_dimacs (const char *name) const
void	print_excess () const
void	print_graph () const
void	print_prices () const
Int	reduced_cost (const int node, const int child, const int arc) const
Int	refine (Int eps, const bool price_refine=false)
void	restore_costs ()
void	save_costs ()
void	scale_costs (const double scal)
void	set_capacity (const int node, const int num_arc, const Int cap)
void	set_demand (const int node, const Int dem)
void	set_edge (const int node, const int num_arc, const Int cost, const Int cap)
void	set_is_quad_cost (const bool is_quad_cost)
void	set_quad_cost (const int node, const int num_arc, const bool quad_cost)
void	st_flow_decomposition_dag (List< Path< Int > * > &list, const int s, const int t) const
bool	test_optimality_conditions () const
bool	topological_sort (const bool admissible=false, bool *admiss=NULL, Int *rcosts=NULL)
	~MinCostFlow ()

Private Attributes
bool *	_active
double	_alpha
Int *	_capacity
int *	_children
Int *	_cost
Int *	_demand
Int *	_excess
Int *	_flow
double *	_init_double_cost
bool	_is_quadratic_cost
list_int	_list_active
int	_m
Int	_max_cost
int *	_max_num_arcs
int	_maxm
int	_n
int *	_num_arcs
int *	_pr_node
Int *	_prices
bool *	_quad_cost
int *	_reverse
Int *	_save_cost
Timer	_time1
Timer	_time2
int *	_topological_order
bool	_topologically_sorted

Constructor & Destructor Documentation

template<typename Int >

spams::MinCostFlow< Int >::MinCostFlow	(	const int	n,
		const int *	max_num_arcs
	)

Definition at line 2355 of file project.h.

template<typename Int >

spams::MinCostFlow< Int >::~MinCostFlow

(

)

Definition at line 2403 of file project.h.

Member Function Documentation

template<typename Int>

void spams::MinCostFlow< Int >::add_edge ( const int  u, const int  v, const Int  cost, const double  double_cost, const Int  cap  )

inline

Definition at line 2423 of file project.h.

template<typename Int>

void spams::MinCostFlow< Int >::add_flow ( const int  node, const int  num_arc, const Int  flow  )

inline

Definition at line 2463 of file project.h.

template<typename Int >

Int spams::MinCostFlow< Int >::compute_cost

(

)

const

Definition at line 2765 of file project.h.

template<typename Int >

double spams::MinCostFlow< Int >::compute_cost_double

(

)

const

Definition at line 2778 of file project.h.

template<typename Int >

void spams::MinCostFlow< Int >::compute_min_cost	(	const bool	scale_data = true,
		const bool	verbose = false
	)

Definition at line 2488 of file project.h.

References spams::Timer::printElapsed(), spams::Timer::reset(), spams::Timer::start(), and spams::Timer::stop().

Here is the call graph for this function:

template<typename Int >

Int spams::MinCostFlow< Int >::compute_uncap_cost

(

)

const

Definition at line 2792 of file project.h.

template<typename Int >

Int spams::MinCostFlow< Int >::cost_shortest_path_in_dag

(

list_int &

path

)

Definition at line 2894 of file project.h.

References spams::List< T >::clear(), utl::max(), and spams::List< T >::push_front().

Here is the call graph for this function:

template<typename Int>

void spams::MinCostFlow< Int >::discharge ( const int  node, const Int  eps  )

inline

Definition at line 2680 of file project.h.

References MAX, utl::max(), and MIN.

Here is the call graph for this function:

template<typename Int = long long>

Int spams::MinCostFlow< Int >::get_flow ( const int  node, const int  num_arc  ) const

inline

Definition at line 2301 of file project.h.

template<typename Int>

bool spams::MinCostFlow< Int >::price_refine

(

const Int

eps

)

Definition at line 2801 of file project.h.

References spams::BinaryHeap< T >::decrease_key(), spams::BinaryHeap< T >::delete_min(), spams::BinaryHeap< T >::find_min(), spams::BinaryHeap< T >::insert(), spams::BinaryHeap< T >::is_empty(), utl::max(), spams::Timer::start(), and spams::Timer::stop().

Here is the call graph for this function:

template<typename Int>

void spams::MinCostFlow< Int >::price_update ( const Int  eps )

inline

Definition at line 2597 of file project.h.

References spams::BinaryHeap< T >::decrease_key(), spams::BinaryHeap< T >::delete_min(), spams::BinaryHeap< T >::find_min(), spams::BinaryHeap< T >::insert(), spams::BinaryHeap< T >::is_empty(), utl::max(), spams::Timer::start(), and spams::Timer::stop().

Here is the call graph for this function:

template<typename Int >

void spams::MinCostFlow< Int >::print_dimacs

(

const char *

name

)

const

Definition at line 2983 of file project.h.

template<typename Int >

void spams::MinCostFlow< Int >::print_excess ( ) const

inline

Definition at line 3081 of file project.h.

template<typename Int >

void spams::MinCostFlow< Int >::print_graph ( ) const

inline

Definition at line 3099 of file project.h.

template<typename Int >

void spams::MinCostFlow< Int >::print_prices ( ) const

inline

Definition at line 3090 of file project.h.

template<typename Int >

Int spams::MinCostFlow< Int >::reduced_cost ( const int  node, const int  child, const int  arc  ) const

inline

Definition at line 3004 of file project.h.

template<typename Int>

Int spams::MinCostFlow< Int >::refine	(	Int	eps,
		const bool	price_refine = false
	)

Definition at line 2542 of file project.h.

References MIN.

template<typename Int >

void spams::MinCostFlow< Int >::restore_costs

(

)

Definition at line 2475 of file project.h.

template<typename Int >

void spams::MinCostFlow< Int >::save_costs

(

)

Definition at line 2470 of file project.h.

template<typename Int >

void spams::MinCostFlow< Int >::scale_costs

(

const double

scal

)

Definition at line 2480 of file project.h.

template<typename Int>

void spams::MinCostFlow< Int >::set_capacity ( const int  node, const int  num_arc, const Int  cap  )

inline

Definition at line 2454 of file project.h.

template<typename Int = long long>

void spams::MinCostFlow< Int >::set_demand ( const int  node, const Int  dem  )

inline

Definition at line 2285 of file project.h.

template<typename Int>

void spams::MinCostFlow< Int >::set_edge ( const int  node, const int  num_arc, const Int  cost, const Int  cap  )

inline

Definition at line 2443 of file project.h.

template<typename Int = long long>

void spams::MinCostFlow< Int >::set_is_quad_cost ( const bool  is_quad_cost )

inline

Definition at line 2293 of file project.h.

template<typename Int = long long>

void spams::MinCostFlow< Int >::set_quad_cost ( const int  node, const int  num_arc, const bool  quad_cost  )

inline

Definition at line 2289 of file project.h.

template<typename Int>

void spams::MinCostFlow< Int >::st_flow_decomposition_dag	(	List< Path< Int > * > &	list,
		const int	s,
		const int	t
	)		const

Definition at line 2930 of file project.h.

References spams::List< T >::begin(), spams::BinaryHeap< T >::delete_min(), spams::List< T >::end(), spams::BinaryHeap< T >::find_min(), spams::Path< Int >::flow_int, spams::BinaryHeap< T >::insert(), spams::BinaryHeap< T >::is_empty(), MIN, spams::Path< Int >::nodes, and spams::List< T >::push_back().

Here is the call graph for this function:

template<typename Int >

bool spams::MinCostFlow< Int >::test_optimality_conditions

(

)

const

Definition at line 2746 of file project.h.

References MIN.

template<typename Int>

bool spams::MinCostFlow< Int >::topological_sort ( const bool  admissible = false, bool *  admiss = NULL, Int *  rcosts = NULL  )

inline

the function assumes the graph is a DAG

Definition at line 3011 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:

Member Data Documentation

template<typename Int = long long>

bool* spams::MinCostFlow< Int >::_active

private

Definition at line 2330 of file project.h.

template<typename Int = long long>

double spams::MinCostFlow< Int >::_alpha

private

Definition at line 2325 of file project.h.

template<typename Int = long long>

Int* spams::MinCostFlow< Int >::_capacity

private

Definition at line 2338 of file project.h.

template<typename Int = long long>

int* spams::MinCostFlow< Int >::_children

private

Definition at line 2335 of file project.h.

template<typename Int = long long>

Int* spams::MinCostFlow< Int >::_cost

private

Definition at line 2339 of file project.h.

template<typename Int = long long>

Int* spams::MinCostFlow< Int >::_demand

private

Definition at line 2329 of file project.h.

template<typename Int = long long>

Int* spams::MinCostFlow< Int >::_excess

private

Definition at line 2328 of file project.h.

template<typename Int = long long>

Int* spams::MinCostFlow< Int >::_flow

private

Definition at line 2337 of file project.h.

template<typename Int = long long>

double* spams::MinCostFlow< Int >::_init_double_cost

private

Definition at line 2341 of file project.h.

template<typename Int = long long>

bool spams::MinCostFlow< Int >::_is_quadratic_cost

private

Definition at line 2348 of file project.h.

template<typename Int = long long>

list_int spams::MinCostFlow< Int >::_list_active

private

Definition at line 2347 of file project.h.

template<typename Int = long long>

int spams::MinCostFlow< Int >::_m

private

Definition at line 2322 of file project.h.

template<typename Int = long long>

Int spams::MinCostFlow< Int >::_max_cost

private

Definition at line 2324 of file project.h.

template<typename Int = long long>

int* spams::MinCostFlow< Int >::_max_num_arcs

private

Definition at line 2333 of file project.h.

template<typename Int = long long>

int spams::MinCostFlow< Int >::_maxm

private

Definition at line 2342 of file project.h.

template<typename Int = long long>

int spams::MinCostFlow< Int >::_n

private

Definition at line 2321 of file project.h.

template<typename Int = long long>

int* spams::MinCostFlow< Int >::_num_arcs

private

Definition at line 2332 of file project.h.

template<typename Int = long long>

int* spams::MinCostFlow< Int >::_pr_node

private

Definition at line 2334 of file project.h.

template<typename Int = long long>

Int* spams::MinCostFlow< Int >::_prices

private

Definition at line 2327 of file project.h.

template<typename Int = long long>

bool* spams::MinCostFlow< Int >::_quad_cost

private

Definition at line 2349 of file project.h.

template<typename Int = long long>

int* spams::MinCostFlow< Int >::_reverse

private

Definition at line 2336 of file project.h.

template<typename Int = long long>

Int* spams::MinCostFlow< Int >::_save_cost

private

Definition at line 2340 of file project.h.

template<typename Int = long long>

Timer spams::MinCostFlow< Int >::_time1

private

Definition at line 2350 of file project.h.

template<typename Int = long long>

Timer spams::MinCostFlow< Int >::_time2

private

Definition at line 2351 of file project.h.

template<typename Int = long long>

int* spams::MinCostFlow< Int >::_topological_order

private

Definition at line 2344 of file project.h.

template<typename Int = long long>

bool spams::MinCostFlow< Int >::_topologically_sorted

private

Definition at line 2345 of file project.h.

---

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

• ThirdParty/Spams/include/project.h