问题标签 [digraphs]

一位同事给出的一个谜题，我无法弄清楚这个 C 程序实际上是如何编译和运行的。这个>>>=运算符和奇怪的1P1文字是什么？我已经在 Clang 和 GCC 中进行了测试。没有警告，输出为“？？？”

我在 Ruby 1.9.3 中有一个构建RubyTree的程序。我的数据最好被描述为有向无环图（DAG）；请注意，它不是多树。好吧，至少数据应该是一个 DAG，尽管用户尽最大努力用坏数据挫败我的程序。

我通过解析 XML 文档动态构建 DAG。XML 文档没有明确指定树结构，但确实提供了整数 ID 的交叉引用，这些 ID 在文档中的元素之间建立了链接。

我需要确保 RubyTree 不包含任何循环。源数据可能（错误地）有一个循环，如果有，我的程序需要知道它，而不是进入无限循环或崩溃。目前，为了实现这一点，我将 Ruby 标准库的TSort模块混合到 RubyTree 的Tree::TreeNode类中。这使用 Tarjan 的算法在每次添加节点时对图执行拓扑排序。在拓扑排序期间，如果检测到循环，则会引发异常——这正是我想要的。

例如：

我还必须修改其他一些方法。基本上任何需要遍历树或需要实现 TSort 的子节点，或者摆脱它对遍历的依赖（例如，我简化Tree::TreeNode#to_s()为 return Tree::TreeNode#name。）

现在，我的程序在功能上是正确的。我已经完成了重要的测试，结果运行良好：我所要做的就是TSort::Cyclic在代码中的正确位置进行救援，如果我尝试添加一个导致循环的节点，该节点将被删除并且我可以登录报告中待处理的问题（通过修复源数据）。

问题是，在大小为 75000 左右的 RubyTree 上，边数非常接近等于顶点数减 1，迭代运行 Tarjan 算法会产生看起来相当二次的算法复杂度。Tarjan 本身是O(|V| + |E|)，在我的情况下是 about O(2*|V|)，但每次我调用 时add()，都会|V|增加 1，因为我逐个节点地构建图形节点。我不能简单地在最后调用 Tarjan，因为我可能需要在 read-compare-add 循环期间遍历图形或其中的一部分，并且任何遍历尝试都可能会挂起程序或使其崩溃，如果事实上存在一个循环。（不用说，我的代码是单线程的；如果不是，我们就会遇到一个大问题。就目前而言，我依赖于这样一个事实：add()如果存在循环，则永远不会返回而不引发异常，即使存在循环，节点也会以在返回之前清除循环的方式被删除add()。）

但是太慢了！仅此一个循环就需要半个多小时，而我的程序由其他几个步骤组成，这些步骤占用了自己相当多的时间。但就目前而言，从ruby-perf. 我尝试在 RubyTree 实现中从数组切换到链表each，但它通过删除大量Array#concat调用仅将运行时间减少了约 1%。

我发现了Tarjan 的这篇很棒的论文，他发明了 Ruby 所依赖的强连接组件算法，似乎增量循环检测是一个活跃的研究领域。然而，论文中的对话水平明显超出了我的想象，而且我很确定我缺乏将论文的发现转化为 Ruby 代码的数学背景。不仅如此，通过阅读论文的备注部分，他们的尽力而为的算法似乎有自己的令人担忧的最坏情况运行时，所以它甚至可能不会比我目前的方法快，这取决于我的具体情况数据。TSort

我是否在这里遗漏了一些愚蠢的东西，或者我最好的选择是投入脑力去分析 Tarjan 的论文并尝试提出其中一种算法的 Ruby 实现？请注意，我并不特别关心算法的拓扑排序方面；这是我真正想要的副作用。如果树没有经过拓扑排序但仍然保证没有循环，我会非常高兴。

另外值得注意的是，在我的源数据中，周期有点少见。也就是说，循环可能由于数据输入过程中的手动错误而发生，但它们永远不会故意发生，并且应该始终向程序报告，以便它可以告诉我，这样我就可以用比利俱乐部击败某人进入错误的数据。此外，即使程序检测到一个特别讨厌的循环，它也绝对必须继续运行，所以我不能只是把头埋在沙子里，希望不会有任何循环。

实际问题是什么？

应某些人的要求，这是一个演示，您可以运行以查看工作中的问题。

安装 RubyTree 的稳定版本（我使用 MRI 1.9.3）。然后比较这两个程序的输出：

图表 1：打印“第三次”后，主线程上的 CPU 使用率为 100% 时永远挂起

图表2：一路遍历并打印“Done”，结果没有循环

请注意，我通常会在rescue块内做一些事情来记录发生的循环，并大声抱怨创造这些循环的人类罪犯。

对我来说，目标是开发功能上等同于图表 2 的代码，但可以更好地扩展到更大数量的顶点（我预计不会有超过 10^6 个顶点，在这种情况下我会很好）在现代桌面工作站上花费几分钟（“去喝杯咖啡”），但不是几个小时或更长时间。）

我有一个有向图问题，我需要标记每个节点并将节点打印为关于给定输入中的边缘标记和未标记的节点，如果它们在 java 中都标记为各自的开始和结束状态，则接受或拒绝。我已经想出了如何将每个值解析为其单独的实体，但我无法弄清楚如何使用已以括号形式解析的指定输入来遍历图形。这是一个例子：

如果它们被标记或未标记，将如何遍历这些节点并检查边缘？堆栈等？

我只是不明白如何显示该节点已到达每个节点并在给定这些括号的情况下对其进行标记。

我想知道是否有人可以帮助我并让我走上正确的道路来帮助我解决我的问题。我有一个输入字符串：

其中 (1,2,3,4,5) 是节点

• ((1,2),(1,3),(2,3),(2,4),(3,2),(3,5),(4,3),(5,2))是边缘
• 1是开始状态
• 5是结束状态

我必须读入那个输入字符串并说明这个有向图是否可能。在这种情况下是。

我的问题：我对如何从左到右读取这些字符并标记访问过的每个节点并利用它们来表明该图是可能的感到困惑。我不知道如何提取或显示 (1,2) 是从输入字符串 ((1,2),(1,3)....

到目前为止，我的尝试是解析输入字符串并将每个部分（即节点、边缘）视为单独的变量并处理边缘本身。有人可以帮助我，因为我渴望完成这个。

我正在尝试学习和实现有向图，并且在执行程序时遇到了一些困难。

错误：执行程序时，我在调用 addVertex(String) 函数时输入字符串作为输入，并给出错误字符串无法转换为顶点。来自 Java 的错误记录：java.lang.ClassCastException：java.lang.String 无法转换为 DG.Vertex

有人可以解释一下，我做错了什么。谢谢你。

C++17 移除了三元组。IBM 强烈反对这一点（此处和此处），因此似乎存在移除/不移除双方的争论。

但是既然决定删除三合字母，为什么要留下二合字母呢？除了保留三字母的原因（显然重量不足以保留它们）之外，我没有看到任何保留二合字母的理由。

我们都知道digraphs 和 trigraphs的历史好奇心，但是随着近年来对 C++ 所做的所有更改，我很好奇：它们是有效的 C++14 吗？C++17 怎么样？

我正在尝试制作彩色图表。我不断遇到奇怪的行为。

我无法让颜色图自动为节点分配颜色。我尝试执行此操作的所有节点都以相同的颜色结束！

浮动是应该分配给 6 个节点的颜色。7 个浮点数中有两个是相同的，因为它是一个循环。

当我手动指定节点（node_color=['r']等）的颜色时，它工作正常，不仅适用于根（红色），而且适用于循环中的节点。

代码：

这里，x是一个节点名称数组，CD是一个映射名称到浮点数的字典。为了完整起见，它们是：

颜色图功能在其他情况下对我有用，所以我觉得我犯了一个基本错误。有任何想法吗？

我是 Python 新手，已经有一段时间没有编程了，非常感谢您的帮助。

我必须在给定的数据结构中查找所有 n 长度的循环-我目前正在使用列表，但也许 dict 可以完成工作-

第一行中的每个元素直接映射到它下面的元素，如果重复使用映射导致返回初始值，则形成一个循环。假设我有：

那么循环是(3)和(4,6,8)

或者

循环在哪里(3,7,18,5)，(6,12)并且(13)

我真的被困住了，所以提前感谢您的帮助。

这是我在这里的第一个问题，因此对于您在我的帖子中可能发现的最终形式错误，我深表歉意。

我正在为“无向连接加权图”编写一个简单的类，它必须使用基于向量的邻接列表。

问题是，当我从 Eclipse 运行程序时，MS Windows 说它“停止工作”，调试后我收到“0x00AE251A 处的未处理异常......访问冲突写入位置......”消息。环顾四周，我发现这个问题可能是由于缺少指针破坏或指针初始化（？）引起的。我从标准指针切换到 shared_ptr 来解决这个问题，但错误是一样的......

有人可以启发我吗？我几乎浪费了一整天的时间来寻找原因，但没有成功。