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_ |
|
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 |
Implements flowlessly::Graph.
|
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 |
Implements flowlessly::Graph.
|
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 |
Implements flowlessly::Graph.
|
virtual |
Get a random outgoing arc.
Implements flowlessly::Graph.
|
virtual |
Get the cost of the flow that has been sent in the graph.
Implements flowlessly::Graph.
|
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 |
Implements flowlessly::Graph.
|
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.
|
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.
node_id | the node id for which to compute the refine potential |
eps | current epsilon optimality value |
|
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 |
Implements flowlessly::Graph.
|
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 |
Implements flowlessly::Graph.
|
virtual |
|
virtual |
Scales up all arc costs.
scale_up | scale up factor. |
Implements flowlessly::Graph.
bool flowlessly::AdjacencyMapGraph::TopologicalSort | ( | vector< uint32_t > * | ordered | ) |
Construct a topological order of the admissible graph.
ordered_nodes | vector populated with the ordered nodes |
|
virtual |
Print the assignments of tasks to PUs. NOTE: the file is not going to be closed.
Implements flowlessly::Graph.
|
virtual |
NOTE: the file is not going to be closed.
Implements flowlessly::Graph.
|
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. |
Implements flowlessly::Graph.