系统中用到了进度计划编制功能,支持从 project 文件直接导入数据,并能够在系统中对 wbs 任务进行增、删、改操作。wbs 任务分解中一个重要的概念就是前置任务,前置任务设置确定了不同任务项之间的依赖关系,以软件开发的一般过程为例,需求调研就是系统设计的前置任务。具体来说前置任务又分为以下四种类型
把这个任务的开始日期和前提条件任务的结束日期对齐,一般用于串行的任务安排,前一个任务必须完成后才能启动下一个新任务
把这个任务的开始日期和前提条件任务的开始日期对齐,一般用于并行任务的安排,也可以一个任务启动后,第二个任务延后或提前数日启动。
把这个任务的结束日期和前提条件任务的结束日期对齐,可以用于协调任务的统一时间完成,这样可以定义好任务的开始时间
把这个任务的结束日期和前提条件任务的开始日期对齐,或者说是前置任务开始的日期决定了后续任务的完成时间
不管是哪种类型,某项任务总是依赖于其前置任务,这就要求,任务的前置关系不能出现循环(闭环),比如 A->B->A 这种情况是绝对不允许的。
任务关系表基本数据格式如下
SourceId 跟 TargetId 标识任务的 Id,通过 SourceId、TargetId 确定任务之间前后置关系。每个任务项可以看作是一个节点,任务的前置关系可以标识节点与节点之间有向连线,这在数据结构中是一种标准的有向图。
先看一下数据结构中对图的定义:图是由有穷、非空点集和边集合组成,简写成 G(V,E);
其中 G 表示 Graph,V 和 E 是图中两个基本元素,V 表示 Vertex(顶点),E 表示 Edge(边)。图按照边是否有方向又分为有向图和无向图,上面我们看到用箭头表示边方向的是一个有向图,无向图一般用下图方式表示。
本文还涉及到关于图的一个重要概念是度。
度:与某个顶点相连接的边数称为该定点的度
出度、入度:对于有向图的概念,出度表示此顶点为起点的边的数目,入度表示此顶点为终点的边的数目
图的存储结构设计有很多种,常用的有邻接矩阵和邻接链表两种。
邻接矩阵采用 2 个数组,一个 1 维数组用来存储节点信息,一个 2 维数组用来存储边信息。其中二维数组 arr[i][j] 表示节点 i 到 j 的边信息,如果为 1 表示有边,如果为 0 表示无边。
从这个矩阵中,很容易知道图中的信息。1、可以判断任意两顶点之间是否有边无边 2、要知道某个顶点的度,其实就是这个顶点 vi 在邻接矩阵中第 i 行或(第 i 列)的元素之和 3、求顶点 vi 的所有邻接点就是将矩阵中第 i 行元素扫描一遍,arc[i][j] 为 1 就是邻接点
邻接链表总体思路如下:图中顶点用一个一维数组存储,当然,顶点也可以用单链表来存储,不过,数组可以较容易的读取顶点的信息,更加方便。图中每个顶点 vi 的所有邻接点构成一个线性表,由于邻接点的个数不定,所以,用单链表存储,无向图称为顶点 vi 的边表,有向图则称为顶点 vi 作为弧尾的出边表。 顶点表的各个结点由 data 和 firstedge 两个域表示,data 是数据域,存储顶点的信息,firstedge 是指针域,指向边表的第一个结点,即此顶点的第一个邻接点。边表结点由 adjvex 和 next 两个域组成。adjvex 是邻接点域,存储某顶点的邻接点在顶点表中的下标,next 则存储指向边表中下一个结点的指针。
关于图的多种存储结构设计方式,请参考数据结构相关数据,慢慢理解。
本文采用邻接链表存储结构实现,对于有向图是否包含闭环的判断,采用的是拓扑排序方法,如果能够用拓扑排序完成对图中所有节点的排序的话,就说明这个图中没有环,而如果不能完成,则说明有环。
拓扑排序算法的主要操作步骤如下:
1、从有向图中选取一个没有前驱 (即入度为 0) 的顶点,并输出之;
2、从有向图中删去此顶点同时找到该顶点的邻接点,将该顶点的邻接点的入度 - 1,若入度为 0 则压入栈中
重复上述两步,直至图空,或者图不空但找不到入度为 0 的顶点为止。如果找到的顶点数与图的顶点集合总数相等,说明无闭环,否则说明存在闭环。具体实现思路还需要慢慢体会。
根据上面对图的邻接链表相关定义及理解,首先定义图的顶点类。
- /// <summary>
- /// 顶点
- /// </summary>
- /// <typeparam name="TValue">数据类型泛型</typeparam>
- public classVertex
- {
- publicTValue data;// 数据
- publicNode firstLinkNode; // 第一个邻接节点
- public boolvisited;// 访问标志,遍历时使用
- public intinDegree;// 表示该节点入度
- /// <summary>
- /// 构造函数
- /// </summary>
- /// <param name="value"></param>
- public Vertex(TValue value)
- {
- data = value;
- }
- }
定义链表邻接点类
- /// <summary>
- /// 表示链表中的邻接点
- /// </summary>
- public classNode
- {
- publicVertex adjvex; //顶点
- publicNode next; //下一个邻接点
- /// <summary>
- /// 构造函数
- /// </summary>
- /// <param name="value"></param>
- publicNode(Vertex value)
- {
- adjvex = value;
- }
- }
定义邻接链表表示类,其中包含图的顶点集合的属性、添加顶点、添加边(有向边、无向边)、拓扑排序是否成功(有向图闭环检测)等操作方法,具体的实现及说明参看代码注释。
- /// <summary>
- /// 图的邻接表表示类
- /// </summary>
- /// <typeparam name="T">泛型类型</typeparam>
- public classAdjacencyList
- {
- List> items; // 图的顶点集合
- /// <summary>
- /// 构造函数
- /// </summary>
- public AdjacencyList()
- {
- items =newList>();
- }
- /// <summary>
- /// 添加一个顶点
- /// </summary>
- /// <param name="item"></param>
- public void AddVertex(T item)
- { // 顶点不存在
- if(!Contains(item))
- {
- items.Add(newVertex(item));
- }
- }
- /// <summary>
- /// 添加无向边
- /// </summary>
- /// <param name="from">头顶点</param>
- /// <param name="to">尾顶点</param>
- public voidAddEdge(Tfrom, T to)
- {
- Vertex fromVer = Find(from);//找到起始顶点
- if(fromVer ==null)
- throw newArgumentException("头顶点并不存在!");
- Vertex toVer = Find(to); //找到结束顶点
- if(toVer ==null)
- throw newArgumentException("尾顶点并不存在!");
- //无向图的两个顶点都需记录边信息,有向图只需记录单边信息
- //即无相图的边其实就是两个双向的有向图边
- AddDirectedEdge(fromVer, toVer);
- AddDirectedEdge(toVer, fromVer);
- }
- /// <summary>
- /// 查找图中是否包含某项
- /// </summary>
- /// <param name="item"></param>
- /// <returns></returns>
- public bool Contains(T data)
- {
- foreach(Vertex v in items)
- {
- if (v.data.Equals(data))
- return true;
- }
- return false;
- }
- /// <summary>
- /// 根据顶点数据查找顶点
- /// </summary>
- /// <param name="data">数据</param>
- /// <returns></returns>
- publicVertex Find(T data)
- {
- foreach(Vertex v in items)
- {
- if (v.data.Equals(data))
- return v;
- }
- return null;
- }
- /// <summary>
- /// 添加有向边
- /// </summary>
- /// <param name="fromVer">头顶点</param>
- /// <param name="toVer">尾顶点</param>
- public voidAddDirectedEdge(Vertex fromVer, Vertex toVer)
- {
- if(fromVer.firstLinkNode ==null)//无邻接点时,当前添加的尾顶点就是firstLinkNode
- {
- fromVer.firstLinkNode =newNode(toVer);
- }
- else // 该头顶点已经存在邻接点,则找到该头顶点链表最后一个Node,将toVer添加到链表末尾
- {
- Node tmp, node = fromVer.firstLinkNode;
- do
- { // 检查是否添加了重复有向边
- if (node.adjvex.data.Equals(toVer.data))
- {
- throw newArgumentException("添加了重复的边!");
- }
- tmp = node;
- node = node.next;
- } while(node !=null);
- tmp.next =newNode(toVer); //添加到链表未尾
- }
- }
- /// <summary>
- /// 拓扑排序是否能成功执行
- /// 对有向图来说,如果能够用拓扑排序完成对图中所有节点的排序的话,就说明这个图中没有环,而如果不能完成,则说明有环。
- /// </summary>
- /// <returns></returns>
- public bool TopologicalSort()
- {
- Stack> stack = newStack>(); // 定义栈items.ForEach(it =>// 循环顶点集合,将入度为0的顶点入栈
- {
- if(it.inDegree ==0)
- stack.Push(it); //入度为0的顶点入栈
- });
- intcount =0;// 定义查找到的顶点总数
- while(stack.Count >0)
- {
- Vertex t = stack.Pop(); // 出栈count++;
- if(t.firstLinkNode !=null)
- {
- Node 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 boolCheckDigraphLoop(List<string> originalData)
- {
- AdjacencyList<string> adjacencyList =newAdjacencyList<string>();
- stringfromData =string.Empty;
- stringtoData =string.Empty;
- //构造有向图的邻接表表示originalData.ForEach(it =>
- {
- fromData = it.Split(',')[0];//得到from顶点数据toData = it.Split(',')[1];//得到to定点数据
- adjacencyList.AddVertex(fromData);
- adjacencyList.AddVertex(toData);
- varfromVertex = adjacencyList.Find(fromData);// 找到起始顶点
- vartoVertex = adjacencyList.Find(toData);// 找到目标顶点toVertex.inDegree++;//目标顶点的入度+1adjacencyList.AddDirectedEdge(fromVertex, toVertex);//添加有向边
- });
- return adjacencyList.TopologicalSort();
- }
- }
测试
- static voidMain(string[] args)
- {
- List<string> temp =newList<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");
- varresult= GraphHelper.CheckDigraphLoop(temp);
- Console.WriteLine(result);
- Console.ReadLine();
- }
参考数据结构关于图的相关 C 语言实现,用 C# 实现了通过拓扑排序算法进行的有向图闭环检测功能。
对于无向图的闭环检测检测一般采用如下思路:
第一步:删除所有度 <=1 的顶点及相关的边,并将另外与这些边相关的其它顶点的度减一。
第二步:将度数变为 1 的顶点排入队列,并从该队列中取出一个顶点重复步骤一。
如果最后还有未删除顶点,则存在环,否则没有环。
感兴趣的朋友可以自己去揣摩实现一下。
来源: http://www.cnblogs.com/fonour/p/6875032.html