问题标签 [graph-reduction]

我正在分析其依赖项的一些代码。假设有一些相互交织的依赖关系，如下所示：

B 取决于 A 和 C C 取决于 B 和 F E 取决于 C 和 F D 取决于 B 和 C 和 E

我们对 B 和 C 有一个问题，它们相互依赖。它们应该组合成一个超级节点。我们对 C 和 E 和 F 有问题，它们有一个循环。它们应该组合成一个超级节点。

你最终会得到

是否有允许这种减少的良好库或算法源（首选 Java，但愿意接受建议）？

循环中的任何节点都合并为一个节点。任何指向新节点中任何节点的节点都应该指向新节点。新节点中的任何节点指向的任何节点都应该导致新节点指向该节点。

谢谢！

我试图找到一种正式的方式来考虑haskell中的空间复杂性。我发现这篇关于 Graph Reduction ( GR ) 技术的文章在我看来是一种可行的方法。但我在某些情况下应用它时遇到问题。考虑以下示例：

假设我们有一棵二叉树：

和两个遍历树的函数，一个 ( count1 ) 可以很好地流动，另一个 ( count2 ) 可以立即在内存中创建整个树；根据分析器。

我想我理解它在count1的情况下是如何工作的，这是我认为在图形缩减方面发生的事情：

我认为从序列中可以清楚地看出它在恒定空间中运行，但是在count2的情况下会发生什么变化？

我理解其他语言的智能指针，所以我隐约明白count2函数中的额外r参数以某种方式防止树的节点被破坏，但我想知道确切的机制，或者至少是我可以使用的正式机制其他情况也是如此。

感谢您的关注。

从无堆栈语言如何工作？

真的吗？这很有趣，因为虽然我自己从未体验过，但我读到如果你不使用严格版本的折叠函数然后强制评估无限折叠，你会得到堆栈溢出。当然，这表明存在堆栈。谁能澄清一下？

我正在阅读 Haskell 中的半显式并行性，并感到有些困惑。

人们说这种方法允许我们通过并行评估 Haskell 程序的每个子表达式来自动进行并行化。但是这种方法有以下缺点：

1）它创建了太多的小项目，无法有效地安排。据我了解，如果你对 Haskell 程序的每一行都使用 par 函数，它会创建太多线程，而且根本不实用。那正确吗？

2）使用这种方法，并行性受到源程序中数据依赖性的限制。如果我理解正确，这意味着每个子表达式都必须是独立的。就像，在 par 函数中，a 和 b 必须是独立的。

3) Haskell 运行时系统不一定创建线程来计算表达式 a 的值。相反，它会创建一个火花，它有可能在与父线程不同的线程上执行。

所以，我的问题是：最后运行时系统会创建一个线程来计算 a 吗？或者如果需要表达式a来计算表达式b，系统会创建一个新线程来计算a？否则，它不会。这是真的？

我是 Haskell 的新手，所以也许我的问题对你们所有人来说仍然是基本的。感谢您的回答。

I am currently using Python to solve a "tree summarization" problem. My tree consists of nodes which have weights and children. An example

I am interested in finding all possible graphs obtainable by edge contractions. When I contract two edges, the old vertices are replaced by a new vertex whose weight is the sum of the old vertices. For example, contracting Child 2 with Grandchild 1 results in:

Of course this is only one possible edge contraction. Even for this small tree, there are many more contractions (e.g. (child 1, child 2), (child 1, parent), (child 2, parent)).

For each of these new trees, I need to again find all trees obtained by contracting one node (ultimately, the problem is to reduce a n-node tree to an m-node tree).

I am currently "brute forcing", recursively calling edge_contract() until I reach trees of the right node size. But the code needs to be able to work on moderately sized trees (~25-50 nodes) and the current implementation is not.

Is this type of tree contraction a solved problem. What are some good ways to tackle the problem?

我想知道我在此页面上读到的空间泄漏示例（遗憾的是那里没有解释）： https ://en.wikibooks.org/wiki/Haskell/Graph_reduction

棘手的空间泄漏示例：

(\xs -> 头 xs + 最后 xs) [1..n]

(\xs -> 最后一个 xs + 头 xs) [1..n]

第一个版本在 O(1) 空间上运行。O(n) 中的第二个。

我不确定，我是否理解正确（希望你能提供帮助）。据我所知，懒惰的评价是指最左边最外层的评价。因此，在这些示例中，我们将减少这些 redexes，如下所示：

(\xs -> 头 xs + 最后 xs) [1..200]

=> ([1..200] -> 头部 xs + 最后 xs)

=> 头部 [1..200] + 最后 [1..200]

=> 1 + 最后 [1..200]

=> 1 + 最后 [2..200]

=> ... ...

=> 1 + 最后一个 [199..200]

=> 1 + 最后 [200]

=> 1 + 200

=> 201

和

(\xs -> 最后一个 xs + 头 xs) [1..200]

（[1..200] -> 最后 xs + 头 xs）

最后 [1..200] + 头部 [1..200]

最后 [2..200] + 头部 [1..200]

……

最后 [199..200] + 头部 [1..200]

最后 [200] + 头部 [1..200]

200 + 头 [1..200]

200 + 1

201

也许我以错误的方式减少了它（请纠正我，如果我错了），但在这里我看不到可能的空间泄漏。所以，我首先用 ghci 测试了运行时（不是空间）：

根据 wikibooks，第二个版本应该存在空间泄漏，但运行时要快得多（这可能是可能的，这里没什么奇怪的）。

我有以下源代码：

...我编译它没有优化，然后我调用了程序：

这是一个很好的结果，我们有 2.3% 的垃圾收集，使用的内存大约是 1 MB。然后我编译了另一个没有优化的案例，得到了以下结果：

这更糟糕，有很多垃圾收集正在进行，内存使用率要高得多。

这里到底发生了什么？我不明白为什么会有空间泄漏。

PS 如果你用完全优化 (O2) 编译这两种情况，那么这两个程序几乎同样有效。

我有一个大的有向无环图，我想计算该图的传递约简。

我目前正在使用简单的深度优先搜索来计算传递减少，但该算法对于我的用例来说太慢了。但是，我已经能够在邻接矩阵表示上找到有效的算法，而我的表示大致相当于邻接列表。（它实际上表示为一组 C++ 对象，每个对象都有指向其子代和父代的指针）。

我显然可以将我的 DAG 转换为邻接矩阵，进行归约，然后将其转换回来；但这似乎有点浪费，如果可能的话，我想要一个更简单的算法。

我的图表包含约 100,000 个节点。

是否有基于边缘成本缩短路径（并删除节点）的算法？我不能很好地用语言表达，所以我希望这些图像能够很好地总结出来：

我想将直接汉密尔顿路径（DHP）减少为无向汉密尔顿路径（UHP），就此而言，标准算法是将DHP中的每个顶点（例如v）拆分为3个顶点，即vIN，vMID和vOUT。 我的问题是，为什么我们需要中间顶点，即 vMID？ 所有这些顶点无论如何都是相互连接的。