分类：计算机 / 算法
- 项目前后期关系算法问题
项目表中存在如下3个字段： 项目编号：当前项目的编号。 前期项目编号：当前项目的所有前期项目的项目编号，包括前期的前期。 后期项目编号：当前项目的所有后期项目的项目编号，包括后期的后期。 数据示例：有A、B、C、D四个项目，关系如下图，存储结构如下表。 前期项目编号 项目编号 后期项目编号 - A B,C,D A B C,D A,B C - A,B D - 需要对系统中现存的项目前后期关系数据做校验、修正、简化、分析。 校验 校验前后期关系数据的完整性、一致性。 算法思想：如果A在B的前期中，则B一定在A的后期中。 # 获取项目列表 projects = ... # 映射表：项目编号 → 项目 map = {project["code"]: project for project in projects} for project in projects: code = project["code"] for previous_code in project["previous_codes"]: if previous_code not in map: print(f"{code} 的前期项目 {previous_code} 不存在") elif code not in map[previous_code]["next_codes"]: print(f"{code} 不在前期项目 {previous_code} 的后期项目中") for next_code in project["next_codes"]: if next_code not in map: print(f"{code} 的后期项目 {next_code} 不存在") elif code not in map[next_code]["previous_codes"]: print(f"{code} 不在后期项目 {next_code} 的前期项目中") 修正 针对校验出的问题，修正办法： 项目编号不存在：可能是项目编号改变了但未同步更新，修正项目编号，修正同步更新机制；如果真的不存在，则确认后删除。 B不在其前期A的后期中：在A的后期中补充B。 A不在其后期B的前期中：在B的前期中补充A。 多次运行校验，直到无错误。 简化 前期、后期字段这么设计，是为了做链接，方便从一个项目跳转到有前后期关系的任意项目，但这给我们分析前后期关系情况带来了麻烦。实际上，项目表中只需要存储项目编号+直接后期项目编号（不包括后期的后期）这两个字段即可，直接前期、所有前期、所有后期都可以通过这两个字段动态计算出来。因此，在校验并修正之后，我们对关系的存储结构做简化。 算法思想：首先确认不存在隔代后期关系，即在A→B→C的场景下，A→C一定是无效的。那么，对于任意一条弧A→B，如果存在顶点P，且同时存在P→A、P→B，则P→B一定是无效的。 # 遍历每一条弧 for project in projects: code = project["code"] for next_code in project["next_codes"]: # 找出同时满足p→code和p→next_code的顶点 for p in projects: if code in p["next_codes"] and next_code in p["next_codes"]: # 删除弧p→next_code p["next_codes"].remove(next_code) 分析 聚类 将有前后期关系的所有项目聚类在一起，构成一个个独立的项目群。 算法思想：求有向图的所有极大连通子图，用并查集实现。 # 项目编号的并查集，简单实现 # 初始每个项目编号是一个集合 disjoint_set = [{project["code"]} for project in projects] for project in projects: code = project["code"] for next_code in project["next_codes"]: # 找出code所在的集合set1 for set1 in disjoint_set: if code in set1: # 找出next_code所在的集合set2 for set2 in disjoint_set: if next_code in set2: # 如果set1不是set2，则合并为一个集合 if set1 is not set2: set1.update(set2) disjoint_set.remove(set2) 算法结束时，并查集中的每个集合就是一个项目群。 图形化 我们希望以图形的方式直观地看到每个项目群中各项目的前后期关系。 Python的networkx+matplotlib库可以实现图（graph）的绘制。绘制时，需要计算顶点的摆放层号，使得绘图结果清晰、美观。 算法思想：对图做拓扑排序，入度为0的顶点被取出的批次，就是顶点的层号。 # 映射表：项目编号 → 项目 project_map = {project["code"]: project for project in projects} # 项目群序号 order = 1 # 遍历项目群 for codes in disjoint_set: # codes表示顶点集合 # 只关注多顶点子图，不关注单顶点子图 if len(codes) > 1: # 弧集合 arcs = [ (code, next_code) for code in codes for next_code in project_map[code]["next_codes"] ] # 映射表：顶点 → 弧尾顶点集合 in_map = {code: set() for code in codes} for arc in arcs: in_map[arc[1]].add(arc[0]) # 映射表：顶点 → 绘图时的层号 layer_map = {} # 拓扑排序，入度为0的顶点被取出的批次，就是层号 layer = 0 while in_map: # 找出入度为0的顶点，得到层号 zero_degree_codes = [ code for code, values in in_map.items() if len(values) == 0 ] for code in zero_degree_codes: layer_map[code] = layer layer += 1 # 删除入度为0的节点 for code in zero_degree_codes: del in_map[code] for values in in_map.values(): values.discard(code) # 绘图 fig, ax = plt.subplots(figsize=(24, 13.5)) graph = nx.DiGraph() graph.add_nodes_from(codes) graph.add_edges_from(arcs) for code in codes: graph.nodes[code]["subset"] = layer_map[code] positions = nx.multipartite_layout(graph) nx.draw_networkx_nodes(graph, positions, ax=ax, node_size=10000) nx.draw_networkx_edges(graph, positions, ax=ax, arrowsize=20, min_target_margin=50) nx.draw_networkx_labels(graph, positions, ax=ax, font_color="white") ax.axis("off") plt.savefig(f"output/项目前后期关系图/{order}.png") plt.close(fig) order += 1 算法缺陷：由于networkx按顺序绘制顶点，因此存在弧交叉、弧穿越顶点的问题，但总体上绘图结果还是很好的。