DAG

DAG(Directed Acyclic Graph)有向无环图

实现一个任务按顺序执行的DAG

c++

#include <iostream>
#include <vector>
#include <memory>
#include <functional>
#include <string>
#include <unordered_map>
using namespace std;

class Task{
public:
    string name;//任务名
    vector<string> pre_tasks; //前置任务名
    bool isFinish = true;//是否完成
    Task(string name_,vector<string> pre_tasks_):name(name_),pre_tasks(pre_tasks_){};
    void execute(){ cout << name +"执行" << endl;};
};


class DAG{
public:
    unordered_map<string,Task*> umap;
    DAG(){};
    void add_task(Task* task){
        this->umap[task->name] = task;
        task->isFinish = false;
    };

    void execute_task(string name){
        if(umap[name]->isFinish){
            return;
        }
        for(string task_name :umap[name]->pre_tasks){
            if(umap[task_name]->isFinish != true){
                execute_task(task_name);
            }
        }
        umap[name]->execute();
        umap[name]->isFinish = true;
    };

    void execute_all(){
        for(auto [name,Task]: umap){
            execute_task(name);
        }
    };

};


int main()
{
    DAG* dag = new DAG();
    dag->add_task(new Task("A",{}));
    dag->add_task(new Task("C",{"A"}));
    dag->add_task(new Task("D",{"C"}));
    dag->add_task(new Task("E",{"D"}));
    dag->add_task(new Task("F",{"A","D"}));
    dag->add_task(new Task("H",{"C","A"}));

    // dag->execute_task("C");
    // dag->execute_task("H");
	// dag->execute_task("F");
	
    dag->execute_all();
    return 0;
}

DAG ​

DAG