一个简单的流程图遍历算法实现

这是实际项目中遇到的一个需求，现在将实现过程简单记录下来，作为备忘。

需求

在项目中开发了审批流程维护工具，开发人员可以使用工具定义审批流程图，现在需要对定义的流程图生成模拟测试用例。流程图有若干分支，针对每一分支，生成一个测试用例，需要遍历所有分支，生成一组测试用例。

数据结构

将流程图看作由节点和连接组成，节点抽象为Node，节点的下游节点用集合 SubNodes表示。为了记录流程节点的执行顺序，创建一个新的结构NodeWithIdx，这个结构包括节点Node，和该节点在当前用例中的执行顺序idx。一组NodeWithIdx构成一个用例。

算法：
创建保存NodeWithIdx的堆栈，从根节点开始，
1、创建NodeWithIdx实例，包含相关的Node实例，并设置Idx=0，将对象压入堆栈
2、判断当前节点是否有子节点，如果没有子节点，那么，堆栈中的节点构成一条路径，记录这条路径，栈顶的对象出栈
3、如果有子节点，但Idx得值已经超过子节点得个数（遍历完成），栈顶的对象出栈
4、按照当前节点（栈顶对象）Idx的值，获取子节点,然后Idx++，如果有子节点，重复第一步创建相应子节点的NodeWithIdx实例，重复第2步，获取子节点
5、如果栈为空，算法结束。否则，栈顶对象的Idx值加1，继续第2步。

代码如下：

/// <summary>
/// 每一个分支生成一个用例
/// </summary>
/// <param name="process"></param>
/// <returns></returns>
public static List<FlowTestCase> GenerateTestCasesByProcess(Process process)
{
    //找到开始流程
    var startevent = process.Activities.FirstOrDefault(o => o.EventType == "StartEvent");

    var lst = new List<FlowTestCase>();
    var stack = new Stack<TempActivity>();
    var root = new TempActivity(startevent, stack.ToList());
    stack.Push(root);

    TempActivity current;
    while(stack.Count>0)
    {
        current = stack.Peek();
        if (current.NextActivities.Count == 0)
        {
            //完成一条路径
            FlowTestCase newcase = GetTestCase(stack.ToList(),process.Name, lst.Count);
            lst.Add(newcase);
            stack.Pop();

        }
        else if (current.NextActivities.Count > current.IndexOfNextConnection)
        {
            var nextact = new TempActivity(current.NextActivities[current.IndexOfNextConnection], stack.ToList());
            stack.Push(nextact);
            current.IndexOfNextConnection++;

        }
        else
        {
            //当前退栈
            stack.Pop();
        }
    }

    return lst;
}

TempActivity的目的是在寻找过程中，记录当前节点中已经遍历的连接的位置，如果相关节点已经遍历完成，就出栈。为防止循环计算，本算法排除驳回类型的路径，也就是不考虑后续节点返回到之前路过的某一节点的情况。

/// <summary>
/// 20190417 用于计算路径得结构
/// </summary>
public class TempActivity
{
    public Activity MyActiviy { get; set; }

    public int IndexOfNextConnection { get; set; }

    /// <summary>
    /// 前面得活动，为了避免循环，需要去掉下级连接中返回得路径
    /// </summary>
    private List<TempActivity> PrevActivities { get; set; }

    /// <summary>
    /// 下级节点，如果下级节点为0，说明形成最终路径
    /// </summary>
    public List<Activity> NextActivities { get; set; }

    public TempActivity(Activity MyA,List<TempActivity> prevActivities)
    {
        MyActiviy = MyA;
        PrevActivities = prevActivities;
        NextActivities = new List<Activity>();
        foreach(var conn in MyActiviy.OutConnections)
        {
            if (!prevActivities.Any(o => o.MyActiviy.Name == conn.TargetActivity.Name))
            {
                NextActivities.Add(conn.TargetActivity);
            }
        }
        IndexOfNextConnection = 0;
    }
}