🏁 👱🏿 👩🏾‍🏫 图上的调试算法-现在带有图片 🎖️ 🎤 👨‍👧‍👦

想象一下第一年的典型情况：您了解并实现了Dinits算法，但该算法无效，您也不知道为什么。标准解决方案是逐步进行调试，每次在一张纸上绘制图形的当前状态时，但这非常不便。在软件工程一个学期项目中，我试图纠正这种情况，在一篇博文中，我将告诉您如何最终获得Visual Studio插件。您可以在这里下载它，源代码和文档可以在这里找到。这是为Dinits算法获得的图形的屏幕截图。

关于我自己

我叫奥尔加（Olga），我从圣彼得堡HSE的“应用数学和计算机科学”方向三年级毕业，获得软件工程学位。进入大学之前，我没有参与编程。

研究：要求

在我们的教师实践学期研究工作中。通常情况是这样的：在学期开始时，会进行研究工作的介绍-不同公司的代表提供各种项目。然后，学生选择自己喜欢的项目，主管选择自己喜欢的学生，依此类推。最后，每个学生都能找到适合自己的项目。

但是还有另一种方法：您可以独立地找到主管和项目，然后说服策展人，这个项目确实可以成为成熟的R＆D。为此，请证明：

您将要做一些新的事情。当然，该项目可能具有类似物，但您的版本应比它们具有一些优势。
任务应该很复杂，也就是说，应该有一个学期的工作，而不是一天的工作。同时，该项目必须在一个学期内真正完成。
您的项目应该对世界有用。就是说，当被问到为什么有必要这样做时，您不应该回答：“好吧，我需要做一些研究。”

我选择了第二种方式。在我与主管达成协议后，要做的第一件事就是找到项目的主题。想法清单包括：Lua的代码样式检查器，允许您计算零件表达式的调试器，以及用于奥林匹克/编程培训的工具，该工具可以使您直观地查看代码中正在发生的事情。即，用于任意数据结构的可视化程序与调试器结合在一起。例如，一个人写了一个笛卡尔树，并在过程中绘制了顶点，边，当前顶点等。最后，我决定继续讨论这个选项。

项目工作计划

我在该项目上的工作包括以下阶段：

需要对学科领域进行研究，以了解是否已经解决了这个问题（然后必须更改项目主题），存在哪些类似物，它们在工作中可以考虑的优缺点。
定义创建的工具将具有的特定功能 。该项目的主题是非常抽象的陈述，这对于确保任务相当复杂是必要的，但同时可以在一个学期内完成。
需要创建原型用户界面来演示如何使用创建的工具。它比单词描述的一组功能增加了更多的特异性。
依赖关系的选择 -您需要从开发人员的角度了解如何安排一切，并确定在编写代码的过程中将使用的工具。
创建一个原型（概念验证） ，这是一个最小的示例，其中大部分将被硬编码。在这个示例中，我不得不处理将要使用的所有工具，并且还学习了如何解决在此过程中出现的所有困难，以便最终版本已经“干净”了。
在内容部分上工作 ，即工具逻辑的开发和实现。
需要项目保护 ，以便快速谈论已完成的工作，并有机会向所有人，甚至是那些不屑一顾的人进行评估。这是毕业前的训练。同时，一个制作精良的项目并不能保证该报告的质量，因为它需要其他技能，例如与公众对话的能力。

我总是和我的主管一起进行计划。我们也总是想出并讨论此过程中出现的所有想法。另外，主管给了我有关代码的建议，并帮助了时间管理。关于所有技术问题（难以理解的错误等），我也经常报告，但大多数情况下，我自己设法解决了这些问题。

学科研究

首先，我们的领导层应该已经确信，这个话题值得我研究。从第一点开始：寻找类似物。

事实证明，有许多类似物。但是它们大多数是为内存可视化而设计的。也就是说，他们将在笛卡尔树的可视化方面做得很好，但他们无法理解数组上的堆不应绘制为数组，而应绘制为树。这些类似物包括gdbgui ，数据显示调试器，Eclipse jGRASP的插件和Visual Studio 数据结构Visualizer的插件。后者也是针对奥林匹克编程问题而创建的，但仅能显示指针上的数据结构。

还有其他一些工具：用于Python的Algojammer （我们希望加号是奥林匹克竞赛中最流行的语言）和1994年开发的Lens工具。通过描述判断，后者几乎完成了所需的工作，但不幸的是，它是在Sun OS 4.1.3（1992年以来的操作系统）下创建的。因此，尽管有源代码可用，但还是决定不要在这种可疑的考古上浪费时间。

因此，经过一些研究，发现可以完全满足我们要求并同时在现代机器上工作的Tula尚不存在。

功能定义

第二步是证明此任务相当复杂，但可行。为此，有必要提出一些比“我想要一幅美丽的图画，并让一切立即变得清晰起来”更具体的内容。

在这个项目中，我们决定只专注于可视化图形：图形上有很多算法可以用不同的方式实现，即使缩小范围，任务仍然是不平凡的。

还必须以某种方式将工具与调试器集成在一起，这或多或少是显而易见的。我们需要能够查看变量和表达式的值，并从这些值绘制出完整的图片。

之后，有必要提出一种特定的语言，使我们能够根据需要根据程序的当前状态构建图形。除了图形本身之外，还必须提供以下功能：更改顶点和边缘的颜色，为其添加任意标签以及更改其他属性。因此，第一个想法是：

确定我们有哪些顶点，例如，从0到n的数字。
使用布尔条件确定顶点之间是否存在边。在这种情况下，边线的类型不同，每种类型都有其自己的属性集。
此外，我们还可以使用布尔条件定义顶点属性（例如颜色）。
使用调试器逐步执行以下步骤：计算所有表达式，检查所有条件，并据此绘制图形。

用户界面原型

我在NinjaMock中绘制了用户界面的原型。这样做是为了更好地理解从用户角度看界面的外观，以及用户需要执行的操作。如果原型存在问题，我们将理解存在一些逻辑上的不一致，因此应该放弃这个想法。为了保真，我采用了一些算法。下图显示了我如何想象DFS可视化设置和Floyd算法的示例。

正如我想象的DFS设置。 该图存储为邻接表，因此顶点i和j之间的边由条件g[i].find() != g[i].end() （实际上，为了不重复边，必须检查i <= j ）。 DFS路径单独显示： p[j] == i 。 这些边缘将被定向。

我认为对于弗洛伊德算法，有必要将存储在数组c的实际边绘制为黑色，将灰色（在此阶段找到的最短路径）存储在数组d绘制为灰色。 对于每个边缘和最短路径，将写入其权重。

依赖选择

对于下一步，有必要了解如何进行所有这些操作。首先，需要与调试器集成。当单词“ debugger”是gdb时，想到的第一件事是，但是您必须从头开始创建整个图形界面，这对于一个学期的学生来说确实很难。第二个显而易见的想法是为某些现有的开发环境创建一个插件。作为选项，我考虑了QTCreator，CLion和Visual Studio。

CLion选项几乎立即被废弃，因为，首先，它已关闭了源代码，其次，对于文档而言，一切都非常糟糕（没有人需要其他困难）。与Visual Studio不同，QTCreator是跨平台的和开放源代码的，因此，起初，我们决定对此进行详细介绍。

然而，事实证明，QTCreator不适合使用插件进行扩展。为QTCreator创建插件的第一步是从源代码构建。我花了一个半星期。最后，我发送了两个有关组装过程的错误报告（在这里和那里）。是的，这就是为了发现QTCreator中的调试器没有公共API而花费了很多心血来构建QTCreator。我回到了另一个选择，即Visual Studio。

事实证明，这是正确的决定：Visual Studio不仅具有出色的API，而且具有出色的文档。通过调用_debugger.GetExpression(...).Value简化了表达式_debugger.GetExpression(...).Value 。 Visual Studio还提供了遍历框架并在任何框架的上下文中评估表达式的功能。为此，请将属性CurrentStackFrame更改为所需的属性。您还可以跟踪调试程序竞赛的更新，以在更改时重画图像。

当然，这不是我应该从头开始进行图形可视化的方法-为此有很多特殊的库。其中最著名的是Graphviz ，我们计划首先使用它。但是对于Visual Studio插件而言，将库用于C＃将更加合乎逻辑，因为我将在上面编写它。我在Google上搜索了一下，发现了MSAGL库：它具有所有必需的功能，并且具有简单直观的界面。

概念证明

现在，一方面具有用于计算任意表达式的机制，另一方面具有用于可视化图形的库，因此有必要制作一个原型。首先为DFS制作了原型，然后以Dinits 算法， Kuhn算法，双连接组件搜索，笛卡尔树和SNM为例。从第一年到第二年，我采用了这些算法的旧实现，创建了一个新插件，并绘制了与此任务相对应的图形（所有变量名均已硬编码）。这是我为Kuhn算法得到的图的示例：

在此图上，当前匹配的边显示为紫色，当前dfs顶点显示为红色，访问的顶点为灰色，不是来自匹配的交替链的边显示为红色。

我认为允许稍微修改算法代码以使其更容易可视化是允许的。例如，对于笛卡尔树，事实证明，将所有创建的节点添加到向量比绕过插件内部的树更容易。

一个不愉快的发现是Visual Studio中的调试器不支持从STL调用方法和函数。这意味着不可能像最初假定的那样使用std::find检查容器中元素的存在。通过创建用户定义的函数或通过在布尔数组中复制属性“元素包含在容器中”，可以解决此问题。

在我的试用插件中，发生了类似以下的事情（如果图形存储为邻接表）：

首先是从0到_debugger.GetExpression("n").Value的for循环_debugger.GetExpression("n").Value ，该_debugger.GetExpression("n").Value将所有顶点添加到图中，每个顶点都有自己的编号。
然后有两个嵌套的for _debugger.GetExpression($"g[{i}].size()").Value ，第一个嵌套for i从0到n ，第二个嵌套的j从0到_debugger.GetExpression($"g[{i}].size()").Value和edge {i, _debugger.GetExpression($"g[{i}][{j}]").Value} 。
如果需要，一些附加信息将添加到顶点和边的标签中。例如，数组d的值负责到选定顶点的距离。
如果该算法基于dfs，则在此之后，所有玻璃框架以及堆栈上的所有顶点（ stackFrame.FunctionName.Equals("dfs") && stackFrame.Arguments.Item(1) == v ）都以灰色突出显示。
然后，对于从0到n每个i ，表示顶点的数目，检查了一些条件，如果满足这些条件，则某些属性在顶点处更改，通常是颜色更改。

那时，我“按需”编写了代码，而没有试图为所有算法提出通用方案，或者至少以某种方式编写了精美的代码。每个新插件的创建始于上一个插件的复制粘贴。

图形配置

在研究之后，有必要制定一个可应用于所有算法的通用方案。引入的第一件事是顶点和边的索引。每个索引都有一个唯一的名称，范围的结尾是使用_debugger.GetExpression计算的。要访问索引的值，请使用其名称加上__（即__x__）。具有替换索引值的位置以及当前函数的名称（__CURRENT_FUNCTION__）及其参数值（__ARG1 __，__ ARG2__等）的表达式称为模板。

将索引替换为每个顶点或边，然后在调试器中对其进行计算。模板用于过滤掉一些索引值（如果图形存储为邻接矩阵c ，则索引将是0和n之间的a和b，用于验证的模板是c[__a__][__b__] ）。索引范围的边界也是模板，因为它们可能包含以前的索引。

图可以具有不同类型的顶点和边。例如，在二部图中搜索最大匹配的情况下，可以对每个分数分别进行索引。因此，针对顶点和边引入了族的概念。对于每个系列，索引和所有属性都是独立确定的。在这种情况下，边可以连接来自不同族的顶点。

您可以为顶点或边族指定特定的属性，这些属性将有选择地应用于族中的元素。如果满足条件，则应用该属性。条件由一个评估为true或false的模板和一个函数名称的正则表达式组成。仅针对当前玻璃框架或所有玻璃框架检查该条件（然后，如果至少满足一个条件，则认为已满足）。

属性非常多样化。对于顶点：标签，填充颜色，边框颜色，边框宽度，形状，边框样式（例如，虚线）。对于边缘：标签，颜色，宽度，样式，方向（您可以指定两个箭头-从头到尾，反之亦然；在这种情况下，可以同时有两个箭头）。

重要的是，每次从头开始绘制图形时，都不会以任何方式考虑先前的状态。如果图形在算法中动态变化，这可能是一个问题-顶点和边会急剧改变其位置，然后很难理解正在发生的事情。

可以在此处找到图形配置的详细说明。

使用者介面

通过界面，我决定不打扰。带有设置的主窗口（ ToolWindow ）包含以JSON序列化的配置的文本区域以及一系列顶点和边系列。每个族都有其自己的设置窗口，并且族中的每个属性都具有另一个窗口（获得了三层嵌套）。图形本身在单独的窗口中绘制。将其放在ToolWindow中不起作用，因此我向MSAGL开发人员发送了错误报告，但他们回答这不是目标用例。另一个错误报告已发送到Visual Studio，因为TextBoxes有时会挂在其他设置窗口中。

外挂程式

为了配置图形，该插件具有一个用户界面，并且能够（取消）以JSON序列化配置。所有组件的交互的一般方案如下：

蓝色显示了最初创建的组件，灰色显示了我创建的组件。启动Visual Studio时，扩展名会初始化（此处主要组件指定为Main）。用户有机会通过界面指定配置。每次更改调试器上下文时，都会通知主要组件。如果定义了配置并执行了要调试的程序，则将启动GraphRenderer。他收到配置输入，并在调试器的帮助下建立一个图形，然后将其显示在特殊的窗口中。

例子

结果，我创建了一个工具，使您可以可视化图形算法，并且需要对代码进行一些小的更改。它已经在八个不同的任务上进行了测试。这是一些结果图片：

福特-贝尔曼算法（Ford-Bellman algorithm）：计算房屋的最短路径的顶点由房屋表示，当前为顶点找到的最短距离为d，红色表示松弛通过的边缘。

DFS动画-当前顶点显示为红色，堆栈中的顶点为灰色，其他访问的顶点为绿色。 覆盆子肋骨指示旁路的方向。

此处提供更多示例算法。

近红外保护

为了保护研究工作，要求学生在七分钟内讲述一个学期的工作。同时，无论该主题是作为研究工作的一部分提出的还是由学生自己发现的，您都需要能够做出回答，以说明为什么该项目的主题属于开头所述的要求。通常，报告的结构如下：首先要有动机，然后要对类似物进行审查，然后说说为什么它们不适合我们，然后制定目的和目标，然后描述如何解决每个任务。最后是一张包含结果的幻灯片，它再次表明目标已经实现，所有任务都已解决。

由于我已经在初始阶段决定了类似物的动机和审查，因此我只需要将所有信息收集在一起并压缩到7分钟即可。最后，我成功了，防守顺利进行，我获得了最高的研究分数。

图上的调试算法-现在带有图片