Inheritance diagram for flowlessly::Graph:

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

virtual 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)=0

virtual uint32_t	AddNode (int32_t supply, int64_t potential, NodeType type, bool first_scheduling_iteration)=0

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

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

virtual 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)=0

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

virtual Arc *	GetRandomArc (uint32_t node_id)=0

virtual int64_t	GetTotalCost ()=0

virtual bool	IsEpsOptimal (int64_t eps)=0

virtual bool	IsFeasible ()=0

virtual bool	IsInTopologicalOrder (const vector< uint32_t > &node_ids)=0

virtual void	InitializeGraph ()=0

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

virtual void	RemoveArc (Arc *arc)=0

virtual void	RemoveNode (uint32_t node_id)=0

virtual void	ScaleDownCosts (int64_t scale_down)=0

virtual void	ScaleUpCosts (int64_t scale_up)=0

virtual void	WriteAssignments (FILE *out_file)=0

void	WriteAssignments (const string &out_file_name)

virtual void	WriteFlowGraph (FILE *out_graph_file)=0

void	WriteFlowGraph (const string &out_graph_file)

void	WriteGraph (const string &out_graph_file)

virtual void	WriteGraph (FILE *out_graph_file)=0

uint32_t	get_max_node_id () const

uint32_t	get_sink_node ()

set< uint32_t > &	get_source_nodes ()

vector< int64_t > &	get_potentials ()

Protected Attributes
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

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

pure 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

Implemented in flowlessly::AdjacencyMapGraph.

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

pure 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

Implemented in flowlessly::AdjacencyMapGraph.

virtual void flowlessly::Graph::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
	)

pure 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

Implemented in flowlessly::AdjacencyMapGraph.

virtual Arc* flowlessly::Graph::GetRandomArc ( uint32_t node_id )

pure virtual

Get a random outgoing arc.

Implemented in flowlessly::AdjacencyMapGraph.

virtual int64_t flowlessly::Graph::GetTotalCost ( )

pure virtual

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

Implemented in flowlessly::AdjacencyMapGraph.

virtual bool flowlessly::Graph::IsEpsOptimal ( int64_t eps )

pure 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

Implemented in flowlessly::AdjacencyMapGraph.

virtual bool flowlessly::Graph::IsFeasible ( )

pure 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.

Implemented in flowlessly::AdjacencyMapGraph.

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

pure virtual

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

Implemented in flowlessly::AdjacencyMapGraph.

virtual void flowlessly::Graph::RemoveArc ( Arc * arc )

pure 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