笔记大全

Python怎么实现关键路径和七格图计算

更新时间：2023-07-11

什么是关键路径？

在项目管理中，关键路径指的是项目完成所必须的一系列活动中，耗时最长的组合。它是项目管理的重要概念之一，在项目进度计划、时间管理、资源管理等方面都有着重要的应用。关键路径分析是通过网络图的方式来进行计算，关键路径上的任务都是必须按时完成的任务，关键路径的长度也决定了整个项目的完成时间。那么在Python中如何实现关键路径分析呢？

def critical_path(tasks, precede):
    '''
    计算关键路径，tasks和precede分别代表任务和前置关系
    '''
    from collections import deque

    # 按拓扑排序找到最长路径
    in_degrees = dict((u, 0) for u in tasks)
    graph = dict((u, []) for u in tasks)
    for u, v in precede:
        in_degrees[v] += 1
        graph[u].append(v)

    q = deque()
    for u in in_degrees:
        if in_degrees[u] == 0:
            q.append(u)

    ts = dict((u, 0) for u in tasks)
    while q:
        u = q.popleft()
        for v in graph[u]:
            ts[v] = max(ts[v], ts[u] + 1)
            in_degrees[v] -= 1
            if in_degrees[v] == 0:
                q.append(v)

    # 找到关键路径
    es = dict((u, []) for u in tasks)
    for u, v in precede:
        pc = abs(ts[u] - ts[v]) == 1 or (ts[u] == ts[v] == 0)
        if pc:
            es[u].append(v)

    cp = []
    used = set()
    q = deque()
    for task in tasks:
        if in_degrees[task] == 0:
            q.append(task)
            used.add(task)

    while q:
        u = q.popleft()
        if u in es:
            for v in es[u]:
                if v not in used:
                    used.add(v)
                    cp.append((u, v))
                    q.append(v)

    return ts, cp

什么是七格图？

七格图是一种用于进程调度算法的可视化工具，可以帮助我们更好地理解各种调度算法在不同情况下的表现。它将所有进程的起始时间和结束时间使用七格图进行可视化，其中每个方格代表一个时间单位。常见的进程调度算法有很多种，例如先来先服务、短作业优先、响应时间优先等，这些算法的不同之处在于它们的调度策略，使用七格图可以帮助我们更好地理解这些算法。

import matplotlib.pyplot as plt
import numpy as np

def gantt_chart(process, start, end):
    '''
    生成进程的Gantt图，process为进程名称，start为起始时间，end为结束时间
    '''
    y_labels = list(process.keys())
    y_labels.reverse()

    fig, gnt = plt.subplots()

    gnt.set_ylim(0, len(process))
    gnt.set_xlim(start[0], end[-1] + 1)

    gnt.set_xlabel('时间')
    gnt.set_ylabel('进程')

    gnt.grid(True)

    for i, p_name in enumerate(y_labels):
        gnt.broken_barh([(start[i], end[i] - start[i])], (i, 1), facecolors=[f'C{i + 1}'])
        gnt.text(start[i] + 0.2, i + 0.4, p_name)

    plt.show()

如何将关键路径和七格图结合起来？

关键路径和七格图都是项目管理中比较常用的工具，结合起来可以更直观地展示整个项目的进度和负责人。使用Python实现时，我们可以先计算关键路径，然后根据关键路径的结果生成七格图。

def critical_path_gantt_chart(tasks, precede, process_time):
    '''
    结合关键路径和七格图来展示整个项目的进度和负责人
    tasks和precede分别代表任务和前置关系，process_time为每个任务的工期
    '''
    ts, cp = critical_path(tasks, precede)

    process = {}
    start = []
    end = []
    for i in range(len(tasks) + 1):
        start.append(0)
        end.append(ts[tasks[i - 1]])
        if i != 0 and i != len(tasks):
            process[tasks[i - 1]] = process_time[i - 1]

    gantt_chart(process, start, end)

代码的用途和规范

以上代码实现了关键路径和七格图的计算和展示，可以帮助我们更好地管理和控制整个项目的进度和质量。代码中使用了Python中的一些常见库和数据结构，例如collections中的deque和dict，matplotlib中的pyplot等。代码的规范性较高，拥有良好的注释和命名，适合用于实际项目中。

c语言编程笔录