我正在创建一个库来支持一些标准的图形遍历。一些图是明确定义的：即通过提供数据结构或通过重复调用相关方法来添加所有边。有些图只是隐式定义的：即，我只能提供一个函数，给定一个节点，将返回其子节点（特别是，我遍历的所有无限图当然必须隐式定义）。
遍历生成器需要高度可定制。比如我应该可以指定是否要DFS post-order/pre-order/in-order、BFS等；应该按照什么顺序访问孩子（如果我提供了key对他们进行分类的顺序）；是否应该维护访问节点集；是否应该与节点一起产生后向指针（指向父级的指针）；等等
我正在为这个库的 API 设计而苦苦挣扎（一旦 API 清晰，实现一点也不复杂）。我希望它优雅、合乎逻辑且简洁。是否有任何符合这些标准的图形库可以用作模板（不必在 Python 中）？
当然，如果有一个 Python 库已经完成了所有这些，我想知道，所以我可以避免自己编写代码。
（我正在使用 Python 3。）
如果您需要处理无限图，那么您将需要某种对图的功能接口（正如您在 q 中所说的那样）。所以我会将其作为标准表示并提供辅助函数来获取其他表示并生成功能表示。
对于结果，也许你可以产生（你暗示一个生成器，我认为这是一个好主意）一系列结果对象，每个结果对象代表一个节点。如果用户想要更多信息，比如反向链接，他们会调用一个方法，并提供额外的信息（在可能的情况下懒惰地计算，这样你就可以避免那些不需要它的人的成本）。
你没有提到图表是否有方向。显然，您可以将所有图形视为有向图并返回两个方向。但随后实施效率不高。通常（例如jgrapht）库对不同类型的图形具有不同的接口。
（我怀疑您将不得不对此进行大量迭代，然后才能在优雅的 api 和效率之间取得良好的平衡）
最后，你知道函数式图形库吗？我不确定它会有什么帮助，但我记得（几年前！）认为那里的 api 是一个不错的。
遍历算法和图数据结构实现应该是分开的，并且应该只通过标准的 API 相互通信。（如果它们是耦合的，则必须为每个实现重写每个遍历算法。）
所以我的问题真的有两个部分：
我相信C++ Boost Graph Library很好地回答了我的两个问题。我希望它可以（理论上）用 Python 重写，尽管在我尝试之前可能会有一些障碍。
顺便说一句，我找到了一个在 Python 上下文中处理问题 1 的网站：http ://wiki.python.org/moin/PythonGraphApi 。不幸的是，它自 2011 年 8 月以来一直没有更新。