如何实现一个图化框架？代码已开源！-轻识

作者 Chunel Feng，编程爱好者，阿里巴巴引擎开发工程师。

个人微信：ChunelFeng
个人博客：一面之猿网^[1]
个人项目：CGraph 图计算框架^[2]

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

我给大家举个例子：

人必须「出生」后，然后才能「上学」和「工作」。

同样的，「出生」后还可以「恋爱」，然后「结婚」，「生娃」。

你可以「上学」的时候「恋爱」，也可以「工作」的时候再「撩妹」。但是，你必须先完成「上学」之后，才能开始「工作」。

同样的，你必须「恋爱」后，才能「结婚」，然后再「生娃」（好吧，这个顺序，你想咋样我都支持你，哈哈）。

最终，我们都会「被辞退」，我想大概是 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);               // 注册MyNode1类型的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，地址：https://github.com/ChunelFeng/CGraph

点击阅读原文可直达！ 欢迎大家前来帮忙 review，star and fork 哦。如果能帮忙找到几个 bug，或者做一些功能和性能上优化，那当然就更好了，哈哈哈哈！！！！！

引用链接

[1] 一面之猿网: http://www.chunel.cn
[2] CGraph 图计算框架: https://github.com/ChunelFeng/CGraph
[3] Chunel Feng: https://github.com/ChunelFeng

长按识别下图二维码，关注公众号「Doocs 开源社区」，第一时间跟你们分享好玩、实用的技术文章与业内最新资讯。