代做C++图论、做写图论C++程序

日期：2018-05-09 12:56

图论Projet

目标：

1.在内存中表示出一个有向带权图

2.能检测出是否存在环路

3.计算等级

4.搜索存在的路径（可访问性）

5.验证调度图的属性

6.分别最早和最迟计算日历

7.从约束表创建调度图

编程语言

C / C ++，你的程序必须由你的老师在他的PC上编译。他会告诉你他有什么。你将不得不适应它（使用你自己的电脑和学校的电脑）。

功能实现

文档的这一部分给出了您需要执行的程序的功能描述。 它通常描述了它的体系结构。

要实施的功能可以分为“级别”或“操作模式”。 第一级对应于实现通用图处理。 在这些“级别”中进展越多，则更具体的处理被集成调度图。

注意：

在验证你的工作时，将验证你的程序实际上实现了不同的级别。 例如，将验证您的程序是否能够检查任何图形上是否存在环路，并且能够计算包含多个入口点和/或点的图表上的等级值。输出。

提示（来自之前的说明）：例如，您的程序可能会先询问用户所需的“操作模式”或“级别”。

int main(){

…

cout << "Niveau souhaité" ;

cin >> niveau ;

switch (niveau) {

case 1 : …

case 2 : …

case 4 : …

case 4 : …

} ;

…

}

或链接4个级别：

int main(){

…

cout << "Niveau 1" ;

…

cout << "Niveau 2" ;

…

cout << "Niveau 3" ;

…

cout << "Niveau 4" ;

…

}

等级1“基本”：加载图和一般的处理方

导入：读取“文本”文件中的给定图形，并将其存储在内存中“图形”文件：见附录。

数据结构：文件中描述的图形存储在内存中。您的程序必须能够在内存中存储具有以下属性的任何图形：

有向图并且有值（每个弧都有整数值）。从给定顶点到另一个给定顶点的最多存在1个弧（无多图）。

顶点由数字标识，从'0'开始并且不打破编号：例如对于包含10个顶点的图，从'0'到'9'的顶点。只有在程序执行期间才知道顶点的数量和弧的数量。 您的程序不得在顶点数量，弧线数量或弧线值方面施加限制。

处理完成后，程序不能再访问该文件，并且只能访问内存中图形的表示。

以邻接矩阵和值矩阵的形式显示图形。

通过读取文件从内存中查看内容，不能直接。 建议用屏幕上的空白框替换邻接矩阵的零点，当然如果列对齐正确执行。

检测图中是否存在环路

你的程序必须打印执行的痕迹。 例如，对于入口点消除技术，它必须指示每个步骤消除的顶点。

执行轨迹的内容当然取决于实施的方法。

计算每个顶点的等级

至于环路检测，程序必须显示其执行的痕迹，例如分配给每次迭代的队列。

等级2：验证调度图和计算的日历和边距

除了为第1级提供的发展之外：

验证图形的属性

你的程序需要验证包括：

- 图形只包含一个入口点和一个出口点（对于级别2，我们不需要手动添加输入和输出顶点：图形会被视为 它在输入文件中描述），

- 任何顶点是从入口点访问，

- 所有其他顶点都可以访问出口点，

- 弧的值是正值或零，

- 所有来自顶点的边都具有相同的值，

- 图形不包含电路（使用第1级的代码）。

计算日历和边距

首先计算最早的日历，然后计划以后。 最初认为项目结束日期等于其最早日期，然后重新计算通过最早在项目结束日期的110％确定日期来完成 （可能四舍五入为整数值）。 对于每种情况，程序都会计算边距。

您可以使用您选择的方法计算日历和边距。 某些方法不使用顶点排序，但仍需要始终将此排序计算插入到程序中。

级别3：加载约束表

这里，图形是从一个文本文件中读取的约束表中创建的。 然后在计算日历和边距之前检查调度图的属性。

除了为第1级和第2级开发的内容之外：

约束文件见附件。

任务由整数表示，从'1'开始，并且没有破坏序列（例如，对于10个任务的项目，从'1'到'10'）。

约束是在类和TD中接近的类型：X任务只能在Y任务完成时开始。

导入和创建图形

根据在课堂和TD中看到的原理，将约束读取并转换为图形。 有一个在这个阶段没有检查。顶点“开始”和“结束”当然会添加相应的弧线。

等级4：加载约束表并控制图的构造

除了为1到3级开发的内容之外：

导入并构建正确的图形

当加载约束和创建图表时，必须检查它必须遵守的属性。 如果情况并非如此，则认为约束条件不一致。 用户可以选择直接查询修改一个或多个约束。

这种机制可以在全局读取所有约束并完成图形创建之后完成，也可以在分析过程中每次将约束转换为圆弧时完成。

警告：与用户交互时，请仅参考约束条件，而不是图表。

例如，我们不会对用户说“在已经存在的弧（A，B）和（B，C）中添加弧（C，A）时存在问题”，

而是：“考虑到已满足”B需求A“和”C需求B“的约束'A需求C'，存在一个问题”。

附件 1 – « 图形»文件结构

你的txt文件应该有以下的结构

第一行    顶点数量

第二行    弧的数量

第三行 到3+ 每行末尾加« 弧的数量 »初始端点，然后末端点，随后是弧的值

例如，如果文件中的内容如下

3

4

1 2 25

1 0 12

2 0 -5

0 1 0

这对应于包含从'0'到'2'编号的3个顶点（连续编号）和4个圆弧（1,2），（1,0），（2,0），（0,1），弧的值分别为25，12，-5和0。

附件 2 –« 约束 »图的结构

你的txt文件应该有以下的结构

第一行

第二行 到2 + « 任务的编号»

剩下的行

任务数量

任务的编号和它的执行时间

x（一个任务的号码），然后是一个数字列表y1 y2 ...，

后跟'0'，表示任务＃x无法启动

只有当任务完成时。

例如，如果你的约束文件中包括以下内容

5

12

225

34

41

52

10

31 2 0

21 0

51 4 0

40

这对应于包含5个编号从'1'到'5'的任务的项目，其持续时间分别为2,25,4,1和2，并且约束条件为：

任务1和4没有限制，可以随时开始

2只能在1完成时启动

3只能在1和2完成时启动

5只能在1和4完成时启动