JavaScript+SVG实现Web前端WorkFlow⼯作流DAG有向⽆环图⼀、效果图展⽰及说明
（图⼀）
（图⼆）
附注说明：
1. 图例都是DAG有向⽆环图的展现效果。两张图的区别为第⼆张图包含了多个分段关系。放置展⽰图⽚效果主要是为了说明该例⼦⽀持
多段关系的展现（当前也包括单独的节点展现，图例没有展⽰）
2.图例中的圆形和曲线均使⽤的是SVG绘制。之前考虑了三种⽅式，⼀种是html5的canvas，⼀种是原始的html DOM，再有就是SVG。
不过canvas对事件的⽀持不是很好（记得之前看过⼀篇⽂章主要是通过计算⿏标定位是否在canvas上的某个区域来触发事件机制，⽐较不适⽤⼯作流节点上的各种事件触发机制），另外原始的 DOM虽然对事件的处理⽐canvas要⽅便，但是从编码和绘制dom上则会过度的耗费资源，尤其是曲线的绘制，毕竟过多的dom操作都会影响性能拖慢响应速度，所以综合考虑使⽤SVG，它提供了绘制圆形，多边形，路径等操作，尤其是path的使⽤对于我们这种不会画曲线的⼈太⽅便了。并且svg的dom对事件的⽀持和处理也很好。
⼆、有向⽆环图分析
Okay，了解了⽀持的展现效果和使⽤的技术，下⾯开始分析开发workflow的dag有向⽆环图吧（透露⼀下，有向⽆环图最重要的是计算每个节点的最⼤步长了，最⼤步长也就是该节点在这⼀段关系中，距离根节点的最远距离，⽹上有⼀些计算的算法什么的，不过本⼈不会，搞不通算法）。本例的核⼼技术其实是递归。就是⽤递归就算每个节点的最⼤步长。还不了解递归是什么的童鞋们先了解⼀下递归。
  1. 梳理dag关系，剥离不存关系的节点和存在关系的节点，并到每段关系的根节点
（图三）
附注说明：
上图是⼀个DAG有向⽆环图的关系链展⽰。（不要认为dag有向⽆环图单单指的是上图的中间部分，我们完全可以将上图理解为⼀个完整的dag关系。因为考虑问题要全⾯嘛！不是所有的节点只存在⼀段关系中，也不是所有的节点就⼀定和其它节点有关系。所以当然会出现上图的展⽰情况。当然，上图的任何⼀段单提取出来也是⼀段完整的dag关系。不过，为了后续的讲解和dag插件通⽤性，举了⼀个存在多种情况的dag关系的例⼦，之后的讲解也会按照这个图⽚来说明）。
⽅法思路:
  前提：已知当前dag图中的所有节点和所有关系链。（注意节点间的关系链是有向的）
1. 遍历所有的节点，逐个节点判定当前遍历的节点是否在关系链中，若不存在，则把当前节点作为⼀个独⽴的节点存储到⼀个数组中，
我们就叫它 indiviual。（单独的节点其实跟后续的操作没有过多的关系，我们只是考虑到这样特殊的情况，把它们都单独提取出来，展⽰到页⾯上即可。）
2. 同第1步⼀样，不过是取存在在关系链中的所有的节点，把它们push到另⼀个数组中，叫它 refNodes。
3. 获取了所有的再关系链中的节点数组 refNodes，遍历refNodes，并对照关系链，查当前遍历的节点是否有作为输⼊节点类型对应
的输出节点，如果有，表⽰当前遍历的节点不是根节点，若没有，怎该节点为根节点，把它们push到⼀个叫 rootNodes的数组中。
（因为是有向⽆环图，所以关系链是有向的，⽐如A-->B-->C，A作为第⼀次遍历的节点，查是否存在？-->A的这种关系链，也就是A 作为输⼊点它上级的输出点，如果遍历完所有关系链都没有发现这种情况，则A是⼀个根节点。同理，遍历到B的时候，就会到 A-->B这种情况，所以B不是根节点）
。
*注意*：为了保证程序的正确性，数组中不会出现重复的节点，⼀定要在存储数组前执⾏以下去重操作。
a). 可以定义⼀个javascript对象来存储dag中⽤的数据信息
//⼯作流对象
var relation={
links:[],      //当前⼯作流中所有的关系链集合
individual:[],  //存放所有没有关系的节点
refNodes:[],    //存放有关系的节点
rootNodes:[],  //存放关系中的根节点
};
  b). 查根节点⽰例代码，记得数组去重，可以使⽤jquery 的⼯具函数inArray。（links数组中存储的是所有的关系链对象link.具体的依照个⼈开发习惯定义，这⾥只是为了⽅便读者可以理解部分代码给出我使⽤的⽰例）
/**
  links中的关系对象存储⽰例
  var relation={
    links:[
      {
        output:{
          nodeId:A,  //输出节点的id
          pointName:A_1  //输出接线点名称
        },
        input:{
          nodeId:B,  //输⼊节点的id
          pointName:B_1  //输⼊接线点的名称
        }
      }
    ]
  }
**/
//查根节点
function findRootNodes(){
var fNodes.length;
for(var i=0;i<len;i++){
var fNodes[i];
var isRootNode=true;
$.each(relation.links,function(l,link){
var in_node=deId;
//当前节点只要有作为输⼊点就不是根节点
if(node==in_node){
isRootNode=false;
}
});
if(isRootNode){
if($.inArray(Nodes)==-1){
}
}
}
}
2. 根据所有的根节点和有关系的节点及所有的关系链到每个节点的最⼤步长　
                (图四)
循环所有的节点和根节点，每个节点的步长查都要从根节点开始计算，如图四所⽰，以查C节点的最⼤步长为例，遍历到C节点上时，查到第⼀个根节点A开始的关系⽹，第⼀次到A，这时的步长是1，然后逐级向下查，第⼆次到B，步长计数为2，第三次到C和D，步长为3，第四次到C和E，步长为4，第五次已经遍历完当前根节点开始的⼀段关系，所以，上图上的⽆和步长5其实是没有的。同理，因为有可能存在多个根节点，所以都要遍历。第⼆个根节点为F，遍历后不到C，所以不记录步长。
注意两⽅⾯：第⼀：取节点的最⼤步长
      第⼆：遍历步长为递归⽅式，每次从根节点查（根节点以集合⽅式存储），取得下⼀级别的节点集合作为开始，每⼀个级别为⼀个步长计数，如此反复，直到集合为空为⽌。
关键代码如下:（节点的步长实际上是为了计算节点的横向排列位置⽤的，所以下⾯的代码⽤了⼀个nodeLevel对象来记录每个节点的最⼤步长)
//根据根节点和所有有关系的节点及关系链到每个节点的最⼤步长
function setNodeMaxStep(){
var fNodes.length;
for(var i=0;i<len;i++){
var search_fNodes[i];  //每次需要判定最⼤步长的节点
//每次从根节点开始查
for(var k=0;k&Nodes.length;k++){
var root_Nodes[k];    //获取当前根节点
var node_arr=new Array();  //存放依次遍历的同级节点,⾸次放⼊根节点，逐步查下⼀级别
node_arr.push(root_node);
var stepCount=1;    //从根节点级别时步长计数器归零
//设置根节点的级别，根节点的步长为零
nodeLevel[root_node]={};
nodeLevel[root_node].breadth=stepCount;
//递归查search_node的最⼤步长
recordNodeStep(node_arr,search_node,stepCount);
}
}
}
function recordNodeStep(arr,search_node,stepCount){
if(arr!=null && arr!=undefined && arr.length>0){
var temp_node_arr=new Array();  //临时存储下⼀级别节点的数组
stepCount++;    //逐级增加步长，级别的判定就是arr数组的出现频次
for(var n=0;n<arr.length;n++){
var temp_node=arr[n];  //作为输出节点去查输⼊点(即查下⼀级节点)
$.each(relation.links,function(l,link){
var in_node=deId;
var out_node=deId;
if(temp_node==out_node){    //查到输⼊点
if($.inArray(in_node,temp_node_arr)==-1){
temp_node_arr.push(in_node);
}
//节点作为输出点时到对应的输⼊点，若输⼊点等于需要判定步长的节点怎记录步长信息
if(in_node==search_node){  //到当前节点则记录当前步长
if(nodeLevel[in_node]==undefined){
nodeLevel[in_node]={};
}
//考虑到被判定步长的节点有可能存在多个根节点的关系链中且每次切换根节点计算步长都会将步长计数器归零，因此需要保留最⼤步长数
if(nodeLevel[in_node].breadth!=undefined && nodeLevel[in_node].breadth!=null){
var last_breadth=nodeLevel[in_node].breadth;
if(stepCount>last_breadth){
nodeLevel[in_node].breadth=stepCount;
}
}else{
nodeLevel[in_node].breadth=stepCount;
}
}
}
});
}
arr=temp_node_arr;
recordNodeStep(arr,search_node,stepCount);
}
}
3. 根据每个节点的最⼤步长计算节点的深度级别，这样最终可以通过坐标的⽅式定位节点的位置
可以遍历每个节点的步长Map对象，然后以步长做为key，初始化每个步长的深度级别为0。然后再次遍历节点的步长Map对象，取得当前步长的深度数，遇到同步长的节点深度+1即可。这样，接线的纵向排列问题即可解决。svg canvas
代码如下：
function setNodesDeepth(){
var deepthLevel={};
$.each(nodeLevel,function(i,node){
var breadth=node.breadth;
if(deepthLevel[breadth]==undefined && deepthLevel[breadth]==null){
deepthLevel[breadth]=0;
}
});
$.each(nodeLevel,function(i,node){
var breadth=node.breadth;
deepthLevel[breadth]+=1;
node.deepth=deepthLevel[breadth];
});
}
Okay，Dag最关键的核⼼步长定位解决了。不过我们之前还有⼀个individual的数组⽤来存放单独的节点，这个就简单啦，完全可以将它们全部横向展⽰在svg画布上的顶端。可以直接遍历这个数组，每个节点的横向步长逐个+1即可，纵向级别可固定为1。然后计算节点的X，Y 坐标位置放置到svg画布上即可。
三、关于接线点和绘制和曲线的绘制说明
  1. 接线点
因为本例⽤的是圆形的节点，接线点也是在圆形的边界上，所以还是以圆形节点为例。计算⽅式其实就是使⽤的JavaScript的Math对象的sin和cos函数来确定接线点的位置的。（不会使⽤的⼩伙伴可以上⽹上搜⼀下，好多的例⼦，不再赘述了。）
  2.曲线
曲线的绘制时通过svg的path路径绘制的，看了⽹上的例⼦，只要确定起⽌点的x和y坐标即可。
例⼦如下：起始点坐标(354,164) 终⽌点坐标(762,80)，然后结合例⼦看⼀下就知道怎么放置位置了吧。
<path d="M354,164C762,164,354,80,762,80" stroke-width="3" fill="none" stroke="#dddddd"></path>
结束语
本⽂主要介绍了⼀下在不会算法的情况下，如何使⽤递归获取有向⽆环图中各个节点的最⼤步长。以此来设置各节点的位置信息来实现
dag的布局。通过此⽅法，我们只需要知道节点和节点的关系即可绘制出⼀幅dag有向⽆环图了。如果希望⽤户交互和体验更好些，可以实现svg缩放效果和移动效果。可以使⽤svg的scale和translate⽅法来实现。
第⼀次写⽂章，如果有⽋缺和不⾜的地⽅，欢迎⼤家指正探讨，不尽详细，感谢阅读。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。