<分区>
我正在创建一个库来支持一些标准的图形遍历。一些图是明确定义的:即,所有边都是通过提供数据结构或通过重复调用相关方法来添加的。有些图仅隐式定义:即,我只能提供一个函数,给定一个节点,该函数将返回其子节点(特别是,当然,我遍历的所有无限图都必须隐式定义)。
遍历生成器需要高度可定制。比如我应该可以指定是否要DFS后序/前序/中序,BFS等; child 应该按什么顺序被访问(如果我提供一个 key
来对它们进行排序);是否应维护访问节点集;后向指针(指向父节点的指针)是否应该与节点一起产生;等
我正在为这个库的 API 设计而苦苦挣扎(一旦 API 清晰,实现一点也不复杂)。我希望它优雅、合乎逻辑且简洁。是否有任何满足这些条件的图形库可以用作模板(不必使用 Python)?
当然,如果有一个 Python 库已经完成了所有这些,我很想知道,这样我就可以避免自己编写代码。
(我正在使用 Python 3。)
如果您需要处理无限图,那么您将需要某种图的功能接口(interface)(如您在 q 中所说)。所以我会将其作为标准表示并提供采用其他表示并生成函数表示的辅助函数。
对于结果,也许你可以产生(你暗示一个生成器,我认为这是一个好主意)一系列结果对象,每个对象代表一个节点。如果用户想要更多信息,比如反向链接,他们会调用一个方法,并提供额外的信息(在可能的情况下延迟计算,这样你就可以避免那些不需要它的人的成本)。
你没有提到图表是否是有向的。显然,您可以按指示处理所有图形并返回两个方向。但随后的实现效率不高。通常(例如 jgrapht )库对不同类型的图有不同的接口(interface)。
(我怀疑在优雅的 api 和效率之间取得良好的平衡之前,您将不得不对此进行大量迭代)
最后,你知道functional graph library吗? ?我不确定它会有什么帮助,但我记得我在想(几年前!)那里的 API 很不错。