问题标签 [graph-theory]

好吧，我正面临着我的家人即将加入的人，并且正在努力选择名字。

我考虑过编写软件来显示名字并强迫我选择我更喜欢的，类似于小猫战争。

但是，一旦我得到一个巨大的图表，我就不知道如何处理它，尤其是如果有循环的话。例如，我喜欢 mike 胜过 sam，sam 胜过 jared， jared 胜过 mike - 简单地分配选票并计算它们是没有意义的（我认为 kitten war 就是这样做的）。此外，我可能有一天会得到 mike vs jared 并以一种方式投票，但如果我在另一天得到它，就会以不同的方式投票。

所以：

• 获得数据后，如何处理图表并对名称进行排名？

交替：

• 还有哪些有用的算法可以用来做出选择（比如车辆样式，如果你正在寻找一辆新车）？

-亚当

给定几个单词的输入，我想要一个实用程序，它可以返回一组不同的相关术语、短语或概念。需要注意的是，它需要有一个大的术语图，否则该功能不会很有用。

例如，提交“棒球”将返回

Google Sets是我能找到的此类功能的最佳示例，但我无法使用它，因为它们没有公共 API（而且我不会违反他们的 TOS）。此外，单个单词输入不会获得非常多样化的结果。我正在寻找一个切线的解决方案。

我尝试过的最接近的方法是使用WikiPedia 的 API来搜索类别和反向链接，但没有办法直接按"相关性"或"流行度"对这些结果进行排序。没有它，建议列表就会很庞大，而且到处都是，这不是立即有用的，而且很难减少。

使用 A Thesaurus 也可以最低限度地工作，但这会遗漏任何专有名词或切线相关的术语（如上面列出的任何结果）。

我很乐意重用一个开放服务，如果存在的话，但我还没有找到足够的东西。

我正在寻找一种方法来实现这一点，要么在内部使用大量的起始集，要么重用提供此功能的免费服务。

有解决办法吗？ 提前谢谢！

更新： 感谢您提供令人难以置信的密集和信息丰富的答案。我将在 6 到 12 个月内选择一个成功的答案，届时我希望能理解你们所有人的建议 =)

我正在维护一个数据仓库，其中包含关于必须合并的一类实体的多个数据源。每个源都有一个自然键，并且应该发生的是，始终为每个自然键创建一个且只有一个代理键。如果来自一个源系统的具有特定自然键的一条记录与来自具有不同自然键的另一个源系统的另一条记录表示相同的实体，则将为两者分配相同的代理键。

换句话说，如果源系统 A 具有与源系统 B 的自然键 DEF 表示相同实体的自然键 ABC，我们将为两者分配相同的代理键。该表如下所示：

这就是计划。但是，这个系统已经生产了一段时间，代理键分配是一团糟。在源系统 B 知道之前，源系统 A 会在某一天给出自然键 ABC。DW 为其分配了代理键 1。然后源系统 B 开始给出自然键 DEF，它表示与源系统 A 的自然键 ABC 相同的东西。DW 错误地给了这个组合代理键 2。该表如下所示：

所以仓库乱七八糟。还有比这更复杂的情况。我有一个很短的清理时间表，需要找出一组干净的自然键映射的代理键。

一点谷歌搜索表明，这可以建模为非二分图中的匹配问题：

维基百科 - 匹配

MIT 18.433 组合优化 - 非二分匹配讲义

我需要 Edmond 的路径、树和花算法的易于理解的实现（不是最佳执行）。我没有正式的数学或计算机科学背景，我所拥有的是自学的，而且我今晚不在数学上。任何人都可以帮忙吗？一个指导我实现的写得很好的解释将不胜感激。

编辑：

数学方法是最优的，因为我们想要最大化全局适应度。贪婪的方法（首先获取 A 的所有实例，然后是 B，然后是 C...）会将您绘制到局部最大值角落。

无论如何，我把这个推回业务分析师手动完成（全部 2000 万）。我正在帮助他们评估全局匹配质量。这是理想的，因为无论如何他们都是签字的人，所以我的背面被遮住了。

不使用代理键不会改变匹配问题。仍然需要发现和维护 1:1 自然键映射。代理键是一个方便的锚，仅此而已。

我有一个 n 部分（无向）图，作为邻接矩阵给出，例如这里的这个：

我想知道是否有一组矩阵运算可以应用于这个矩阵，这将导致一个矩阵“列出”这个图中的所有路径（长度为 n，即通过所有分区）。对于上面的示例，有路径 a->b->d 和 a->c->d。因此，我想得到以下矩阵作为结果：

第一条路径包含节点 a、b、d，第二条路径包含节点 a、c、d。如有必要，结果矩阵可能有一些全为 0 的行，如下所示：

谢谢！

PS我看过计算传递闭包的算法，但这些通常只告诉两个节点之间是否存在路径，而不是直接告诉哪些节点在该路径上。

这里的图表是指类似于这些图像的东西：

理想的解决方案是：

• 仅使用托管代码
• 允许输出到位图图像
• 允许输出到 WPF 元素
• 包括某种交互式表面，用于显示支持缩放、平移和重组节点的图形

我也有兴趣了解可能用作此类工作起点的项目。如果它需要一些发展来实现我想要的，那么我准备好解决它。这个目标中最复杂的部分似乎是在合理的时间范围内获得图形布局。

我正在寻找一种算法来“反转”（反转？从里到外？）一个 DAG：

我使用的表示是不可变的，真正的 DAG（没有“父”指针）。我想以某种方式遍历图形，同时构建具有等效节点的“镜像”图形，但节点之间的关系方向倒置。

所以输入是一组“根”（这里是{A}）。输出应该是结果图中的一组“根”：{G, F}。（根是指没有传入引用的节点。叶子是没有传出引用的节点。）

输入的根变成输出的叶子，反之亦然。变换应该是自身的逆。

（出于好奇，我想向我用来表示 XML 以进行结构查询的库添加一个功能，通过它我可以将第一棵树中的每个节点映射到第二棵树中的“镜像”（然后返回再次）为我的查询规则提供更多的导航灵活性。）

我有一个问题：

我有一个 A 类和一个 B 类，可以通过编程检查它们的实例对象是否在不同数量上彼此相似或不同。例如，它们可能完全匹配，或者完全不同（即使类别不同，它们仍然可以表示相同的信息并且得分相同。）

现在，给定两个集合，一个是 A，一个是 B，将 As 和 B 配对的最佳方式是什么，以使它们最匹配，如果任一集合大于另一个集合或如果某些 As 或 B 完全不同而无法匹配？

我的第一次尝试是创建一个二维数组，其中每个单元格都是匹配的“分数”（0 = 完美，数字越大越差），并在每条路径中递归查找最低累积分数。这行得通，结果很完美，但速度非常慢。

关于更有效算法的任何想法？

如果您想知道，我的 A 类代表一个混音器输入通道，我的 B 代表相同的持久状态（称为场景）。我要解决的问题是如何将场景导入现有混音器，其中场景 (B) 可能与任何现有通道 (A) 略有不同甚至高度不同。如果我可以稍微修改任何一个以匹配，我不想只添加频道 (A)。例如，我可以在 A 中添加一个效果插入，以便与 B 完美匹配，避免添加另一个 A。

麦克风

什么是 Splay 树、红黑树、AVL 树、B 树和 T 树？

我正在寻找好的实现。

如何找出导致 equals() 返回 false 的原因？

我不是在问一个确定的、永远正确的方法，而是在问一些有助于开发过程的东西。目前我必须进入 equals() 调用（通常是它们的树），直到其中一个为假，然后进入它，令人作呕。

我考虑过使用对象图，将其输出到 xml 并比较两个对象。但是，XMLEncoder 需要默认构造函数，jibx 需要预编译，我的项目中没有使用 x-stream 和 simple api。我不介意将单个类甚至一个包复制到我的测试区域并在那里使用它，但是为此导入整个 jar 是不会发生的。

我还考虑过自己构建一个对象图遍历器，我可能仍然会这样做，但我不想开始处理特殊情况（有序集合、非有序集合、地图......）

知道该怎么做吗？

编辑：我知道添加罐子是正常的做事方式。我知道罐子是可重复使用的单元。但是，为此（在我的项目中）需要的官僚机构并不能证明结果是合理的——我会继续调试并介入。

I have an adjaceny matrix for a graph which tracks the edges between the nodes by having a 1 in the corresponding adjMat[i,j] = 1; Through this adjaceny matrix i wish to find out all the closed paths of length 4 which exists in the graph. Can anyone please provide me with a pseudo code. thank u