问图形库API

EN

如果您需要处理无限图，那么您将需要某种类型的图形函数接口(正如您在Q中所说的那样)。因此，我会将其作为标准表示，并提供辅助函数，这些函数接受其他表示并生成函数表示。

对于结果，也许您可以生成(您暗示一个生成器，我认为这是一个好主意)一系列的result对象，每个对象代表一个节点。如果用户想要更多的信息，比如反向链接，他们会调用一个方法，然后提供额外的信息(尽可能懒惰地计算，这样你就可以避免不需要它的人的成本)。

你没有提到这个图是不是有向图。显然，您可以将所有图视为有向图，并返回两个方向。但是，实现效率就不那么高了。通常(例如jgrapht)库对于不同类型的图形有不同的接口。

(我怀疑在优雅的api和效率之间取得良好平衡之前，您将不得不对此进行大量迭代)

最后，你知道functional graph library吗？我不确定它会有什么帮助，但我记得我在想(几年前)那里的api很不错。

遍历算法和图形数据结构的实现应该是分开的，并且应该只通过标准的API相互通信。(如果它们耦合在一起，则必须为每个实现重写每个遍历算法。)

所以我的问题实际上有两个部分：

1. 如何设计图形数据结构的API (由遍历等图形算法和创建/访问图形的客户端代码使用)
2. 如何设计图形遍历算法的API (由需要遍历图的客户端代码使用)

我相信C++ Boost Graph Library很好地回答了我的两个问题。我希望(理论上)可以用Python重写它，尽管在尝试之前可能看不到一些障碍。

顺便说一句，我发现了一个在Python上下文中处理问题1的网站：http://wiki.python.org/moin/PythonGraphApi。不幸的是，它自2011年8月以来就没有更新过。