#include <network_flow.hpp>

Collaboration diagram for network_flow:

Data Structures
struct	nf_balance_t

struct	nf_capacity_t

struct	nf_cost_t
	edge tags More...

struct	nf_distance_t

struct	nf_edge_description_t

struct	nf_flow_t

struct	nf_imbalance_t

struct	nf_index_t

struct	nf_name_t
	vertex tags More...

struct	nf_potential_t

struct	nf_pseudo_flow_t

struct	nf_reduced_cost_t

struct	nf_residual_capacity_t

struct	nf_vertex_description_t

Public Types
using	network_flow_graph_type = boost::adjacency_list< boost::vecS, boost::vecS, boost::bidirectionalS, vertex_nf_property, edge_nf_property >
	definition of the Network Flow Graph More...

Public Member Functions
	network_flow (int _debug_level)
	Constructor of the class. More...

	~network_flow ()=default
	Destructor of the class. More...

bool	successive_shortest_path_algorithm ()
	Computes the solution for the min cost flow problem with successive shortest path algorithm. More...

void	clear_results ()
	Clears results of a previous computation. More...

bool	print_graph (const char *file_name="network_flow.dot")
	Prints a textual description of the graph in a .dot file format. More...

Private Types
using	vertex_nf_description_property = boost::property< nf_vertex_description_t, std::string >
	vertex properties More...

using	vertex_nf_balance_property = boost::property< nf_balance_t, double, vertex_nf_description_property >

using	vertex_nf_imbalance_property = boost::property< nf_imbalance_t, double, vertex_nf_balance_property >

using	vertex_nf_potential_property = boost::property< nf_potential_t, double, vertex_nf_imbalance_property >

using	vertex_nf_distance_property = boost::property< nf_distance_t, double, vertex_nf_potential_property >

using	vertex_nf_index_property = boost::property< nf_index_t, unsigned long, vertex_nf_distance_property >

using	vertex_nf_property = boost::property< nf_name_t, std::string, vertex_nf_index_property >

using	edge_nf_description_property = boost::property< nf_edge_description_t, std::string >
	edge properties More...

using	edge_nf_pseudo_flow_property = boost::property< nf_pseudo_flow_t, double, edge_nf_description_property >

using	edge_nf_residual_capacity_property = boost::property< nf_residual_capacity_t, double, edge_nf_pseudo_flow_property >

using	edge_nf_reduced_cost_property = boost::property< nf_reduced_cost_t, double, edge_nf_residual_capacity_property >

using	edge_nf_flow_property = boost::property< nf_flow_t, double, edge_nf_reduced_cost_property >

using	edge_nf_capacity_property = boost::property< nf_capacity_t, double, edge_nf_flow_property >

using	edge_nf_property = boost::property< nf_cost_t, double, edge_nf_capacity_property >

using	pmap_nf_vertex_description_t = boost::property_map< network_flow_graph_type, nf_vertex_description_t >::type
	vertex maps More...

using	pmap_nf_balance_t = boost::property_map< network_flow_graph_type, nf_balance_t >::type

using	pmap_nf_imbalance_t = boost::property_map< network_flow_graph_type, nf_imbalance_t >::type

using	pmap_nf_potential_t = boost::property_map< network_flow_graph_type, nf_potential_t >::type

using	pmap_nf_distance_t = boost::property_map< network_flow_graph_type, nf_distance_t >::type

using	pmap_nf_index_t = boost::property_map< network_flow_graph_type, nf_index_t >::type

using	pmap_nf_name_t = boost::property_map< network_flow_graph_type, nf_name_t >::type

using	pmap_nf_edge_description_t = boost::property_map< network_flow_graph_type, nf_edge_description_t >::type
	edge maps More...

using	pmap_nf_pseudo_flow_t = boost::property_map< network_flow_graph_type, nf_pseudo_flow_t >::type

using	pmap_nf_residual_capacity_t = boost::property_map< network_flow_graph_type, nf_residual_capacity_t >::type

using	pmap_nf_reduced_cost_t = boost::property_map< network_flow_graph_type, nf_reduced_cost_t >::type

using	pmap_nf_flow_t = boost::property_map< network_flow_graph_type, nf_flow_t >::type

using	pmap_nf_capacity_t = boost::property_map< network_flow_graph_type, nf_capacity_t >::type

using	pmap_nf_cost_t = boost::property_map< network_flow_graph_type, nf_cost_t >::type

using	vertex_pair = std::pair< network_flow_graph_type::vertex_descriptor, network_flow_graph_type::vertex_descriptor >

Private Member Functions
std::string	get_vertex_description (network_flow_graph_type::vertex_descriptor vd)
	Generates the description string of the vertex vd. More...

std::string	get_edge_description (network_flow_graph_type::edge_descriptor ed)
	Generates the description string of the edge ed. More...

void	update_vertex_imbalance (network_flow_graph_type::vertex_descriptor vd)
	Updates the vertex imbalance. More...

void	generic_label_correcting_algorithm (network_flow_graph_type::vertex_descriptor source, network_flow_graph_type::vertex_descriptor target, std::vector< network_flow_graph_type::edge_descriptor > *P)
	Implements the generic label correcting algorithm for vertex distances labelling. More...

Private Attributes
CustomOrderedSet< vertex_pair >	inserted_edges

int	debug_level

Detailed Description

Definition at line 55 of file network_flow.hpp.

Member Typedef Documentation

◆ edge_nf_capacity_property

using network_flow::edge_nf_capacity_property = boost::property<nf_capacity_t, double, edge_nf_flow_property>

private

Definition at line 161 of file network_flow.hpp.

◆ edge_nf_description_property

using network_flow::edge_nf_description_property = boost::property<nf_edge_description_t, std::string>

private

edge properties

Definition at line 150 of file network_flow.hpp.

◆ edge_nf_flow_property

using network_flow::edge_nf_flow_property = boost::property<nf_flow_t, double, edge_nf_reduced_cost_property>

private

Definition at line 159 of file network_flow.hpp.

◆ edge_nf_property

using network_flow::edge_nf_property = boost::property<nf_cost_t, double, edge_nf_capacity_property>

private

Definition at line 163 of file network_flow.hpp.

◆ edge_nf_pseudo_flow_property

using network_flow::edge_nf_pseudo_flow_property = boost::property<nf_pseudo_flow_t, double, edge_nf_description_property>

private

Definition at line 152 of file network_flow.hpp.

◆ edge_nf_reduced_cost_property

using network_flow::edge_nf_reduced_cost_property = boost::property<nf_reduced_cost_t, double, edge_nf_residual_capacity_property>

private

Definition at line 157 of file network_flow.hpp.

◆ edge_nf_residual_capacity_property

using network_flow::edge_nf_residual_capacity_property = boost::property<nf_residual_capacity_t, double, edge_nf_pseudo_flow_property>

private

Definition at line 155 of file network_flow.hpp.

◆ network_flow_graph_type

using network_flow::network_flow_graph_type = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, vertex_nf_property, edge_nf_property>

definition of the Network Flow Graph

Definition at line 168 of file network_flow.hpp.

◆ pmap_nf_balance_t

using network_flow::pmap_nf_balance_t = boost::property_map<network_flow_graph_type, nf_balance_t>::type

private

Definition at line 175 of file network_flow.hpp.

◆ pmap_nf_capacity_t

using network_flow::pmap_nf_capacity_t = boost::property_map<network_flow_graph_type, nf_capacity_t>::type

private

Definition at line 199 of file network_flow.hpp.

◆ pmap_nf_cost_t

using network_flow::pmap_nf_cost_t = boost::property_map<network_flow_graph_type, nf_cost_t>::type

private

Definition at line 201 of file network_flow.hpp.

◆ pmap_nf_distance_t

using network_flow::pmap_nf_distance_t = boost::property_map<network_flow_graph_type, nf_distance_t>::type

private

Definition at line 181 of file network_flow.hpp.

◆ pmap_nf_edge_description_t

using network_flow::pmap_nf_edge_description_t = boost::property_map<network_flow_graph_type, nf_edge_description_t>::type

private

edge maps

Definition at line 189 of file network_flow.hpp.

◆ pmap_nf_flow_t

using network_flow::pmap_nf_flow_t = boost::property_map<network_flow_graph_type, nf_flow_t>::type

private

Definition at line 197 of file network_flow.hpp.

◆ pmap_nf_imbalance_t

using network_flow::pmap_nf_imbalance_t = boost::property_map<network_flow_graph_type, nf_imbalance_t>::type

private

Definition at line 177 of file network_flow.hpp.

◆ pmap_nf_index_t

using network_flow::pmap_nf_index_t = boost::property_map<network_flow_graph_type, nf_index_t>::type

private

Definition at line 183 of file network_flow.hpp.

◆ pmap_nf_name_t

using network_flow::pmap_nf_name_t = boost::property_map<network_flow_graph_type, nf_name_t>::type

private

Definition at line 185 of file network_flow.hpp.

◆ pmap_nf_potential_t

using network_flow::pmap_nf_potential_t = boost::property_map<network_flow_graph_type, nf_potential_t>::type

private

Definition at line 179 of file network_flow.hpp.

◆ pmap_nf_pseudo_flow_t

using network_flow::pmap_nf_pseudo_flow_t = boost::property_map<network_flow_graph_type, nf_pseudo_flow_t>::type

private

Definition at line 191 of file network_flow.hpp.

◆ pmap_nf_reduced_cost_t

using network_flow::pmap_nf_reduced_cost_t = boost::property_map<network_flow_graph_type, nf_reduced_cost_t>::type

private

Definition at line 195 of file network_flow.hpp.

◆ pmap_nf_residual_capacity_t

using network_flow::pmap_nf_residual_capacity_t = boost::property_map<network_flow_graph_type, nf_residual_capacity_t>::type

private

Definition at line 193 of file network_flow.hpp.

◆ pmap_nf_vertex_description_t

using network_flow::pmap_nf_vertex_description_t = boost::property_map<network_flow_graph_type, nf_vertex_description_t>::type

private

vertex maps

Definition at line 173 of file network_flow.hpp.

◆ vertex_nf_balance_property

using network_flow::vertex_nf_balance_property = boost::property<nf_balance_t, double, vertex_nf_description_property>

private

Definition at line 136 of file network_flow.hpp.

◆ vertex_nf_description_property

using network_flow::vertex_nf_description_property = boost::property<nf_vertex_description_t, std::string>

private

vertex properties

Definition at line 134 of file network_flow.hpp.

◆ vertex_nf_distance_property

using network_flow::vertex_nf_distance_property = boost::property<nf_distance_t, double, vertex_nf_potential_property>

private

Definition at line 142 of file network_flow.hpp.

◆ vertex_nf_imbalance_property

using network_flow::vertex_nf_imbalance_property = boost::property<nf_imbalance_t, double, vertex_nf_balance_property>

private

Definition at line 138 of file network_flow.hpp.

◆ vertex_nf_index_property

using network_flow::vertex_nf_index_property = boost::property<nf_index_t, unsigned long, vertex_nf_distance_property>

private

Definition at line 144 of file network_flow.hpp.

◆ vertex_nf_potential_property

using network_flow::vertex_nf_potential_property = boost::property<nf_potential_t, double, vertex_nf_imbalance_property>

private

Definition at line 140 of file network_flow.hpp.

◆ vertex_nf_property

using network_flow::vertex_nf_property = boost::property<nf_name_t, std::string, vertex_nf_index_property>

private

Definition at line 146 of file network_flow.hpp.

◆ vertex_pair

using network_flow::vertex_pair = std::pair<network_flow_graph_type::vertex_descriptor, network_flow_graph_type::vertex_descriptor>

private

Definition at line 270 of file network_flow.hpp.

Constructor & Destructor Documentation

◆ network_flow()

network_flow::network_flow ( int _debug_level )

explicit

Constructor of the class.

Parameters

debug_level_ is the debug level

Definition at line 53 of file network_flow.cpp.

◆ ~network_flow()

network_flow::~network_flow ( )

default

Destructor of the class.

Member Function Documentation

◆ clear_results()

void network_flow::clear_results ( )

Clears results of a previous computation.

Definition at line 419 of file network_flow.cpp.

References edges, initial_value, inserted_edges, network_flow_graph, p_nf_cost, p_nf_distance, p_nf_edge_description, p_nf_flow, p_nf_imbalance, p_nf_potential, p_nf_pseudo_flow, p_nf_reduced_cost, p_nf_residual_capacity, and p_nf_vertex_description.

Referenced by successive_shortest_path_algorithm().

Here is the caller graph for this function:

◆ generic_label_correcting_algorithm()

void network_flow::generic_label_correcting_algorithm	(	network_flow_graph_type::vertex_descriptor	source,
		network_flow_graph_type::vertex_descriptor	target,
		std::vector< network_flow_graph_type::edge_descriptor > *	P
	)

private

Implements the generic label correcting algorithm for vertex distances labelling.

Parameters

source	is the source vertex
target	is the target vertex
P	is the shortest path from source to target

Definition at line 319 of file network_flow.cpp.

References edges, initial_value, network_flow_graph, p_nf_distance, p_nf_reduced_cost, p_nf_residual_capacity, and lenet_tvm::target.

Referenced by successive_shortest_path_algorithm().

Here is the caller graph for this function:

◆ get_edge_description()

std::string network_flow::get_edge_description ( network_flow_graph_type::edge_descriptor ed )

private

Generates the description string of the edge ed.

Called by print_graph function and used to fill the edge_nf_description_property. Useful to printing methods

Parameters

ed	is the edge

Returns: the description string

Definition at line 492 of file network_flow.cpp.

References I2S, p_nf_capacity, p_nf_cost, p_nf_flow, p_nf_pseudo_flow, p_nf_reduced_cost, and p_nf_residual_capacity.

Referenced by print_graph().

Here is the caller graph for this function:

◆ get_vertex_description()

std::string network_flow::get_vertex_description ( network_flow_graph_type::vertex_descriptor vd )

private

Generates the description string of the vertex vd.

Called by print_graph function and used to fill the vertex_nf_description_property. Useful to printing methods

Parameters

vd	is the vertex

Returns: the description string

Definition at line 481 of file network_flow.cpp.

References I2S, p_nf_balance, p_nf_distance, p_nf_imbalance, p_nf_index, p_nf_name, and p_nf_potential.

Referenced by print_graph().

Here is the caller graph for this function:

◆ print_graph()

bool network_flow::print_graph ( const char * file_name = "network_flow.dot" )

Prints a textual description of the graph in a .dot file format.

Parameters

file_name is the name of the text file

Returns: true if everything gone good, false otherwise

Definition at line 455 of file network_flow.cpp.

References edges, get_edge_description(), get_vertex_description(), network_flow_graph, p_nf_edge_description, and p_nf_vertex_description.

Referenced by successive_shortest_path_algorithm().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ successive_shortest_path_algorithm()

bool network_flow::successive_shortest_path_algorithm ( )

Computes the solution for the min cost flow problem with successive shortest path algorithm.

Returns: true if it finds the solution, false otherwise

Definition at line 74 of file network_flow.cpp.

References clear_results(), D, debug_level, DEBUG_LEVEL_MINIMUM, DEBUG_LEVEL_PEDANTIC, DEBUG_LEVEL_VERBOSE, DEBUG_LEVEL_VERY_PEDANTIC, edges, generic_label_correcting_algorithm(), I2S, initial_value, inserted_edges, k, network_flow_graph, original, P, p_nf_balance, p_nf_capacity, p_nf_cost, p_nf_distance, p_nf_flow, p_nf_imbalance, p_nf_potential, p_nf_pseudo_flow, p_nf_reduced_cost, p_nf_residual_capacity, PRINT_DBG_MEX, print_graph(), lenet_tvm::target, and update_vertex_imbalance().

Here is the call graph for this function:

◆ update_vertex_imbalance()

void network_flow::update_vertex_imbalance ( network_flow_graph_type::vertex_descriptor vd )

private

Updates the vertex imbalance.

Parameters

vd	is the vertex

Definition at line 394 of file network_flow.cpp.

References network_flow_graph, p_nf_balance, p_nf_imbalance, and p_nf_pseudo_flow.

Referenced by successive_shortest_path_algorithm().

Here is the caller graph for this function:

Field Documentation

◆ debug_level

int network_flow::debug_level

private

Definition at line 273 of file network_flow.hpp.

Referenced by successive_shortest_path_algorithm().

◆ inserted_edges

CustomOrderedSet<vertex_pair> network_flow::inserted_edges

private

Definition at line 271 of file network_flow.hpp.

Referenced by clear_results(), and successive_shortest_path_algorithm().

◆ network_flow_graph

network_flow_graph_type network_flow::network_flow_graph

Network flow graph pointer.

Definition at line 205 of file network_flow.hpp.

Referenced by clear_results(), generic_label_correcting_algorithm(), print_graph(), successive_shortest_path_algorithm(), and update_vertex_imbalance().

◆ p_nf_balance

pmap_nf_balance_t network_flow::p_nf_balance

Definition at line 211 of file network_flow.hpp.

Referenced by get_vertex_description(), successive_shortest_path_algorithm(), and update_vertex_imbalance().

◆ p_nf_capacity

pmap_nf_capacity_t network_flow::p_nf_capacity

Definition at line 235 of file network_flow.hpp.

Referenced by get_edge_description(), and successive_shortest_path_algorithm().

◆ p_nf_cost

pmap_nf_cost_t network_flow::p_nf_cost

Definition at line 237 of file network_flow.hpp.

Referenced by clear_results(), get_edge_description(), and successive_shortest_path_algorithm().

◆ p_nf_distance

pmap_nf_distance_t network_flow::p_nf_distance

Definition at line 217 of file network_flow.hpp.

Referenced by clear_results(), generic_label_correcting_algorithm(), get_vertex_description(), and successive_shortest_path_algorithm().

◆ p_nf_edge_description

pmap_nf_edge_description_t network_flow::p_nf_edge_description

Edge maps variables.

Definition at line 225 of file network_flow.hpp.

Referenced by clear_results(), and print_graph().

◆ p_nf_flow

pmap_nf_flow_t network_flow::p_nf_flow

Definition at line 233 of file network_flow.hpp.

Referenced by clear_results(), get_edge_description(), and successive_shortest_path_algorithm().

◆ p_nf_imbalance

pmap_nf_imbalance_t network_flow::p_nf_imbalance

Definition at line 213 of file network_flow.hpp.

Referenced by clear_results(), get_vertex_description(), successive_shortest_path_algorithm(), and update_vertex_imbalance().

◆ p_nf_index

pmap_nf_index_t network_flow::p_nf_index

Definition at line 219 of file network_flow.hpp.

Referenced by get_vertex_description().

◆ p_nf_name

pmap_nf_name_t network_flow::p_nf_name

Definition at line 221 of file network_flow.hpp.

Referenced by get_vertex_description().

◆ p_nf_potential

pmap_nf_potential_t network_flow::p_nf_potential

Definition at line 215 of file network_flow.hpp.

Referenced by clear_results(), get_vertex_description(), and successive_shortest_path_algorithm().

◆ p_nf_pseudo_flow

pmap_nf_pseudo_flow_t network_flow::p_nf_pseudo_flow

Definition at line 227 of file network_flow.hpp.

Referenced by clear_results(), get_edge_description(), successive_shortest_path_algorithm(), and update_vertex_imbalance().

◆ p_nf_reduced_cost

pmap_nf_reduced_cost_t network_flow::p_nf_reduced_cost

Definition at line 231 of file network_flow.hpp.

Referenced by clear_results(), generic_label_correcting_algorithm(), get_edge_description(), and successive_shortest_path_algorithm().

◆ p_nf_residual_capacity

pmap_nf_residual_capacity_t network_flow::p_nf_residual_capacity

Definition at line 229 of file network_flow.hpp.

Referenced by clear_results(), generic_label_correcting_algorithm(), get_edge_description(), and successive_shortest_path_algorithm().

◆ p_nf_vertex_description

pmap_nf_vertex_description_t network_flow::p_nf_vertex_description

Vertex maps variables.

Definition at line 209 of file network_flow.hpp.

Referenced by clear_results(), and print_graph().

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

/workspace/src/HLS/binding/register/algorithms/network_flow.hpp
/workspace/src/HLS/binding/register/algorithms/network_flow.cpp

Data Fields
network_flow_graph_type	network_flow_graph
	Network flow graph pointer. More...

pmap_nf_vertex_description_t	p_nf_vertex_description
	Vertex maps variables. More...

pmap_nf_balance_t	p_nf_balance

pmap_nf_imbalance_t	p_nf_imbalance

pmap_nf_potential_t	p_nf_potential

pmap_nf_distance_t	p_nf_distance

pmap_nf_index_t	p_nf_index

pmap_nf_name_t	p_nf_name

pmap_nf_edge_description_t	p_nf_edge_description
	Edge maps variables. More...

pmap_nf_pseudo_flow_t	p_nf_pseudo_flow

pmap_nf_residual_capacity_t	p_nf_residual_capacity

pmap_nf_reduced_cost_t	p_nf_reduced_cost

pmap_nf_flow_t	p_nf_flow

pmap_nf_capacity_t	p_nf_capacity

pmap_nf_cost_t	p_nf_cost

Data Structures

Public Types

Public Member Functions

Data Fields

Private Types

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ edge_nf_capacity_property

◆ edge_nf_description_property

◆ edge_nf_flow_property

◆ edge_nf_property

◆ edge_nf_pseudo_flow_property

◆ edge_nf_reduced_cost_property

◆ edge_nf_residual_capacity_property

◆ network_flow_graph_type

◆ pmap_nf_balance_t

◆ pmap_nf_capacity_t

◆ pmap_nf_cost_t

◆ pmap_nf_distance_t

◆ pmap_nf_edge_description_t

◆ pmap_nf_flow_t

◆ pmap_nf_imbalance_t

◆ pmap_nf_index_t

◆ pmap_nf_name_t

◆ pmap_nf_potential_t

◆ pmap_nf_pseudo_flow_t

◆ pmap_nf_reduced_cost_t

◆ pmap_nf_residual_capacity_t

◆ pmap_nf_vertex_description_t

◆ vertex_nf_balance_property

◆ vertex_nf_description_property

◆ vertex_nf_distance_property

◆ vertex_nf_imbalance_property

◆ vertex_nf_index_property

◆ vertex_nf_potential_property

◆ vertex_nf_property

◆ vertex_pair

Constructor & Destructor Documentation

◆ network_flow()

◆ ~network_flow()

Member Function Documentation

◆ clear_results()

◆ generic_label_correcting_algorithm()

◆ get_edge_description()

◆ get_vertex_description()

◆ print_graph()

◆ successive_shortest_path_algorithm()

◆ update_vertex_imbalance()

Field Documentation

◆ debug_level

◆ inserted_edges

◆ network_flow_graph

◆ p_nf_balance

◆ p_nf_capacity

◆ p_nf_cost

◆ p_nf_distance

◆ p_nf_edge_description

◆ p_nf_flow

◆ p_nf_imbalance

◆ p_nf_index

◆ p_nf_name

◆ p_nf_potential

◆ p_nf_pseudo_flow

◆ p_nf_reduced_cost

◆ p_nf_residual_capacity

◆ p_nf_vertex_description