Inheritance diagram for flowlessly::AdjacencyMapGraph:

Public Member Functions
	AdjacencyMapGraph (Statistics *stats)

	AdjacencyMapGraph (uint32_t max_node_id, uint32_t num_arcs, uint32_t sink_node, const set< uint32_t > &source_nodes, const vector< unordered_map< uint32_t, Arc * > > &arcs, const vector< Node > &nodes, const set< uint32_t > &unused_node_ids, Statistics *stats)

Arc *	AddArc (uint32_t src_node_id, uint32_t dst_node_id, uint32_t min_flow, int32_t capacity, int64_t cost, int32_t type)

void	AddNode (uint32_t node_id, int32_t supply, int64_t potential, NodeType type, bool first_scheduling_iteration)

uint32_t	AddNode (int32_t supply, int64_t price, NodeType type, bool first_scheduling_iteration)

void	ChangeArc (Arc *arc, uint32_t new_min_flow, int32_t new_capacity, int64_t new_cost, int32_t new_type)

void	ChangeArc (uint32_t src_node_id, uint32_t dst_node_id, uint32_t new_min_flow, int32_t new_capacity, int64_t new_cost, int32_t new_type, bool is_multi_arc, int64_t old_cost)

void	GetMachinePUs (uint32_t machine_node_id, set< uint32_t > *pu_ids)

Arc *	GetRandomArc (uint32_t node_id)

unordered_multimap< uint32_t, uint32_t > *	GetTaskAssignments ()

int64_t	GetTotalCost ()

void	InitializeGraph ()

bool	IsEpsOptimal (int64_t eps)

bool	IsFeasible ()

bool	IsInTopologicalOrder (const vector< uint32_t > &node_ids)

int64_t	MaxRefinePotential (uint64_t node_id, int64_t eps)

bool	TopologicalSort (vector< uint32_t > *ordered)

void	RemoveArc (Arc *arc)

void	RemoveNode (uint32_t node_id)

void	ScaleDownCosts (int64_t scale_down)

void	ScaleUpCosts (int64_t scale_up)

void	UpdateAdmissibleGraph (const vector< uint32_t > &updated_nodes)

void	WriteAssignments (FILE *out_file)

void	WriteFlowGraph (FILE *out_graph_file)

void	WriteGraph (FILE *out_graph_file)

set< uint32_t > &	get_active_node_ids ()

vector< unordered_map < uint32_t, Arc * > > &	get_admissible_arcs ()

vector< unordered_map < uint32_t, Arc * > > &	get_arcs ()

vector< Node > &	get_nodes ()

Public Member Functions inherited from flowlessly::Graph
	Graph (uint32_t max_node_id, uint32_t num_arcs, uint32_t sink_node, const set< uint32_t > &source_nodes)

void	ReadGraph (FILE graph_file, bool first_scheduling_iteration, bool end_of_scheduling)

void	WriteAssignments (const string &out_file_name)

void	WriteFlowGraph (const string &out_graph_file)

void	WriteGraph (const string &out_graph_file)

uint32_t	get_max_node_id () const

uint32_t	get_sink_node ()

set< uint32_t > &	get_source_nodes ()

vector< int64_t > &	get_potentials ()

Additional Inherited Members
Protected Attributes inherited from flowlessly::Graph
uint32_t	max_node_id_

uint32_t	num_arcs_

uint32_t	sink_node_

set< uint32_t >	source_nodes_

vector< int64_t >	potentials_

Member Function Documentation

uint32_t flowlessly::AdjacencyMapGraph::AddNode	(	int32_t	supply,
		int64_t	potential,
		NodeType	type,
		bool	first_scheduling_iteration
	)

virtual

Adds a new node to the graph.

Parameters

supply	the supply of the new node
price	the price of the new node
type	the type of the ndode

Returns: the id of the new node

Implements flowlessly::Graph.

void flowlessly::AdjacencyMapGraph::ChangeArc	(	Arc *	arc,
		uint32_t	new_min_flow,
		int32_t	new_capacity,
		int64_t	new_cost,
		int32_t	new_type
	)

virtual

Change a given arc. The change can increase or decrease the arc's capacity or cost.

Parameters

arc	the arc that is going to be changed
new_min_flow	the new minimum flow bound of the arc
new_capacity	the new arc capacity
new_cost	the new arc cost
new_type	the new arc type

Implements flowlessly::Graph.

void flowlessly::AdjacencyMapGraph::ChangeArc	(	uint32_t	src_node_id,
		uint32_t	dst_node_id,
		uint32_t	new_min_flow,
		int32_t	new_capacity,
		int64_t	new_cost,
		int32_t	new_type,
		bool	is_multi_arc,
		int64_t	old_cost
	)

virtual

Change one of the arcs between two src_node_id and dst_node_id.

Parameters

src_node_id	the source node of the arc
dst_node_id	the destination node of the arc
new_min_flow	the new minimum flow bound of the arc
new_capacity	the new arc capacity
new_cost	the new arc cost
new_type	the new arc type
is_multi_arc	true if the arc is one of the multiple arcs
old_cost	if the arc is one of the multiple arcs between the two nodes then we use the old_cost to identify the arc

Implements flowlessly::Graph.

Arc * flowlessly::AdjacencyMapGraph::GetRandomArc ( uint32_t node_id )

virtual

Get a random outgoing arc.

Implements flowlessly::Graph.

int64_t flowlessly::AdjacencyMapGraph::GetTotalCost ( )

virtual

Get the cost of the flow that has been sent in the graph.

Implements flowlessly::Graph.

bool flowlessly::AdjacencyMapGraph::IsEpsOptimal ( int64_t eps )

virtual

Checks epsilon optimality of the flow graph. A flow graph is eps-optimal if there is no arc with capacity > 0 and cost + potential[src_vertex_id] - potential[dst_vertex_id] < -eps.

Parameters

eps Epsilon

Implements flowlessly::Graph.

bool flowlessly::AdjacencyMapGraph::IsFeasible ( )

virtual

Checks if the flow in the graph is feasible. A flow is feasible if all the supply is satisfied, there's no excess supply left and the flow on every arc is within bounds. NOTE: It does not check if the flow is the min cost flow.

Implements flowlessly::Graph.

bool flowlessly::AdjacencyMapGraph::IsInTopologicalOrder ( const vector< uint32_t > & node_ids )

virtual

Checks if the nodes in the vector are in topological order.

Implements flowlessly::Graph.

int64_t flowlessly::AdjacencyMapGraph::MaxRefinePotential	(	uint64_t	node_id,
		int64_t	eps
	)

Computes the maximum refine potential that can be used in a relabel operation.

Parameters

node_id	the node id for which to compute the refine potential
eps	current epsilon optimality value

Returns: the maximum refine potential value

void flowlessly::AdjacencyMapGraph::RemoveArc ( Arc * arc )

virtual

Removes the given arc from the graph. It updates the supply at the source and destination nodes. Removing an arc may change the graph s.t. there's no feasible flow. However, the method does not check feasibility.

Parameters