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_ |
|
pure virtual |
Adds a new node to the graph.
supply | the supply of the new node |
price | the price of the new node |
type | the type of the ndode |
Implemented in flowlessly::AdjacencyMapGraph.
|
pure virtual |
Change a given arc. The change can increase or decrease the arc's capacity or cost.
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.
|
pure virtual |
Change one of the arcs between two src_node_id and dst_node_id.
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.
|
pure virtual |
Get a random outgoing arc.
Implemented in flowlessly::AdjacencyMapGraph.
|
pure virtual |
Get the cost of the flow that has been sent in the graph.
Implemented in flowlessly::AdjacencyMapGraph.
|
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.
eps | Epsilon |
Implemented in flowlessly::AdjacencyMapGraph.
|
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.
|
pure virtual |
Checks if the nodes in the vector are in topological order.
Implemented in flowlessly::AdjacencyMapGraph.
|
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.
arc | the arc to remove |
Implemented in flowlessly::AdjacencyMapGraph.
|
pure virtual |
Remove the graph node corresponding to the given id. NOTE: The id is going to be re-used when new nodes will be added to the graph.
node_id | the id of the node to remove |
Implemented in flowlessly::AdjacencyMapGraph.
|
pure virtual |
Scales down all arc costs.
scale_down | scale down factor |
Implemented in flowlessly::AdjacencyMapGraph.
|
pure virtual |
Scales up all arc costs.
scale_up | scale up factor. |
Implemented in flowlessly::AdjacencyMapGraph.
|
pure virtual |
Print the assignments of tasks to PUs. NOTE: the file is not going to be closed.
Implemented in flowlessly::AdjacencyMapGraph.
void flowlessly::Graph::WriteAssignments | ( | const string & | out_file_name | ) |
Print the assignments of tasks to PUs.
|
pure virtual |
NOTE: the file is not going to be closed.
Implemented in flowlessly::AdjacencyMapGraph.
void flowlessly::Graph::WriteFlowGraph | ( | const string & | out_graph_file | ) |
Writes the flow of the graph.
out_graph_file | the name of the file to which to write the flow |
void flowlessly::Graph::WriteGraph | ( | const string & | out_graph_file | ) |
Writes the graph to a file using the DIMACS format.
out_graph_file | the name of the file to which to write the graph |
|
pure virtual |
Writes the graph to a file using the DIMACS format.
out_graph_file | the file to which to write the graph NOTE: the file is not going to be closed. |
Implemented in flowlessly::AdjacencyMapGraph.