问题标签 [graph-theory]

有人知道 Smalltalk 中图算法的实现吗？

我想要一些允许您在模型对象或其他东西上实现接口并提供传递闭包、传递减少、拓扑排序等算法的东西。

人们最终会经常重新实现这些广泛适用的算法，如果有一个每个人都可以使用的通用实现，那就太好了。

我猜，指向可以移植的其他（最好是 OO）语言的类似库的指针也很有用。

我正在尝试帮助某人编写一个我认为很容易的程序，但当然它从来都不是:)

我正在尝试制定班级名册（通常在 10 到 20 名学生之间），并有效地将每个同学与另一个同学配对，以组成独特的小组。因此，在一个 10 人的班级中，您可以有 9 个小组。

它也需要能够处理奇数个学生，这增加了我的困惑。

我正在考虑在 Java 中执行此操作，但这很灵活。关于算法方式的任何想法，以保证 a) 不是无限循环（以 2 个已经成为合作伙伴的人结束）和 b) 我的目标是时间比空间更有效，因为班级规模会很小！

谢谢！

我查看了Microsoft GLEE（非商业用途）和其他用于绘制图形的库，但我需要一个良好的商业用途图形 API 来显示通过 Internet 的复杂路线。

我需要能够显示大量的节点和顶点。有任何想法吗？

我有大量加权节点，边缘将节点集群连接在一起。该图遵循典型的小世界布局。

我希望找到一种寻路算法，它不会消耗处理器能力，沿着最佳可能路径找到一条路径，其中节点的权重最有利，最快的路线不是最重要的因素。该算法还考虑了负载和流量重新路由。

（旁注：这里可以使用神经网络吗？）

谢谢

我在看ACO。对于这种问题，有什么比 ACO 更好的吗？

正确的A*算法在没有负载平衡的情况下找到成本最低或最快的路线。

可以说最快或最短的路线不是最重要的路线，更重要的是遵循加权节点具有一定值的路径。没有。

没有2。如果使用 A*，那条路由上的流量就会超载，那么这条路径突然就变得多余了。因此，尽管 A* 很酷，但它没有 ACO 的某些特性，即固有的负载平衡。

-- 除非我弄错和误解了 A*

那么什么比 ACO 更胜一筹？

这看起来真的像是 ACO 和 A* 之间的一场对决，关于 A* 的正面讨论太多了，我一定会更深入地研究它。

首先是对大卫的回应；我可以在后台运行 ACO 模拟并提出最佳路径，所以是的，有初始启动成本，但幸运的是，启动并不是必需的。所以我有能力多次运行模拟。一个真正的麻烦是找到连接的源节点和目标节点。而 A* 似乎很容易做到这一点。现在，当这个网络变得像数百万个节点一样大时会发生什么。A* 能否轻松扩展？

我将进一步研究 A*。但我留给你最后一个问题！

A* 能否像 Antnet (ACO) 一样扩展？

我有一个大约 100 个节点和大约 200 条边的无向图。一个节点标记为“开始”，一个节点标记为“结束”，大约有十几个标记为“必须通过”。

我需要找到从“开始”开始，在“结束”结束，并通过所有“必须通过”节点（以任何顺序）的最短路径。

（http://3e.org/local/maize-graph.png / http://3e.org/local/maize-graph.dot.txt是有问题的图表 - 它代表宾夕法尼亚州兰开斯特的玉米迷宫）

我需要有关渲染具有 178,000 个节点和 500,000 条边的无向图的建议。我尝试过 Neato、Tulip 和 Cytoscape。Neato 甚至都无法接近，Tulip 和 Cytoscape 声称他们可以处理它，但似乎无法处理。（Tulip 什么都不做，Cytoscape 声称正在工作，然后就停止了。）

我只是想要一个具有远程合理布局的节点的矢量格式文件（ps 或 pdf）。

比如说，假设我有一个树形结构，那么我自然会使用一个树形控件，因为该 GUI 元素完美地映射到该结构。

但我所拥有的是一个图表，可能太宽而无法放入一个网页。我想不出真正匹配结构的 GUI 示例。我有一些不太合适的想法是，网络本身，带有超链接、浏览器后退按钮和前进按钮。但这一次只显示一个节点。我想尽可能多地显示节点，并允许导航到图表的新区域。像谷歌地图这样的东西可能是一个很好的模型，因为你可以完全自由地向任何方向滚动。

我正在使用带有路径压缩的 Lengauer 和 Tarjan 算法来计算具有数百万个节点的图的支配树。该算法非常复杂，我不得不承认我没有花时间完全理解它，我只是在使用它。现在我需要计算根节点的直接子节点的支配树，并可能将图形向下递归到某个深度，重复此操作。即，当我为根节点的子节点计算支配树时，我想假装根节点已从图中删除。

我的问题是，是否有一个有效的解决方案，利用已经在初始支配树中为根节点计算的直接支配信息？换句话说，我不想为每个孩子从头开始，因为整个过程非常耗时。

天真地看起来这一定是可能的，因为在图表的深处会有很多节点，它们的 idms 就在它们上方一点点，并且不受图表顶部的变化的影响。

顺便说一句：支配树的主题由编译器人员“拥有”并且在经典图论书籍中没有提到它，这很奇怪。我使用它的应用程序——我的 FindRoots java 堆分析器——与编译器理论无关。

澄清：我在这里谈论有向图。我指的“根”实际上是可达性最大的节点。我已经更新了上面的文本，用“graph”替换了对“tree”的引用。我倾向于将它们视为树木，因为形状主要是树状。该图实际上是 Java 堆中的对象，并且您可以想象它是合理的层次结构。我发现支配树在进行 OOM 泄漏分析时很有用，因为您感兴趣的是“是什么让这个对象保持活力？” 答案最终是它的支配者。支配树可以让你<ahem>看到树林而不是树木。但有时很多垃圾会漂浮到树顶，所以你有一个根，下面有成千上万个孩子。对于这种情况，我想尝试计算以根的每个直接子节点（在原始图中）为根的支配树，然后可能会向下一层等等。（我暂时不担心反向链接的可能性：）

是否有一种有效的算法来检测有向图中的循环？

我有一个有向图，表示需要执行的作业计划，作业是节点，依赖项是边。我需要在该图中检测导致循环依赖的循环错误情况。

每年圣诞节，我们都会为我家的礼物交换画名字。这通常涉及多次重绘，直到没有人拉他们的配偶。所以今年我编写了自己的名字绘图应用程序，它接收一堆名字，一堆不允许的配对，并向每个人发送一封电子邮件，以及他们选择的礼物。

现在，算法是这样工作的（在伪代码中）：

有谁知道更多关于图论的人知道某种在这里会更好地工作的算法吗？就我的目的而言，这是可行的，但我很好奇。

编辑：由于电子邮件不久前发出，我只是希望能学到一些东西，我将把它改写为一个图论问题。我对排除都是配对的特殊情况不感兴趣（比如配偶没有得到对方）。我对有足够的排除项以找到任何解决方案成为困难部分的情况更感兴趣。我上面的算法只是一个简单的贪心算法，我不确定在所有情况下都会成功。

从一个完整的有向图和一个顶点对列表开始。对于每个顶点对，删除从第一个顶点到第二个顶点的边。

目标是得到一个图，其中每个顶点都有一条边进入，一条边离开。