首页 > 代码库 > WBS任务分解中前置任务闭环回路检测:有向图的简单应用(C#)

WBS任务分解中前置任务闭环回路检测:有向图的简单应用(C#)

1 场景描述

系统中用到了进度计划编制功能,支持从project文件直接导入数据,并能够在系统中对wbs任务进行增、删、改操作。wbs任务分解中一个重要的概念就是前置任务,前置任务设置确定了不同任务项之间的依赖关系,以软件开发的一般过程为例,需求调研就是系统设计的前置任务。具体来说前置任务又分为以下四种类型

  • Finish-to-Start (FS)

   把这个任务的开始日期和前提条件任务的结束日期对齐,一般用于串行的任务安排,前一个任务必须完成后才能启动下一个新任务

  • Start-to-Start (SS)

   把这个任务的开始日期和前提条件任务的开始日期对齐,一般用于并行任务的安排,也可以一个任务启动后,第二个任务延后或提前数日启动。

  • Finish-to-Finish (FF)

   把这个任务的结束日期和前提条件任务的结束日期对齐,可以用于协调任务的统一时间完成,这样可以定义好任务的开始时间

  • Start-to-Finish (SF)

   把这个任务的结束日期和前提条件任务的开始日期对齐,或者说是前置任务开始的日期决定了后续任务的完成时间

不管是哪种类型,某项任务总是依赖于其前置任务,这就要求,任务的前置关系不能出现循环(闭环),比如A->B->A这种情况是绝对不允许的。

技术分享

任务关系表基本数据格式如下

技术分享

SourceId跟TargetId标识任务的Id,通过SourceId、TargetId确定任务之间前后置关系。每个任务项可以看作是一个节点,任务的前置关系可以标识节点与节点之间有向连线,这在数据结构中是一种标准的有向图。

技术分享

2 图及图的存储结构

2.1 图的基本概念

先看一下数据结构中对图的定义:图是由有穷、非空点集和边集合组成,简写成G(V,E);

其中G表示Graph,V和E是图中两个基本元素,V表示Vertex(顶点),E表示Edge(边)。图按照边是否有方向又分为有向图和无向图,上面我们看到用箭头表示边方向的是一个有向图,无向图一般用下图方式表示。

技术分享

本文还涉及到关于图的一个重要概念是

:与某个顶点相连接的边数称为该定点的度

出度、入度:对于有向图的概念,出度表示此顶点为起点的边的数目,入度表示此顶点为终点的边的数目

2.2 图的存储结构

图的存储结构设计有很多种,常用的有邻接矩阵和邻接链表两种。

2.2.1 邻接矩阵

邻接矩阵采用2个数组,一个1维数组用来存储节点信息,一个2维数组用来存储边信息。其中二维数组arr[i][j]表示节点i到j的边信息,如果为1表示有边,如果为0表示无边。

 

技术分享

从这个矩阵中,很容易知道图中的信息。
1、可以判断任意两顶点之间是否有边无边
2、要知道某个顶点的度,其实就是这个顶点vi在邻接矩阵中第i行或(第i列)的元素之和
3、求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一遍,arc[i][j]为1就是邻接点

2.2.2 邻接链表

邻接链表总体思路如下:
图中顶点用一个一维数组存储,当然,顶点也可以用单链表来存储,不过,数组可以较容易的读取顶点的信息,更加方便。
图中每个顶点vi的所有邻接点构成一个线性表,由于邻接点的个数不定,所以,用单链表存储,无向图称为顶点vi的边表,有向图则称为顶点vi作为弧尾的出边表。
顶点表的各个结点由data和firstedge两个域表示,data是数据域,存储顶点的信息,firstedge是指针域,指向边表的第一个结点,即此顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex是邻接点域,存储某顶点的邻接点在顶点表中的下标,next则存储指向边表中下一个结点的指针。

技术分享

关于图的多种存储结构设计方式,请参考数据结构相关数据,慢慢理解。

本文采用邻接链表存储结构实现,对于有向图是否包含闭环的判断,采用的是拓扑排序方法,如果能够用拓扑排序完成对图中所有节点的排序的话,就说明这个图中没有环,而如果不能完成,则说明有环。

拓扑排序算法的主要操作步骤如下:

1、从有向图中选取一个没有前驱(即入度为0)的顶点,并输出之;

2、从有向图中删去此顶点同时找到该顶点的邻接点,将该顶点的邻接点的入度-1,若入度为0则压入栈中

     重复上述两步,直至图空,或者图不空但找不到入度为0的顶点为止。如果找到的顶点数与图的顶点集合总数相等,说明无闭环,否则说明存在闭环。具体实现思路还需要慢慢体会。

3 编码实现

根据上面对图的邻接链表相关定义及理解,首先定义图的顶点类。

/// <summary>/// 顶点/// </summary>/// <typeparam name="TValue">数据类型泛型</typeparam>public class Vertex<TValue>{    public TValue data; // 数据    public Node<TValue> firstLinkNode; // 第一个邻接节点    public bool visited; // 访问标志,遍历时使用    public int inDegree; // 表示该节点入度    /// <summary>    /// 构造函数    /// </summary>    /// <param name="value"></param>    public Vertex(TValue value)     {        data = value;    }}

定义链表邻接点类

/// <summary>/// 表示链表中的邻接点/// </summary>public class Node<TValue>{    public Vertex<TValue> adjvex; //顶点    public Node<TValue> next; //下一个邻接点    /// <summary>    /// 构造函数    /// </summary>    /// <param name="value"></param>    public Node(Vertex<TValue> value)    {        adjvex = value;    }}

定义邻接链表表示类,其中包含图的顶点集合的属性、添加顶点、添加边(有向边、无向边)、拓扑排序是否成功(有向图闭环检测)等操作方法,具体的实现及说明参看代码注释。

/// <summary>/// 图的邻接表表示类/// </summary>/// <typeparam name="T">泛型类型</typeparam>public class AdjacencyList<T>{    List<Vertex<T>> items; // 图的顶点集合    /// <summary>    /// 构造函数    /// </summary>    public AdjacencyList()    {        items = new List<Vertex<T>>();    }    /// <summary>    /// 添加一个顶点    /// </summary>    /// <param name="item"></param>    public void AddVertex(T item)    {   // 顶点不存在        if (!Contains(item))        {            items.Add(new Vertex<T>(item));        }    }    /// <summary>    /// 添加无向边    /// </summary>    /// <param name="from">头顶点</param>    /// <param name="to">尾顶点</param>    public void AddEdge(T from, T to)     {        Vertex<T> fromVer = Find(from); //找到起始顶点        if (fromVer == null)            throw new ArgumentException("头顶点并不存在!");        Vertex<T> toVer = Find(to); //找到结束顶点        if (toVer == null)            throw new ArgumentException("尾顶点并不存在!");        //无向图的两个顶点都需记录边信息,有向图只需记录单边信息        //即无相图的边其实就是两个双向的有向图边        AddDirectedEdge(fromVer, toVer);        AddDirectedEdge(toVer, fromVer);    }    /// <summary>    /// 查找图中是否包含某项    /// </summary>    /// <param name="item"></param>    /// <returns></returns>    public bool Contains(T data)     {        foreach (Vertex<T> v in items)        {            if (v.data.Equals(data))                return true;        }        return false;    }    /// <summary>    /// 根据顶点数据查找顶点    /// </summary>    /// <param name="data">数据</param>    /// <returns></returns>    public Vertex<T> Find(T data)     {        foreach (Vertex<T> v in items)        {            if (v.data.Equals(data))                return v;        }        return null;    }    /// <summary>    /// 添加有向边    /// </summary>    /// <param name="fromVer">头顶点</param>    /// <param name="toVer">尾顶点</param>    public void AddDirectedEdge(Vertex<T> fromVer, Vertex<T> toVer)    {        if (fromVer.firstLinkNode == null) //无邻接点时,当前添加的尾顶点就是firstLinkNode        {            fromVer.firstLinkNode = new Node<T>(toVer);        }        else // 该头顶点已经存在邻接点,则找到该头顶点链表最后一个Node,将toVer添加到链表末尾                                      {            Node<T> tmp, node = fromVer.firstLinkNode;            do            {   // 检查是否添加了重复有向边                if (node.adjvex.data.Equals(toVer.data))                {                    throw new ArgumentException("添加了重复的边!");                }                tmp = node;                node = node.next;            } while (node != null);            tmp.next = new Node<T>(toVer); //添加到链表未尾        }    }    /// <summary>    /// 拓扑排序是否能成功执行    /// 对有向图来说,如果能够用拓扑排序完成对图中所有节点的排序的话,就说明这个图中没有环,而如果不能完成,则说明有环。    /// </summary>    /// <returns></returns>    public bool TopologicalSort()    {        Stack<Vertex<T>> stack = new Stack<Vertex<T>>(); // 定义栈        items.ForEach(it =>    // 循环顶点集合,将入度为0的顶点入栈        {            if (it.inDegree == 0)                stack.Push(it);         //入度为0的顶点入栈        });        int count = 0;   // 定义查找到的顶点总数        while (stack.Count > 0)        {            Vertex<T> t = stack.Pop();  // 出栈            count++;            if (t.firstLinkNode != null)            {                Node<T> tmp = t.firstLinkNode;                while (tmp != null)                {                    tmp.adjvex.inDegree--;  // 邻接点入度-1                    if (tmp.adjvex.inDegree == 0) // 如果邻接点入度为0,则入栈                        stack.Push(tmp.adjvex);                    tmp = tmp.next; // 递归所有邻接点                }            }        }        if (count < items.Count) // 找到的结果数量小于图顶点个数相同,表示拓扑排序失败,表示有闭环        {            return false;        }        return true;    }}

根据数据库存储的SourceId和TargetId集合,封装一个GraphHelper类,提供一个检测有向图闭环的CheckDigraphLoop的静态方法

/// <summary>/// 图操作辅助类/// </summary>public class GraphHelper{    /// <summary>    /// 检测有向图是否有闭环回路    /// </summary>    /// <param name="originalData">初始数据:逗号分割的from跟to字符串集合</param>    /// <returns></returns>    public static bool CheckDigraphLoop(List<string> originalData)    {        AdjacencyList<string> adjacencyList = new AdjacencyList<string>();        string fromData = http://www.mamicode.com/string.Empty;        string toData = http://www.mamicode.com/string.Empty;        //构造有向图的邻接表表示        originalData.ForEach(it =>        {            fromData = it.Split(,)[0]; //得到from顶点数据            toData = http://www.mamicode.com/it.Split(,)[1];   //得到to定点数据            adjacencyList.AddVertex(fromData);            adjacencyList.AddVertex(toData);            var fromVertex = adjacencyList.Find(fromData); // 找到起始顶点            var toVertex = adjacencyList.Find(toData); // 找到目标顶点            toVertex.inDegree++; //目标顶点的入度+1            adjacencyList.AddDirectedEdge(fromVertex, toVertex); //添加有向边        });        return adjacencyList.TopologicalSort();    }}

测试

static void Main(string[] args) {     List<string> temp = new List<string>();     temp.Add("1,2");     temp.Add("1,3");     temp.Add("2,4");     temp.Add("2,5");     temp.Add("3,6");     temp.Add("3,7");     temp.Add("5,6");     temp.Add("6,1");     var result=  GraphHelper.CheckDigraphLoop(temp);     Console.WriteLine(result);     Console.ReadLine(); }

4 总结

参考数据结构关于图的相关C语言实现,用C#实现了通过拓扑排序算法进行的有向图闭环检测功能。

对于无向图的闭环检测检测一般采用如下思路:

第一步:删除所有度<=1的顶点及相关的边,并将另外与这些边相关的其它顶点的度减一。  

第二步:将度数变为1的顶点排入队列,并从该队列中取出一个顶点重复步骤一。  

如果最后还有未删除顶点,则存在环,否则没有环。 

感兴趣的朋友可以自己去揣摩实现一下。

WBS任务分解中前置任务闭环回路检测:有向图的简单应用(C#)