1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
/**
*
* @file plugins/CriticalPath/ParseDAG.hpp
*
* @copyright 2008-2024 Bordeaux INP, CNRS (LaBRI UMR 5800), Inria,
* Univ. Bordeaux. All rights reserved.
*
* @author Camille Ordronneau
* @author Johnny Jazeix
* @author Mathieu Faverge
*
* @date 2024-07-17
*/
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/adj_list_serialize.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/bellman_ford_shortest_paths.hpp>
#include <boost/property_map/dynamic_property_map.hpp>
#include <boost/property_map/function_property_map.hpp>
#include <boost/graph/graph_utility.hpp>
#include "ParseTasks.hpp"
#include <ostream>
#include <vector>
#include <boost/graph/topological_sort.hpp>
#define MINSIZE 100
typedef std::pair<double, double> pair;
typedef std::pair<pair, pair> doublepair;
using namespace boost;
struct Vertex
{
std::string task_name, label, fillcolor, style;
int not_max_breadth;
int task_id;
double execution_time;
double time_elapsed;
};
struct Edge
{
std::string color;
};
typedef property<graph_name_t, std::string> graph_p;
typedef adjacency_list<vecS, vecS, bidirectionalS, Vertex, Edge, graph_p> graph_t;
using weight_map_t = boost::property_map<graph_t, double Edge::*>::type;
/*!
* \brief Initializes .dag graph representation with values from .rec and computes critical path length. Returns the length and the index of the ending vertex of the critical path
* \param g Graph representing the DAG
* \param task_time Vector of task times indexed by JobId, get_time(JobId) returns execution time of correspondant task
*/
std::pair<std::pair<double, size_t>, double> critical_path_length(graph_t &g, std::vector<double> &task_time);
/*!
* \brief Draws critical_path in DAG graph representation
* \param g Graph representing the DAG
* \param source_task it starts from the last task of the execution of the critical path (it changes during the drawing process)
*/
void dag_draw_critical_path(graph_t &g, int source_task);
/*!
* \brief Returns vector of all critical path tasks from last to first (in order to minimize complexity we inluded dag_draw_cp lines here as it is the same loop)
* \param g Graph representing the DAG
* \param source_task it starts from the last task of the execution of the critical path (it changes during the drawing process)
*/
std::vector<int> critical_path(graph_t &g, int source_task);
/*!
* \brief Returns vector of all last critical tasks (This function in unused but could be interesting if there is numerous critical paths (having the same length of course))
* \param g Graph representing the DAG
* \param max_value is the length of the critical path
*/
std::vector<int> critical_last_tasks(graph_t &g, double max_value);
/*!
* \brief Returns max breadth in an interval (begin-end), and the sub-interval where it is achieved
* param g Graph on which we want to compute the max breadth in the interval (begin - end)
* param begin Start time of the interval
* param end End time of the interval
*/
std::pair<double, pair> get_number_processing(graph_t &g, double begin, double end);
/*!
* \brief Computes max breadth in graph and retuns in addition to it the interval where it is achieved
* param g Graph we want to compute its max breadth
*/
std::pair<double, pair> max_breadth(graph_t &g);
|
