我正在尝试在无向、循环、加权图上执行一些计算，并且我正在寻找一个好的函数来计算聚合权重。

每条边都有一个在 [1,∞) 范围内的距离值。该算法应该更加重视较低的距离（它应该是单调递减的），并且应该为距离 ∞ 分配值 0。

我的第一直觉是简单的 1/d，它同时满足了这两个要求。（嗯，从技术上讲，1/∞ 是未定义的，但程序员往往比数学家更容易让它滑动。） 1/d 的问题是该函数更关心 1/1 和 1/2 之间的差异比 1/34 和 1/35 之间的差异。我想更清楚一点。我可以使用 √(1/d) 或 ∛(1/d) 甚至 ∜(1/d)，但我觉得我错过了一大堆可能性。有什么建议么？

（我想到了 ln(1/d)，但随着 d 变为 ∞，它变为 -∞，我想不出将其推至 0 的好方法。）

后来：

我忘记了一个要求：w(1) 必须为 1。（这不会使现有答案无效；乘法常数很好。）

我一直在研究一个我认为人们可能会感兴趣的问题（也许有人知道预先存在的解决方案）。

我有一个大型数据集，由一长串指向对象的指针组成，如下所示：

任何时候都有太多的对象需要保存在内存中（可能有数百 GB），因此它们需要存储在磁盘上，但可以缓存在内存中（可能使用 LRU 缓存）。

我需要遍历这个列表来处理每一对，这需要将这对中的两个对象都加载到内存中（如果它们还没有缓存在那里）。

所以，问题是：有没有办法重新排序列表中的对以最大化内存缓存的有效性（换句话说：最小化缓存未命中的数量）？

笔记

1. 显然，重新排序算法应该尽可能快，并且不应该依赖于能够一次将整个列表保存在内存中（因为我们没有足够的 RAM）——但它可以迭代必要时列出数次。

2. 如果我们处理的是单个对象，而不是对，那么简单的答案就是对它们进行排序。这显然在这种情况下不起作用，因为您需要考虑这对中的两个元素。

3. 问题可能与找到最小图割有关，但即使问题是等价的，我认为最小割的解决方案也不满足

4. 我的假设是启发式方法会将数据从磁盘中流出，并以更好的顺序将其分块写回。它可能需要多次迭代。

5. 实际上，它可能不仅仅是成对的，它可能是三胞胎、四胞胎或更多。我希望对对执行此操作的算法可以很容易地推广。

有没有人有使用 prefuse 图形工具包的经验？是否可以更改已显示的图形，即。添加/删除节点和/或边缘，并使显示正确适应？

例如，prefuse 带有一个可视化朋友网络的示例：

http://prefuse.org/doc/manual/introduction/example/Example.java

我想做的事情是这样的：

但这似乎不起作用。有什么提示吗？

我的算法课中的一项任务是设计一个详尽的搜索算法来解决集团问题。也就是说，给定大小为n的图，算法应该确定是否存在大小为k的完整子图。我想我已经得到了答案，但我不禁认为它可以改进。这是我所拥有的：

版本 1

输入：由数组 A[0,... n -1] 表示的图，要查找的子图的大小k。

输出：如果存在子图则为真，否则为假

算法（在类似 python 的伪代码中）：

版本 2

输入：大小为 n x n 的邻接矩阵，k 是要查找的子图的大小

输出：大小为 k 的 A 中的所有完整子图。

算法（这次是函数式/Python 伪代码）：

有没有人有任何想法、意见或建议？这包括我可能错过的错误以及使其更具可读性的方法（我不习惯使用太多伪代码）。

版本 3

幸运的是，我在提交作业之前和我的教授谈过了。当我给他看我写的伪代码时，他笑着告诉我我做的工作太多了。其一，我不必提交伪代码；我只需要证明我理解这个问题。第二，他想要蛮力解决方案。所以我上交的东西看起来像这样：

输入：一个图 G = (V,E)，找到k的 clique 的大小

输出：如果集团确实存在则为真，否则为假

算法：

1. 求笛卡尔积 V ^k。
2. 对于结果中的每个元组，测试每个顶点是否相互连接。如果全部连接，则返回 true 并退出。
3. 返回 false 并退出。

更新：添加了第二个版本。我认为这正在变得更好，尽管我没有添加任何花哨的动态编程（我知道）。

更新 2：添加了更多评论和文档以使第 2 版更具可读性。这可能是我今天上交的版本。感谢大家的帮助！我希望我能接受多个答案，但我接受了对我帮助最大的人的答案。我会让你们知道我的教授的想法。

是否存在用于在图中查找冗余边的既定算法？

比如我想发现 a->d 和 a->e 是多余的，然后去掉它们，像这样：

=>

编辑：Strilanc 很好地为我读懂了我的想法。“冗余”这个词太强了，因为在上面的例子中，a->b 或 a->c 都不被认为是冗余的，但 a->d 是。

如何计算 C# 中的最小二分顶点覆盖？有这样做的代码片段吗？

编辑：虽然问题对于一般图来说是 NP 完全的，但对于二部图来说，它可以在多项式时间内解决。我知道它在某种程度上与二分图中的最大匹配有关（通过 Konig 定理），但我无法正确理解该定理以便能够将最大二分匹配的结果转换为顶点覆盖。

给定一个具有n个顶点 (| V | = n )的无向图G =( V , E ) ，如何确定它是否包含O ( n ) 中的环？

每个节点都连接到每个其他节点（没有冗余连接）的图是如何调用的？

我知道这张图有 N * (N - 1) / 2 条边。

如何从/到给定节点的有向图中找到（迭代）所有循环？

例如，我想要这样的东西：

但不是：B->C->B

（在 .NET 的上下文中，它的价值是什么）

我倾向于不使用继承，也很少使用接口。我遇到了一个认为接口是自吐槽以来最好的东西的人。他到处使用它们。我不明白这一点，因此接下来的问题。我只是想检查一下我对接口的理解。

如果您在任何地方都使用界面，我假设您可以预测未来，您的应用程序需求已确定并且您的应用程序不会发生任何变化。对我来说，尤其是在早期开发过程中，界面成为了拖累。该应用程序在其生命周期中非常动态。如果您需要在界面中减去或添加成员，很多东西都会中断。上面的人说他创建了另一个接口来处理新成员。什么都没有。

不是组合吗？为什么不使用没有接口的组合？更灵活。

他如何处理必须从接口中减去成员的情况？基本上他不会。事情刚刚破裂，这很好，因为现在您可以看到所有受影响的区域并修复它们。我们不应该更优雅地找出所有相关代码路径的位置，而应该通过蛮力撕掉部分类？

我将软件应用程序视为图形。完整图是最坏的情况，具有 n(n-1)/2。这意味着每个班级都与每个班级交谈。令人困惑的蜘蛛网。n-1 是最好的，其中它们是严格的通信等级。添加另一个接口只是为了补偿一个新的需要的成员，会在图中添加一个顶点，这意味着更多的边和更强的 n(n-1)/2 方程的实现。没有接口的组合更像是 mixin。只有选择类使用特定的方法。使用接口，所有类都被迫使用成员，即使它们不需要它们。组合/混合方法不会添加新的不需要的边缘。