在写项目管理方面的软件，求关键路径的算法。有相关例子吗？

Question

在写项目管理方面的软件，求关键路径的数法。有相关例子吗？条件：
1.有10个任务(a,b,c,d,e,f,g,h,i,j)
2.每一个任务完成的时间都不相同。
3.比如a需要5天,b需要3天,c需要8天,d需要2天,e需要5天,f需要9天,g需要3天,h需要1天,i需要11天,j需要4天。
4.c完成任务后f才能做，g完成任务后a才能做,a和d必须同时完成后i才能做。
5.求计算出关键路径,来定出任务的核心流程。以上只是例子，真正的比这个复杂多了。可能有几百个子任务，要找到关键路径。有相关例子吗？ 谢谢大家！！

Answer 1

用C#写一个
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;namespace ConsoleApplication1
{
    interface ITask
    {
        int During { get; }
        IEnumerable<TaskItem> KeyPaths { get; }
    }    class TaskItem : ITask
    {
        public string Name { get; set; }
        public int During { get; set; }
        public IEnumerable<TaskItem> KeyPaths { get { return new TaskItem[] { this }; } }
    }    class TaskGroup : ITask
    {
        public List<ITask> Tasks { get; set; }
        public int During { get { return Tasks.Max(x => x.During); } }
        public IEnumerable<TaskItem> KeyPaths { get { return Tasks.OrderByDescending(x => x.During).First().KeyPaths; } }
    }    class TaskString : ITask
    {
        public List<ITask> Tasks { get; set; }
        public int During { get { return Tasks.Sum(x => x.During); } }
        public IEnumerable<TaskItem> KeyPaths { get { return Tasks.SelectMany(x => x.KeyPaths); } }
    }    static class ITaskHelper
    {
        public static TaskItem StartWith(string name, int during)
        {
            return new TaskItem() { Name = name, During = during };
        }        public static TaskGroup And(this ITask thistesk, ITask tesk)
        {
            if (thistesk is TaskGroup)
            {
                (thistesk as TaskGroup).Tasks.Add(tesk);
                return thistesk as TaskGroup;
            }
            return new TaskGroup() { Tasks = new List<ITask>() { thistesk, tesk } };
        }        public static TaskGroup And(this ITask thistesk, string name, int during)
        {
            return ITaskHelper.And(thistesk, new TaskItem() { Name = name, During = during });
        }        public static TaskString Then(this ITask thistesk, ITask tesk)
        {
            if (thistesk is TaskString)
            {
                (thistesk as TaskString).Tasks.Add(tesk);
                return thistesk as TaskString;
            }
            return new TaskString() { Tasks = new List<ITask>() { thistesk, tesk } };
        }        public static TaskString Then(this ITask thistesk, string name, int during)
        {
            return ITaskHelper.Then(thistesk, new TaskItem() { Name = name, During = during });
        }
    }    class Program
    {
        static void Main(string[] args)
        {
            var t = ITaskHelper.StartWith("找茶叶", 1).And("洗茶碗", 3).And(ITaskHelper.StartWith("洗茶壶", 2).Then("烧开水", 10)).Then("泡茶", 10).And("招呼客人聊天", 5).Then("上茶", 1);
            Console.WriteLine(string.Join("->", t.KeyPaths.Select(x => x.Name)));
        }
    }
}洗茶壶->烧开水->泡茶->上茶
Press any key to continue . . .VB能写得更优雅么？不服来辩。

Answer 2

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;namespace ConsoleApplication1
{
    interface ITask
    {
        int During { get; }
        IEnumerable<TaskItem> KeyPaths { get; }
    }    class TaskItem : ITask
    {
        public string Name { get; set; }
        public int During { get; set; }
        public int Order { get; set; }
        public IEnumerable<TaskItem> KeyPaths { get { return new TaskItem[] { this }; } }
        public override string ToString()
        {
            return string.Format("{0}({1})", Name, During);
        }
    }    class TaskGroup : ITask
    {
        public List<ITask> Tasks { get; set; }
        public int During { get { return Tasks.Max(x => x.During); } }
        public IEnumerable<TaskItem> KeyPaths { get { return Tasks.OrderByDescending(x => x.During).First().KeyPaths; } }
        public override string ToString()
        {
            return "[" + string.Join(" / ", Tasks.Select(x => x.ToString())) + "]";
        }
    }    class TaskString : ITask
    {
        public List<ITask> Tasks { get; set; }
        public int During { get { return Tasks.Sum(x => x.During); } }
        public IEnumerable<TaskItem> KeyPaths { get { return Tasks.SelectMany(x => x.KeyPaths); } }
        public override string ToString()
        {
            return string.Join(" -> ", Tasks.Select(x => string.Format("{0}", x.ToString())));
        }
    }    static class ITaskHelper
    {
        public static TaskItem StartWith(string name, int during)
        {
            return new TaskItem() { Name = name, During = during };
        }        public static TaskGroup And(this ITask thistesk, ITask tesk)
        {
            if (thistesk is TaskGroup)
            {
                (thistesk as TaskGroup).Tasks.Add(tesk);
                return thistesk as TaskGroup;
            }
            return new TaskGroup() { Tasks = new List<ITask>() { thistesk, tesk } };
        }        public static TaskGroup And(this ITask thistesk, string name, int during)
        {
            return ITaskHelper.And(thistesk, new TaskItem() { Name = name, During = during });
        }        public static TaskString Then(this ITask thistesk, ITask tesk)
        {
            if (thistesk is TaskString)
            {
                (thistesk as TaskString).Tasks.Add(tesk);
                return thistesk as TaskString;
            }
            return new TaskString() { Tasks = new List<ITask>() { thistesk, tesk } };
        }        public static TaskString Then(this ITask thistesk, string name, int during)
        {
            return ITaskHelper.Then(thistesk, new TaskItem() { Name = name, During = during });
        }
    }    class AutoSchedule
    {
        List<TaskItem> Tasks { get; set; }
        Dictionary<TaskItem, List<TaskItem>> DependList { get; set; }        private AutoSchedule()
        {
            Tasks = new List<TaskItem>();
            DependList = new Dictionary<TaskItem, List<TaskItem>>();
        }        public static AutoSchedule New() { return new AutoSchedule(); }        public AutoSchedule DefineTask(string name, int during)
        {
            if (Tasks.Any(x => x.Name == name)) throw new ArgumentException(name + " is already in list");
            Tasks.Add(new TaskItem() { Name = name, During = during });
            return this;
        }        bool AIsRequiredB(string a, string b)
        {
            if (DependList.Keys.Any(x => x.Name == a))
                return DependList[DependList.Keys.Single(x => x.Name == a)].Any(x => x.Name == b);
            return false;
        }        IEnumerable<string> whichRequiresA(string a)
        {
            if (DependList.Keys.Any(x => x.Name == a))
                return DependList[DependList.Keys.Single(x => x.Name == a)].Select(x => x.Name);
            return new string[] { };
        }        bool detectDependLoop(string task, string requiredtask)
        {
            return task == requiredtask || AIsRequiredB(task, requiredtask) || whichRequiresA(task).Any(x => detectDependLoop(x, requiredtask));
        }        public AutoSchedule DefineDepend(string name, params string[] required)
        {
            if (Tasks.All(x => x.Name != name) || required.Any(x => Tasks.All(y => y.Name != x)))
                throw new InvalidOperationException("no such a task");
            if (required.Any(x => detectDependLoop(x, name)))
                throw new InvalidOperationException("loop require detected");
            if (DependList.Keys.All(x => x.Name != name))
                DependList.Add(Tasks.Single(x => x.Name == name), new List<TaskItem>());
            DependList[DependList.Keys.Single(x => x.Name == name)]
                .AddRange(required.Select(x => Tasks.Single(y => y.Name == x)).Where(y => !DependList[DependList.Keys.Single(x => x.Name == name)].Contains(y)));
            return this;
        }        void decOrder(TaskItem task, int newOrder)
        {
            task.Order = newOrder < task.Order ? newOrder : task.Order;
            foreach (var t in DependList.Where(x => x.Value.Contains(task)).Select(x => x.Key))
                decOrder(t, newOrder - 1);
        }        public ITask ScheduleIt()
        {
            Tasks.ForEach(x => x.Order = Tasks.Count());
            foreach (var item in DependList)
            {
                decOrder(item.Key, item.Value.Min(x => x.Order) - 1);
            }
            TaskString ts = new TaskString();
            ts.Tasks = new List<ITask>();
            foreach (var item in Tasks.GroupBy(x => x.Order).OrderByDescending(x => x.Key))
            {
                TaskGroup tg = new TaskGroup();
                tg.Tasks = new List<ITask>();
                tg.Tasks.AddRange(item);
                ts.Tasks.Add(tg);
            }
            return ts;
        }
    }    class Program
    {
        static void Main(string[] args)
        {
            var t = AutoSchedule.New()
                .DefineTask("a", 5)
                .DefineTask("b", 3)
                .DefineTask("c", 6)
                .DefineTask("d", 2)
                .DefineTask("e", 5)
                .DefineTask("f", 9)
                .DefineTask("g", 3)
                .DefineTask("h", 1)
                .DefineTask("i", 11)
                .DefineTask("j", 4)
                .DefineDepend("f", "c")
                .DefineDepend("a", "g")
                .DefineDepend("i", "a", "d")
                .ScheduleIt();
            Console.WriteLine(t);
            Console.WriteLine(string.Join("->", t.KeyPaths.Select(x => x.Name)));
        }
    }
}[b(3) / c(6) / d(2) / e(5) / g(3) / h(1) / j(4)] -> [a(5) / f(9)] -> [i(11)]
c->f->i
Press any key to continue . . .

Answer 3

首先谢谢大家的发言。经过一段时间思考，我发现原来关键路径的问题是会随着子任务的增加变得越来越复杂。如果建立象MS project 这样的甘特图才能简单的体现出关键路径。但是甘特图控件一直没有找到。

Answer 4

做成ms project那样，gantt chart控件一搜一大把

Answer 5

这是拼写错误么？if (thistesk is TaskString)
优雅是个个人感觉的事情

Answer 6

是的，拼写错误。不过用VS真的不用担心，直接用重构-重命名就改过来了。
重构-重命名 是什么
我都是search ,replace

Answer 7

是的，拼写错误。不过用VS真的不用担心，直接用重构-重命名就改过来了。
重构-重命名 是什么
我都是search ,replace直接修改一处变量，VS会在这个变量下加上一个小红线，点一下，弹出菜单，选择重命名，收工。

Answer 8

请热心人,帮忙看看下面的求助吧!
请高手帮忙修正一个注册表模块!已经做成工程文件,有详细的实例的!
http://bbs.csdn.net/topics/390428796

Answer 9

是的，拼写错误。不过用VS真的不用担心，直接用重构-重命名就改过来了。
重构-重命名 是什么
我都是search ,replace直接修改一处变量，VS会在这个变量下加上一个小红线，点一下，弹出菜单，选择重命名，收工。这样的话工程中所有的变量名称都会被替换？

Answer 10

是的，拼写错误。不过用VS真的不用担心，直接用重构-重命名就改过来了。
重构-重命名 是什么
我都是search ,replace直接修改一处变量，VS会在这个变量下加上一个小红线，点一下，弹出菜单，选择重命名，收工。这样的话工程中所有的变量名称都会被替换？
所有代表这个变量的变量名都会被替换。比如你有2个方法，每个方法都定义了这么一个局部变量，那么只有当前的那个会被替换。

Answer 11

是的，拼写错误。不过用VS真的不用担心，直接用重构-重命名就改过来了。
重构-重命名 是什么
我都是search ,replace直接修改一处变量，VS会在这个变量下加上一个小红线，点一下，弹出菜单，选择重命名，收工。这样的话工程中所有的变量名称都会被替换？其实这很好理解，C#和VB不同的是，前者微软开放了编译器的每个编译步骤，比如词法分析、语法分析、语义分析、中间代码生成。所以给VS编写C#插件很容易，你可以用词法分析的结果做代码高亮，用语法分析的结果做代码折叠，用语义分析的结果做重构（对于重命名来说，无非就是修改抽象语法树，AST的一个变量声明的节点），还可以控制中间代码生成实现AOP动态拦截。当然了，如果能够开源，那就更好了。而给VB6开发插件，面对实现完全不透明且破烂不堪的VB语言，大部分的插件也就只能做做代码生成或者很低级的界面简化操作，要不就是错漏百出。