纯序员给你介绍图化框架的简单实现——执行逻辑

友情提示：项目相关视频在B站持续更新中，内容略新于文章更新，欢迎观看交流和一键三连：

大家好，我是不会写代码的纯序员——Chunel。有人说，码如人生。人生中，有些事情是可以同时进行的，有些事情又必须是前后依次进行的；有些事情是可以刚开始就做的，有些事情又必须等待某个时机成熟了才可以开始。

我给大家举个例子：
人必须出生后，然后才能上学和工作。同样的，出生后还可以恋爱，然后结婚，和生娃。你可以上学的时候恋爱；也可以工作的时候再撩妹。但是，你必须先完成上学之后，才能开始工作。同样的，你必须恋爱后，才能结婚，然后再生娃（好吧，这个顺序，你想咋样我都支持你，哈哈）。最终，我们都会被辞退，我想大概是35岁左右吧。

看上面这个例子，和程序开发中常用的图化框架（比如TensorFlow）是不是很像。今天，纯序员给大家提供一种思路，可以轻松的实现一套属于自己的轻量级的图化框架。

分析

这个问题乍一看很难。但是我们来拆解一下，其实一共只有几步：

1，构建图框架，把node（图中的节点）和node的依赖信息注册到图中
2，对图进行分析，找出其中没有任何依赖的node，放入一个queue中
3，依次执行queue中的节点，直到queue中所有node被执行完毕
4，搜集依赖queue中node执行的节点（称为newNode）
5，清空queue，然后将newNode中所有未被运行且依赖的节点均被执行的节点，放入queue中
6，重复3、4、5步骤，直到queue中无node插入，则结束

举例

看着看着就晕了？没关系，看举个例子来，就比较容易理解了。

我们来看上图这个例子，然后对照上面的步骤，开始我们的流程。

执行A的内容，直到全部结束
执行B和C节点的内容，直到全部结束
执行D和E的内容，直到全部结束
执行F的内容，直到全部结束
执行G的内容

所以说，最终的执行顺序，应该是 A->B->C->E->D->F->G。这样下来，是不是就是比较清楚了。

优化

你以为就这样就结束了？很多朋友应该已经看出来了，上图中B和C的执行顺序，应该是没有任何先后依赖的。所以，为了加速整体流程，B和C应该并发执行，而不是先执行B，结束后再执行C。

再继续看，D、E、F这三个节点。如果按照上面的说法，应该是D和E并发执行，都结束后再执行F。我们假设，D、E、F的流程的耗时，分别为 D=3s（秒），E=1s，F=2s 。那这个子流程结束，就需要max(3s,1s)+2s，也就是5s。但是F虽然依赖E，但是并不依赖D啊。

于是，优化点又来了，把E和F当做一个簇（cluster），簇内部依次执行。同时簇作为一个整体，与D并发执行。这样下来，这个子流程的最终耗时就应该是max(3s, 1s+2s)，也就是3s。

当然了，还有很多优化思路我没有提到，或者我压根不知道的。也欢迎大家来一起讨论。

实现

懂了，但是不知道代码应该如何下手？至于代码实现，纯序员早已贴心的为你写了一套通用组件——CGraph。仅需要自己实现一下节点的功能函数，然后调用一个注册接口，并且设定依赖节点，就可以轻松的run起来上面提到的所有功能了。

就以上面画的那个图来举例吧，代码实现一共就这么几句话：

#include "/src/GraphCtrl/GraphInclude.h"

class MyNode1 : public GraphNode {
public:
    CSTATUS run () override {
        CSTATUS status = STATUS_OK;
        std::cout << "enter node1 run function. sleep for 1 second ... " << std::endl;
        this_thread::sleep_for(chrono::milliseconds(1000));
        return status;
    }
};

#include "/src/GraphCtrl/GraphInclude.h"

class MyNode2 : public GraphNode {
public:
    CSTATUS run () override {
        CSTATUS status = STATUS_OK;
        std::cout << "enter node1 run function. sleep for 2 second ... " << std::endl;
        this_thread::sleep_for(chrono::milliseconds(2000));
        return status;
    }
};

#include "MyGraphNode/MyNode1.h"
#include "MyGraphNode/MyNode2.h"

void graph_demo() {
    /* 创建图化 */
    Graphic* graphic = new Graphic();

    GraphNode* A = nullptr;
    GraphNode* B = nullptr;
    GraphNode* C = nullptr;
    GraphNode* D = nullptr;
    GraphNode* E = nullptr;
    GraphNode* F = nullptr;
    GraphNode* G = nullptr;

    /* 注册节点，其中MyNode1和MyNode2必须为GraphNode的子类 */
    graphic->registerGraphNode<MyNode1>(&A);               // A节点执行，没有任何依赖信息
    graphic->registerGraphNode<MyNode1>(&B, {A});          // B节点执行，依赖A节点执行完毕
    graphic->registerGraphNode<MyNode2>(&C, {A});
    graphic->registerGraphNode<MyNode1>(&D, {B});          // D节点执行，依赖B节点执行完毕
    graphic->registerGraphNode<MyNode2>(&E, {B});
    graphic->registerGraphNode<MyNode1>(&F, {E});
    graphic->registerGraphNode<MyNode1>(&G, {C, D, F});    // G节点执行，依赖C、E、F节点执行完毕

    /* 图信息初始化，准备开始计算 */
    graphic->init();

    /* 运行图计算。初始化后，支持多次循环计算 */
    graphic->run();

    /* 图信息逆初始化，准备结束计算 */
    graphic->deinit();
    delete graphic;
}

写在最后

这没有理由说看不懂了吧。当然了，CGraph自身也在不断的迭代和演进过程中，我们也会不断的借(co)鉴(py)行业中比较先进和成熟的一些实现方法。这个过程也需要大家大力的参与、鼓励和拍砖。

目前CGraph源码已经开源至github上，源码地址是：CGraph项目github链接，欢迎大家前来帮忙review，star and fork哦。如果能帮忙找到几个bug，或者做一些功能和性能上优化，那当然就更好了，哈哈哈哈！！！！！

    					[2021.05.09 by Chunel]

个人信息

微信: ChunelFeng
邮箱: chunel@foxmail.com
个人网站：www.chunel.cn
github地址: https://github.com/ChunelFeng