solve network flow graph with min-cost flow More...

#include <Lgf.h>

Public Types

typedef T	value_type
typedef value_type	cost_type
typedef lemon::SmartDigraph	graph_type
typedef graph_type::Node	node_type
typedef graph_type::Arc	arc_type
typedef graph_type::NodeMap< value_type >	node_value_map_type
typedef graph_type::NodeMap< string >	node_name_map_type
typedef graph_type::ArcMap< value_type >	arc_value_map_type
typedef graph_type::ArcMap< value_type >	arc_cost_map_type
typedef graph_type::ArcMap< value_type >	arc_flow_map_type
typedef graph_type::NodeMap< value_type >	node_pot_map_type
typedef lemon::NetworkSimplex< graph_type, value_type, cost_type >	alg_network_simplex_type
typedef lemon::CostScaling< graph_type, value_type, cost_type >	alg_cost_scaling_type
typedef alg_cost_scaling_type	alg_type

Public Member Functions
	Lgf ()
	constructor
virtual	~Lgf ()
	destructor
alg_type::ProblemType	operator() (string const &filename)
	API to run the algorithm.
virtual void	print_graph (string const &filename) const
	print graph
virtual void	print_solution (string const &filename) const
	print solution
void	read_lgf (string const &lgfFile)
	read input file in .lgf format and initialize graph

Protected Member Functions
alg_type::ProblemType	run ()
	run algorithm

Protected Attributes
graph_type	m_graph
	input graph
arc_value_map_type	m_hLower
	lower bound of flow, usually zero
arc_value_map_type	m_hUpper
	upper bound of flow, arc capacity in mcf
arc_cost_map_type	m_hCost
	arc cost in mcf
node_value_map_type	m_hSupply
	node supply in mcf
node_name_map_type	m_hName
	node name in mcf
cost_type	m_totalcost
	total cost after solving
arc_flow_map_type	m_hFlow
	solution of min-cost flow, which is the dual solution of LP
node_pot_map_type	m_hPot
	dual solution of min-cost flow, which is the solution of LP

Detailed Description

template<typename T>
class limbo::solvers::lpmcf::Lgf< T >

solve network flow graph with min-cost flow

Template Parameters

T data type

Definition at line 54 of file Lgf.h.

Member Typedef Documentation

◆ alg_cost_scaling_type

template<typename T>

typedef lemon::CostScaling<graph_type, value_type, cost_type> limbo::solvers::lpmcf::Lgf< T >::alg_cost_scaling_type

Definition at line 73 of file Lgf.h.

◆ alg_network_simplex_type

template<typename T>

typedef lemon::NetworkSimplex<graph_type, value_type, cost_type> limbo::solvers::lpmcf::Lgf< T >::alg_network_simplex_type

Definition at line 72 of file Lgf.h.

◆ alg_type

template<typename T>

typedef alg_cost_scaling_type limbo::solvers::lpmcf::Lgf< T >::alg_type

Definition at line 78 of file Lgf.h.

◆ arc_cost_map_type

template<typename T>

typedef graph_type::ArcMap<value_type> limbo::solvers::lpmcf::Lgf< T >::arc_cost_map_type

Definition at line 67 of file Lgf.h.

◆ arc_flow_map_type

template<typename T>

typedef graph_type::ArcMap<value_type> limbo::solvers::lpmcf::Lgf< T >::arc_flow_map_type

Definition at line 68 of file Lgf.h.

◆ arc_type

template<typename T>

typedef graph_type::Arc limbo::solvers::lpmcf::Lgf< T >::arc_type

Definition at line 63 of file Lgf.h.

◆ arc_value_map_type

template<typename T>

typedef graph_type::ArcMap<value_type> limbo::solvers::lpmcf::Lgf< T >::arc_value_map_type

Definition at line 66 of file Lgf.h.

◆ cost_type

template<typename T>

typedef value_type limbo::solvers::lpmcf::Lgf< T >::cost_type

Definition at line 60 of file Lgf.h.

◆ graph_type

template<typename T>

typedef lemon::SmartDigraph limbo::solvers::lpmcf::Lgf< T >::graph_type

Definition at line 61 of file Lgf.h.

◆ node_name_map_type

template<typename T>

typedef graph_type::NodeMap<string> limbo::solvers::lpmcf::Lgf< T >::node_name_map_type

Definition at line 65 of file Lgf.h.

◆ node_pot_map_type

template<typename T>

typedef graph_type::NodeMap<value_type> limbo::solvers::lpmcf::Lgf< T >::node_pot_map_type

Definition at line 69 of file Lgf.h.

◆ node_type

template<typename T>

typedef graph_type::Node limbo::solvers::lpmcf::Lgf< T >::node_type

Definition at line 62 of file Lgf.h.

◆ node_value_map_type

template<typename T>

typedef graph_type::NodeMap<value_type> limbo::solvers::lpmcf::Lgf< T >::node_value_map_type

Definition at line 64 of file Lgf.h.

◆ value_type

template<typename T>

typedef T limbo::solvers::lpmcf::Lgf< T >::value_type

Definition at line 59 of file Lgf.h.

Constructor & Destructor Documentation

◆ Lgf()

template<typename T>

limbo::solvers::lpmcf::Lgf< T >::Lgf ( )

inline

constructor

Definition at line 82 of file Lgf.h.

◆ ~Lgf()

template<typename T>

virtual limbo::solvers::lpmcf::Lgf< T >::~Lgf ( )

inlinevirtual

destructor

Definition at line 95 of file Lgf.h.

Member Function Documentation

◆ operator()()

template<typename T>

alg_type::ProblemType limbo::solvers::lpmcf::Lgf< T >::operator() ( string const & filename )

inline

API to run the algorithm.

Parameters

filename input file in .lgf format

Definition at line 99 of file Lgf.h.

◆ print_graph()

template<typename T>

virtual void limbo::solvers::lpmcf::Lgf< T >::print_graph ( string const & filename ) const

inlinevirtual

print graph

Parameters

filename output file in .lgf format

Definition at line 112 of file Lgf.h.

◆ print_solution()

template<typename T>

virtual void limbo::solvers::lpmcf::Lgf< T >::print_solution ( string const & filename ) const

inlinevirtual

print solution

Parameters

filename output file name

Reimplemented in limbo::solvers::lpmcf::LpDualMcf< T >.

Definition at line 170 of file Lgf.h.

◆ read_lgf()

template<typename T>

void limbo::solvers::lpmcf::Lgf< T >::read_lgf ( string const & lgfFile )

inline

read input file in .lgf format and initialize graph

Parameters

lgfFile input file name

Definition at line 197 of file Lgf.h.

◆ run()

template<typename T>

alg_type::ProblemType limbo::solvers::lpmcf::Lgf< T >::run ( )

inlineprotected

run algorithm

Returns: solving status: OPTIMAL, INFEASIBLE, or UNBOUNDED

Definition at line 210 of file Lgf.h.

Member Data Documentation

◆ m_graph

template<typename T>

graph_type limbo::solvers::lpmcf::Lgf< T >::m_graph

protected

input graph

Definition at line 254 of file Lgf.h.

◆ m_hCost

template<typename T>

arc_cost_map_type limbo::solvers::lpmcf::Lgf< T >::m_hCost

protected

arc cost in mcf

Definition at line 257 of file Lgf.h.

◆ m_hFlow

template<typename T>

arc_flow_map_type limbo::solvers::lpmcf::Lgf< T >::m_hFlow

protected

solution of min-cost flow, which is the dual solution of LP

Definition at line 262 of file Lgf.h.

◆ m_hLower

template<typename T>

arc_value_map_type limbo::solvers::lpmcf::Lgf< T >::m_hLower

protected

lower bound of flow, usually zero

Definition at line 255 of file Lgf.h.

◆ m_hName

template<typename T>

node_name_map_type limbo::solvers::lpmcf::Lgf< T >::m_hName

protected

node name in mcf

Definition at line 259 of file Lgf.h.

◆ m_hPot

template<typename T>

node_pot_map_type limbo::solvers::lpmcf::Lgf< T >::m_hPot

protected

dual solution of min-cost flow, which is the solution of LP

Definition at line 263 of file Lgf.h.

◆ m_hSupply

template<typename T>

node_value_map_type limbo::solvers::lpmcf::Lgf< T >::m_hSupply

protected

node supply in mcf

Definition at line 258 of file Lgf.h.

◆ m_hUpper

template<typename T>

arc_value_map_type limbo::solvers::lpmcf::Lgf< T >::m_hUpper

protected

upper bound of flow, arc capacity in mcf

Definition at line 256 of file Lgf.h.

◆ m_totalcost

template<typename T>

cost_type limbo::solvers::lpmcf::Lgf< T >::m_totalcost

protected

total cost after solving

Definition at line 260 of file Lgf.h.

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

/home/abuild/rpmbuild/BUILD/limbo-3.5.4-build/limbo-3.5.4/limbo/solvers/lpmcf/Lgf.h

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ alg_cost_scaling_type

◆ alg_network_simplex_type

◆ alg_type

◆ arc_cost_map_type

◆ arc_flow_map_type

◆ arc_type

◆ arc_value_map_type

◆ cost_type

◆ graph_type

◆ node_name_map_type

◆ node_pot_map_type

◆ node_type

◆ node_value_map_type

◆ value_type

Constructor & Destructor Documentation

◆ Lgf()

◆ ~Lgf()

Member Function Documentation

◆ operator()()

◆ print_graph()

◆ print_solution()

◆ read_lgf()

◆ run()

Member Data Documentation

◆ m_graph

◆ m_hCost

◆ m_hFlow

◆ m_hLower

◆ m_hName

◆ m_hPot

◆ m_hSupply

◆ m_hUpper

◆ m_totalcost